B-Trees and B+ Trees

14.1From binary trees to m-way search trees

An m-way search tree stores at most m−1 ordered keys per node. A node containing k keys has k+1 child-pointer positions, partitioning the search space into k+1 ordered ranges; some pointers may be null. Here all keys are distinct. A match at an ordinary search-tree node ends the search there.

14.2Indexing and multilevel indexing

See the contents-page illustration

For a data file sorted by a distinct search key, a sparse index can store one entry per data block: the minimum key in that block and a pointer to it. Search chooses the entry with the largest key not exceeding the requested key. If the index spans several pages, build another sparse index over those pages.

The root R has two entries, one for each first-level index page. I1 and I2 each have three entries, one for each data block they cover. These are minimum-key/pointer pairs, so an index page with k entries has k pointers; it is not drawn using the k+1 separator-pointer layout of a B-tree node.

14.3Index-capacity exercises

Sparse-index example

30,000 sorted records; record size 100 B; block size 1024 B; key size 9 B; block pointer 6 B.

Dense multilevel-index example

16,384 records; record size 32 B; block size 1024 B; key size 6 B. Assume both record locators and upper-level block pointers occupy 10 B.

14.4B-tree structure and order

Order from a block-size constraint

Key = 9 B; record pointer = 7 B; child block pointer = 6 B; block = 512 B. An internal node with capacity p child pointers has p−1 key/record-pointer entries.

The maximum order is 24: p=24 occupies exactly 512 B; p=25 would occupy 534 B. Real page overhead can lower this capacity.

Maximum records in four full levels

For order 23, every full node stores 22 keys; each full internal node has 23 children. Counting the root as level 1:

This counts each B-tree key/record-pointer entry once, including entries in internal nodes.

14.5B-tree insertion

Compare with the original insert-55 diagram

Search for the key first. If it is absent, insert its entry into the appropriate leaf in sorted order. An overflowing node has too many keys. Split it around a median, move the median entry to the parent, and reconnect all child pointers. Repeat upward if necessary. Splitting the root creates a new root and adds one level.

insert(tree, entry):
    leaf = search_for_absent_key(tree, entry.key)
    insert_sorted(leaf.entries, entry)
    node = leaf
    while node has more than m - 1 entries:
        parent = node.parent
        left, median_entry, right = split(node)
        if parent is null:
            tree.root = new_root(median_entry, left, right)
            return
        replace node in parent by left, median_entry, right
        node = parent

Order-4 construction exercise

Insert 2, 5, 10, 1, 6, 9, 4, 3, 12, 18, 20, 25. Here use top-down insertion: split any full three-key node before descending into it. This produces the following final tree. A bottom-up split convention can produce a different valid tree.

14.6B-tree deletion

For a leaf key, remove the entry directly. For an internal key, replace its entry with its predecessor (largest key in the left subtree) or successor (smallest key in the right subtree), then remove that replacement at its leaf. The examples below use bottom-up repair after deletion.

With this repair-after-deletion method, merging a one-key-deficient node and a minimum-size sibling fits within the node capacity. For order 5: 1 + 1 + 2 = 4 keys. No overflow split is needed during the repair.

14.7B+ tree structure

Use internal order m and a separate leaf capacity q. Non-root internal nodes have ⌈m/2⌉…m children; with the half-full convention, non-root leaves have ⌈q/2⌉…q entries. An internal root has 2…m children. A leaf root has 0…q entries. All leaves have the same depth.

• With this separator convention, equality follows the pointer to the right of the matching separator. For [30,60], P0 covers k<30, P1 covers 30≤k<60, and P2 covers k≥60.
• Record pointers r5, r10, … appear only in leaves. Internal separator copies do not represent extra data records.
• After finding the first qualifying leaf, a range scan follows next-leaf pointers in order. The final next pointer is null.

B+ insertion and deletion

Insert at a leaf. If a leaf splits, keep all data entries in the two leaves, copy the minimum key of the new right leaf into the parent, and repair the next-leaf links. If an internal node splits, move its separating key up and redistribute child pointers. Splitting can propagate to the root.

Delete at the leaf. Borrow or merge if its occupancy falls below the chosen minimum, update affected separator keys to preserve the routing convention, and repair leaf links after a merge. Repair deficient ancestors as needed; an empty internal root is replaced by its only child.

14.8B+ tree capacity calculations

Key = 9 B; record locator = 7 B; block pointer = 6 B; block size = 512 B. Ignore page overhead and reserve one next-leaf pointer per leaf.

Here leaf capacity q counts data entries, and internal order p counts child pointers. Keeping these quantities separate avoids the ambiguous term “leaf order.”

14.9B-tree versus B+ tree

Both are balanced multiway trees designed to reduce page accesses. B+ trees are particularly useful for ordered scans because the data entries occupy a linked sequence of leaves.

Applications and implementation choices

Database and file-system indexes use B-tree-family structures in several forms. MySQL documents InnoDB’s ordinary clustered and secondary indexes as B-trees. Clustered-index leaves contain row data; secondary-index leaves contain indexed keys and primary-key locators. Spatial indexes use R-trees. Do not infer the exact variant from a product category alone.

LevelDB and RocksDB use log-structured merge-tree designs. They should not be listed as examples of B+ tree storage engines.