Looking from the outside of it would be hard to give you any real advice, however consider the following:

1) hosting location and plan, yes.

1.1) If your hosting is on a bad server shared with many sites on overselling it may give you a poor performance.

1.2) If your hosting server have a bad connectivity and/or link to your networking or a target set of network as in not having good exit links to a given region resulting in more hops to reach it, it will also give you a poor performance

1.3) Verify how many users you have will also help you in case your hosting limit your website resources

2) Test your own code counting the execution time, that can simple be done by saving when it started and when it ended then (end-start) = time taken to execute

2.1) This would help you nailing down if your code is having the issue or not

2.2) Also try to test it at different interval of times such as when the server or your site is less used by users and when it is most used so you can have an average between the 2.

3) Review your own code to see what can be improved

4) If you are using MySQL or other database engine, review your queries, see if you have slow queries, see if you have properly indexes setup.

4.1) Index will most likely improve the query performance in most cases

4.2) Some queries may take longer to run and can be simplified for performance

4.3) Test your queries on the console or direct on the database or using a 3rd party tool to verify how long they take to execute

5) Check your content, if youre are loading data from other websites that may slow down your own site like, javascript or ajax content.

6) Use of CDN for static content to improve delivery to your users in a faster manner

These are some points I would recommend you checking.

It seemed fairly responsive when I tried a simple search.

The search engine database would be the biggest bottlenet.

Are you using a SQL db like MySQL or Postgres? If so, depending on how much search data you want to store, I would strongly consider looking at something else, perhaps one of the NoSQL databases. Remember Google stores petabytes of data in multiple large data centers.

I have heard/read that Google uses a NoSQL or similar, but proprietary database.

After the DB, make sure the application is scaleable and doesn't need to store any state other than the session.

Optimisation is not about guessing. If I had a dollar for each time where the slow code was not what I thought it would be...

Find yourself a profiling tool and use it to find the performance bottlenecks rather than relying on intuition.

Cgimaster covers a lot of good points worthy of investigation.

Your host is going to be a primary factor in performance, so if you're running on a shared hosting environment then before we've begun to look at your code efficiency - we've got problems!

A VPS/Dedicated hosting solution is highly recommended or you can investigate the many cloud-like offerings that exist in the market place today. Amazon, Heruko, etc.

CDN? Yeah that too.

Profiling your code is going to be extremely important to identify bottlenecks in queries and or classes, methods and functions. It would be useful to learn more about what languages you are using from scripting, to database and to possibly see some non-proprietary database queries or profiling reports to help you further.

You should consider caching certain queries and results to avoid unnecessary calls to your database. Some thought needs to be invested in how to implement caching in your instance since you're running a search engine, the very nature of what you provide is dynamic. But still, caching can providing significant savings around the board.

From the horses mouth: Google Research Publication: BigTable

An excellent, really really excellent write up on bigtable is here on StackOverflow (What database does Google use? - Stack Overflow) The article here covers a lot of detail on what BigTable is and some of how it works.

It's important to note that Google built BigTable from the ground up, and you won't be able to get a copy of it yourself. I guess it contains a lot of their secret sauce.

These are the features it supports:

• fast and extremely large-scale DBMS
• a sparse, distributed multi-dimensional sorted map, sharing characteristics of both row-oriented and column-oriented databases.
• designed to scale into the petabyte range
• it works across hundreds or thousands of machines
• it is easy to add more machines to the system and automatically start taking advantage of those resources without any reconfiguration
• each table has multiple dimensions (one of which is a field for time, allowing versioning)
• tables are optimized for GFS (Google File System) by being split into multiple tablets - segments of the table as split along a row chosen such that the tablet will be ~200 megabytes in size.

Check the StackOverflow post out (if you're a programmer you should be living here) and if you are in for some more mind-stretching, here is the BigTable whitepaper research, all 14 PDF pages of gorgeous exposition: http://research.google.com/archive/bigtable-osdi06.pdf

Now all this means that for you will need to change your traditional SQL DBMS for something much more scalable. Old and busted, new and Improved.

While BigTable isn't really in the NoSQL area (I think, I deal mostly with SQL DBs anyway because I don't have the data requirements that something like a search engine needs) careful research should provide a suitable NoSQL alternative.