B-Tree Family Deep Dive: Core Principles and Implementation of B+ Trees

When deleting a key from a B+ tree, the operation is not simply removing the entry from the leaf node: we must also maintain the structural invariant that every node (except the root) holds at least $t = \lceil m/2 \rceil - 1$ keys, where $m$ is the maximum number of keys per node (the tree’s degree). To understand this process, consider a B+ tree with degree $m=5$ (maximum 4 keys per node, minimum 2 keys per non-root node) initialized with the following structure:

• Root node $R$: internal node with separator keys $[15, 30]$, pointing to three child leaf nodes
• Leaf node $C1$: keys $[5, 10, 12]$ (3 keys, satisfies the minimum threshold

To complete the deletion operation example introduced earlier, let us walk through the full lifecycle of removing key `5` from the leaf node $C1$ (which now contains only `[5, 10]` after the prior deletion of `12`). For a B+ tree with degree $m=5$ (minimum $t = \lceil 5/2 \rceil = 3$ keys per non-root node? Wait, correction: for B+ trees, the minimum occupancy rule is typically $\lceil m/2 \rceil$ keys per node, so for $m=5$, minimum is 3 keys? No, wait, let's correct that: for B+ trees where $m$ is the maximum number of child pointers per internal node, the maximum number of keys per internal node is $m-1$, and the minimum number of keys per non-root internal node is $\lceil m/2 \rceil - 1$, while leaf nodes have the same minimum key count. For $m=5$, minimum keys per non-root node is $\lceil 5/2 \rceil -1 = 2$, so a leaf node with 1 key violates the invariant. When we delete `5` from $C1$, it will hold only `[10]` (1 key), which is below the 2-key minimum. We first attempt to *redistribute* keys with its left sibling $C0$ (keys `[2, 3, 8]`) or right sibling $C2$ (keys `[16, 20, 25]`). Since $C0$ has 3 keys (above the 2-key minimum), we can borrow its rightmost key `8`, moving it to $C1$ and updating the separator key in parent root $R$ from `15` to `8`? No, wait, separator keys are the first key of the right child. Wait, $C0$ is the left child of root $R$, $C1$ is the middle child, $C2$ is the right child. The separator keys in $R$ are `[15, 30]`, meaning all keys in $C0$ are <15, keys in $C1$ are ≥15 and <30, keys in $C2$ are ≥30. Oh right, I messed up the initial example earlier. So $C0$ has keys <15, $C1$ has 15≤keys<30, $C2$ has ≥30. So when we delete `5` from $C1$? No no, `5` is in $C0$, sorry, let's correct the example to be consistent: initial structure:

• Root $R$ (internal): separator keys `[15, 30]`, child pointers $p_0 \to C0$, $p_1 \to C1$, $p_2 \to C2$
• $C0$ (leaf): keys `[5, 10, 12]` (all <15)
• $C1$ (leaf): keys `[15, 18, 22]` (15≤keys<30)
• $C2$ (leaf): keys `[32, 35, 40]` (≥30)

Now delete key `12` from $C0$: $C0$ now has `[5,10]` (2 keys, meets minimum, no redistribution needed). Next delete key `5` from $C0$: $C0$ now has `[10]` (1 key, below 2-key minimum). Check left sibling: none (it is the leftmost leaf). Check right sibling $C1$: has 3 keys (above minimum). We can borrow the first key of $C1$ (which is `15`, the minimum key of $C1$'s range) to $C0$, so $C0$ becomes `[10,15]`, $C1$ becomes `[18,22]`, and we update the first separator key in root $R$ from `15` to `18` (since the first key of $C1$ is now `18`). This redistribution avoids the more expensive merge operation, which is why most B+ tree implementations prioritize redistribution over merging when possible. If $C1$ also had only 2 keys (the minimum), redistribution would not be possible, so we would merge $C0$ and $C1$ into a single leaf node with keys `[10,15,18,22]` (4 keys, well above the 2-key minimum), then remove the first separator key `18` from root $R$, leaving root $R$ with only separator key `[30]` and two child pointers. If the root had only one key after this merge, we would *delevel* the tree by making the merged leaf node the new root, reducing the tree height by 1.

3.3 Page-Level Storage Mapping: From Logical Index to Disk Blocks

All disk-based B+ tree implementations map logical index nodes to fixed-size storage pages (typically 4KB to 16KB for HDDs, 16KB to 64KB for SSDs, depending on the database system). This mapping is not arbitrary: it is designed to align with the operating system’s page size and the storage device’s block size to avoid partial read/write operations that degrade performance.

3.3.1 Page Header and Node Layout

Every B+ tree page starts with a fixed-size header that stores metadata required for crash recovery and concurrency control. For example, InnoDB’s 16KB B+ tree page header includes the following fields (see <https://dev.mysql.com/doc/refman/8.0/en/innodb-physical-record.html> for official documentation): | Field Name | Size (Bytes) | Purpose | |--------------------------|--------------|-------------------------------------------------------------------------| | `page_type` | 2 | Identifies page type (e.g., B+ tree internal node, leaf node, overflow page) | | `page_number` | 4 | Unique identifier for the page within the tablespace | | `lsn` | 8 | Log Sequence Number of the last modification to the page, used for crash recovery | | `checksum` | 4 | CRC32 checksum to detect page corruption | | `min_key`, `max_key` | Variable | Cached minimum and maximum keys in the page, used for fast range scan pruning | | `sibling_page_number` | 4 | Page number of the right sibling leaf node, used for forward range scans |

The remainder of the page stores the node’s keys and child pointers. For internal nodes, the layout is typically an array of `(key, child_pointer)` pairs, sorted in ascending key order. For leaf nodes, the layout is an array of `(key, row_pointer)` pairs, where `row_pointer` is either a physical row ID (for non-clustered indexes) or the full row data (for clustered indexes, as in InnoDB). To avoid scanning the entire page for lookups, most implementations add a *slot directory* at the end of the page: a compact array of offsets to each `(key, pointer)` pair, enabling binary search over the keys in $O(\log k)$ time where $k$ is the number of keys per page.

3.3.2 Overflow and Forwarding Pages

When a row is too large to fit in the leaf node’s page (e.g., a `VARCHAR(65535)` column in PostgreSQL), the B+ tree leaf stores a *forwarding pointer* to an overflow page that holds the full row data. For secondary indexes in InnoDB, if the secondary index key is too large to fit in the 16KB page, InnoDB automatically uses a *prefix compression* strategy: it stores only the minimal prefix of the key that distinguishes it from the previous key in the leaf node, reducing key storage overhead by 30-50% for long string keys in practice.

```mermaid graph TD A[Leaf Page 123] -->|Forwarding Pointer| B[Overflow Page 456] B -->|Points back to| A A -->|Right Sibling Pointer| C[Leaf Page 124] C -->|Forwarding Pointer| D[Overflow Page 789] ``` *Figure 3.4: Overflow and sibling page linkage in InnoDB B+ tree leaf nodes*

3.4 Key Encoding and Ordering Rules

The performance and correctness of a B+ tree depend entirely on consistent key encoding and ordering. Unlike in-memory data structures, B+ tree keys must be stored in a *binary-comparable* format that preserves the logical sort order of the database’s collation. For example, a case-insensitive collation for English text requires encoding keys in a normalized case (e.g., all lowercase) before storage, so that binary comparison of encoded keys matches the logical sort order.

3.4.1 Fixed-Length vs. Variable-Length Keys

Fixed-length keys (e.g., 4-byte integers, 16-byte UUIDs) are trivial to encode and compare, with a constant comparison cost of $O(1)$. Variable-length keys (e.g., strings, binary blobs) require more careful handling: 1. Prefix truncation: For