The B+ Tree Deep Dive: Why Database Indexes Use Balanced Trees Instead of Hash Maps

Suppose you are executing a range query on an e-commerce platform:

SELECT * FROM orders 
WHERE created_at BETWEEN '2026-09-01' AND '2026-09-08';

The orders table contains 50,000,000 rows.

If your database indexes the created_at column using a Hash Index, point lookups (WHERE created_at = '2026-09-01') execute in $O(1)$ time. But range queries fail completely: a hash function scatters adjacent dates across completely different bucket pages, forcing the database to scan all 50,000,000 rows.

If your database uses a standard Binary Search Tree (BST) or Red-Black Tree, nodes have a fan-out of 2. For 50,000,000 rows, the binary tree reaches a depth of 26 levels.

Traversing 26 levels requires making 26 separate random disk page reads. At 10ms per disk seek, a single query takes 260 milliseconds.

This is why database engines use B+ Trees. A B+ Tree can index 1,000,000,000 rows with a tree height of just 3 to 4 levels, solving both point lookups and range scans in 3 disk page reads.

B-Tree vs B+ Tree: The Fundamental Difference

Database engines do not use standard B-Trees. They use a specialized variant called the B+ Tree.

STANDARD B-TREE (Data Payloads Stored at EVERY Level)

                 [ Key: 50 | Data: Record50 ]
                /                            \
  [ Key: 20 | Data: Record20 ]      [ Key: 70 | Data: Record70 ]

B+ TREE (Data Payloads Stored ONLY at Leaf Nodes)

                      [ Key: 50 | Pointer ]            <--- Internal Node (Keys Only)
                     /                     \
       [ Key: 20 | Pointer ]         [ Key: 70 | Pointer ]
       /                   \         /                   \
 [ Leaf Node 10,20 ] <=====> [ Leaf Node 30,50 ] <=====> [ Leaf Node 70,90 ]
 (Contains Payloads)         (Contains Payloads)         (Contains Payloads)

The Three Key Differences of a B+ Tree:

Internal Nodes Store Only Router Keys & Page Pointers: Internal non-leaf nodes contain zero data payload records. They store only key values used to navigate search paths.
Data Payloads Live Exclusively in Leaf Pages: All table row data (or Record ID pointers) resides inside leaf nodes at the bottom level of the tree.
Leaf Nodes Form a Doubly Linked List: Every leaf page maintains prev and next pointers connecting it to adjacent leaf pages in physical sorted order.

High Fan-Out: Why Tree Depth Remains 3 or 4

The secret to B+ Tree disk performance is high node fan-out.

Because an internal B+ Tree node fits inside a single 16KB database page and stores only small keys and 4-byte page pointers, a single 16KB page node can store 1,000 key-pointer pairs.

$\text{Fan-Out } (M) \approx 1,000 \text{ pointers per 16KB Page Node}$

Let’s calculate how many records a B+ Tree can index at different tree heights:

Tree Height ( $H$ )	Formula	Maximum Indexed Records
Height 1 (Root node only)	$1,000^1$	1,000 rows
Height 2 (Root + Leaf Level)	$1,000^2$	1,000,000 rows
Height 3 (Root + 1 Internal + Leaf)	$1,000^3$	1,000,000,000 rows (1 Billion!)
Height 4	$1,000^4$	1,000,000,000,000 rows (1 Trillion!)

Even for a table containing 1 Billion rows, locating any specific record requires traversing at most 3 page node levels from root to leaf!

Because the Root Page and top internal nodes sit permanently cached inside the database Buffer Pool RAM, finding a record requires only 1 physical disk read.

How B+ Trees Handle Range Queries in $O(1)$ Linked Steps

Return to our range query:

SELECT * FROM orders WHERE created_at BETWEEN '2026-09-01' AND '2026-09-08';

Executing a range query in a B+ Tree occurs in two phases:

PHASE 1: Point Search for Start Boundary ('2026-09-01')
Root Page ---> Internal Page ---> Leaf Page 402 (Found start date!)

PHASE 2: Sequential Leaf Traversal along Doubly Linked List
Leaf Page 402 ----(next)----> Leaf Page 403 ----(next)----> Leaf Page 404
(Reads sequential pages until date > '2026-09-08')

Phase 1 (Point Search): Traverse down from root to leaf to find the start date '2026-09-01'. This takes $O(\log N)$ steps (3 page reads).
Phase 2 (Leaf Traversal): Follow .next pointers sequentially across adjacent leaf pages until reaching '2026-09-08'.

Because adjacent leaf pages sit next to each other, range scans perform high-speed sequential disk reads instead of random disk seeks!

Node Splitting and Merging Mechanics

B+ Trees maintain strict balance invariants automatically as records get inserted or deleted.

1. Node Splitting on Insert

When an insertion fills a 16KB leaf page beyond capacity:

The storage engine splits the leaf page into two pages, each half-full ( $50\%$ fill factor).
The median key is copied up into the parent internal page.
If the parent internal page is full, it splits recursively upward toward the root.

INSERTING INTO FULL LEAF PAGE:
[ 10 | 20 | 30 | 40 | 50 (FULL!) ]

AFTER PAGE SPLIT:
Parent Node:       [ 30 ]
                  /      \
Leaf Pages:  [ 10 | 20 ]  [ 30 | 40 | 50 ]

2. Node Merging on Delete

When deletions cause a page fill factor to drop below a threshold (e.g. $< 50\%$ ), the storage engine merges adjacent sibling leaf pages to prevent memory waste.

Quick Summary

B+ Trees store data payloads exclusively in leaf nodes; internal nodes store navigation keys and page pointers only.
High fan-out (~1,000 pointers per 16KB page) keeps tree depth to 3 or 4 levels, even for billions of rows.
Doubly-linked leaf pages enable high-speed $O(1)$ range scans using sequential disk I/O.
Automatic page splitting and merging maintain structural tree balance during writes.

References & Further Reading

Graefe, G. (2011). Modern B-Tree Techniques. Foundations and Trends in Databases, 3(4), 203–402.
PostgreSQL Source Code. Page Header and ItemId Data Structure (src/include/storage/bufpage.h). GitHub.
Lomet, D. B. (2001). The Microstructure of Log-Structured File Systems and Databases. IEEE Data Engineering Bulletin, 24(2), 11–17.