memtable. "skipdb" is an open-source implementation of an ACID ordered key/value database, implemented with a skip list instead of a b-tree. ConcurrentSkipListSet and ConcurrentSkipListMap in the Java 1.6 API. Used by Apache HBase. Speed Tables are a fast key-value datastore for Tcl that use skiplists for indexes and lockless shared memory. "leveldb" is a fast key-value storage library written at Google that provides an ordered mapping from string keys to string values Con Kolivas' MuQSS Scheduler for the Linux kernel uses skip lists SkiMap uses skip lists as base data structure to build a more complex 3D Sparse Grid for Robot Mapping systems. "IOWOW" is a persistent C11 key/value storage library that uses skip lists as its main data structure. Skip lists are used for efficient statistical computations of running medians (also known as moving medians). 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 as lock-free concurrent dictionaries. There are also several US patents for using skip lists to implement (lockless) priority queues and concurrent dictionaries. See also Bloom filter Skip graph References External links "Skip list" entry in the Dictionary of Algorithms and Data Structures Skip Lists: A Linked List with Self-Balancing BST-Like Properties on MSDN in C# 2.0 Why Skip Lists? Skip Lists lecture (MIT OpenCourseWare: Introduction to Algorithms) Open Data Structures - Chapter 4 - Skiplists, Pat Morin Skip trees, an alternative data structure to skip lists in a concurrent approach Skip tree graphs, a distributed version of skip trees More on skip tree graphs, a distributed version of skip trees Computer-related introductions in 1989 Linked lists Probabilistic data structures de:Liste (Datenstruktur)#Skip-Liste