Does anybody knows how Google or Yahoo perform searches for keywords against very very huge amounts of data? What sort of database or technologies do they employ for this?
It takes few milliseconds, but they have more than a billion pages indexed.
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It only takes a minute to sign up.Sign up to join this community
I am sure there is a combination of things:
lots of it - data is distributed and replicated across many nodes and different data centers
The heart of Google's search technology is PigeonRank™, a system for ranking web pages developed by Google founders Larry Page and Sergey Brin at Stanford University:
Building upon the breakthrough work of B. F. Skinner, Page and Brin reasoned that low cost pigeon clusters (PCs) could be used to compute the relative value of web pages faster than human editors or machine-based algorithms. And while Google has dozens of engineers working to improve every aspect of our service on a daily basis, PigeonRank continues to provide the basis for all of our web search tools.
Why Google's patented PigeonRank™ works so well
PigeonRank's success relies primarily on the superior trainability of the domestic pigeon (Columba livia) and its unique capacity to recognize objects regardless of spatial orientation. The common gray pigeon can easily distinguish among items displaying only the minutest differences, an ability that enables it to select relevant web sites from among thousands of similar pages.
By collecting flocks of pigeons in dense clusters, Google is able to process search queries at speeds superior to traditional search engines, which typically rely on birds of prey, brooding hens or slow-moving waterfowl to do their relevance rankings.
When a search query is submitted to Google, it is routed to a data coop where monitors flash result pages at blazing speeds. When a relevant result is observed by one of the pigeons in the cluster, it strikes a rubber-coated steel bar with its beak, which assigns the page a PigeonRank value of one. For each peck, the PigeonRank increases. Those pages receiving the most pecks, are returned at the top of the user's results page with the other results displayed in pecking order.
It's important to bear in mind a couple of things about google:
Their DB is the proprietary BigTable - it was custom designed BY GOOGLE to exactly fit their needs
Their proprietary DB is built on top of their proprietary file system - Google File System - this was designed, again BY GOOGLE, to be easily expandable using common commodity hardware. As Aaron mentioned in his answer, they have a large number of average servers instead of a small number of very powerful servers.
They store individual tables across multiple machines as a way of making access quicker - their software knows which data is on which machine and instead of thrashing through a disk to locate it can go straight to the server with the relevant info.
Google does not use traditional relational database technology. It developed its own technology, big table and map reduce. The original research papers are here : Big Table and Map/Reduce. Also of interest is the SSTable, sorted string table.
Read Steven Levy's "In The Plex: How Google Thinks, Works, and Shapes Our Lives". This book is a fascinating read about all things Google and does discuss at a high level some of the technology and engineering behind search. Aaron sums it up really well in his answer and Levy's book will give you some more detail about how they do it.