Databases keep their data on disks, and disks are slow. A single read can cost as much as millions of ordinary computer steps. So a good index is not the one with the fewest comparisons. It is the one that touches the disk the fewest times.
In 1970 Rudolf Bayer and Edward McCreight, working at Boeing, described how to keep a large sorted index on a disk while keys are added and removed all the time. They named the structure a B-tree. More than fifty years later, the B-tree and its close relatives still sit under most relational databases and file systems.
A B-tree stores many keys in each page, so the tree is wide and very short. Pages are always at least half full, and every leaf is at the same depth. When a page overflows it splits in the middle and pushes one key up. So a search reads only a handful of pages, even for millions of keys.
A page is a block of the disk
A disk is read in blocks. Reading one key costs the same as reading a whole block, so the paper organizes the index into pages, one page per block. Each page holds many keys in sorted order, and a pointer sits between neighbors.
The rules in the paper are short. A page holds between k and 2k keys, except the root, which may hold as few as one. A page that is not a leaf with j keys has j + 1 children. And every path from the root to a leaf has the same length. That last rule is the key one: the tree is always perfectly balanced.
Think of a dictionary's thumb tabs. You do not scan every word. You flip to the right letter, then the right page, then scan a short list. A B-tree is a thumb-tab index with the tabs themselves arranged in layers.
