B+Tree vs B-Tree: Deep Dive into Structure, Performance, and MySQL Use Cases
An in‑depth comparison of B+Tree and B‑Tree reveals how their differing node designs affect storage capacity, tree height, disk I/O, range queries, caching, and insert/delete costs, with concrete MySQL InnoDB examples illustrating why B+Tree is the preferred index structure.
Logical Structure Differences
B‑Tree stores keys and data in every node, resulting in a smaller fan‑out and higher tree height. Leaf nodes are not linked, so range scans must traverse the whole tree. Query path length varies because data may be found at any level.
B+Tree stores only keys and child pointers in internal nodes, giving a larger fan‑out and lower height. All records reside in leaf nodes that are linked together in a doubly‑linked list, enabling efficient ordered scans. Every search reaches a leaf, so path length is stable.
Tree Height Estimation (MySQL InnoDB, 16 KB page)
Assume a primary key of type BIGINT (8 bytes) plus a 6‑byte child pointer and ~120 bytes page header. A leaf or internal node can hold roughly 1 160 keys.
Height ≈ log base 1160 of N.
Examples:
1 M rows → height 2–3 (2–3 I/O operations).
100 M rows → height 3–4 (3–4 I/O operations).
1 B rows → height ≤ 4 (4 I/O operations).
For a B‑Tree the same page can hold about 500–800 keys (key + data + pointer). Height ≈ log base 500 of N, typically 1–2 levels higher than B+Tree for the same N.
Performance Comparison
Disk I/O
B+Tree : Larger fan‑out (≈ 1 160 keys per 16 KB page) yields 3–4 levels for tens of millions of rows, often only 3 disk reads. The root page is usually cached.
B‑Tree : Smaller fan‑out (≈ 500–800 keys) leads to higher tree height and more reads; data is scattered, and range queries must walk the whole tree.
Range Queries
B+Tree : Leaf nodes are linked; a query such as WHERE id BETWEEN 100 AND 1000 can be satisfied by scanning the leaf list.
B‑Tree : Requires descending to leaves and then scanning the entire subtree, which is less efficient.
Point Queries
B‑Tree : Data may be found in an internal node, potentially reducing I/O if the root contains the key.
B+Tree : Every lookup reaches a leaf, but the lower height usually results in fewer I/O operations overall.
Cache Utilization
B+Tree : Only index keys occupy internal nodes, allowing more entries to fit in memory and improving cache hit rates.
B‑Tree : Data stored in nodes reduces the effective cache capacity.
Insert / Delete Overhead
B+Tree : Modifications affect leaf pages; page splits or merges involve fewer pages, giving stable performance.
B‑Tree : Data spread across many levels can cause larger restructuring work.
MySQL InnoDB Usage
InnoDB implements the clustered index as a B+Tree. Typical depth is 3–4 for tens of millions of rows.
Run SHOW INDEX FROM table to inspect the index depth and confirm the tree height.
Key Takeaway
The B+Tree’s design—internal nodes contain only index entries and leaf nodes are linked—produces a higher fan‑out, lower height, fewer disk I/Os, faster range scans, and better cache efficiency, making it the preferred index structure for relational databases and many file systems.
Architecture & Thinking
🍭 Frontline tech director and chief architect at top-tier companies 🥝 Years of deep experience in internet, e‑commerce, social, and finance sectors 🌾 Committed to publishing high‑quality articles covering core technologies of leading internet firms, application architecture, and AI breakthroughs.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.