Skip list

In short: A skip list is a sorted linked list with extra “express lanes” so elements can be found in O(log n) on average.

In more detail: The bottom level contains all elements. Each higher level contains, chosen at random, about half of the elements of the level below. A search starts at the top, jumps far, and drops down when it would overshoot.

In Depth

• Insert: Insert the element at the bottom, then decide with a coin flip how many extra levels it appears in.
• Advantage over trees: Simpler to implement, good for concurrent access since less restructuring is needed.
• Disadvantage: Slightly more memory for the pointers, runtime guaranteed only on average.
• Use: Redis (sorted sets), LevelDB/RocksDB memtables.

See also: B-tree and B+ tree