B-Tree Concept

Every B-tree implementation must uphold a specific set of invariants—properties that remain true before and after every operation. These aren't arbitrary constraints; they're carefully chosen rules that together guarantee the logarithmic height, efficient space utilization, and reliable performance that make B-trees the foundation of modern database indexing.

Understanding these properties deeply is essential because they explain why B-tree algorithms work the way they do. Every split during insertion, every merge during deletion, every rotation during rebalancing—all exist to maintain these invariants.

Before diving into properties, we must address a significant source of confusion: different textbooks and implementations use different terminology. Understanding these conventions is essential for reading any B-tree literature or documentation.

The Two Major Conventions

Convention 1: Maximum Children (Order m)

• Used by Knuth, most database textbooks, and our curriculum
• A B-tree of order m has at most m children per node
• Each node has at most m-1 keys
• Non-root nodes have at least ⌈m/2⌉ children (at least ⌈m/2⌉ - 1 keys)

Convention 2: Minimum Degree (t)

• Used by CLRS (Cormen et al.) and algorithms courses
• Every non-root node has at least t-1 keys and at most 2t-1 keys
• Equivalent to order m = 2t in the first convention
• The root has at least 1 key (can be empty only if tree is empty)

Why the Confusion Exists

Bayer and McCreight's original paper used the maximum children convention. When Cormen et al. wrote their influential algorithms textbook, they chose the minimum degree convention because it simplifies certain proofs. Both are valid; both are widely used.

Practical Note: Database documentation typically uses 'order' loosely to mean 'approximately how many keys/children per node.' For actual implementation, what matters is:

• Block size (how large is each node?)
• Key size and pointer size
• Calculated maximum entries that fit in a block

The theoretical conventions help with analysis; practical implementations derive limits from hardware constraints.

Formal Statement: Every node in a B-tree contains at most m-1 keys and has at most m children.

This is the upper bound property—it limits how full any node can become.

Why This Property Is Essential

1. Disk Block Alignment: Nodes must fit within disk blocks. If nodes could grow unboundedly, we'd need multiple I/O operations per node.

2. Memory Allocation: Fixed maximum size allows predictable memory allocation. The data structure doesn't require dynamic resizing of individual nodes.

3. Efficient In-Node Search: Binary search within a node is O(log m). Unbounded m would degrade in-node search performance.

What Happens at Maximum Capacity

When an insertion would exceed the maximum, the node must split:

1. Create a new sibling node
2. Move half the keys to the sibling
3. Promote the median key to the parent
4. If the parent overflows, recursively split up the tree

This splitting mechanism is how B-trees grow in height—only when the root splits does height increase. This guarantees that height increases are rare and global (all leaves remain at the same level).

The Invariant Maintained:

For all nodes N: keys(N) ≤ m-1 AND children(N) ≤ m

Formal Statement: Every non-root internal node has at least ⌈m/2⌉ children (and therefore at least ⌈m/2⌉ - 1 keys).

This is the lower bound property—it prevents nodes from becoming too sparse.

Why This Property Is Essential

1. Space Efficiency: Guarantees at least 50% utilization. Without this, a malicious sequence of insertions and deletions could create nearly-empty nodes, wasting disk space and increasing tree height.

2. Height Bound: The minimum occupancy directly determines the maximum tree height. More children per node means fewer levels needed.

3. Balanced Structure: Combined with the leaf-level property, minimum occupancy ensures the tree remains balanced regardless of insertion/deletion patterns.

What Happens Below Minimum Capacity

When a deletion would reduce a node below minimum occupancy, one of three things happens:

1. Redistribution (Rotation): If a sibling has extra keys, borrow one through the parent.

Before:  [10 | 20]      After:   [15 | 20]
         /  |  \                 /  |  \
      [5] [15|17] [25]       [5|10] [17] [25]

(Borrow 15 from right sibling; 10 moves down from parent)

2. Merge: If no sibling can spare keys, merge with a sibling, pulling down a parent key.

Before:  [10 | 20 | 30]    After:   [10 | 30]
         /  |  \   \                /  |   \
      [5] [15] [25] [35]       [5] [15|20|25] [35]

(Merge [15] with [25], pull down 20 from parent)

3. Recursive Propagation: If merging causes the parent to underflow, continue up the tree.

The Root Exception

The root is special: it can have as few as 1 key (2 children) or even 0 keys if the tree contains a single node. This exception exists because:

• The tree must start somewhere (single-node trees are valid)
• When the last child of the root merges, the root shrinks, reducing tree height

Formal Statement: A node with k children contains exactly k-1 keys.

This property establishes the structural relationship between keys and child pointers within each node.

The Separator Role of Keys

Keys in a B-tree node serve as separators or fence posts that divide the key space into regions. Think of it like a fence:

       Keys:    [  K₁  |  K₂  |  K₃  ]
                  |      |      |      |
    Children:   C₀     C₁     C₂     C₃
                  ↓      ↓      ↓      ↓
              < K₁   K₁≤x<K₂  K₂≤x<K₃  ≥ K₃

• 3 keys create 4 regions (children)
• k-1 keys create k regions
• Each child pointer leads to a subtree containing keys in that region

Why k-1 Keys for k Children?

Mathematically, if you have k intervals, you need k-1 separators:

• 2 intervals → 1 separator (like binary search)
• 3 intervals → 2 separators
• k intervals → k-1 separators

This is analogous to:

• A road with k segments needs k-1 mile markers
• An array of k sections needs k-1 dividing indices
• A sorted sequence of k teams needs k-1 ranking positions between them

Leaf Node Interpretation

Leaf nodes are slightly different: they have keys but no child pointers (or null child pointers). Some definitions say leaves have k keys and k+1 null pointers; others say leaves simply have k keys.

Conceptually:

• Internal nodes: keys are separators for navigation
• Leaf nodes: keys are the actual data (in classic B-trees) or point to data (in B+-trees)

The Invariant Maintained:

For all non-leaf nodes N: children(N) = keys(N) + 1
For all leaf nodes N: children(N) = 0

Formal Statement: Keys within each node are stored in non-decreasing (sorted) order: K₁ ≤ K₂ ≤ K₃ ≤ ... ≤ Kₖ₋₁.

This property enables efficient in-node search and maintains the global ordering necessary for correct navigation.

Why Sorted Order Matters

1. Binary Search Within Nodes

With sorted keys, finding the appropriate child pointer is O(log k) using binary search:

Node: [5 | 12 | 23 | 47 | 89]

Search for 30:
- Compare with middle (23): 30 > 23 → search right half
- Compare with middle of right (47): 30 < 47 → search left portion
- Position found: between 23 and 47 → follow pointer between them

Total comparisons: O(log k) ≈ O(log m)

2. Sequential Access Support

Sorted order within nodes supports range queries. Once you find the starting point, you scan forward through sorted keys.

Maintaining Sorted Order During Insertion

When inserting a new key into a node, the key must be placed in the correct position to maintain sorted order:

Before: [5 | 12 | 47 | 89]  (inserting 23)

1. Find insertion position: between 12 and 47 (index 2)
2. Shift elements right: [5 | 12 | _ | 47 | 89]
3. Insert key: [5 | 12 | 23 | 47 | 89]

After: [5 | 12 | 23 | 47 | 89] ✓ Sorted order maintained

This shifting operation is O(m) in the worst case but happens in memory after the node is loaded, so it's fast compared to disk I/O.

Duplicate Keys

The 'non-decreasing' allows for duplicate keys in classic B-tree definitions. Different databases handle duplicates differently:

• Allow duplicates with ties: K₁ = K₂ = K₃ is valid
• Unique key with TID: Store (key, tuple_id) pairs to break ties
• Overflow pages: Store duplicate key values in linked overflow structures

The Invariant Maintained:

For all nodes N with keys K₁, K₂, ..., Kₖ:
  K₁ ≤ K₂ ≤ ... ≤ Kₖ

Formal Statement: For a node with keys K₁, K₂, ..., Kₖ₋₁ and children C₀, C₁, ..., Cₖ₋₁:

• All keys in subtree rooted at C₀ are less than K₁
• All keys in subtree rooted at Cᵢ (for 0 < i < k-1) are ≥ Kᵢ and < Kᵢ₊₁
• All keys in subtree rooted at Cₖ₋₁ are ≥ Kₖ₋₁

This property extends the key ordering from within nodes to the entire tree structure. It's the property that makes B-tree search work correctly.

Visual Representation

The Global Ordering Property

Subtree ordering creates a global sorted order across the entire tree. An in-order traversal of a B-tree visits all keys in sorted order:

1. Recursively visit subtree C₀
2. Visit key K₁
3. Recursively visit subtree C₁
4. Visit key K₂
5. ... and so on

This is why B-trees excel at range queries: once you find the starting key, all subsequent keys in range are reachable by forward traversal.

Search Algorithm Correctness

Subtree ordering is what makes B-tree search correct. When searching for key K:

1. Start at root
2. At each node, find position i where Kᵢ₋₁ ≤ K < Kᵢ (or edge cases)
3. Follow child pointer Cᵢ
4. Repeat until finding K or reaching a leaf

The subtree ordering property guarantees that if K exists in the tree, following this algorithm will find it. More importantly, it guarantees that if K is not found by this algorithm, it doesn't exist anywhere in the tree.

Formal Statement: All leaf nodes appear at the same depth (the tree has uniform depth).

This is perhaps the most distinctive property of B-trees compared to other tree structures. While AVL trees and Red-Black trees maintain bounded height difference, B-trees maintain zero height difference—all paths from root to leaf have identical length.

Why Perfect Balance Is Revolutionary

Consider the implications:

How B-trees Maintain Perfect Balance

The key insight is that B-trees grow and shrink at the root, not at the leaves:

Tree Growth (Height Increase):

1. Insertions happen at leaf level
2. If leaf overflows, it splits; median goes to parent
3. If parent overflows, it splits; median goes to grandparent
4. This propagates up to root
5. If root overflows, it splits; a new root is created with one key
6. Result: ALL leaves are now one level deeper

Tree Shrinkage (Height Decrease):

1. Deletions happen at leaf level (after swapping if necessary)
2. If leaf underflows, merge or redistribute
3. Merge propagates up if parent underflows
4. If root has only one child after merge, that child becomes new root
5. Result: ALL leaves are now one level shallower

The Invariant Maintained:

For all leaf nodes L₁, L₂: depth(L₁) = depth(L₂) = h
where h is the tree height

The six properties we've discussed don't exist in isolation—they work together as a cohesive system that guarantees B-tree performance. Let's see how they interact.

The Height Guarantee

Combining minimum occupancy and leaf balance, we can derive the height bound:

• Each internal node has at least ⌈m/2⌉ children
• With n keys, height h satisfies: n + 1 ≤ 2 × (⌈m/2⌉)^h
• Solving: h ≤ log_{⌈m/2⌉}((n+1)/2)
• For large m: h ≈ log_m(n)

The Space Guarantee

Combining all properties:

• Maximum space: n keys stored in at most n + n/(⌈m/2⌉-1) + ... ≈ n × (1 + 2/(m-2)) nodes
• Minimum utilization: ~50% of allocated node space contains data
• Wastage bounded: at most 50% overhead regardless of insertion/deletion pattern

The Time Guarantee

All operations (search, insert, delete):

• Traverse at most h levels: O(log_m n) disk accesses
• At each level, O(log m) comparisons for in-node search
• Total comparisons: O(log_m n × log m) = O(log n)
• Dominant cost: O(log_m n) disk I/O

We've explored each B-tree property in depth. Let's consolidate:

What's Next

With properties understood, the next page examines node structure in detail—how individual B-tree nodes are laid out in memory and on disk, what metadata they contain, and how internal vs. leaf nodes differ in structure and purpose.