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

B-Tree Definition and Properties

Understand B-tree structure, order, and key properties that maintain balance and enable efficient disk-based operations.

B-Tree Definition and Properties

You'll learn: What B-trees are and the key properties that make them ideal for storing massive datasets on disk.

What is a B-Tree?

A B-tree is a self-balancing search tree designed for systems that read and write large blocks of data, like databases and file systems. Unlike binary trees (which have at most 2 children per node), B-trees allow many keys and children per node, reducing tree height dramatically.

Think of a B-tree node like a filing cabinet drawer that can hold multiple folders (keys) instead of just one. This "wide and shallow" structure minimizes the number of disk accesses needed to find data.

Core Properties

Every B-tree of order m (sometimes called the "degree") follows these rules:

  1. Multiple keys per node: Each internal node contains between ⌈m/2⌉ - 1 and m - 1 keys (except the root)
  2. Sorted keys: Keys within a node are stored in ascending order
  3. Multiple children: A node with k keys has k + 1 children
  4. All leaves at same level: The tree remains perfectly balanced—every path from root to leaf has the same length
  5. Root exception: The root may have as few as 1 key (if it's not a leaf)

Why B-Trees?

B-trees minimize disk I/O by packing many keys into each node (matching disk block sizes). Instead of traversing 20 levels in a binary tree, you might only need 3 levels in a B-tree to search millions of records.

For example, a B-tree of order 100 with height 3 can store over 970,000 keys while requiring only 3 disk reads maximum.

Key Takeaway: B-trees are self-balancing multi-way search trees that keep all leaves at the same depth and pack many keys per node, making them perfect for minimizing disk accesses in database systems.