B-Trees and B+ Trees

A static multilevel index from Indexing must be rebuilt as the file grows. B-trees and B+ trees are multilevel indexes that stay balanced under inserts and deletes: every leaf is at the same depth, and every node except the root is at least half full. One node is one disk block, so the number of levels (edge height plus 1) is the number of index block accesses for a search.

The standard calculations are the order of a node from the block, key and pointer sizes, the minimum and maximum number of keys or levels, and the tree after a sequence of insertions or deletions.

Order. The order $p$ of a node is its maximum number of child pointers; a node then holds at most $p - 1$ keys. This is the convention of Elmasri and Navathe ($p$) and of Korth, Silberschatz and Sudarshan ($n$). Other sources define order as the maximum number of keys, or use a minimum degree $t$; read the question's definition before computing.

B-tree of order $p$.

B+ tree of order $p$ (internal) and $p_{\text{leaf}}$ (leaf).

Search. From the root, follow the pointer between the two keys that bracket the search key (in a B+ tree, go right on equality, since keys equal to a separator are stored in its right subtree). A B-tree search may stop at an internal node; a B+ tree search always reaches a leaf. Cost: one block per level, plus one data block.

Range search in a B+ tree: find the first key, then walk the leaf chain. A B-tree has no leaf chain and needs an in-order traversal.

Insertion into a B+ tree (the convention used in the traces and in the checks):

In a B-tree a full node splits around its median key, which moves up together with its data pointer; no key is copied. Some books put the extra key in the right half instead of the left; both give valid trees, so a problem that wants one exact tree must fix the rule.

Deletion removes the key from its leaf; if the leaf falls below the minimum it borrows from a sibling (redistribution) or merges with it, and the parent loses a separator, which can propagate up and shrink the root. One fixed rule is used, since books differ:

Order from sizes. Block size $B$, key $V$, block (tree) pointer $P$, record pointer $P_r$:

Take the largest integer satisfying each. A B+ internal node has no record pointers, so its order is larger than the B-tree order for the same block: the larger internal fan-out can reduce the number of levels, but need not do so in every instance.

Height bounds for a B+ tree with $N$ keys and $h$ levels (the root is level 1, leaves are level $h$, $h \ge 2$):

The minimum uses a root with 2 children, minimum fan-out below it, and minimum leaves. So $N$ keys need at least the smallest $h$ with $p^{h-1} p_{\text{leaf}} \ge N$ levels and at most the largest $h$ whose minimum does not exceed $N$.

B-tree maximum. A B-tree of order $p$ and $h$ levels holds at most $(p - 1)(1 + p + \cdots + p^{h-1}) = p^h - 1$ keys.

B-tree minimum. Let $k = \lceil p/2 \rceil$. The sparsest tree has a root with 1 key and 2 children, and every other internal node with $k$ children and $k-1$ keys, and every leaf with $k-1$ keys. Level $i \ge 2$ then has $2k^{i-2}$ nodes, so

Unlike the B+ minimum, every level contributes keys, because B-tree internal nodes hold keys of their own.

Example 1: orders. $B = 1024$, $V = 10$, $P = 8$, $P_r = 8$.

Example 2: levels for one million keys. With $p = 57$, $p_{\text{leaf}} = 56$ and $N = 1000000$:

Example 3: inserting into a B+ tree of order 4 ($p = 4$, $p_{\text{leaf}} = 3$: at most 3 keys per node). Insert 20, 40, 10, 30, 15, 35, 7, 26, 18, 22, 5:

The tree is now root $(15, 20, 30)$ over leaves $(5, 7, 10)$, $(15, 18)$, $(20, 22, 26)$, $(30, 35, 40)$.

Example 4: a split that reaches the root (Figure 2). Insert 42 into that tree. The leaf $(30, 35, 40, 42)$ splits into $(30, 35)$ and $(40, 42)$ and copies 40 up. The root becomes $(15, 20, 30, 40)$, four keys, so it splits: $(15, 20)$ stays left, 30 moves up into a new root, $(40)$ goes right. The tree now has 3 levels: root $(30)$, internal nodes $(15, 20)$ and $(40)$, leaves $(5, 7, 10)$, $(15, 18)$, $(20, 22, 26)$, $(30, 35)$, $(40, 42)$.

Continuing with 13, 46 and 27 gives the tree of Figure 1: 13 splits $(5, 7, 10, 13)$ and copies 10 up; 46 fits; 27 splits $(20, 22, 26, 27)$, copies 26 up, and the internal node $(10, 15, 20, 26)$ splits with 20 moving up to the root.

Example 5: B-tree insertion. B-tree of order 5 (at most 4 keys per node), inserting 10, 20, ..., 90 in order:

Unlike a B+ tree, 30 and 60 are stored only in the root; no leaf repeats them. Here the sorted input leaves every node except the rightmost at the minimum of $\lceil 5/2 \rceil - 1 = 2$ keys.

Example 6: B+ deletion with the rule above. Start from the tree of Figure 1 (order 4: leaves need at least 2 keys, internal nodes at least 2 children). Delete 30, then 22, then 42.

The tree keeps 3 levels throughout. The sibling rule matters: with the right sibling tried first, step 2 merges the short internal node with $(42)$ instead, pulling 30 down, and gives root $(20)$ over $(10, 15)$ and $(30, 42)$, a different valid tree. (After step 3 the two rules happen to meet again.) A question that wants one exact tree must state the rule.

Common misconceptions.