Diagrama de una skip list con niveles y punteros hacia adelante

Skip lists: la estructura de datos detrás de Redis y LevelDB

Las skip lists son una estructura de datos probabilística que Redis usa para implementar sorted sets y que LevelDB usa en su MemTable. En vez de balancear un árbol con rotaciones, cada nodo decide con una moneda al aire cuántos niveles de atajos tener. El resultado es un rendimiento esperado de O(log n) con una implementación mucho más simple que un árbol AVL o rojo-negro.