B-Tree Nodes — Keys, Values & Children

This is the structural heart of database indexing. A B-tree is what lets real databases find a row among millions in a handful of disk reads, and answer range queries without scanning everything. This lesson builds the node structure itself; later lessons add insertion/splitting and search.

Why not a plain binary search tree?

A binary search tree (BST) gives O(log n) lookups too, in theory — but each node holds only one key and has at most two children, so the tree gets tall. On disk, every level of tree depth you descend is (conceptually) a separate disk read, and disk reads are slow relative to CPU work. A B-tree trades "one key per node" for "many keys per node," which makes each node fatter but the tree much shorter — fewer levels means fewer reads to reach any key. That's the entire motivation for the shape you're about to build.

Order, keys, and children

A B-tree of order M obeys:

• Each node holds up to M−1 keys, kept sorted.
• Each internal node has up to M children — one more child than it has keys, because children sit between (and around) the keys: child₀ holds keys less than key₀, child₁ holds keys between key₀ and key₁, and so on.
• Leaf nodes hold only keys (and, in a real database, their associated row data) — no children.
• Internal nodes hold keys and child pointers, used purely to route searches to the right subtree.

For this lesson you're building an order-3 tree (sometimes called a 2-3 tree): each node holds 1–2 keys and has 2–3 children if it's internal.

       [10, 20]              <- root: 2 keys, 3 children
      /    |    \
 [1,5]  [12,15]  [25,30]     <- leaves

Here, [1,5] holds keys less than 10, [12,15] holds keys between 10 and 20, and [25,30] holds keys greater than 20 — that ordering invariant is what makes searching the tree correct.

Representing a node

class BTreeNode:
    def __init__(self, leaf=True):
        self.leaf = leaf
        self.keys = []       # sorted list of keys
        self.children = []   # only populated if not a leaf; len(children) == len(keys) + 1

Insertion (in the simplest form, before you need to handle splitting a full node) is: find the correct leaf via the same descend-by-comparison logic as binary search, then insert the key into that leaf's sorted key list at the right position:

def insert_into_leaf(node, key):
    i = 0
    while i < len(node.keys) and node.keys[i] < key:
        i += 1
    node.keys.insert(i, key)

Notice this is exactly the "which half is the target in" comparison from binary search, generalized from 2 children to M children — you're locating where a key belongs among a node's keys the same way you located a target in a sorted array.

Printing level by level

BTREE PRINT asks for a breadth-first (level-order) traversal, printing every node's keys on one line per level:

[10,20]
[1,5] [12,15] [25,30]

The standard technique is a queue-based BFS: start with a queue containing just the root; repeatedly dequeue a whole level's worth of nodes, print each one's keys (space-separated, each bracketed), then enqueue that level's children for the next iteration.

def print_levels(root):
    level = [root]
    while level:
        print(" ".join(f"[{','.join(map(str, n.keys))}]" for n in level))
        level = [c for n in level for c in n.children]

What's deliberately deferred

This lesson does not yet require splitting an overfull node (order-3 means a leaf can only hold 2 keys before it must split into two leaves with a new key promoted to the parent) — that's the subject of the node-splitting lesson to come. For now, focus on getting the node shape, the sorted-insert-into-a-leaf behavior, and the level-order print exactly right, since every later B-tree operation (splitting, range search, deletion) builds directly on this representation.