Why Databases Store Data in B+ Trees: From Naive Disk Storage to Indexed Pages

Most modern database systems—both relational engines like MySQL (InnoDB) and document stores like MongoDB (WiredTiger)—rely on B+ trees as their primary on-disk storage format. While computer science curricula often introduce B+ trees as abstract balancing data structures, their adoption in real-world storage engines is driven by the physical realities of secondary storage (HDDs and SSDs).

To understand why B+ trees dominate database architecture, we must analyze the physics of disk I/O, trace how a naive file-based database breaks down, and examine how page-based tree indexing solves the fundamental constraints of disk mutation.

---

1. The Naive Approach: Flat-File Storage

To build intuition, consider the simplest possible database storage design: a single file on disk where rows (or documents) are appended sequentially, one after another.

+-------------+-------------+-------------+-------------+
| Row 1 (ID:1)| Row 2 (ID:2)| Row 3 (ID:5)| Row 4 (ID:7)|
+-------------+-------------+-------------+-------------+

In relational databases, records are almost universally clustered (ordered) by their Primary Key. If data must remain ordered on disk, this naive single-file design fails catastrophically across every standard CRUD operation.

The Failure Modes of Flat-File Storage

1. Insert Operations ($O(N)$)

• Appending to the very end of an append-only log is fast ($O(1)$).
• However, if the primary key order must be maintained and an incoming record has an ID that belongs in the middle (e.g., inserting ID 3 between 2 and 5), the database cannot simply “make space”.
• Unlike an in-memory array or a text editor buffer, a disk file does not shift bytes downward when writing to an offset. Writing to an existing offset overwrites whatever bytes were already there.
• Consequence: To insert in the middle, the storage engine must allocate a new file, copy all rows prior to the target offset, write the new row, copy the remainder of the file, and delete the old file. An insert is strictly $O(N)$ disk write overhead.

2. Update Operations ($O(N)$)

• If an update modifies variable-width data (such as expanding a VARCHAR column from 100 bytes to 120 bytes), the new record infringes on the boundary of the neighboring record.
• Because disk storage does not automatically expand offsets, expanding a record requires rewriting all subsequent data down-file in a new copy—again degrading to $O(N)$.

3. Point Lookups / Find ($O(N)$)

• Without indexing, finding a record requires a full linear scan from offset 0 through the file until the target record matches, resulting in $O(N)$ disk I/O.

4. Delete Operations ($O(N)$)

• Removing a row cannot simply leave a “hole” without wasting storage space over time.
• Reclaiming that space immediately requires shifting all succeeding rows forward, once again requiring an $O(N)$ file copy.

5. Range Queries

• While contiguous layout makes iterating over a range efficient once located, finding the lower bound still requires an $O(N)$ scan.

Every core database operation in a naive flat file incurs an $O(N)$ disk overhead, rendering it completely unfeasible for production workloads.

---

2. The Physical Reality: Disk Blocks and Pages

Storage drives do not read or write data at the byte level. The operating system and physical storage controllers interact using a minimum unit of transfer known as a disk block (typically 4 KB on modern filesystems, or 8–16 KB in database engines like InnoDB).

+-------------------------------------------------------------+
|               Operating System Disk Block (4 KB)            |
+-------------------------------------------------------------+
| Even if you request 1 byte, the OS reads the full 4 KB block|
| from disk into an OS page cache/RAM buffer.                 |
+-------------------------------------------------------------+

• If a query needs to read a single 40-byte row, the disk controller must read the entire 4 KB block containing that row into memory, extract the desired bytes, and discard the rest.
• If a write modifies 5 bytes, the entire 4 KB block must be written back out.

The Page-Block Alignment

Because 4 KB is the physical atomicity unit of disk I/O, database engines align their internal node structures to match this size.

If we designate each node of our search structure to be 4 KB:

• Suppose the average row size is 40 bytes.
• A single 4 KB node can house roughly $\frac{4096}{40} \approx 100$ rows (accounting for internal headers and slot pointers).
• Reading a node translates into exactly one physical disk I/O operation.

---

3. The B+ Tree Architecture

A B+ tree is an $M$-way search tree optimized for systems that read and write large blocks of memory. Unlike standard B-trees, a B+ tree enforces two foundational invariants:

1. All user data (rows/documents) is stored strictly in the leaf nodes.
2. All non-leaf (internal) nodes store only routing keys and child page pointers.
3. All leaf nodes are chained sequentially via pointers (linked list).

graph TD
    Root["Root Node: [Key: 201 | Key: 401]"]
    
    L1_1["Internal Page 1: [Key: 101]"]
    L1_2["Internal Page 2: [Key: 301]"]
    L1_3["Internal Page 3: [Key: 501]"]
    
    Leaf1["Leaf Page 1<br/>IDs: 1 - 100"] 
    Leaf2["Leaf Page 2<br/>IDs: 101 - 200"]
    Leaf3["Leaf Page 3<br/>IDs: 201 - 300"]
    Leaf4["Leaf Page 4<br/>IDs: 301 - 400"]
    Leaf5["Leaf Page 5<br/>IDs: 401 - 500"]
    Leaf6["Leaf Page 6<br/>IDs: 501 - 600"]

    Root -->|ID < 201| L1_1
    Root -->|201 <= ID < 401| L1_2
    Root -->|ID >= 401| L1_3

    L1_1 -->|ID < 101| Leaf1
    L1_1 -->|ID >= 101| Leaf2

    L1_2 -->|ID < 301| Leaf3
    L1_2 -->|ID >= 301| Leaf4

    L1_3 -->|ID < 501| Leaf5
    L1_3 -->|ID >= 501| Leaf6

    Leaf1 -.->|Next Pointer| Leaf2
    Leaf2 -.->|Next Pointer| Leaf3
    Leaf3 -.->|Next Pointer| Leaf4
    Leaf4 -.->|Next Pointer| Leaf5
    Leaf5 -.->|Next Pointer| Leaf6

How Nodes Are Serialized to Disk

Nodes do not float in memory; they are stored within tablespace data files on disk:

• The data file is partitioned into uniform contiguous regions of 4 KB (or 16 KB for MySQL).
• A pointer to a child or sibling node is simply the byte offset within that file (e.g., offset = page_number * 4096).
• Pages do not need to be physically adjacent on disk; the internal tree structure and child offset pointers route the storage engine to the exact byte ranges.

---

4. How Core Operations Work in a B+ Tree

1. Point Lookup (find_by_id)

Suppose we want to find row ID 3 in a 3-level B+ tree:

1. Read Root Page: Perform 1 disk I/O to pull the 4 KB root node into memory. Inspect the routing keys. Key 3 falls into the bucket for the first child page.
2. Read Internal Page: Perform a 2nd disk I/O at the child page’s disk offset. Inspect routing keys. Key 3 belongs in Leaf Page 1 (IDs: 1-100).
3. Read Leaf Page: Perform a 3rd disk I/O at Leaf Page 1’s offset. The engine now has 100 rows in memory.
4. In-Memory Search: Execute binary search across the sorted slot array of the leaf page to retrieve the row.

Complexity: Point lookup requires exactly $H$ disk I/Os, where $H$ is the height of the tree ($O(\log_B N)$, where $B$ is the node fanout). For massive tables with millions of rows, $H$ is typically only 3 or 4.

2. Insert Operations

Suppose we insert row ID 4:

1. Traverse from the root to locate the appropriate leaf page (3 reads).
2. Load that single 4 KB leaf page into a RAM buffer.
3. Insert row 4 in sorted order within the in-memory page array, shifting sibling rows inside that 4 KB buffer.
4. Write the modified 4 KB page back out to disk (1 disk write/flush).

Note on Page Splits: If the 4 KB page is already full, the engine splits the page into two 2 KB halves, allocates a new disk block, and propagates the new split key up to the parent internal node. Even with page splits, mutations remain local without requiring an $O(N)$ full-file rewrite.

3. Update and Delete Operations

• Update: Navigate to the leaf page via tree traversal (height $H$ reads). Modify the row within the in-memory page. Flush the single 4 KB block back to disk (1 write).
• Delete: Traverse to the leaf page. Erase the record from the page’s slot array. Mark the block as dirty and flush to disk. If the page falls below a minimum occupancy threshold, the engine merges it with an adjacent sibling page.

4. Range Queries (The True Superpower of B+ Trees)

Consider a query fetching all rows between ID 100 and ID 550 (SELECT * FROM table WHERE id BETWEEN 100 AND 550):

graph LR
    Root -->|Traverse O(log N)| LeafPage1["Leaf Page 2 (IDs 101-200)"]
    LeafPage1 -->|Disk Read Next| LeafPage2["Leaf Page 3 (IDs 201-300)"]
    LeafPage2 -->|Disk Read Next| LeafPage3["Leaf Page 4 (IDs 301-400)"]
    LeafPage3 -->|Disk Read Next| LeafPage4["Leaf Page 5 (IDs 401-500)"]
    LeafPage4 -->|Disk Read Next| LeafPage5["Leaf Page 6 (IDs 501-600)"]

1. Locate Lower Bound: Execute a point lookup for ID 100 using the internal routing nodes ($O(\log_B N)$ disk reads).
2. Linear Leaf Traversal: Because all leaf pages contain direct disk-offset pointers to their next and previous siblings, the database does not need to traverse back up to the root or internal nodes.
3. It sequentially reads Leaf Page 2 $\rightarrow$ Leaf Page 3 $\rightarrow$ Leaf Page 4 $\rightarrow$ Leaf Page 5 $\rightarrow$ Leaf Page 6, stopping as soon as an ID exceeds 550.

This turns what would be complex tree backtracking into an optimal, sequential stream of block reads.

---

5. B-Tree vs. B+ Tree: Why Databases Choose B+ Trees

A common interview and systems question is: Why not use a standard B-tree, which can store keys and data inside internal nodes as well?

Feature	Standard B-Tree	B+ Tree	Architectural Impact
Data Storage	Stored in both internal and leaf nodes.	Stored only in leaf nodes.	Non-leaf pages in a B+ tree are pure routing arrays, containing no heavy payload bytes.
Branching Factor (Fanout)	Low. Heavy record payloads reduce the number of keys a 4 KB node can hold.	High. A 4 KB internal node can hold hundreds of keys and child pointers.	Higher fanout drastically reduces the tree height $H$. A flatter tree requires fewer disk I/Os to hit a leaf.
Range Queries	Requires an expensive in-order tree traversal (jumping up and down levels).	Sequential traversal across leaf node sibling pointers.	Eliminates non-sequential disk seeks during index scans.
Read Predictability	Variable depth ($1$ to $H$ reads depending on where data sits).	Constant depth ($H$ reads for every single point query).	Predictable latency profiles for database reads.

By keeping internal nodes small and compact, the database can often cache the entire root and first level of internal nodes in RAM indefinitely. As a result, disk seeks are confined almost exclusively to the terminal leaf level.

---

Summary of Key Takeaways

1. Disk I/O is Chunk-Based: Hardware interfaces with storage in discrete blocks (typically 4 KB). B+ tree nodes mirror this sizing to maximize data transfer efficiency.
2. Isolation of Mutations: Storing data in independent 4 KB leaf nodes confines insertions, updates, and deletions to a single block, avoiding full-file rewrites ($O(1)$ block updates vs. $O(N)$ file rewrites).
3. Massive Fanout Minimizes Seeks: Because internal nodes store only keys and child offsets, a single 4 KB routing page can reference hundreds of child pages, keeping the tree depth small (typically 3 to 4 levels for hundreds of millions of rows).
4. Linear Leaf Links Enable Fast Ranges: Chaining leaf nodes with disk offset pointers allows sequential scanning across key ranges without ever navigating back up to internal or root nodes.