B-Tree Nodes: Shape and Invariants

After this lesson your program can load a B-tree written as text, print it level by level, and check it against the rules that make a B-tree a B-tree. Search, insert and delete in the next lessons all assume these rules hold; here you learn what they are by testing for them.

Why not a binary tree

A binary search tree holds one key per node, so a million keys take about 20 levels. On disk each level is a separate page read. A B-tree packs many keys into one node (sized to a page), so a million keys fit in 3 or 4 levels: three page reads instead of twenty.

The shape

A B-tree of order m obeys these rules:

          [10, 20]               keys < 10  |  between 10 and 20  |  > 20
         /    |    \
    [1, 5] [12, 15] [25, 30]

The separator rule is inherited downward: a key deep in the tree must respect every ancestor's bounds, not only its parent's.

Writing a tree as text

For tests, a tree is written with parentheses. A leaf lists its keys; an internal node alternates child, key, child, key, ..., child:

((1 5) 10 (12 15) 20 (25 30))        the tree drawn above
(1 3 5)                              a single leaf
()                                   an empty tree

BTREE LOAD <text> builds the tree. A node written as keys only is a leaf. Otherwise the items must alternate node, key, node, ..., node, so (1 (2) 3) and ((1) (2)) have the wrong shape (ERR bad tree: shape). Text that is not a tree at all (unbalanced parentheses, a word that is not an integer, characters left over after the closing parenthesis) is ERR bad tree: syntax. Loading is all-or-nothing: after a failed LOAD the previous tree is still there.

LOAD accepts trees that break the rules above; that is the point, because CHECK has to find the breakage.

Commands

• BTREE NEW <m> starts an empty tree of order m (3 to 16), OK; otherwise ERR order must be 3 to 16. All other commands before the first NEW print ERR no tree.
• BTREE PRINT: one line per level, the root first. A node prints as [k1,k2] and nodes on a level are separated by a space. An empty tree prints (empty).
• BTREE HEIGHT: the number of levels (0 when empty). BTREE STATS: nodes=N keys=K height=H.
• BTREE CHECK: VALID, or INVALID <reason> for the first problem found by a depth-first walk, children left to right. At each node, in this order: keys not strictly increasing (keys not sorted in [..]), more than m-1 keys (too many keys in [..]), fewer than the minimum and not the root (too few keys in [..]), then each key outside its allowed open interval (key K out of range in [..]). Only if the whole walk found nothing: leaves at different depths (leaves at different depths).

Traversal by level

PRINT is breadth-first: start with a list holding the root; print the whole list on one line; the next list is the children of everyone in this one; stop when it is empty. Do not recurse for this; the level structure is the point.

Common mistakes

• Bounds from the parent only. A key in a grandchild must also respect the grandparent's separators; pass the interval down the walk.
• Closed intervals. A child key equal to a separator is out of range, because keys are unique.
• Checking the root against the minimum. The root is exempt.
• Reporting depth problems too early. A different-depth leaf is only reported if no node-level rule fails anywhere.

Your exercise

The starter has the node arena, the commands and the dispatcher. You implement load_tree, print_tree and check_tree. The mistake to avoid: checking each node only against its parent's keys.