Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

B+ trees: propagate leaf splits through multiple levels

Last updated: 3 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A B+ tree routes search through internal separator keys while storing actual keys in leaves. Leaves remain at one depth and form an ordered chain for range scans. An insertion descends to a leaf, inserts the new key, splits an overfull page, and may propagate a separator split through several parents or create a new root. This in-memory program implements unique integer-key insertion with a three-key page limit; it handles more than one tree level. It omits deletion, page persistence, duplicate-record storage, and concurrent writers. The upper separators direct a key equal to the separator into the right child.

Operational case

An inventory index accepts bay keys 47, 52, 61, 19, 26, 58, 83, 31, 67, and 73. Each leaf holds at most three keys. Inserting enough keys creates more leaves and can split an internal page. A scan follows leaf links to report all ten keys in order. Lookup for 58 succeeds; lookup for 49 fails. The linked scan matters because a range query should not have to ascend to the root for every adjacent key. The tiny capacity makes structural changes visible; a storage engine would choose page size and durability rules for its medium.

Working Python program

python
from bisect import bisect_left, bisect_right


class BayPage:
    def __init__(self, leaf):
        self.leaf = leaf
        self.keys = []
        self.children = []
        self.next_page = None


maximum_keys = 3
bay_root = BayPage(True)


def add_to_page(page, bay_key):
    if page.leaf:
        position = bisect_left(page.keys, bay_key)
        if position < len(page.keys) and page.keys[position] == bay_key:
            return None
        page.keys.insert(position, bay_key)
        if len(page.keys) <= maximum_keys:
            return None
        split_at = (len(page.keys) + 1) // 2
        right = BayPage(True)
        right.keys = page.keys[split_at:]
        page.keys = page.keys[:split_at]
        right.next_page, page.next_page = page.next_page, right
        return right.keys[0], right

    position = bisect_right(page.keys, bay_key)
    split = add_to_page(page.children[position], bay_key)
    if split is None:
        return None
    separator, right_child = split
    page.keys.insert(position, separator)
    page.children.insert(position + 1, right_child)
    if len(page.keys) <= maximum_keys:
        return None
    middle = len(page.keys) // 2
    right = BayPage(False)
    right.keys = page.keys[middle + 1:]
    right.children = page.children[middle + 1:]
    separator = page.keys[middle]
    page.keys = page.keys[:middle]
    page.children = page.children[:middle + 1]
    return separator, right


def insert(root, bay_key):
    split = add_to_page(root, bay_key)
    if split is None:
        return root
    separator, right_child = split
    promoted = BayPage(False)
    promoted.keys = [separator]
    promoted.children = [root, right_child]
    return promoted


def contains(root, bay_key):
    page = root
    while not page.leaf:
        page = page.children[bisect_right(page.keys, bay_key)]
    position = bisect_left(page.keys, bay_key)
    return position < len(page.keys) and page.keys[position] == bay_key


def ordered(root):
    page = root
    while not page.leaf:
        page = page.children[0]
    result = []
    while page is not None:
        result.extend(page.keys)
        page = page.next_page
    return result


for bay_key in (47, 52, 61, 19, 26, 58, 83, 31, 67, 73):
    bay_root = insert(bay_root, bay_key)
print(ordered(bay_root))
print(contains(bay_root, 58), contains(bay_root, 49))

Output

Output
[19, 26, 31, 47, 52, 58, 61, 67, 73, 83]
True False

Time, space, and tradeoff

With capacity c and balanced height h, lookup and insertion visit O(h) pages, where h is O(log_c n) for a properly occupied B+ tree. In this Python model, searching within a page uses logarithmic comparisons but list insertion can shift O(c) references. A split may propagate through O(h) ancestors. The program stores O(n) keys and references and uses O(h) recursion. Range scans cost O(h + k) page and item work to return k adjacent keys under a suitable page layout. This code does not model disk I/O, write-ahead logging, or crash-safe page publication; do not treat an in-memory success as a database guarantee.

Common Mistakes

  • Do not store the only copy of a data key in an internal separator.
  • Do not forget to link a new right leaf into the range-scan chain.
  • Do not stop after a leaf split if the parent is also overfull.

Connected lessons

Apply this mutation in the index mutation project, then check the mutation quiz.

B+ deletion: borrow, merge, and repair separators continues this operation with mutation checks.

data structures
range-query-structures
Storage details