Programación
Skip Lists: The Data Structure Behind Redis and LevelDB
Skip lists are a probabilistic data structure that Redis uses to implement sorted sets and that LevelDB uses in its MemTable. Instead of balancing a tree with rotations, each node flips a coin to decide how many levels of shortcuts to have. The result is expected O(log n) performance with an implementation much simpler than an AVL or red-black tree.









