B-tree
On the roadmap:Advanced · step 3: Storage engines
A balanced tree with many keys in each node, so finding any key takes only a few steps. Nodes split as they fill and the tree stays level.
In plain words
A sorted index, like the one at the back of a book, organised in levels. Each node holds many keys in order. To find a key you pick the one child that covers it, and repeat. When a node gets too full it splits in two and pushes its middle key up, so the tree stays perfectly level.
Why it matters
Disks and SSDs read in big blocks, so the best index reads as few blocks as it can. A B-tree packs hundreds of keys into each node, so even a billion keys need only a handful of reads. It also keeps keys in order, which makes range queries cheap.
Where you meet it
- Database indexes: the default index type in most relational databases is a B-tree or a close variant
- File systems and storage engines that keep ordered data on disk
- Embedded databases such as SQLite
You will be able to
- Explain why a wide, shallow tree suits disks
- Insert by splitting full nodes and moving the middle key up
- Say how a B+ tree differs and why databases prefer it
In interviews
Comes up in 'how does a database index work?' and 'why is a B-tree better than a binary tree on disk?'.
Practise on the Interview Ready roadmap1Learn the idea first
2See it work before you read the code
3Build it and run the check
What you build
- Nodes holding sorted keys, with a child between each pair
- Searching by choosing the one child that covers the key
- Insert that splits a full node and moves its middle key up
- A tree that grows taller only when the root splits
export type BNode = { keys: number[]; kids: BNode[]; leaf: boolean };
/** A B-tree where every node except the root holds between t - 1 and 2t - 1 keys. Real databases use t in the hundreds so a node fills one disk page. */
export class BTree {
root: BNode = { keys: [], kids: [], leaf: true };
constructor(readonly t = 2) {}
has(key: number): boolean {
let n = this.root;
for (;;) {
let i = 0;
while (i < n.keys.length && key > n.keys[i]) i++;
if (n.keys[i] === key) return true;
if (n.leaf) return false;
n = n.kids[i];
}
}
insert(key: number): void {
if (this.has(key)) return;
const r = this.root;
if (r.keys.length === 2 * this.t - 1) { // a full root: split it first, the tree grows one level taller
const s: BNode = { keys: [], kids: [r], leaf: false };
this.root = s;
this.split(s, 0);
this.insertInto(s, key);
} else this.insertInto(r, key);
}
/** Split the full child kids[i] into two, moving its middle key up into the parent. */
private split(parent: BNode, i: number): void {
const t = this.t, y = parent.kids[i];
const z: BNode = { keys: y.keys.splice(t), kids: y.leaf ? [] : y.kids.splice(t), leaf: y.leaf };
const middle = y.keys.pop()!;
parent.keys.splice(i, 0, middle);
parent.kids.splice(i + 1, 0, z);
}
private insertInto(n: BNode, key: number): void {
let i = 0;
while (i < n.keys.length && key > n.keys[i]) i++;
if (n.leaf) { n.keys.splice(i, 0, key); return; }
if (n.kids[i].keys.length === 2 * this.t - 1) { // split a full child before going down, so a split never has to travel back up
this.split(n, i);
if (key > n.keys[i]) i++;
}
this.insertInto(n.kids[i], key);
}
height(): number { let h = 1, n = this.root; while (!n.leaf) { n = n.kids[0]; h++; } return h; }
/** All keys in order. */
keys(): number[] {
const out: number[] = [];
const walk = (n: BNode) => { n.keys.forEach((k, i) => { if (!n.leaf) walk(n.kids[i]); out.push(k); }); if (!n.leaf) walk(n.kids[n.keys.length]); };
walk(this.root);
return out;
}
}
Rather run it on your own computer?
Save the code as index.ts and the check as check.ts in one folder. The check exits with an error if anything is wrong and prints b-tree ok when everything passes. You need Node.js installed.
mkdir b-tree && cd b-tree
# save index.ts and check.ts in this folder
npx tsx check.tsHow real systems do it
This lab is the core idea in a small form. Here is what production versions add or do differently.
- Most databases use a B+ tree variant: values live only in the leaves and the leaves are linked in order, so a range scan is a simple walk along the bottom.
- A node is sized to a disk page, commonly several kilobytes, so one read brings in hundreds of keys. The lab uses tiny nodes so you can watch every split.
- Real trees let many readers and writers work at once with locks or latch tricks, and log each change to a write-ahead log first.
- Random keys such as UUIDv4 split nodes all over the tree, while ever-growing keys such as time-ordered ids fill the right-hand edge neatly.
Ways to index data
| Lookup | Range queries | Writes | Pick it when | |
|---|---|---|---|---|
| B-tree or B+ tree | A few page reads | Excellent: keys are in order | Moderate: pages change in place and sometimes split | You want a general-purpose index |
| Hash index | One read | Not supported | Fast | You only ever look up exact keys |
| LSM tree | May check several files | Good | Very fast: sequential writes | The data is write-heavy |
| Binary search tree in memory | About log2 of n steps | Good | Fast in memory | The data fits in RAM, not on disk |
| Sorted array | Binary search | Excellent | Slow: items shift | The data is read-only |
What it cannot do
Writes change pages in place
An insert can rewrite a page and a split rewrites several, so heavy random writes cost more than in an LSM tree.
This lab has no delete
Real trees must merge or borrow when a node gets too empty.
Random keys fragment it
Keys inserted in random order leave nodes part full and spread writes over the whole tree.
A node should fit a page
The benefit depends on matching the node size to the storage block.
4Now extend it
Each one makes your version closer to what real systems do. Pick one and make the check cover it.
- Add delete, which merges or borrows from a neighbour when a node gets too empty
- Turn it into a B+ tree: keep values only in the leaves and link the leaves for range scans
- Pick the order so a node fills one disk page and measure the height for a million keys