Databases almost always use B+-trees (even when docs say “B-Trees”). Here’s why and how they differ.
| Aspect | B-tree | B+-tree |
|---|---|---|
| Where are records (row pointers/values)? | In any node (internal or leaf). | Only in leaves. Internal nodes hold keys + child pointers only. |
| Range scans | Harder—must do an in-order traversal that touches internal nodes + leaves. | Fast—all data is in leaves and leaves are linked (sibling pointers) → sequential scan. |
| Fan-out (children per internal node) | Lower (nodes are bigger because they can carry data). | Higher (internal nodes are small: keys + pointers) → shallower tree. |
| Point lookup cost | O(log_f N) I/Os; may end in an internal node. | O(log_f N) I/Os; always ends in a leaf. Similar asymptotics, often faster due to higher fan-out. |
| Cache behavior | Internal nodes can be larger and dirtier (contain data). | Internal nodes are tiny and hot in cache; leaves carry the churn. |
| Update/split locality | Splits can happen at various levels containing data. | Most splits happen at leaves; internal levels change less often. |
| Typical DB usage | Rare on disk. | Standard for on-disk indexes (InnoDB, PostgreSQL btree AM, SQL Server, Oracle, etc.). |
- B-tree: “Some data in the attic and some in the rooms.” You might stop upstairs (internal node) for a hit.
- B+-tree: “Keys upstairs, all data downstairs (leaves) and the rooms are connected in a hallway.” Point lookups go down; range scans just walk the hallway.