A query like SELECT * FROM users WHERE id = 42 should not have to scan every user row. With a good index, the database can jump close to the row it needs.

Most relational database indexes use a B-tree, or a close variant called a B+ tree, to make that jump fast.

B-trees work well because of their shape. They are sorted trees, but each node can hold many keys. In a database, a node is usually sized to fit a storage page, so one page read brings in many keys at once.

A normal binary tree with a billion keys might be around 30 levels deep. If each level required another page read, lookups would be slow. A B-tree with the same data may be only 3 or 4 levels deep.

In short, a B-tree spends a small amount of CPU searching inside a page so it can avoid many expensive page reads.

This chapter covers how B-trees are structured and why databases rely on them.