B-trees and tries
Not every balanced tree is binary. B-trees pack many keys into each node to suit disks and databases, while tries organise strings by their characters.
Why multiway trees
Reading from disk or SSD happens in blocks of several kilobytes, and each read is far slower than a memory access. A binary tree of a billion keys has about 30 levels, meaning up to 30 slow reads per lookup. If each node instead holds hundreds of keys and children, the tree is only 3 or 4 levels deep.
B-tree structure
A B-tree of minimum degree t keeps between t - 1 and 2t - 1 sorted keys in every node except the root, and an internal node with k keys has k + 1 children. All leaves are at the same depth, so the tree is perfectly height-balanced. Keys in a node split the key ranges of its children, generalising the BST property.
Searching and inserting
To search, scan or binary-search the keys in a node, then descend into the child whose range contains the target: O(log n) total with very few node reads. To insert, descend to a leaf and add the key. If a node becomes overfull, split it into two half-full nodes and push the median key up into the parent, which may split in turn. When the root splits, the tree grows one level taller at the top.
Deletion
Deletion removes a key and, if a node falls below the minimum, borrows a key from a sibling through the parent or merges with a sibling. Merges can shrink the root, reducing height. The details are intricate, but every operation touches O(log n) nodes, with a high branching factor making that number tiny.
B+ trees
Most databases and file systems use B+ trees, a variant where all actual records or record pointers live in the leaves, internal nodes hold only routing keys, and leaves are linked in sorted order. Range queries find the first matching leaf and then follow the links, which is ideal for queries such as all orders between two dates. MySQL's InnoDB, PostgreSQL indexes, NTFS, and many others use B-tree variants.
Tries
A trie, or prefix tree, stores strings character by character: each edge is labelled with a character, and each path from the root spells a prefix. A flag marks nodes where a complete word ends. Looking up a word of length m costs O(m), independent of how many words are stored, and all words with a given prefix lie in one subtree, enabling fast autocomplete.
Trie trade-offs and variants
Tries can use a lot of memory, since each node may hold an array of child pointers for the whole alphabet. Using hash maps for children saves space. Radix trees compress chains of single-child nodes into one edge labelled with a string; routers use related structures for longest-prefix matching on IP addresses, and suffix trees index every suffix of a text for fast substring search.
Worked example
With up to 1,000 keys per node, a B-tree's levels hold about 1,000, then 1,000,000, then 1,000,000,000 keys in total. So a billion keys need only about 3 levels, and the top one or two levels usually stay cached in memory, leaving about one disk read per lookup. A trie holding "car", "cart", and "care" shares the path c-a-r, with end-of-word flags at r, t, and e; the prefix "car" leads to all three.
Key takeaways
Multiway trees reduce height to minimise slow block reads. B-trees keep many sorted keys per node, all leaves at equal depth, and grow by splitting full nodes and pushing medians up; deletion borrows or merges. B+ trees keep records in linked leaves and dominate database and file-system indexes, excelling at range queries. Tries store strings by characters for O(m) lookups and prefix search; radix trees compress them, and suffix trees index substrings.
Flashcard
Nodes with many children
Check your understanding
Why do databases prefer B+ trees over binary search trees for indexes on disk?