B-Tree Structure and Properties
You'll learn: How B-Trees organize keys and pointers within nodes to maintain efficient, balanced indexing.
What Is a B-Tree Node?
A B-Tree is a balanced tree where each node can hold multiple keys and child pointers—not just one like a binary tree. The number of keys a node can hold is controlled by the order parameter (often called m), which defines the tree's "branching factor."
Think of each node as a sorted filing cabinet drawer: it holds multiple labeled dividers (keys) in order, with spaces between them pointing to other drawers (child nodes).
Node Structure
Each B-Tree node contains:
- Keys: Sorted values (e.g., index column values)
- Child pointers: References to subtrees; a node with
nkeys hasn+1child pointers - Metadata: Often a flag indicating whether it's a leaf node
For example, a node might look like: [10 | 20 | 30] with pointers to four children containing values <10, 10-20, 20-30, and >30.
The Order Parameter and Minimum Degree
The order m (or minimum degree t) constrains node capacity:
- Each node holds at most
m-1keys (or2t-1keys if using minimum degree) - Each non-root node must hold at least
⌈m/2⌉ - 1keys (ort-1keys) - This minimum occupancy rule keeps the tree balanced—no node can be mostly empty
Root exception: The root can have as few as one key.
Why This Matters
These constraints guarantee the tree stays balanced—all leaf nodes are at the same depth. When a node overflows (too many keys), it splits; when it underflows (too few), nodes merge or borrow keys. This automatic rebalancing keeps search, insert, and delete operations efficient.
Key Takeaway: B-Tree nodes hold multiple sorted keys with child pointers between them, governed by an order parameter that enforces minimum and maximum occupancy to maintain balance.