Ropes, skip lists and tries

The Ask HN thread on cool but obscure data structures went up last Thursday and already has a couple of hundred top-level answers. I read all of them, over two lunch breaks and most of an evening, and kept a tally, because of course I did. Bloom filters came up more than anything else, which made me smile, since I wrote about them a few years ago and got more mail about that post than almost anything else on here. Tries came second. Further down there were HyperLogLog, cuckoo hashing, Fenwick trees, finger trees, and my favorite answer, the “Israeli queue”, where a new arrival who sees a friend already in line gets to go and stand next to them.

I don’t think most of these are obscure, exactly. They’re things people learned once in a data structures class and never used, because the standard library gave them a hash map, a sorted map and a growable array and that covered 95% of their work. The other 5% is where these come in, and you’ve almost certainly used all three of the ones below today without knowing it, inside an editor, a database or a router.

Ropes

When I was a teenager I wrote a text editor in Turbo C, because every DOS programmer of a certain age did. The whole file lived in one big char array. Inserting a character meant moving everything after the cursor one byte to the right, with memmove, and deleting meant moving it back. On a 20 KB file that was fine. I then tried to open a file of about 60 KB, near the limit of what a single segment could hold, and typing near the top of it became noticeably laggy on a 286. I “fixed” it by not editing big files.

The problem is that an array is the wrong shape for text you’re editing. Every insert in the middle costs O(n), and an editor does almost nothing but insert in the middle. A rope is what you use instead. It’s a binary tree whose leaves hold short strings, and the string the rope represents is all the leaves read left to right. Each internal node stores a weight, which is the total length of the text in its left subtree. That one number is what makes it work.

To find the character at position i, start at the root. If i is less than the weight, go left. Otherwise subtract the weight from i and go right. When you hit a leaf, i is the offset into that leaf’s string. In the drawing, position 12 goes right at the root (12 ≥ 10, leaving 2), left at the next node (2 < 6), and lands on the o in brown_. If you count it out, the_quick_brown_fox has an o at index 12, so it works.

Concatenating two ropes is just a new root with the two ropes as children, and its weight is the length of the left one. Splitting at a position walks down the same path and cuts the tree in two along it. Insert is split, then concatenate twice. Delete is split twice and concatenate the outside pieces. All of those are O(log n) as long as the tree stays roughly balanced, which is the part that takes real code. The original paper, Boehm, Atkinson and Plass’s “Ropes: an Alternative to Strings” from 1995, rebalances when the depth gets too far out of line with the length, using Fibonacci numbers as the thresholds.

There’s a nice side effect. Since an edit only creates new nodes along one path and shares everything else, the old version of the rope is still intact. Undo is “keep a pointer to the old root”, which is a lot simpler than the undo stack I wrote for that Turbo C editor, which never did work properly.

Ropes are a good fit for editors that need to handle huge files and lots of concurrent edits. xi-editor is built on one. They’re not the only answer, though. Emacs uses a gap buffer, which is my old char array with a hole kept open at the cursor, so typing in one place is cheap and only jumping around costs you. VS Code moved its text buffer to what it calls a piece tree a few years ago, which is a piece table (the original file plus an append-only buffer of everything you typed, and a list of spans pointing into the two) with the spans kept in a red-black tree. Their write-up, from 2018, is one of the better engineering blog posts I’ve read about a data structure in a real product, mostly because they measured things before choosing.

Skip lists

A skip list is a sorted linked list with express lanes. The bottom level is an ordinary sorted linked list of every element. The level above it skips some of them, the level above that skips more, and a search starts on the top level, goes right as far as it can without overshooting, drops down a level, and repeats.

If you built the levels perfectly, every second node on level 2, every fourth on level 3 and so on, you’d have a binary search over a linked list, O(log n). The trouble is keeping it perfect while things get inserted and deleted, which is the same problem balanced trees solve with rotations and colors. William Pugh’s trick, in his 1990 paper “Skip Lists: A Probabilistic Alternative to Balanced Trees”, was to stop trying. When you insert a node, flip a coin. Heads, it also goes on level 2. Flip again. Heads, level 3, and so on until you get tails. Nothing else ever gets rebalanced.

The analysis is short enough to do on a napkin, which is part of why I like it. With a fair coin, a node reaches level k with probability 1/2^(k−1), so out of n nodes you expect about n/2 on level 2, n/4 on level 3, and the top level is around log₂ n. The expected number of pointers per node is 1 + 1/2 + 1/4 + … = 2, so the memory overhead is about the same as a doubly linked list. Pugh suggests p = 1/4 instead of 1/2, which gives 1 + 1/4 + 1/16 + … = 4/3 pointers per node and slightly longer searches. The search cost is O(log n) expected. There’s no guarantee. In principle every insert could come up tails and leave you with a plain linked list. With any decent random number generator, it doesn’t happen.

Why use one over a red-black tree? Two reasons, and both are practical. A skip list is much easier to write correctly. I’ve written a red-black tree from scratch exactly once, for a class, and I wouldn’t trust that one in production. A basic skip list is maybe 60 lines. And skip lists are much easier to make concurrent, because an insert only touches a few neighboring pointers and doesn’t rotate anything, so you can do it with compare-and-swap and no locks. That’s why Java’s ConcurrentSkipListMap exists and there’s no concurrent TreeMap.

You’ve probably used one recently. Redis sorted sets, once they grow past a small size, are a skip list plus a hash table. LevelDB’s memtable, the in-memory sorted buffer in front of the LSM tree, is a skip list, and so is RocksDB’s by default. We ran a Redis sorted set as a leaderboard for a customer feature for years without anybody on the team knowing what was underneath it, me included until about 2019.

Tries

A trie stores strings by their characters. The root has one child for each possible first character, each of those has a child for each second character, and so on, and a node is marked when a whole word ends there. To look up “cart” you follow c, a, r, t from the root, and the cost depends on the length of the key, not on how many keys are stored. Edward Fredkin named it in 1960, from retrieval, and as far as I know he meant it to be pronounced “tree”, which is why everybody I’ve ever worked with says “try”, to keep the two apart.

What a trie gives you that a hash table doesn’t is prefixes. Every key starting with “car” sits under one node, so autocomplete is “walk to the node, then list everything below it”. A hash table can tell you whether “cart” is there, but to find all the words that start with “car” it has to look at every key. The naive version has a cost, which is memory. If every node has an array of 26 or 256 child pointers, most of them null, a trie of English words is mostly empty pointers. Real implementations compress it. A radix tree, or Patricia tree (Morrison, 1968), merges every chain of single-child nodes into one edge labeled with a string, so “cart” and “carton” share a “car” edge and then split into “t” and “ton” only where they differ.

Routers are probably the biggest users of tries, though you’d never see it. Forwarding a packet means finding the longest prefix in the routing table that matches the destination address. 10.1.0.0/16 and 10.1.2.0/24 both match 10.1.2.7, and the /24 wins. That’s a walk down a binary trie on the address bits, keeping the last match you passed. The Linux kernel’s IPv4 routing table has been a compressed trie (an LC-trie) for well over a decade. Ethereum’s state is a Merkle Patricia trie, which is the Merkle tree idea applied to a radix tree, so every node’s hash covers the whole subtree under it.

We use one in a much less glamorous place. Our product lets customers configure webhooks per event, and event names are dotted paths like invoice.payment.failed, and a subscription can be a prefix, like invoice.*. For a long time that was a loop over every subscription doing startsWith, which was fine at a few hundred subscriptions and less fine at tens of thousands. One of our engineers replaced it with a trie keyed on the path segments last year, about 80 lines. Lookup went from scanning everything to walking three or four nodes. Nobody outside the team noticed, which is the usual reward for this kind of work.

Knowing they exist

You will rarely write any of these three yourself. I’ve written a skip list once outside of a class, a trie twice, and a rope never, unless that Turbo C editor counts as a first draft of what not to do. But knowing they exist changes which questions you ask. When someone tells me a feature needs “all the keys with this prefix”, I now think trie before I think SQL LIKE 'foo%', even if we end up with the LIKE (which, with the right index, is quietly a B-tree range scan anyway). When someone says a structure needs to be sorted and concurrent, I think skip list. And when someone proposes storing a document as one big string and patching it in place, I think about my 286.

The thread has a few dozen more I’d never heard of. I’ve bookmarked the answer about succinct data structures, the ones that store a tree in barely more bits than the information-theoretic minimum and still let you navigate it, because I don’t understand them yet, and that’s usually a good sign that a weekend is coming.