CONCEPT Cited by 1 source
B+tree¶
A B+tree is a B-tree variant with two structural modifications that make it dominate database indexes over the plain B-tree:
- Key/value pairs are stored only at leaf nodes. Internal nodes store only keys and child pointers.
- Leaf nodes form a doubly-linked list. Each leaf carries next/previous pointers to its sibling leaves, so in-order traversal reads the values sequentially without ascending back into internal nodes.
(Source: sources/2024-09-09-planetscale-b-trees-and-database-indexes.)
Why these changes matter¶
- More keys per internal node → shallower tree. With no value payload in internal nodes, internal-node bytes are spent entirely on keys + child pointers. Given a fixed node size (disk block), the fan-out is higher, so the tree depth for the same row count is lower, so lookups touch fewer pages.
- Range scans become sequential. A query like
WHERE k BETWEEN a AND b ORDER BY kdescends once to the leaf containinga, then walks the linked-list of leaves untilb. No repeated descents. This is why time-range queries on a sequential primary key are effectively sequential I/O.
MySQL / InnoDB specifics¶
InnoDB's B+tree implementation further specialises:
- Non-leaf nodes store N child pointers instead of N+1. The classical B+tree has one more child than keys at each node; InnoDB's variant has one per key.
- All levels are doubly-linked lists. Next/previous pointers exist not just on leaves but on internal nodes too, so traversal can go sideways at any level.
- Node size = 16 KB by default — one InnoDB page.
- Default behaviour is clustered — the table's primary key IS the root of a B+tree whose leaves contain the entire row. See concepts/clustered-index.
B-tree vs B+tree summary¶
| Property | B-tree | B+tree |
|---|---|---|
| Where values live | Any node | Leaves only |
| Internal-node key density | Medium | High |
| Tree depth (same row count) | Deeper | Shallower |
| Range scan | Repeated descents | Linked-list walk on leaves |
| Sibling traversal | No | Yes (linked list) |
| Typical DB usage | Rare | Dominant (MySQL, Postgres, MongoDB, SQLite) |
Why databases prefer B+trees¶
Ben Dicken summarises two operational reasons the B+tree wins:
Since inner nodes do not have to store values, we can fit more keys per inner node! This can help keep the tree shallower.
All of the values can be stored at the same level, and traversed in-order via the bottom-level linked list.
— sources/2024-09-09-planetscale-b-trees-and-database-indexes
Seen in¶
- sources/2024-09-09-planetscale-b-trees-and-database-indexes — B+tree properties, MySQL/InnoDB specialisation, range-scan via leaf linked list. The article's central argument — that primary-key choice changes the tree's insert shape — is about the B+tree specifically.
- systems/innodb — all InnoDB table + index structures are B+trees.
- systems/wiredtiger — MongoDB's default storage engine, also B+tree-based.