B Plus Tree

The variant almost every real index actually uses

While 20.2 described the conceptual B-Tree, most production databases (PostgreSQL's default btree index, MySQL's InnoDB indexes, SQL Server's clustered/non-clustered indexes) actually implement a refinement called the B+ Tree. The name is confusingly similar, but the internal shape differs in one crucial way.

The key difference: where the data lives

• In a plain B-Tree, data pointers (or the actual row data) can live in any node — root, internal, or leaf.
• In a B+ Tree, internal nodes (including the root) hold only keys, used purely for navigation. All actual data pointers/values live exclusively in the leaf nodes.

For our students table, imagine a B+ Tree index on gpa. The internal nodes contain only signpost values like 2.0, 2.5, 3.0, 3.5 to guide the search downward — none of them point to actual student rows. Only when you reach a leaf node do you find an actual gpa value paired with a pointer back to the matching row(s) in the table.

The second key feature: linked leaves

B+ Tree leaf nodes are linked together in a chain (typically a doubly linked list), in sorted key order. This is the feature that makes B+ Trees so good at range queries.

Consider:

sql
SELECT * FROM students WHERE gpa BETWEEN 3.0 AND 3.5;

With a B+ Tree index on gpa, the engine navigates down through internal nodes once to find the leaf containing 3.0, then simply walks along the linked leaf chain — collecting every subsequent key up to 3.5 — without ever needing to re-traverse the tree from the root. This sequential leaf-walk is very cheap.

With a plain B-Tree (where matching data could be scattered across internal and leaf nodes at different depths), satisfying the same range query would require a more complex in-order traversal jumping between different levels of the tree — much less efficient.

Why this matters practically

• Equality lookups (WHERE gpa = 3.5) are still fast in both structures — O(log n) tree descent.
• Range lookups (BETWEEN, >, <, ORDER BY) are where the B+ Tree's leaf-chain genuinely shines, which is why it's the near-universal choice for general-purpose database indexes.

Edge cases

• Because internal nodes hold no data, they can be more compact and fit more keys per node (higher branching factor), which can make the tree even shallower than an equivalent plain B-Tree.
• A key stored in an internal node for navigation is often duplicated in a leaf node too — this redundancy is intentional and part of what enables the leaf chain to be self-sufficient for range scans.
• ORDER BY gpa can sometimes be satisfied "for free" by simply walking the leaf chain in order, avoiding a separate sort step entirely.

Interview-style Q&A

Q: What's the single structural difference that defines a B+ Tree versus a plain B-Tree? A: In a B+ Tree, only leaf nodes hold actual data pointers; internal nodes exist purely for navigation via keys, and the leaves are linked together for efficient sequential access.

Q: Why are B+ Trees especially good for range queries? A: Because once the starting leaf is found, the linked leaf chain can simply be walked in sorted order to collect the rest of the range — no repeated tree traversal needed.

Key takeaway: B+ Tree = B-Tree navigation (fast equality) + linked, data-only leaves (fast ranges) — which is exactly why it, not the plain B-Tree, is the default index structure in virtually every real database engine.