TreesTrees

B-Tree Insertion

A balanced multiway search tree with wide nodes holding many keys, designed to minimize disk or cache-line reads for very large ordered data.

Learn B-Tree →

Keys to insert — Integers inserted one at a time into an empty order-4 B-tree (max 3 keys per node); up to 18

Path from root

1/67An empty B-tree: a single leaf holding no keys. Unlike a BST, a node here stores several keys at once and has one more child than it has keys, so every key acts as a separator between two subtrees.

Node being examinedPath from the rootKey just placed hereOverflowing / split node

PseudocodeLearn B-Tree →

1insert(key):                        # order 4: max 3 keys, 4 children per node
2  node = root
3  while node is not a leaf:
4    descend into the child whose key range contains key
5  insert key into that leaf, keeping its keys sorted
6  while node holds more than 3 keys:            # overflow
7    median = the middle key of node
8    split node into a left half and a right half
9    insert median into the parent as the separator between the halves
10    if node was the root: build a new root holding median   # the tree grows upward here

Variables

height1

nodes1

keys0

Complexity

access O(log n)

search O(log n)

insert O(log n)

delete O(log n)

Speed