Skip List - Usages

Usages

List of applications and frameworks that use skip lists:

• Cyrus IMAP server offers a "skiplist" backend DB implementation (source file)
• QMap (up to Qt 4) template class of Qt that provides a dictionary.
• Redis, an ANSI-C open-source persistent key/value store for Posix systems, uses skip lists in its implementation of ordered sets.
• nessDB, a very fast key-value embedded Database Storage Engine (Using log-structured-merge (LSM) trees), uses skip lists for its memtable.
• skipdb is an open-source database format using ordered key/value pairs.
• Running Median using an Indexable Skiplist is a Python implementation of a skiplist augmented by link widths to make the structure indexable (giving fast access to the nth item). The indexable skiplist is used to efficiently solve the running median problem (recomputing medians and quartiles as values are added and removed from a large sliding window).
• ConcurrentSkipListSet and ConcurrentSkipListMap in the Java 1.6 API.

Skip lists are also used in distributed applications (where the nodes represent physical computers, and pointers represent network connections) and for implementing highly scalable concurrent priority queues with less lock contention, or even without locking, as well lockless concurrent dictionaries. There are also several US patents for using skip lists to implement (lockless) priority queues and concurrent dictionaries.