AlgoScope

B-Tree

structureadvancedTime O(log n) per operationSpace O(n)

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 15, 3, 27, 8, 40, 12, 33, 19, 45, 5, 22, 38 into an empty B-tree with up to 4 keys per node. A node holds up to 4 keys in order and one more child than it has keys; every key goes into a leaf, and a node that ends up with 5 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.

  1. 3 8 15 27 40 overflows. Which key goes up?

    • 8
    • 15
    • 27

    Answer: 15. The middle key: it separates the two halves and becomes the new boundary in the parent.

  2. Which leaf receives 12?

    • 3 8
    • 27 40

    Answer: 3 8. At every node, follow the child that sits between the two keys surrounding 12.

  3. Which leaf receives 33?

    • 27 40
    • 3 8 12

    Answer: 27 40. At every node, follow the child that sits between the two keys surrounding 33.

  4. Which leaf receives 19?

    • 27 33 40
    • 3 8 12

    Answer: 27 33 40. At every node, follow the child that sits between the two keys surrounding 19.

  5. Which leaf receives 45?

    • 19 27 33 40
    • 3 8 12

    Answer: 19 27 33 40. At every node, follow the child that sits between the two keys surrounding 45.

  6. 19 27 33 40 45 overflows. Which key goes up?

    • 27
    • 33
    • 40

    Answer: 33. The middle key: it separates the two halves and becomes the new boundary in the parent.

  7. Which leaf receives 5?

    • 3 8 12
    • 19 27
    • 40 45

    Answer: 3 8 12. At every node, follow the child that sits between the two keys surrounding 5.

  8. Which leaf receives 22?

    • 19 27
    • 3 5 8 12
    • 40 45

    Answer: 19 27. At every node, follow the child that sits between the two keys surrounding 22.

  9. Which leaf receives 38?

    • 40 45
    • 3 5 8 12
    • 19 22 27

    Answer: 40 45. At every node, follow the child that sits between the two keys surrounding 38.

How it runs, step by step

  1. Insert 15, 3, 27, 8, 40, 12, 33, 19, 45, 5, 22, 38 into an empty B-tree with up to 4 keys per node. A node holds up to 4 keys in order and one more child than it has keys; every key goes into a leaf, and a node that ends up with 5 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 12 keys into a B-tree with up to 4 keys per node.

  2. Insert 15. The root is a leaf, so the key goes straight in: 15.

    Insert 15 into leaf 15.

  3. Insert 3. The root is a leaf, so the key goes straight in: 3 15.

    Insert 3 into leaf 3 15.

  4. Insert 27. The root is a leaf, so the key goes straight in: 3 15 27.

    Insert 27 into leaf 3 15 27.

  5. Insert 8. The root is a leaf, so the key goes straight in: 3 8 15 27.

    Insert 8 into leaf 3 8 15 27.

  6. Insert 40. The root is a leaf, so the key goes straight in: 3 8 15 27 40. That is 5 keys, one too many.

    Insert 40 into leaf 3 8 15 27 40.

  7. 3 8 15 27 40 has 5 keys and the limit is 4, so it splits. The middle key, 15, moves up to the parent; the keys below it form the left node and the keys above it the right node.

    Split 3 8 15 27 40 around 15.

  8. The root split, so there is no parent to receive 15: a new root holding just 15 is created above 3 8 and 27 40. 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 15; height 2.

  9. Insert 12. From the root, at each node take the child between the keys that surround 12, down to the leaf 3 8, and slot it in order: 3 8 12.

    Insert 12 into leaf 3 8 12.

  10. Insert 33. From the root, at each node take the child between the keys that surround 33, down to the leaf 27 40, and slot it in order: 27 33 40.

    Insert 33 into leaf 27 33 40.

  11. Insert 19. From the root, at each node take the child between the keys that surround 19, down to the leaf 27 33 40, and slot it in order: 19 27 33 40.

    Insert 19 into leaf 19 27 33 40.

  12. Insert 45. From the root, at each node take the child between the keys that surround 45, down to the leaf 19 27 33 40, and slot it in order: 19 27 33 40 45. That is 5 keys, one too many.

    Insert 45 into leaf 19 27 33 40 45.

  13. 19 27 33 40 45 has 5 keys and the limit is 4, so it splits. The middle key, 33, moves up to the parent; the keys below it form the left node and the keys above it the right node.

    Split 19 27 33 40 45 around 33.

  14. 19 27 stays as the left node, 40 45 is the new right node, and 33 joins the parent, now 15 33, between them.

    Split done; parent is 15 33.

  15. Insert 5. From the root, at each node take the child between the keys that surround 5, down to the leaf 3 8 12, and slot it in order: 3 5 8 12.

    Insert 5 into leaf 3 5 8 12.

  16. Insert 22. From the root, at each node take the child between the keys that surround 22, down to the leaf 19 27, and slot it in order: 19 22 27.

    Insert 22 into leaf 19 22 27.

  17. Insert 38. From the root, at each node take the child between the keys that surround 38, down to the leaf 40 45, and slot it in order: 38 40 45.

    Insert 38 into leaf 38 40 45.

  18. 12 keys in 4 nodes, height 2, after 2 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 2 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

Related

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

Next up