Google must have a gigantic database with hundreds of million, if not billions, of text rows. When I type in a search for a string for which they clearly cannot have a pre-stored result, how do they manage to search trough all those rows in less than a second?
Masses of computing power and indexing techniques that unsurprisingly they keep a trade secret.
They’re willing to sell it to you: Google appliance
I’m sure the indexing is very clever, but the sheer computing grunt is the real explanation of Google’s speed.
From here
In general, search engines work by keeping an inverted list: a list of words, and for each word, a list of all the documents that word appears in. When you enter a query, the engine gets the lists for each of your query words and combines the lists according to some formula to get the ranked list of results. That method can be very fast, even with millions of documents.
Since Google indexes billions of documents, a standard inverted list would still be pretty slow. They probably use the basic inverted list, but also do some pruning, some sampling, and some approximation to speed things up. The nice thing about having a huge heterogeneous corpus like the web is that you can be less than exact and still do very well.