When you ask a database for the row holding the order you placed three months ago, the answer usually arrives in a few milliseconds. Across a table with millions of rows, that is not magic: it is the result of your data not being searched but deliberately ordered inside a structure called a B-tree. Understand what that is and you understand why almost every database engine in the world —from MySQL to PostgreSQL, from SQL Server to Oracle— uses it as its default index.
The problem: searching without reading everything
Picture a table with 100 million rows and no index at all. To find one specific row, the engine has no choice but to walk through them one by one until it hits the one that matches the condition: a full table scan, whose cost grows linearly with the number of rows. With 100 million records, every query would mean reading hundreds of thousands of disk blocks. That is what makes a system slow when someone forgot to create an index.
The obvious alternative is to keep the data sorted and use a binary search: split the space in half, discard one part, repeat. With 100 million rows, about 27 comparisons would suffice. But there is a deeper problem: disks do not read one comparison at a time, but in contiguous blocks (typically 4 to 16 KB), and every jump to a different block costs a physical access. Binary search over a sorted array triggers far too many jumps.
The solution: a tree that grows in width, not height
Enter the B-tree (the B has no single official meaning; it is usually attributed to “balanced” or to its inventor, Rudolf Bayer). It is a search tree whose nodes hold multiple sorted keys and multiple pointers to children. Each node is designed to occupy exactly one disk block, so reading a node costs a single physical access.
The decisive trait is that the tree stays balanced: every leaf (the nodes on the last level) sits at the same depth. When a node fills up it splits in two and the middle key rises; when it drains too far it merges with a sibling. As a result the height —the number of levels you must descend— stays around 3 or 4 even with billions of rows, because the number of children per node (the branching factor) usually runs between 100 and 500.
Keys, leaves and pointers: the journey of a query
When you run a query with a condition on an indexed column, the engine’s planner descends from the tree’s root. At each node it compares your value against the keys it holds and decides which child to follow, exactly like a binary search but crossing few levels and reading one block per level. When it reaches a leaf it finds the record it was looking for.
Two variants are worth distinguishing. In the classic B-tree, data may live in any node. In the B+ tree, the one used by InnoDB (MySQL) and PostgreSQL, data lives only in the leaves, which are additionally linked to each other in order. That link turns range scans —every row between two dates, say— into a simple sequential walk across the leaves, with no need to climb back up the tree.
The index in real storage
The concrete implementation varies. In MySQL with InnoDB, the whole table is a B+ tree whose key is the primary key: a clustered index, so rows are physically stored ordered by it. Every other index is secondary and its leaves store the primary-key value, not the full row, forcing a second jump. In PostgreSQL, by contrast, rows live in a separate structure called the heap, and indexes store a physical row identifier (the ctid) that points to the row’s location on disk.
Those details explain practical decisions you will meet day to day. If your query asks for columns already present in the index itself, the engine can answer without touching the table: a covering index, usually the cheapest win available. They also explain why indexes are not free: every INSERT or UPDATE must update every index on the table, and a poorly chosen secondary index can cost more in writes than it saves in reads.
The B-tree is not alone
It helps to place it in the landscape. B-trees are tuned for reads and for on-disk data, but other families cover specific cases. LSM trees (Log-Structured Merge), used by Cassandra, RocksDB or LevelDB, trade away some read performance to be far faster at writes: instead of modifying blocks in place, they buffer changes in memory and flush them to disk in bursts — a design aimed at massive ingestion. And a hash index only supports equality comparisons, not ranges, so it fills a very narrow niche.
That the B-tree keeps winning after decades is not nostalgia: it is the structure that best balances reads, writes and space usage when data lives on a slow disk. Next time a query answers instantly over millions of rows, you know who is doing the work under the hood: a patient, balanced tree with a huge branching factor that turns a linear problem into a matter of three or four disk accesses.
