Searching a wiki is critical, especially for large sites. Although we encourage structuring your content using categories, parent-child page relations and using the ListPages module for navigation, nothing can replace the good old Search button.
Although searching seems really simple from the user's perspective, it is a real challenge to provide sufficient infrastructure to power it. Currently we need to handle over 100,000 searches per day, index 11,000,000 pages and forum threads spread over 400,000 sites. And not only we provide search functionality on individual sites, but also Wikidot-wide.
While Wikidot was quite small (you know, these early days when we had no more than 10,000 users altogether), we were using TSearch2 - which added search functionality to the SQL database itself. And it was working fine.