---
title: B-Trees
source: 'https://academia.sh/en/courses/data-structures/b-trees'
course: 'Data Structures'
language: en
updated: '2026-08-17T18:07:59+00:00'
license: 'CC BY-SA 4.0'
---

# B-Trees

Design driven by block-based storage, high branching factor, the B+ tree leaf chain, and index usage.

The previous lesson showed that increasing the number of keys per node shortens the
tree. This lesson asks: why stop that number at two or three?

The answer depends on where the data resides. If the data is in memory, the difference
is small — memory access is already cheap. If the data is **on disk**, the situation
changes, and this change has led an entire family of data structures to be designed
around that condition.

## The Block Reality

The memory hierarchy in the How Computers Work course placed persistent storage at
the lowest layer: access is orders of magnitude slower than main memory.

The second, more decisive fact is that persistent storage is read at the **block**
level. Even when only a single byte is requested, the entire block — on the order of
kilobytes — is fetched. What determines the cost, therefore, is not the number of
bytes read but **how many blocks are read**.

This directly changes tree design. In an in-memory tree, the goal is to reduce the
number of comparisons; in a tree on disk, the goal is to reduce **the number of node
visits**. Every node visit is a block read.

The consequence is clear: a node should be large enough to fill a block. If the node
is smaller than the block, part of the fetched block goes to waste; if it is larger, a
single node requires reading multiple blocks. Either way, the number of reads
increases unnecessarily.

## The B-Tree

A **B-tree** is the generalized form of the 2-3 tree. A parameter $t$ (the minimum
degree) is chosen, and the following rules hold:

- Every node except the root holds at least $t-1$ and at most $2t-1$ keys.
- An internal node with $k$ keys has $k+1$ children.
- All leaves are at the same depth.

Setting $t = 2$ yields the 2-3-4 tree; in practice, $t$ is chosen as the largest value
for which the node still fits in a block — on the order of hundreds.

Insertion and deletion follow the same split and merge rules as the previous lesson.
An overflowing node is split in two and the middle key is promoted; a node left
without a key either borrows from a sibling or merges with one.

## The Consequence for Height

A high branching factor reduces height dramatically:

$$
h \approx \log_{b} n
$$

Here $b$ is the average branching factor.

```python
import math

def height(record_count: int, branching: int) -> int:
    """Approximate tree height given a branching factor."""
    return math.ceil(math.log(record_count, branching))


for branching in (2, 3, 100, 500):
    print(branching, height(1_000_000, branching), height(1_000_000_000, branching))

# 2   20 30
# 3   13 19
# 100 3  5
# 500 3  4
```

One million records require twenty node visits in a binary tree, and three in a
B-tree with a branching factor of one hundred. When disk access is the dominant cost,
that is the difference between twenty block reads and three.

Even with a billion records, the depth is five. Once the root and upper levels are
cached in memory, the actual number of disk accesses typically drops to one or two
blocks.

## The B+ Tree

The commonly used variant is the **B+ tree**, and it introduces two changes:

**Records are kept only in the leaves.** Internal nodes carry only routing keys. This
lets internal nodes fit more keys — the branching factor increases and the tree
becomes even shorter.

**Leaves are linked to one another.** Each leaf points to the next, so the leaves
form a sorted linked list.

The second change transforms range queries. A query such as "all records with a
value between 100 and 200" would require repeatedly traversing a plain B-tree. In a
B+ tree, the starting point is searched for once, and the leaf chain is then followed
in order.

This is why nearly all database indexes are B+ trees: both point lookups and range
scans are handled efficiently by the same structure. Index design in the Databases
curriculum builds directly on this structure.

## Comparison

| Metric | Balanced binary tree | B-tree / B+ tree |
|---|---|---|
| Node size | Small (a few links) | Block-sized |
| Height ($10^6$ records) | ~20 | ~3 |
| Suitable environment | Memory | Disk, network, block-based storage |
| Range query | Tree traversal | Leaf chain in a B+ tree |
| Search within a node | None | Binary search or linear scan |

The last row reveals a detail: the total number of **comparisons** in a B-tree is not
lower than in a binary tree. Keys are also searched within each node, and the total
number of comparisons ends up similar. What is gained is not comparisons but the
number of **block reads**.

This is the clearest example that choosing a data structure cannot be separated from
its hardware context: the same algorithm makes a different structure correct in a
different memory hierarchy.

## Search Within a Node

When a node holds hundreds of keys, choosing the correct child within that node
becomes a search problem in its own right. Two options exist, and the choice is
guided by observations from earlier courses.

**Binary search** makes the number of comparisons logarithmic. **Linear scan**
performs more comparisons but reads keys contiguously and takes full advantage of
cache lines.

Since the node fits in a block and the block is already in memory, the difference
between the two methods is small; implementations often combine them — linear search
for small nodes, binary search for large ones.

This detail illustrates, once more, a lesson the course keeps repeating: the number
of comparisons alone is not a sufficient metric; how many times each level of memory
is accessed must also be counted.

## Write Overhead and Durability

The second fact of block-based storage is that writing is more expensive than
reading. Even if a single key in a node changes, the entire block is rewritten.

This gives rise to two design decisions. Keeping nodes **more than half full**
reduces how often splits and merges occur. **Batching** writes lets successive
changes to the same block combine into a single write.

The durability requirement follows from the same fact: if the system halts during a
split, the structure can be left inconsistent. Databases manage this risk by writing
changes to a log first — the data-structure-level counterpart of the write-ahead log
idea from the How Computers Work course.

## Uses

- **Database indexes.** Primary and secondary indexes are kept as B+ trees.
- **File systems.** Storing directory entries and block mappings.
- **Key-value stores.** Implementations that require ordered access.
- **File formats.** Index blocks embedded in large data files.

What these structures share is that the memory hierarchy layer they are designed for
is known explicitly; the same tree is built with different parameters for a
different layer.

For write-heavy workloads, an alternative family — log-structured merge trees — may
be preferred: they batch writes and write them to disk sequentially. Comparing the
two families is a topic of the Databases curriculum.

## Summary

- Persistent storage is read at the block level; the number of blocks read determines
  the cost.
- In a B-tree, node size is matched to the block; the branching factor reaches the
  order of hundreds.
- Height is proportional to $\log_b n$; three node visits suffice for a million
  records.
- The rules are the generalized form of the 2-3 tree: splitting, promotion,
  borrowing, and merging.
- In a B+ tree, records are kept only in the leaves and the leaves are chained; range
  queries reduce to a sequential scan.
- The gain lies not in the number of comparisons but in the number of block reads.

## Next Step

The trees covered so far preserved full ordering. In some problems, however, only
fast access to the **smallest** (or largest) element is needed; full ordering is an
unnecessary cost. The next lesson covers the heap structure, which works under this
relaxed condition, and the priority queue it implements.