Skip to content
Tutorials Center
My learning

Topics

Lesson 101 of 225 ยท Trees

B-Trees and B+ Trees

Learn why databases use B-trees and B+ trees: disk pages, order, search, insert with node splits, range scans, and a small B-tree you can run in Python.

Every tree so far assumed that following a pointer is cheap. That is true in memory, but it is false for data stored on a disk or SSD. Storage is read in pages (often 4 to 16 KB), and fetching one page costs thousands of times more than a memory access. A balanced binary tree with a million keys has height about 20, so a lookup could mean 20 separate page reads. That is slow.

The fix is to make each node as big as a page, so one read brings in hundreds of keys. A B-tree is a balanced search tree whose nodes hold many keys and have many children. With 100 or more children per node, a tree with a million keys is only 3 or 4 levels deep. Almost every database index and file system uses a B-tree or its cousin, the B+ tree, and this lesson shows how they work.

The idea: wide nodes, same search logic

A binary search tree node has one key and two children: "less than" and "greater than". A B-tree node has k sorted keys and k + 1 children. The keys act as signposts that split the key space into k + 1 ranges.

TEXT
                    [ 20 | 40 ]
                   /     |     \
       [5 | 10 | 15]  [25 | 30]  [45 | 50 | 60]
         keys < 20    20 < keys < 40    keys > 40

To find 30, you read the root, see 20 < 30 < 40, follow the middle child, and find 30 there. Inside one node you can scan or binary-search the sorted keys, which costs only CPU time on data you already loaded.

The rules

A B-tree has a minimum degree t (at least 2), and these rules hold:

  1. Every node holds at most 2t - 1 keys. Every node except the root holds at least t - 1 keys.
  2. An internal node with k keys has exactly k + 1 children.
  3. Keys inside a node are sorted, and they separate the key ranges of the children.
  4. All leaves are at the same depth.

Rule 4 is the heart of it: the tree is perfectly balanced and grows or shrinks at the root, not at the leaves. Rules 1 and 2 guarantee wide nodes, so the height is at most about log_t(n).

Some books use "order" (the maximum number of children) instead of minimum degree, and definitions differ slightly. The ideas are the same. In this lesson t is the minimum degree, so a node has between t and 2t children (except the root).

How much do wide nodes save?

The height is the number of page reads in the worst case. With branching factor b, a tree with n keys needs about log_b(n) levels:

Python Levels needed for a million keys

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A billion keys fit in a tree about 4 levels deep when each node has 500 children. Better still, the root and the next level are small enough to stay cached in memory, so a real lookup is often 1 or 2 disk reads.

Searching

Search looks like a BST search with a little more work per node:

  1. In the current node, find the first key that is greater than or equal to the target (binary search with bisect_left).
  2. If it equals the target, you are done.
  3. If the node is a leaf, the key is absent.
  4. Otherwise go down into the child at that position and repeat.

The cost is O(log n) page reads and O(t log n) comparisons, or O(log n) comparisons if you binary-search inside each node.

Inserting: split instead of grow downward

A BST adds a new leaf under an existing node. A B-tree always inserts the key into a leaf. If the leaf is already full (2t - 1 keys), it must split: the middle key moves up into the parent, and the other keys form two nodes of t - 1 keys each.

TEXT
Insert 25 into a full leaf (t = 2, so the maximum is 3 keys):

before:   parent:  [ 10 ]
                   /    \
                [5]    [20 | 30 | 40]   <- full

split around the middle key (30), then insert 25:

after:    parent:  [ 10 | 30 ]
                   /    |    \
                [5]  [20 | 25]  [40]

The parent might be full too. The standard trick (the one used below) is to split any full node on the way down, before descending into it. Then a parent always has room for the key pushed up by a split. If the root itself is full, the tree gets a new root with one key and two children. That is the only way the height ever increases, and it increases for all leaves at once.

Python A B-tree with insert, search and traces

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the trace. After inserting 10, 20 and 30 the root is a full leaf. Inserting 40 splits it, so a new root appears holding 20, and the tree grows from height 1 to height 2. Keys are added in sorted order, which is a worst case for a BST, yet the leaves of this tree stay at the same depth throughout.

Deleting, briefly

Deletion has more cases but follows the same philosophy: keep every node (except the root) at or above t - 1 keys.

  • Remove from a leaf if it keeps enough keys.
  • If a node would become too small, borrow a key from a sibling through the parent (a rotation), or merge with a sibling, pulling a separator key down from the parent.
  • Deleting from an internal node replaces the key with its in-order predecessor or successor, then deletes that from a leaf.
  • If the root ends up empty, its only child becomes the new root, and the height shrinks by one.

All of these touch O(log n) nodes.

2-3 and 2-3-4 trees: the smallest B-trees

The tiniest useful B-trees have names of their own, and they are the key to understanding red-black trees.

  • A 2-3 tree has 2-nodes (one key, two children) and 3-nodes (two keys, three children). All leaves are on the same level.
  • A 2-3-4 tree also allows 4-nodes (three keys, four children). It is exactly the B-tree with t = 2 that you ran above.

2-3 tree insertion is done bottom-up. Find the leaf where the key belongs and add it there. A 2-node simply becomes a 3-node. If the leaf was already a 3-node, it now briefly holds three keys, so it splits: the middle key goes up to the parent and the other two keys become two separate 2-nodes. The parent might overflow in turn, and the split travels upward, possibly all the way to the root, where a new root is created. A 2-3-4 tree instead splits 4-nodes on the way down, as in the code above, so that it never has to climb back up.

TEXT
2-3 tree, insert 30 into the 3-node [10 | 20]:

[10 | 20] + 30  ->  temporarily [10 | 20 | 30]
split: the middle key 20 moves up, 10 and 30 become two nodes

      [20]
     /    \
  [10]    [30]
Python Bottom-up insertion in a 2-3 tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A red-black tree is a way to store a 2-3-4 tree using ordinary binary nodes. Each node of the 2-3-4 tree becomes a small cluster of red-black nodes:

2-3-4 node Red-black form
2-node [b] One black node
3-node [a | b] A black node with one red child (the other key)
4-node [a | b | c] A black node with two red children

Red links mean "this node belongs to the same 2-3-4 node as its parent". The red-black rules then follow from the B-tree rules: no two reds in a row (a 4-node has at most three keys) and every path has the same number of black nodes (every leaf of a B-tree is at the same depth). A color flip in a red-black tree is the same operation as splitting a 4-node. Learning 2-3-4 trees first makes the rotations and recolorings feel like bookkeeping instead of magic.

Complexity

Operation Page reads Comparisons (with binary search per node)
Search O(log_t n) O(log n)
Insert O(log_t n) O(log n), plus O(t) to shift keys within a node
Delete O(log_t n) O(log n), plus O(t) per node touched
Space O(n) each node is at least about half full

The base of the logarithm is what matters on disk: log_100(n) is about six times smaller than log_2(n).

B+ trees: the version databases use

A B+ tree is a small change with a large payoff:

  1. Only leaves store the data (the rows, or pointers to them). Internal nodes hold only keys used for routing.
  2. Internal nodes have no data to carry, so more keys fit per page and the tree is even shallower.
  3. Every key appears in a leaf, and the leaves are linked in a chain (a linked list in key order).
TEXT
internal:                [ 30 | 60 ]
                       /      |      \
leaves:   [10 20 25] -> [30 40 50] -> [60 70 80 90]
           (linked left to right)

The chain makes range queries cheap. To get everything between 25 and 70, search down the tree once for 25, then walk right along the leaf chain until you pass 70. A plain B-tree would need an in-order traversal that jumps up and down between levels.

Python A tiny B+ tree: leaf chain and range scan

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The range query touched only the leaves that overlap the range, in order, with no backtracking. That is why database engines such as MySQL's InnoDB store tables as B+ trees: WHERE price BETWEEN 10 AND 20 and ORDER BY become cheap scans (see the SQL tutorial on indexes).

B-tree versus B+ tree

B-tree B+ tree
Where data lives in every node only in leaves
Keys in internal nodes each key appears once overall copies used only for routing
Fan-out per page lower higher, so the tree is shallower
Range scan in-order traversal across levels follow the leaf chain
Search cost can stop early at an internal node always reaches a leaf (predictable)

Validating the invariants

A good way to trust a hand-written B-tree is to write a checker that verifies the rules after many inserts: key counts, sorted order, equal leaf depth.

Python Checking the B-tree rules on 500 keys

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Mixing up "order" definitions. Some sources say a B-tree of order m has at most m children; others use minimum degree t. Check which one your source means before comparing formulas.
  • Splitting after the fact. If you wait until a node overflows and then propagate upward, you need parent pointers or recursion on the way back. Splitting full nodes on the way down avoids both.
  • Forgetting that the root is special. It may hold as few as one key.
  • Copying keys into the wrong half. A split leaves t - 1 keys on each side and sends exactly one key up.
  • Assuming B-trees are only for disks. They are also fast in memory because of CPU caches: wide nodes with sorted arrays mean fewer cache misses than pointer-heavy binary trees. Some modern ordered maps use B-trees for that reason.

When to use a B-tree

Use a B-tree or B+ tree when data lives on slow storage, when you need ordered iteration and range queries, or when you want a cache-friendly ordered map. For small in-memory data in Python, a sorted list with bisect or a dictionary is simpler. See hash tables for the unordered alternative, and red-black trees for the binary-tree way of staying balanced.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why are B-trees designed with many keys per node?

    Reading a disk page costs far more than comparing keys in memory, so each node is sized to a page. A large branching factor keeps the height, and so the number of page reads, very small.
  2. 2. How does a B-tree increase its height?

    Inserts always happen in leaves, and splits push keys upward. When the root itself splits, a new root is created, which adds one level above every leaf at once, so all leaves stay at the same depth.
  3. 3. What happens when you insert a key into a full leaf (2t - 1 keys)?

    A split creates two nodes with t - 1 keys each and sends the median key up to the parent as a separator. There is then room in one of the halves for the new key.
  4. 4. Which feature makes range queries efficient in a B+ tree?

    After one root-to-leaf search for the lower bound, you simply follow the next pointers from leaf to leaf until the upper bound. No climbing back up the tree is needed.
  5. 5. A tree has 1,000,000 keys and each node has about 100 children. Roughly how many levels does it have?

    100 cubed is 1,000,000, so about 3 levels (a little more in practice because nodes are not always full). A balanced binary tree would need about 20.

Summary

  • Disk and SSD storage is read in pages, so the cost of a search is the number of pages read. B-trees make nodes page-sized and wide to keep the tree very shallow.
  • A B-tree with minimum degree t has between t - 1 and 2t - 1 keys per node (the root may have fewer), k + 1 children for k keys, and all leaves at the same depth.
  • Search follows the signpost keys down in O(log_t n) page reads.
  • Insert goes into a leaf. Full nodes are split (middle key goes up), and the tree grows only when the root splits.
  • Delete borrows from or merges with siblings to keep nodes from becoming too small.
  • With t = 2 a B-tree is a 2-3-4 tree; 2-3 trees split bottom-up, and red-black trees are 2-3-4 trees stored in binary nodes.
  • A B+ tree keeps data only in linked leaves, which gives higher fan-out and fast range scans. It is the structure behind most database indexes.

Next: Binary Heaps