Course contentsShow
← Computer Science
Lesson 557 of 2,87213. Balanced TreesFree lesson

B-Tree Node Structure

Learn how B-tree nodes store multiple keys and child pointers, and why this design optimizes disk I/O.

B-Tree Node Structure

You'll learn: How B-tree nodes are organized to store multiple keys and child pointers, and why this structure is designed for efficient disk operations.

What Makes B-Tree Nodes Different?

Unlike binary tree nodes that hold one key and two child pointers, a B-tree node is much more capacious. Each node can store multiple keys (sorted in order) and multiple child pointers. Think of a B-tree node like a filing cabinet drawer that holds several folders at once, rather than a single folder.

Anatomy of a B-Tree Node

A B-tree node typically contains:

  • An array of keys (e.g., [10, 20, 30])
  • An array of child pointers (one more pointer than keys)
  • A count of how many keys are currently stored
  • A flag indicating whether it's a leaf node

For example, a node with 3 keys has 4 child pointers:

[pointer₀] [key₁] [pointer₁] [key₂] [pointer₂] [key₃] [pointer₃]

Child pointer i points to subtrees with keys between key i and key i+1.

Why This Design?

B-trees were invented for databases and file systems where data lives on disk. Reading from disk is thousands of times slower than reading from RAM. By packing many keys into one node, a single disk read fetches lots of data at once. This dramatically reduces the number of disk I/O operations needed to find a value.

A node size is typically chosen to match a disk block (e.g., 4KB), maximizing the keys retrieved per read.

Key Takeaway: B-tree nodes store multiple sorted keys and child pointers in a single structure, optimizing disk I/O by minimizing the number of expensive disk reads required for searches and updates.