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

B-trees: split full pages during ordered insertion

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

A B-tree stores several ordered keys per node and routes searches through child ranges. For minimum degree t, every non-root node has between t minus one and two t minus one keys. All leaves have the same depth. Before descending into a full child, insertion can split it and move its median into the parent, so the next descent enters a nonfull node. The example implements unique-key insertion and search in memory with t equal to two. It omits deletion, concurrent page changes, disk persistence, and duplicate-key records; those are separate parts of a storage engine.

Operational case

An inventory index receives bay keys 47, 52, 61, 19, 26, 58, and 83. A page holds at most three keys. As insertions fill pages, a median moves up and two children hold the keys on either side. Searching 58 succeeds; searching 49 fails. Reading every page in order yields 19, 26, 47, 52, 58, 61, 83. The shape may differ with insertion order, but the range boundaries, capacity constraints, and equal leaf depth must remain true. The application should choose page size around its actual storage medium, not this tiny classroom degree.

Working Python program

python
from bisect import bisect_left, bisect_right, insort

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

minimum_degree = 2
root = BayPage()

def contains(page, bay_key):
    position = bisect_left(page.keys, bay_key)
    if position < len(page.keys) and page.keys[position] == bay_key:
        return True
    return False if page.leaf else contains(page.children[position], bay_key)

def split_child(parent, position):
    full = parent.children[position]
    right = BayPage(full.leaf)
    median = full.keys[minimum_degree - 1]
    right.keys = full.keys[minimum_degree:]
    full.keys = full.keys[:minimum_degree - 1]
    if not full.leaf:
        right.children = full.children[minimum_degree:]
        full.children = full.children[:minimum_degree]
    parent.keys.insert(position, median)
    parent.children.insert(position + 1, right)

def insert_nonfull(page, bay_key):
    if page.leaf:
        insort(page.keys, bay_key)
        return
    position = bisect_right(page.keys, bay_key)
    if len(page.children[position].keys) == 2 * minimum_degree - 1:
        split_child(page, position)
        if bay_key > page.keys[position]:
            position += 1
    insert_nonfull(page.children[position], bay_key)

def insert(bay_key):
    global root
    if contains(root, bay_key):
        return
    if len(root.keys) == 2 * minimum_degree - 1:
        parent = BayPage(False)
        parent.children = [root]
        split_child(parent, 0)
        root = parent
    insert_nonfull(root, bay_key)

def ordered(page):
    if page.leaf:
        return page.keys[:]
    result = []
    for position, bay_key in enumerate(page.keys):
        result.extend(ordered(page.children[position]))
        result.append(bay_key)
    result.extend(ordered(page.children[-1]))
    return result

for bay_key in (47, 52, 61, 19, 26, 58, 83):
    insert(bay_key)
print(ordered(root))
print(contains(root, 58), contains(root, 49))

Output

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

Time, space, and tradeoff

A balanced B-tree has O(log_t n) page levels. A search or insertion visits that many nodes; searching and moving keys within a node costs O(t) CPU work in this list-based model, giving O(t log_t n) time in the simple bound. Memory is O(n) keys plus child references. A storage engine often weighs page reads separately from comparisons; this Python model does not simulate I/O, crash recovery, or write-ahead logging. Insertion may allocate a new root, and deleting keys requires borrow or merge logic absent here. Validate minimum occupancy and uniform leaf depth before treating a larger implementation as correct.

Common Mistakes

  • Do not descend into a full child without handling its split under this algorithm.
  • Do not confuse a B-tree node with one binary-tree key.
  • Do not infer disk durability from an in-memory page model.

Connected lessons

Apply it: Project: own a maintenance index and work queue and Index and queue invariants.

data structures
range-query-structures
Storage details