How does a database find one row among a billion in an instant?

A database finds one row among a huge number by never looking at most of them. It keeps an index: a second, sorted structure that works like the index at the back of a book. An index is a copy of selected columns, built for very efficient searching, and each entry links back to the full row. Instead of reading the whole table, the database looks in the index, then jumps straight to the right place.

Without an index, a simple search has to examine each item, so twice the data means twice the work. Good indexes grow far more slowly, often in logarithmic time. The price is that every index takes extra storage and extra writing, because it has to be updated whenever the data changes. The order matters too: with a phone book sorted by city, then last name, finding all the people in one city is easy, but finding everyone with a given last name is tedious.

The champion design is the B-tree, invented at Boeing Research Labs by Rudolf Bayer and Edward McCreight. It is a tree of sorted keys where each node can have many children, so the tree stays short and the data sits in few separate blocks. That suits disks, which are slow to reach but quick to read in big chunks. In a textbook example, a million records by plain binary search take 20 disk reads, about 0.2 seconds; a hierarchy of blocks needs only 3 reads. The B-tree is the standard index in almost all relational databases and in many others. And what does the B stand for? The inventors never said.