https://antithesis.com/blog/2026/skiptrees/
Article
-
Explores practical uses of skiplists and proposes an extension called ‘skip trees’.
-
Skiplists offer ordered iteration and O(log n) operations with simpler code than balanced BSTs.
-
Skip trees add hierarchical aggregation, enabling efficient fold/range operations.
-
Motivated by Antithesis’s need to query fuzzer-generated structured data efficiently.
Discussion
-
antirez connection: Redis sorted sets are the most widely deployed skiplist in production.
-
Skeptics note skiplists are pointer-heavy and lose to B+ trees on cache locality in practice.
-
Lock-free skiplists cited as a key advantage for concurrent systems (SingleStore example).
-
Use in LSM tree memtables, key transparency logs, and ledger balance queries noted.
Discuss on HN
