B-Trees for Database Indexing: Structure, Properties, and Operations

A keyword B-tree is a self-balancing search tree designed to keep height small by allowing each node to hold multiple keys and many child pointers. This is especially effective for database indexing because databases often measure cost in expensive storage accesses (e.g., disk/page reads), not in raw in-memory comparisons.2

A helpful mental model is: a B-tree generalizes a BST by replacing each single-key node with a “page-sized” node containing many sorted keys. The keys in a node act as separators that route search to the correct child subtree.

Key terms:

• Order
• Minimum degree t
• Height h
• Fanout
• Separator key

Structure of a B-tree node

A typical B-tree node stores:

• Several keyword keys in ascending order.
• Pointers to children (subtrees). For a node with $k$ keys, there are $k+1$ child pointers (for internal nodes). This is the “keys separate ranges” invariant.

Internal-node routing rule (range separation):

• All keys in the leftmost child subtree are less than the first key.
• Between key $k_i$ and $k_{i+1}$, the corresponding middle child subtree contains keys in that interval.
• All keys in the rightmost child subtree are greater than the last key.

A B-tree is also height-balanced: all leaves appear at the same level.

Mermaid view of sorted keys separating ranges:

Order (and equivalent “minimum degree” form)

Different textbooks define “order” slightly differently. A common definition (Knuth) uses:

• A B-tree of order $m$ has at most $m$ children per node.
• A non-root/non-leaf node has at least $\lceil m/2\rceil$ children.

Wikipedia also highlights terminology ambiguity and explains that “order” can be defined as max children (Knuth) to avoid uncertainty.

In the “minimum degree” parameterization (often used in CLRS-style treatments):

• Each node other than the root has at least $t-1$ keys.
• Each node has at most $2t-1$ keys.
• Root has special-case bounds.

Key terms:

• Root special case
• Underflow
• Overflow
• Split

Core B-tree properties (what makes it “correct” and balanced)

A B-tree maintains these invariants:

1. Sorted keys within each node and range separation between children.
2. Leaf level uniformity: all leaves are on the same depth.
3. Capacity bounds based on the order/min-degree parameter:
   • at most $m$ children (Knuth order definition), with corresponding max keys per node.
   • non-root nodes have a minimum number of children/keys.
4. The root is either a leaf or has at least two children.
5. For any internal node: if it has $k$ children then it has $k-1$ keys (separators).

A compact invariant statement:

• If a node has children $C_1, C_2, \dots, C_{k}$ and keys $x_1, \dots, x_{k-1}$, then:
  • every key in $C_1$ is $< x_1$
  • every key in $C_i$ (for $1<i<k$) is in $(x_{i-1}, x_i)$
  • every key in $C_k$ is $> x_{k-1}$.

Why B-trees are used for database indexing

The storage-access argument (reducing I/O)

Databases often store index nodes on disk pages. Each page access (cache miss) is far more expensive than comparing a handful of keys in memory. B-trees reduce the number of page accesses because they have high fanout and therefore small height.2

Wikipedia explicitly notes that multiway nodes reduce height and help because for disk-backed storage, fewer reads are needed to navigate to the right block.

Key terms:

• Index
• Page (block)
• Blocking factor

How a B-tree index lookup works conceptually

An index entry is a keyword (and sometimes a pointer/record reference). A search:

1. Starts at the root page.
2. Uses the keys in the current node to decide which child pointer/page to follow.
3. Repeats until reaching a leaf (or the node that may contain the key).

Time is often discussed as $O(\log n)$ comparisons and, more importantly, $O(\log_{b} n)$ page reads where $b$ is an effective branching factor/blocking factor.

B-tree insertion and search: a concrete example

We’ll use a small B-tree of order $m=4$ (so each node can have at most $4$ children, i.e., at most $3$ keys, by the non-leaf relationship “$k$ keys ↔ $k+1$ children”). This matches the “keys = children − 1” view and lets us demonstrate a split clearly.

In this simplified setting:

• Max keys per node = $m-1 = 3$.
• When a node would exceed 3 keys, we keyword split it and push a middle key upward (standard B-tree behavior). (The mechanics align with the usual B-tree insertion approach described in textbook summaries of splits/propagation.)

Insert sequence (keys)

Insert in order: $12,\ 7,\ 20,\ 4,\ 9,\ 3,\ 6$

We’ll track the tree’s shape at key steps.

Tree visualization after all insertions

Key terms:

• Leaf node
• Internal node
• Promoted key

Note: Many databases use B+ trees for indexes, where records are stored at leaves and internal nodes store routing keys only; the routing logic is still B-tree-like. (This section focuses on B-tree mechanics and comparisons.)

B-tree vs Binary Search Tree (BST) for database performance

Structural difference affecting height

• A keyword BST has at most 2 children per node → tends to have larger height (worst case linear, and even with balancing, fewer keys per node).
• A B-tree stores many keys per node and has higher fanout → smaller height and fewer storage-page reads.2

Wikipedia states that because B-trees have more than two children per node, a B-tree index will usually have shorter height than a BST, reducing reads during lookup.

Locality and “node-per-page” viewpoint

For database indexes on disk, performance is dominated by I/O latency. B-trees can pack multiple keys into one page, improving locality: you learn much more about the search interval from each page read than in a BST-like layout where a “node” contains only a couple of pointers/keys.2

Cornell’s lecture notes summarize the locality intuition: binary trees may waste cache lines because each node holds too few elements; B-trees store as many elements as fit in a cache line/page, improving practical performance.

Complexity comparison in practice

Both BST and B-tree are “$O(\log n)$” in ideal balanced cases, but:

• BST page reads depend on tree height with fanout 2, so height is larger.
• B-tree page reads depend on height with fanout $b \gg 2$, so fewer levels are traversed.2

A simple comparative heuristic:

• For B-tree: about $\log_{b}(n)$ page accesses (one per level).
• For BST: about $\log_{2}(n)$ levels (one per node) when disk/page granularity aligns poorly with cache lines.

[CalloutBlock] type: "tip" title: "Rule of thumb for index choice" content: "When search cost is dominated by page reads, prefer high-fanout trees (B/B+ trees) over pointer-heavy binary structures."