Sorted trees, skip lists and tries

A hash map is fast for exact keys, but it can't answer "all keys between 100 and 200" or "all words starting with ca". For those, keep keys in sorted order. Three structures do it, each with a different trade-off between simplicity, memory and speed.

• Balanced binary trees, such as red-black trees, keep keys sorted with O(log n) updates, by rotating nodes to stay balanced.
• Skip lists are sorted linked lists with extra express lanes, giving O(log n) average operations. They are simpler to write concurrently.
• Tries store keys character by character, so prefix queries cost time proportional to the prefix length.

The big idea

A sorted structure trades a little speed on exact lookups for ordering. A binary search over a sorted array is already O(log n) and fast for reads. The trees and skip lists add cheap inserts and deletes on top of that.

Pick by workload:

Walking through it: a trie

A trie stores each character as a level. Words sharing a prefix share the path. To check a prefix, walk the path, and fail at the first missing character.

trie = {}
def insert(w):
    node = trie
    for ch in w: node = node.setdefault(ch, {})
    node["$"] = True
def has_prefix(p):
    node = trie
    for ch in p:
        if ch not in node: return False
        node = node[ch]
    return True

for w in ["car", "cart", "dog"]: insert(w)
print(has_prefix("ca"), has_prefix("cab"), has_prefix("do"))

Output:

True False True

ca is a prefix of car. cab fails at the b, since no word has cab in it. do is a prefix of dog. The lookup costs the length of the prefix, however many words are stored. That is why tries power autocomplete, covered in search autocomplete.

Tries use a lot of memory. Each node may hold a pointer per character. Compressed variants, such as radix trees, merge single-child chains to save space.

Red-black trees and skip lists

A red-black tree keeps every path from root to leaf within about twice the shortest path, by colouring nodes and rotating them on insert and delete. Most standard libraries' ordered maps are red-black or similar balanced trees. Their cost is pointer chasing, which hurts cache performance, as covered in arrays and memory layout.

A skip list is a linked list with several levels of express lanes. Each node is promoted to higher levels at random, so searches skip ahead. Inserts only touch local pointers, which makes them simpler to make concurrent. Redis uses a skip list for its sorted sets.

Common mistakes

• Using a hash map for range queries and then scanning every key on each request.
• Building a trie for a small set of words, where a sorted array is smaller and fast enough.
• Ignoring the memory cost of tries on large vocabularies.

Check yourself

• Why does a trie's prefix lookup not depend on the number of words? Answer: it walks one node per character of the prefix, so the cost is the prefix length.
• Why is a skip list easier to make concurrent than a balanced tree? Answer: its updates touch a few local pointers, while a tree rotation can change nodes far apart, which requires more locking or complex lock-free code.

Key takeaways

• Use sorted structures when you need range queries or ordered scans.
• Red-black trees and skip lists give O(log n) ordered updates in memory.
• Tries answer prefix queries in time proportional to the prefix length.

Further learning

Next, see LRU caches, which combine a hash map with a list to evict in constant time.