Every time your application runs a SELECT or UPDATE query, the database does not crawl its rows: it locates the record almost instantly. Most of that work is done by a data structure called the B-tree, which deserves a closer look. It is the invisible archivist behind nearly every modern relational database.
The problem: scanning is slow, but so is pointing
The most naive way to find a value is to read records one by one until you hit it. That is a sequential scan (full table scan), with a cost proportional to the number of rows: a million rows means a million reads in the worst case. To avoid this, the database keeps an index, an auxiliary structure that orders the keys and lets you jump straight to the area where the data lives.
The naive index idea is a balanced binary tree: the classic structure from algorithm textbooks. But here the physics of storage comes in. Databases keep data on disk, and the disk does not read loose bytes: it reads blocks (or pages) of several kilobytes at once. A binary tree with one value per node wastes most of every block and needs one disk jump per level. With lots of data that is many disk reads, and each one costs milliseconds.
What a B-tree is
The key difference of the B-tree is that each node holds not one value but many sorted keys, plus its child links. It is defined by a parameter called order (or branching factor): a node can hold at most d keys and therefore d+1 children, depending on the variant. With a typical order of tens or hundreds, a node takes exactly one disk page. That is critical: one disk read loads a whole node with hundreds of keys into memory.
The high branching factor is the secret behind its tiny height. A binary tree with a million elements has about 20 levels; a B-tree with a branching factor of, say, 200 needs only 3 levels for the same data. Since each level usually means one disk read, going from 20 accesses to 3 cuts the time dramatically.
The properties that keep it balanced
A B-tree does not “unbalance” with use, and that is what makes it predictable. It maintains strict invariants:
- All leaves are at the same depth. The tree grows upwards (the root splits) instead of stretching downward, so the height is always logarithmic.
- Every node (except the root) holds between half and the maximum number of keys allowed. If a node fills up on insert, it splits in two and its middle key moves up to the parent; if a node gets too sparse on delete, it merges with a sibling.
These rules guarantee that search, insertion and deletion are always O(log n), with a very small disk constant thanks to the large pages.
From B-tree to B+ tree
Most real databases (PostgreSQL, MySQL with InnoDB, SQLite) use a variant called the B+ tree. The difference: in a B+, only the leaves store the data (or pointers to it), and the leaves are linked to each other in order. That turns range scans —WHERE price BETWEEN 10 AND 20— into a walk across the leaf list, instead of climbing up and down the tree. And because the upper levels store only keys, they fit more branching factor per page and the height drops even further.
That is why a B+ index over a table with billions of rows usually fits in four or five levels: reading just four or five pages finds any row. That is the visible “miracle” every time a seemingly giant query answers in milliseconds.
Clustered and secondary indexes
Not every B index stores the same thing. A clustered index physically orders the rows in the leaves by the key: there can be only one per table, and it is InnoDB’s implicit order when you define a primary key. A secondary index stores only the indexed key plus a pointer to the row (or to the primary key); you can have many. Searching by a secondary key may require two walks across trees: one to find the primary key and another to reach the row. Choosing which columns to index well is, largely, managing this trade-off between speed and space.
Alternatives and when it is not a B-tree
The B-tree is not the only option. A hash index gives almost constant equality lookups (O(1)), but it cannot do ranges or ordering. Text columns sometimes use inverted index structures (document-style) for substring searches. And in heavy-write scenarios, systems like Apache Cassandra or RocksDB use LSM-trees (Log-Structured Merge), which turn random writes into sequential ones to spare the disk, at the cost of somewhat more expensive reads.
The B-tree remains the default when the workload mixes reads and writes, with ranges and ordering, on mechanical disks or SSDs: the perfect balance between block locality and access cost. It is, literally, the structure that most often decides whether a query takes seconds or microseconds.
