Programación
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.









