B-Tree Nodes — Keys, Values & Children

The B-tree is the most important data structure in database engineering. Nearly every relational database uses B-trees (or the B+ variant) for storing table data and indexes.

What Is a B-Tree?

A B-tree is a self-balancing tree where:

• Every leaf is at the same depth (perfectly balanced)
• Each node can hold multiple keys (not just one like a binary tree)
• Nodes split when they overflow, keeping the tree balanced

Node Structure

A B-tree of order M (also called degree) has these properties:

For order 3 (a "2-3 tree"):

• Each node holds 1-2 keys
• Internal nodes have 2-3 children

Leaf vs Internal Nodes

        [20]              ← Internal node (1 key, 2 children)
       /    \
   [5,10]  [25,30]       ← Leaf nodes (2 keys each, no children)

Internal nodes contain keys that act as "signposts" directing searches:

• Keys less than 20 go left
• Keys >= 20 go right

Leaf nodes contain the actual data (or pointers to data in B+ trees).

Key Ordering

Within each node, keys are always sorted in ascending order. This enables binary search within the node:

Node: [5, 10, 20, 35]
Search for 15:
  Binary search → 15 falls between 10 and 20
  Follow child pointer between keys 10 and 20

B-Tree vs B+ Tree

Most real databases use B+ trees because the leaf-level linked list makes range scans very efficient.

How SQLite Organizes B-Tree Nodes

In SQLite, each node is a page (4096 bytes by default). The page header contains the number of cells, and cells are stored in sorted order by key. We'll build this exact layout in Chapter 4.

Your Task

Implement a B-tree node structure with insert and level-order printing. Start with order 3 — it's the simplest non-trivial case and makes splits easy to visualize.