How to improve search performance

I have a site – http://www.oldies.org.uk/ – with 9233 posts & growing, which is averaging around 10-20 concurrent visitors.

With the aid of wp super cache plugin, general performance is fine, but search is sometimes slow, sometimes taking up to 30-40 seconds – presumably because it takes a while to query that number of posts.

I’d like to speed this up. How can I do this?