A B-tree is a self-balancing search tree where each node holds many keys and has many children — designed to minimize disk reads. It's the structure behind virtually every relational database index (PostgreSQL, MySQL/InnoDB, SQLite) and most filesystems.
| Average | Worst | Space | ||||||
|---|---|---|---|---|---|---|---|---|
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | Worst |
Θ(log n) |
Θ(log n) |
Θ(log n) |
Θ(log n) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(n) |
Each node holds up to 2t−1 keys and 2t children, kept sorted. Search: scan keys in the node, descend into the matching child. Insert: descend; if the target leaf is full, split it and push the median key up. Delete: similar, with merging or borrowing when nodes underfill. Branching factor t is tuned to fit one disk block — typical values are 100s to 1000s.
class BTreeNode:
def __init__(self, t, leaf=False):
self.t = t # minimum degree
self.leaf = leaf
self.keys = []
self.children = []
class BTree:
def __init__(self, t=3):
self.t = t
self.root = BTreeNode(t, leaf=True)
def search(self, key, node=None): # O(log n)
node = node or self.root
i = 0
while i < len(node.keys) and key > node.keys[i]:
i += 1
if i < len(node.keys) and key == node.keys[i]:
return (node, i)
if node.leaf:
return None
return self.search(key, node.children[i])
def insert(self, key): # O(log n)
root = self.root
if len(root.keys) == 2 * self.t - 1:
new = BTreeNode(self.t, leaf=False)
new.children.append(root)
self._split(new, 0)
self.root = new
self._insert_nonfull(new, key)
else:
self._insert_nonfull(root, key)
def _split(self, parent, i):
t = self.t
full = parent.children[i]
new = BTreeNode(t, leaf=full.leaf)
new.keys = full.keys[t:]
if not full.leaf:
new.children = full.children[t:]
full.children = full.children[:t]
parent.keys.insert(i, full.keys[t - 1])
parent.children.insert(i + 1, new)
full.keys = full.keys[:t - 1]
def _insert_nonfull(self, node, key):
i = len(node.keys) - 1
if node.leaf:
while i >= 0 and key < node.keys[i]:
i -= 1
node.keys.insert(i + 1, key)
else:
while i >= 0 and key < node.keys[i]:
i -= 1
i += 1
if len(node.children[i].keys) == 2 * self.t - 1:
self._split(node, i)
if key > node.keys[i]:
i += 1
self._insert_nonfull(node.children[i], key)
bt = BTree(t=3)
for k in [10, 20, 5, 6, 12, 30, 7, 17]:
bt.insert(k)
print(bt.search(12) is not None) # TrueA B-tree generalises a binary search tree so that each node holds many sorted keys and has one more child than it has keys. The keys inside a node act as separators: everything in the child to the left of key 20 is smaller than 20, everything between 20 and 40 lives in the middle child, and so on. With minimum degree t, every node except the root holds between t−1 and 2t−1 keys. That lower bound keeps nodes at least half full, and it guarantees the height is at most about logt(n), so a tree with a branching factor in the hundreds reaches billions of keys in four or five levels.
Unlike AVL or red-black trees, a B-tree never becomes unbalanced in depth: it grows upward by splitting the root, not downward by adding leaves, so every leaf is always at the same depth.
Insertion always starts at a leaf. If the leaf has room, the key is placed in sorted position and the job is done. If it is full, the leaf is split around its median: the lower half stays, the upper half becomes a new sibling, and the median is pushed into the parent as a new separator. If the parent was also full, it splits too, and the cascade can reach the root; splitting the root creates a new root and is the only way the tree gains height. The standard CLRS implementation splits full nodes pre-emptively on the way down, so insertion is a single top-down pass with no backtracking.
Deletion is the mirror image. When removing a key would leave a node with fewer than t−1 keys, it first borrows a key from a sibling through the parent (a rotation) or, if both siblings are minimal, merges with a sibling and pulls the separator down from the parent.
tree = BTree(t=2)
for k in [10, 20, 5, 6, 12, 30, 7, 17]:
tree.insert(k)
def show(node, depth=0):
print(" " * depth + str(node.keys))
for child in node.children:
show(child, depth + 1)
show(tree.root)
print(tree.search(12) is not None) # True
print(tree.search(99)) # NonePrinting the tree level by level after each insert is the quickest way to see splits happen. With t = 2, each node holds at most three keys, so splits occur frequently and the tree is easy to inspect; real systems use much larger nodes.
| Structure | Where data lives | Strength | Typical use |
|---|---|---|---|
| B-tree | Keys and values in every node | Can stop early at an internal node | Filesystems, some embedded stores |
| B+ tree | Values only in leaves; leaves linked | Fast range scans, denser internal nodes | InnoDB, PostgreSQL btree indexes, SQLite |
| LSM tree | Sorted runs on disk, merged in background | High write throughput | RocksDB, Cassandra, BadgerDB |
| Red-black / AVL | One key per node in memory | Simple, low constant factors in RAM | In-memory ordered maps |
The B-tree family wins whenever reading a node is expensive relative to searching inside it, which is the case for disks and SSDs and even for CPU caches. One node is sized to one page (often 4 to 16 KB), so each level of descent costs one I/O, and binary search within the page is cheap. LSM trees trade some read cost for much cheaper writes by avoiding in-place updates.