How B-Tree Indexes Work
IntermediateA B-tree index is the data structure behind almost every database index. It is a balanced tree that keeps keys sorted and lets the database find, insert, and delete rows in logarithmic time — turning a full-table scan into a handful of page reads. Its shallow, wide shape (the B+tree variant links leaves together) makes both single-key lookups and range scans fast, which is why B-trees are the default index in PostgreSQL, MySQL, and most databases.
Think of a B-tree as a well-organised dictionary
To find a word in a dictionary you do not read every page — you open near the right letter, then narrow down by section, then scan a single page. A B-tree works the same way: a few decisions at the top guide you down to the exact page holding your key. And because words are sorted, once you find "cat" you can read "cats," "catch," "category" right after it — that is a range scan, and it is why sorted trees beat hash tables for ranges.
Step by Step
Key Concepts
B-tree vs B+tree
A B-tree stores keys and values throughout the tree. A B+tree stores values only in the leaves and links leaves in order — better for range scans and sequential access, which is why databases use B+trees.
Logarithmic Lookup
Because each node has a high fan-out, the tree is shallow and a lookup costs O(log n) page reads. Even billions of rows resolve in a few disk/page accesses.
Range Scan
Finding all keys between two bounds. Sorted, leaf-linked B+trees excel here — the reason B-trees beat hash indexes when you need ranges, ORDER BY, or prefix matches.
Clustered vs Non-clustered
A clustered index stores the table rows in the index leaves (one per table). A non-clustered index stores a pointer to the row, so a lookup may need a second read to fetch the full row.
Key Facts
- B-trees are shallow because of high fan-out: a tree of billions of rows is typically only 3–4 levels deep, so lookups touch just a few pages.
- Hash indexes are faster for exact-match single lookups but cannot do range scans or ordering — B-trees handle both, which is why they are the default.
- An index speeds reads but must be updated on every write, so each index adds write and storage overhead — index deliberately, not by default.
Real-World Applications
Speeding up a WHERE clause
A B-tree index on users(email) turns a lookup by email from scanning millions of rows into a few page reads — the difference between a slow query and an instant one.
Efficient pagination and ranges
A B-tree on created_at lets the database return "orders from last week, sorted by date" via a range scan over linked leaves, without sorting the whole table.
Frequently Asked Questions
Why do databases use B-trees instead of binary trees or hash tables?
B-trees have high fan-out (many keys per node), so they stay shallow and each lookup reads only a few disk pages — ideal for storage. Unlike hash tables, they keep keys sorted, enabling range scans, ORDER BY, and prefix searches. Binary trees are too deep and cause too many page reads for disk-based data.
What is the difference between a B-tree and a B+tree?
A B-tree stores keys and their associated data throughout all nodes. A B+tree stores data only in the leaf nodes and links those leaves in sorted order. Databases favour B+trees because the linked leaves make range scans and sequential reads very efficient.
What is the lookup complexity of a B-tree index?
O(log n) — logarithmic. Because each node holds many keys, the tree is only a few levels deep even for billions of rows, so finding a key takes just a handful of page reads instead of a full-table scan.
Does adding an index have any downside?
Yes. While an index speeds up reads, it must be updated on every insert, update, and delete of the indexed column, adding write overhead and storage. Over-indexing slows writes, so you should add indexes to match real query patterns rather than indexing every column.