Slow Search on Drupal 6.x site with 60.000+ nodes
60,000 nodes in the search index is definitely a lot. Not only is it slow and suboptimal to use Drupal's default search with such a large number of nodes, but it is going to progressively put more pressure on your infrastructure as you continue adding nodes. 

The solution would definitely be to offload your search to another tool. Two options:


Solr: 60,000 is child's play for Solr. It could suffice you for a lot more even on a commodity machine.
Elastic search: Another tool built on top of Apache Lucene. This one's newer and does not have as many supporting modules for it as Solr does (for Drupal). But it is faster than Solr and can handle concurrent commits much better.


In both these cases, I'd recommend installing the search tool on another server.