Course contentsShow
← Computer Science
Lesson 1677 of 2,87238. Database Transactions and IndexingFree lesson

B-Tree Structure and Properties

Node structure, order parameter, key/pointer organization, and minimum degree constraints in B-Trees.

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 n keys has n+1 child 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-1 keys (or 2t-1 keys if using minimum degree)
  • Each non-root node must hold at least ⌈m/2⌉ - 1 keys (or t-1 keys)
  • 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.