B-Tree
A binary search tree reads one key per step, which is fine in memory and terrible on disk, where every read fetches a whole block. A B-tree puts as many keys in a node as fit in a block and keeps them in order, so one read narrows the search by hundreds of ways at once. Growth is by splitting: every key is inserted into a leaf, a node that overflows splits around its middle key and pushes that key up, and only when the root itself splits does the tree get taller, which is why every leaf is always at the same depth. The 2-3 tree and the 2-3-4 tree are the same rules with two or three keys per node, and the B+ tree is the variant databases prefer: every key lives in a leaf and the leaves are chained, so a range scan is one walk along the bottom.
Insert 50, 20, 70, 10, 30, 60, 80, 40, 90, 25 into an empty 2-3-4 tree. A node holds up to 3 keys in order and one more child than it has keys; every key goes into a leaf, and a node that ends up with 4 keys splits in two around its middle key, which moves up to the parent. All leaves stay at the same depth, so the tree grows only when the root itself splits.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 9, with their answers.
10 20 50 70 overflows. Which key goes up?
Answer: 50. The middle key: it separates the two halves and becomes the new boundary in the parent.
Which leaf receives 30?
Answer: 10 20. At every node, follow the child that sits between the two keys surrounding 30.
Which leaf receives 60?
Answer: 70. At every node, follow the child that sits between the two keys surrounding 60.
Which leaf receives 80?
Answer: 60 70. At every node, follow the child that sits between the two keys surrounding 80.
Which leaf receives 40?
Answer: 10 20 30. At every node, follow the child that sits between the two keys surrounding 40.
10 20 30 40 overflows. Which key goes up?
Answer: 30. The middle key: it separates the two halves and becomes the new boundary in the parent.
Which leaf receives 90?
Answer: 60 70 80. At every node, follow the child that sits between the two keys surrounding 90.
60 70 80 90 overflows. Which key goes up?
Answer: 80. The middle key: it separates the two halves and becomes the new boundary in the parent.
Which leaf receives 25?
Answer: 10 20. At every node, follow the child that sits between the two keys surrounding 25.
How it runs, step by step
Insert 50, 20, 70, 10, 30, 60, 80, 40, 90, 25 into an empty 2-3-4 tree. A node holds up to 3 keys in order and one more child than it has keys; every key goes into a leaf, and a node that ends up with 4 keys splits in two around its middle key, which moves up to the parent. All leaves stay at the same depth, so the tree grows only when the root itself splits.
Inserting 10 keys into a 2-3-4 tree.
Insert 50. The root is a leaf, so the key goes straight in: 50.
Insert 50 into leaf 50.
Insert 20. The root is a leaf, so the key goes straight in: 20 50.
Insert 20 into leaf 20 50.
Insert 70. The root is a leaf, so the key goes straight in: 20 50 70.
Insert 70 into leaf 20 50 70.
Insert 10. The root is a leaf, so the key goes straight in: 10 20 50 70. That is 4 keys, one too many.
Insert 10 into leaf 10 20 50 70.
10 20 50 70 has 4 keys and the limit is 3, so it splits. The middle key, 50, moves up to the parent; the keys below it form the left node and the keys above it the right node.
Split 10 20 50 70 around 50.
The root split, so there is no parent to receive 50: a new root holding just 50 is created above 10 20 and 70. This is the only way the tree gets taller, and every leaf moved down together, so they are still all at depth 2.
New root 50; height 2.
Insert 30. From the root, at each node take the child between the keys that surround 30, down to the leaf 10 20, and slot it in order: 10 20 30.
Insert 30 into leaf 10 20 30.
Insert 60. From the root, at each node take the child between the keys that surround 60, down to the leaf 70, and slot it in order: 60 70.
Insert 60 into leaf 60 70.
Insert 80. From the root, at each node take the child between the keys that surround 80, down to the leaf 60 70, and slot it in order: 60 70 80.
Insert 80 into leaf 60 70 80.
Insert 40. From the root, at each node take the child between the keys that surround 40, down to the leaf 10 20 30, and slot it in order: 10 20 30 40. That is 4 keys, one too many.
Insert 40 into leaf 10 20 30 40.
10 20 30 40 has 4 keys and the limit is 3, so it splits. The middle key, 30, moves up to the parent; the keys below it form the left node and the keys above it the right node.
Split 10 20 30 40 around 30.
10 20 stays as the left node, 40 is the new right node, and 30 joins the parent, now 30 50, between them.
Split done; parent is 30 50.
Insert 90. From the root, at each node take the child between the keys that surround 90, down to the leaf 60 70 80, and slot it in order: 60 70 80 90. That is 4 keys, one too many.
Insert 90 into leaf 60 70 80 90.
60 70 80 90 has 4 keys and the limit is 3, so it splits. The middle key, 80, moves up to the parent; the keys below it form the left node and the keys above it the right node.
Split 60 70 80 90 around 80.
60 70 stays as the left node, 90 is the new right node, and 80 joins the parent, now 30 50 80, between them.
Split done; parent is 30 50 80.
Insert 25. From the root, at each node take the child between the keys that surround 25, down to the leaf 10 20, and slot it in order: 10 20 25.
Insert 25 into leaf 10 20 25.
10 keys in 5 nodes, height 2, after 3 splits. Every leaf is at the same depth, which is the guarantee: a lookup reads one node per level, and with hundreds of keys per node a real B-tree holds millions of keys at height three, which is why databases and file systems use it. The 2-3 and 2-3-4 trees are the same structure at the smallest sizes, and a 2-3-4 tree is a red-black tree drawn differently.
Height 2 after 3 splits.
Remember
- Keys go into leaves; a node with one key too many splits around its middle key, which moves up.
- The tree only grows when the root splits, so every leaf is at the same depth.
- 2-3 and 2-3-4 trees are B-trees with 2 or 3 keys per node; B+ keeps all keys in chained leaves.
Topics covered
Where this is used
DatabasesPostgreSQL indexes
CREATE INDEX with no type named builds a B-tree, and one node is one 8 KB page. A page that holds hundreds of keys puts an index over a hundred million rows three or four levels deep, so locating a row is three or four page reads, and the top levels stay in the buffer cache so most of those reads never touch the disk. Each leaf page also carries a pointer to its right-hand neighbour, which is what lets a scan started by BETWEEN or ORDER BY keep going sideways, and what lets it finish correctly when another session splits a page underneath it mid-scan.
EmbeddedSQLite's file format
A SQLite database file is nothing but B-trees: one per table, one per index, all assembled from fixed-size pages, with interior pages holding separators and child pointers and leaf pages holding the rows. The layout is pinned down byte by byte in the file format spec, so the same file opens unchanged on a phone, a laptop and a server. Setting the page size is setting the node size, and therefore the fanout and the depth.
FilesystemsFilesystem metadata
Btrfs keeps directory entries, extent maps and free space in B-trees, and XFS and NTFS index directories the same way. A directory lookup has to stay fast when the directory holds a million names, and scanning directory blocks in order does not, while the tree turns it into a couple of block reads. Sorted keys also let the filesystem answer "what comes after this entry" directly, which is how a large directory is paged through rather than read whole.
DatabasesInnoDB clustered indexes
In MySQL's InnoDB engine the table itself is a B+ tree keyed by the primary key, with the entire row stored in the leaf, and every secondary index stores that primary key instead of a row address. This is why the choice of primary key changes write throughput: an increasing key appends to the rightmost leaf page over and over, while a random UUID lands on a different page every time and splits pages all across the tree.
Why it works this way
Why a bigger node stops paying off past the block size
Depth is the log of n to the base of the fanout, so the return on a wider node falls away fast: at a billion keys, 300 keys per node gives a depth of about 3.6 and 600 gives about 3.2, which almost never removes a read. The costs do not fall away. Every read transfers twice the bytes, every split rewrites twice as much, and a node that spans two blocks turns one read into two, so the useful maximum is the largest node that still fits in a single block. Search inside that node is not the constraint: once the block is in memory, scanning or binary-searching a few hundred keys costs far less than the read that fetched them.
Why split at the middle key and not somewhere else
Splitting down the middle leaves both halves at least half full, and that floor on occupancy is what bounds the depth: if nodes were allowed to drift towards empty the fanout would fall and the log would go with it. A lopsided split that peels off a single key is cheaper right now and destroys the guarantee later. The middle key is the one that moves up because the split takes it out of both halves, and it is the key that separates them: greater than everything on the left, smaller than everything on the right.
'Order' counts different things in different books
Knuth's order m is the maximum number of children, so a 2-3-4 tree is a B-tree of order 4. CLRS instead uses a minimum degree t, where every node other than the root holds between t - 1 and 2t - 1 keys, and that same 2-3-4 tree is t = 2. Before comparing two descriptions, check whether the number counts keys or children and whether it is a floor or a ceiling, otherwise the stated bounds will look like they contradict each other.
Deleting is the hard half, and real systems often skip it
Insertion only ever splits, but deletion has to restore the half-full floor: borrow a key from a sibling, or merge with a sibling and pull the separator down from the parent, which can leave the parent under-full and cascade all the way to the root. Merging means holding locks on two siblings and their parent at once, so many storage engines decline to do it. They mark the entry dead, leave the page under-occupied and let a background pass reclaim it. PostgreSQL never merges two under-full B-tree pages: VACUUM clears the dead entries and puts a page back on the free list once it is completely empty, so after a bulk delete the index file keeps its size and only a REINDEX packs it down again.
Read more
- B-treeWikipedia
- B+ treeWikipedia
- B-Tree indexesPostgreSQL
- Database file format: B-tree pagesSQLite
- B-tree visualisedUSF