Home/Trees/B-tree
Search algorithmsCTRL K

B-tree

· wide nodes · split on the way down
/trees/b-tree
KEYS
0/ 14
stored so far
NODES
1
pages in use
SPLITS
0
full nodes halved
HEIGHT
1
levels, root included
KEY
0
being inserted
current nodesplit halvesreceived a keypath
14 keys · order 4 · seed 7 · 54 steps
step 0 / 53
Keys14
b_tree.ts
1
function insert(tree: BTree, key: number) {
2
  if (tree.root.keys.length === MAX_KEYS) {
3
    const oldRoot = tree.root;
4
    tree.root = { keys: [], children: [oldRoot], leaf: false };
5
    splitChild(tree.root, 0);
6
  }
7
  insertNonFull(tree.root, key);
8
}
9
function insertNonFull(node: BNode, key: number) {
10
  let index = node.keys.length - 1;
11
  if (node.leaf) {
12
    while (index >= 0 && key < node.keys[index]) index--;
13
    node.keys.splice(index + 1, 0, key);
14
    return;
15
  }
16
  while (index >= 0 && key < node.keys[index]) index--;
17
  index++;
18
  if (node.children[index].keys.length === MAX_KEYS) {
19
    splitChild(node, index);
20
    if (key > node.keys[index]) index++;
21
  }
22
  insertNonFull(node.children[index], key);
23
}
CURRENT STEP
line 1

Order 4 B-tree: each node holds 1 to 3 keys. Start with an empty root.

// how it works

Understanding B-tree

B-tree · one disk page per node, every leaf at the same depth
01

The idea

A B-tree keeps many keys per node, sorted, with one child between each pair of neighbouring keys. Every node except the root holds between t − 1 and 2t − 1 keys, and all leaves sit at the same depth, so the tree is always balanced and very shallow: with t = 64 three levels index millions of keys.

Insertion walks down to a leaf and drops the key in its sorted place. To make room ahead of time, any full node met on the way is split: its middle key moves up into the parent and the two halves become separate children. Splitting the root is the only way the tree gets taller, and it grows from the top.

02

The four stages

1
descendpick the child between the neighbouring keys
2
splita full child: middle key moves up
3
insertinto the leaf, in sorted position
4
growa full root splits into a new root
03

Complexity

best
O(log_t n)node visits per operation
average
O(t · log_t n)keys compared inside the nodes
worst
O(t · log_t n)a split at every level
space
O(n)nodes at least half full
04

Versus its siblings

PAGE READS PER LOOKUP · 100 000 000 KEYS
b-tree, t = 512
3
b-tree, t = 2
14
avl
27
red-black
30
bst, random
40
on disk one page read costs more than a thousand comparisons in memory
05

Pseudocode

INSERT(tree, key)
  if the root is full: make a new root above it and SPLIT the old root
  INSERTNONFULL(root, key)
INSERTNONFULL(node, key)
  if node is a leaf: put key in its sorted place
  else: child ← the child between the keys around key
    if child is full: SPLIT it, the middle key moves up; pick the correct half
    INSERTNONFULL(child, key)
06

When to use

Anything on disk or SSD: database indexes, file systems (NTFS, HFS+, ext4 directories, Btrfs), key-value stores.
In memory too, when cache lines matter: a node the size of a cache line beats a pointer-chasing binary tree.
07

Pitfalls

Splitting on the way down keeps one pass but splits nodes that would not have overflowed; the lazy variant splits on the way up instead.
Deletion must merge or borrow to keep nodes at least half full; it is the hard half of the structure.
Picking t: match the node to the page size, not to the key count.
08

History

Rudolf Bayer and Edward McCreight designed the B-tree at Boeing in 1970 for indexes too large for memory; the B has never been officially explained, with Boeing, balanced and Bayer all offered. The B+ tree, which keeps data only in linked leaves, is the form most databases use today.

Back to Trees