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

B+ leaf pages: split full pages and keep range order

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

A B+ tree keeps sorted entries in leaf pages and uses separator keys in internal pages to route searches. A range scan finds its first leaf and continues across ordered leaves. In a real implementation, page capacity, minimum occupancy, split propagation, parent pointers, and storage durability determine correctness. The program here models only a root with leaf pages: it inserts one key into a full leaf, splits that leaf, and adds a separator. It is not a complete B+ tree or a database index. The model isolates the boundary that a parent separator must match the first key of the new right page.

Operational case

A depot index begins with leaves [19, 47] and [52, 61], each limited to two keys. Adding 58 targets the right leaf. That leaf becomes [52, 58, 61], exceeds capacity, and splits into [52] and [58, 61]. The root separators become 52 and 58. A half-open range [47, 61) returns 47, 52, and 58. The example does not cover duplicate keys, deletion, or a root that itself overflows; those are the next design steps before an implementation can serve live records.

Working Python program

python
from bisect import bisect_right, insort

leaf_pages = [[19, 47], [52, 61]]
separators = [52]
page_capacity = 2

def insert_bay(bay_key):
    page_index = bisect_right(separators, bay_key)
    page = leaf_pages[page_index]
    insort(page, bay_key)
    if len(page) > page_capacity:
        split_at = len(page) // 2
        right_page = page[split_at:]
        leaf_pages[page_index] = page[:split_at]
        leaf_pages.insert(page_index + 1, right_page)
        separators.insert(page_index, right_page[0])

insert_bay(58)
range_keys = [bay_key for page in leaf_pages for bay_key in page if 47 <= bay_key < 61]
print(leaf_pages, separators)
print(range_keys)

Output

Output
[[19, 47], [52], [58, 61]] [52, 58]
[47, 52, 58]

Time, space, and tradeoff

Routing among this model's root separators costs O(log p) comparisons for p leaf pages. Python list insertion may shift O(p) leaf references and O(c) keys within a page of capacity c; the demonstration therefore does not have the I/O behavior of a page-oriented B+ tree. A real balanced B+ tree targets O(log fanout n) page visits for search or update plus scan work for returned entries, but split propagation and persistence require a complete implementation. Treat this fragment as an invariant exercise, not a replacement for a database index.

Common Mistakes

  • Do not claim the one-level model handles arbitrary tree height.
  • Do not forget to update the parent separator after splitting a leaf.
  • Do not equate Python list movement with storage-page I/O.

Connected lessons

Apply it: Project: design a versioned warehouse index and Advanced structure contracts.

data structures
range-query-structures
Storage details