Sin árboles balanceados: así ordena Redis con monedas al aire

Redis ordena millones de elementos en sus sorted sets sin balancear un árbol: cada nodo nuevo decide con una moneda al aire cuántos atajos va a tener. Esa estructura se llama skip list, y también es la que usan LevelDB y RocksDB para su MemTable en memoria.

La idea detrás de una skip list es simple: en vez de forzar un balance perfecto con rotaciones como hace un árbol AVL o rojo-negro, se deja que el azar reparta los atajos. El resultado es una estructura más fácil de implementar, más fácil de paralelizar y con un rendimiento esperado de O(log n) en búsqueda, inserción y borrado.

TL;DR

• Vas a entender cómo una skip list logra búsquedas O(log n) esperado sin rotaciones ni rebalanceo de árbol.- Vas a poder implementar una skip list completa en JavaScript, con inserción, búsqueda y niveles aleatorios.- Vas a saber por qué Redis usa skip lists en sus sorted sets y cómo verificarlo con OBJECT ENCODING.- Vas a entender por qué LevelDB y RocksDB usan skip lists en su MemTable en memoria.- Vas a poder elegir entre skip list, árbol balanceado o hash table según el caso de uso real.- Vas a conocer los errores comunes al elegir la probabilidad p y el nivel máximo de una skip list.- Vas a entender por qué las skip lists son más fáciles de paralelizar que un árbol balanceado.

Qué son las skip lists y por qué importan

Imaginá una línea de tren que para en todas las estaciones. Si querés ir de la estación 1 a la estación 30, tenés que pasar por las 29 anteriores: eso es una lista enlazada ordenada, y buscar un valor cuesta O(n). Ahora agregale una línea expresa que solo para cada 4 estaciones, y encima de esa, otra que para cada 16. Para ir de la estación 1 a la 30 tomás la línea más rápida posible, avanzás lo más que podés, y bajás de nivel solo cuando te vas a pasar de largo. Eso es exactamente una skip list.

El concepto lo formalizó William Pugh en 1990 en el paper "Skip Lists: A Probabilistic Alternative to Balanced Trees", publicado en Communications of the ACM. Su observación central: en vez de mantener un balance garantizado con reglas estrictas (como hace un árbol rojo-negro), se puede lograr un balance esperado igual de bueno dejando que cada nodo tire una moneda para decidir en cuántos niveles va a participar.

Esto importa porque los árboles balanceados clásicos son notoriamente difíciles de implementar bien: las rotaciones de un árbol AVL o los cuatro casos de recoloreo de un árbol rojo-negro son una fuente constante de bugs sutiles. Una skip list resuelve el mismo problema (mantener datos ordenados con acceso rápido) con un algoritmo que cabe en menos de 50 líneas.

Cómo funciona una skip list por dentro

Cada nodo de una skip list guarda un valor y un arreglo de punteros "hacia adelante", uno por cada nivel en el que participa. El nodo cabecera (head) no tiene valor real: apunta al primer nodo de cada nivel. Cuando se inserta un nodo nuevo, se decide su nivel con un bucle simple: empieza en nivel 1, y mientras un número aleatorio sea menor que una probabilidad p, sube un nivel más (hasta un tope máximo).

Con p = 0.5 (el valor original de Pugh), la mitad de los nodos llegan a nivel 2, un cuarto a nivel 3, un octavo a nivel 4, y así sucesivamente. Eso significa que el nivel superior es exponencialmente más angosto que el nivel base, igual que la línea expresa del tren para en muchas menos estaciones que la línea local.
Cada nivel superior de una skip list tiene, en promedio, la mitad de nodos que el nivel de abajo.
El algoritmo de búsqueda arranca en el nivel más alto del nodo cabecera y avanza mientras el siguiente nodo de ese nivel tenga un valor menor al buscado. Cuando el siguiente nodo se pasaría del objetivo (o no existe), el algoritmo baja un nivel y repite, hasta llegar al nivel 0, donde compara directamente contra el valor buscado.

flowchart LR
 subgraph N3["Nivel 3 (expreso)"]
 H3["INICIO"] --> A3["30"] --> F3["FIN"]
 end
 subgraph N2["Nivel 2"]
 H2n["INICIO"] --> A2["10"] --> B2["30"] --> F2["FIN"]
 end
 subgraph N1["Nivel 1"]
 H1["INICIO"] --> A1["5"] --> B1["10"] --> C1["20"] --> D1["30"] --> F1["FIN"]
 end
 subgraph N0["Nivel 0 (todos los datos)"]
 H0["INICIO"] --> A0["5"] --> B0["10"] --> C0["15"] --> D0["20"] --> E0["25"] --> G0["30"] --> F0["FIN"]
 end

Ejemplos prácticos con código

Para ver la diferencia, comparemos primero una búsqueda ingenua sobre una lista enlazada ordenada:

class Node {
 constructor(value) {
 this.value = value;
 this.next = null;
 }
}

function buscarEnListaOrdenada(head, valor) {
 let actual = head;
 let pasos = 0;
 while (actual !== null && actual.value = 0; i--) {
 while (actual.forward[i] !== null && actual.forward[i].value  this.level) {
 for (let i = this.level + 1; i = 0; i--) {
 while (actual.forward[i] !== null && actual.forward[i].value >N3: comparar con 30, es mayor: bajar
 N3->>N2: bajar un nivel
 N2->>N2: comparar con 30, es mayor: bajar
 N2->>N1: bajar un nivel
 N1->>N1: comparar con 20, avanzar
 N1->>N1: comparar con 30, es mayor: bajar
 N1->>N0: bajar un nivel
 N0->>N0: comparar con 25, encontrado

Cómo empezar paso a paso

La forma más rápida de ver una skip list en acción es a través de Redis, que la usa internamente en sus sorted sets (ZSET):

redis-cli ZADD ranking 100 "jugador1" 250 "jugador2" 80 "jugador3"
redis-cli OBJECT ENCODING ranking
redis-cli CONFIG GET zset-max-listpack-entries
redis-cli ZRANGEBYSCORE ranking 0 200

OBJECT ENCODING ranking devuelve listpack mientras el sorted set tiene pocos elementos pequeños. En cuanto supera zset-max-listpack-entries (128 por defecto) o algún valor supera zset-max-listpack-value (64 bytes por defecto), Redis cambia la codificación a skiplist: ahí es donde entra la estructura que vimos arriba, implementada en su código fuente como zskiplist.

💡 Tip: corré OBJECT ENCODING antes y después de agregar cientos de elementos a un sorted set para ver el cambio de listpack a skiplist en vivo.

Para probar la implementación propia en Node.js, el flujo es directo:

mkdir skiplist-demo && cd skiplist-demo
npm init -y

Guardá la clase SkipList del bloque anterior en un archivo skiplist.js, exportala con module.exports = SkipList, y en otro archivo hacé const SkipList = require('./skiplist') para insertar valores y llamar a search.

flowchart TD
 A["Insertar nuevo nodo"] --> B["Nivel = 0"]
 B --> C{"Lanzar moneda"}
 C -->|"cara (25%)"| D["Nivel += 1"]
 D --> C
 C -->|"cruz (75%)"| E["Nivel final decidido"]
 E --> F["Insertar nodo en todos los niveles de 0 a Nivel"]

Casos de uso reales

Los sorted sets de Redis son el ejemplo más visible: se usan para tablas de posiciones (leaderboards), colas de prioridad y limitadores de tasa, y su codificación interna cambia a skip list precisamente para sostener inserciones y rangos rápidos a medida que crecen.

LevelDB, la base de datos clave-valor de Google, implementa su MemTable (el buffer en memoria donde caen las escrituras antes de volcarse a un SSTable en disco) directamente como una skip list, definida en db/skiplist.h dentro del repositorio oficial. RocksDB, el fork de Facebook sobre LevelDB, hereda ese mismo diseño como su MemTable por defecto.

Java trae skip lists concurrentes en su biblioteca estándar: ConcurrentSkipListMap y ConcurrentSkipListSet, en el paquete java.util.concurrent, son estructuras ordenadas sin bloqueos (lock-free) pensadas para múltiples hilos leyendo y escribiendo a la vez.
LevelDB y RocksDB usan la misma skip list como MemTable en memoria.
Los motores de búsqueda que implementan índices invertidos también usan skip lists para saltar bloques enteros de una lista de postings al intersectar los resultados de varios términos, evitando recorrer cada documento uno por uno.

Errores comunes y buenas prácticas

El error más frecuente es elegir mal la probabilidad p. Un p muy alto (cercano a 1) genera demasiados niveles y desperdicia memoria en punteros que casi no se usan. Un p muy bajo (cercano a 0) hace que casi todos los nodos queden en nivel 0, degradando la estructura a una simple lista enlazada.

Redis eligió p = 0.25 en vez del 0.5 original de Pugh, un detalle que vale la pena entender en la siguiente sección.

Otro error es no fijar un maxLevel razonable. En teoría, sin un tope, un nodo podría generar un nivel absurdamente alto; en la práctica se calcula un techo en función del tamaño esperado del set de datos (Redis usa 32 como máximo).

⚠️ Ojo: una skip list no es cache-friendly. Sus punteros saltan por posiciones de memoria dispersas, mientras que un B-tree agrupa varias claves por nodo y aprovecha mejor la caché de la CPU. Por eso los índices en disco casi siempre usan B-trees o B+ trees, no skip lists.

Por último, una skip list implementada de forma directa como la de este artículo no es segura para múltiples escritores simultáneos. Las versiones concurrentes de producción evitan un bloqueo global usando operaciones atómicas de tipo compare-and-swap sobre los punteros de cada nivel.

Comparativa con alternativas

OpciónCuándo usarlaVentajaLimitaciónSkip listEstructuras en memoria con lecturas y escrituras concurrentesSimple de implementar, fácil de paralelizarNo es cache-friendly, más memoria por los punteros extraÁrbol AVL o rojo-negroCuando se necesita balance garantizado en el peor casoO(log n) garantizado, no solo esperadoRotaciones complejas de implementar y depurarB-tree o B+ treeÍndices en disco o bases de datosAgrupa claves por nodo, aprovecha la caché y minimiza I/OPeor para escrituras concurrentes en memoria puraHash tableBúsqueda exacta sin necesidad de ordenO(1) esperado en búsquedaNo mantiene orden, no sirve para rangosLista enlazada ordenadaDatasets muy pequeñosTrivial de implementarO(n) en cada búsqueda

Profundizando: la teoría detrás de las skip lists

El número esperado de niveles de una skip list con n elementos es aproximadamente log en base 1/p de n. Con p = 0.5, eso es log₂(n); con p = 0.25, es log₄(n), un número menor de niveles pero con más nodos por nivel.

Cada nodo tiene, en promedio, 1/(1 - p) punteros hacia adelante. Con p = 0.5 eso da 2 punteros promedio por nodo; con p = 0.25 baja a 1.33 punteros promedio. Esa es la razón concreta por la que Redis eligió 0.25: menos punteros por nodo significa menos memoria consumida por cada entrada de un sorted set, un recurso mucho más caro en una base de datos en memoria que en una en disco.

💭 Clave: bajar p de 0.5 a 0.25 es un compromiso deliberado entre memoria y CPU: se paga con más comparaciones durante la búsqueda a cambio de una estructura más liviana en RAM.

El peor caso teórico de una skip list sigue siendo O(n), si por mala suerte todas las monedas caen igual y ningún nodo sube de nivel. Pero la probabilidad de ese escenario decrece exponencialmente con el tamaño de la estructura, lo que hace que en la práctica el comportamiento observado sea consistentemente O(log n).

La razón por la que las skip lists concurrentes son más simples de razonar que un árbol balanceado concurrente es que insertar un nodo intermedio solo requiere actualizar un puntero por nivel, sin necesidad de reequilibrar el resto de la estructura como exige una rotación en un árbol.

📖 Resumen en Telegram: Ver resumen

Tu próximo paso: cloná la clase SkipList de este artículo, insertá 1000 números aleatorios y contá cuántos niveles usa realmente tu instancia con console.log(lista.level) para comprobar que se acerca a log en base 1/p de n.

Preguntas frecuentes

¿Una skip list es más rápida que un árbol balanceado?

En la práctica el rendimiento esperado es similar, O(log n) en ambos casos. La diferencia está en la simplicidad de implementación y en que un árbol balanceado garantiza el peor caso, mientras que una skip list solo lo garantiza en promedio.

¿Qué pasa en el peor caso de una skip list?

El peor caso teórico es O(n), si el generador de niveles aleatorios produjera una distribución desfavorable. La probabilidad de que eso ocurra decrece exponencialmente a medida que crece la estructura.

¿Por qué Redis usa skip lists y no un árbol B?

Porque los sorted sets de Redis viven enteramente en memoria, donde el beneficio de un B-tree (agrupar claves para minimizar operaciones de disco) no aplica, y la simplicidad de implementar y paralelizar una skip list pesa más.

¿Se puede usar una skip list para índices en disco?

Es poco común, porque sus punteros dispersos no aprovechan bien la caché de la CPU ni minimizan las lecturas de disco como sí lo hace un B-tree o B+ tree, que agrupa muchas claves en cada nodo.

¿Qué probabilidad p conviene usar?

El valor original de Pugh es 0.5. Redis usa 0.25 para reducir la memoria promedio por nodo a cambio de más comparaciones durante la búsqueda, un compromiso razonable cuando la RAM es el recurso más escaso.

¿Existen skip lists concurrentes sin bloqueos?

Sí, ConcurrentSkipListMap de Java es el ejemplo más conocido: usa operaciones atómicas de compare-and-swap sobre los punteros de cada nivel en vez de bloqueos globales.

Referencias

• Wikipedia: Skip list: historia, definición formal y análisis de complejidad de la estructura.- Redis Docs: Sorted sets: documentación oficial de ZADD, ZRANGEBYSCORE y la codificación interna de los sorted sets.- GitHub: google/leveldb: código fuente de LevelDB, incluyendo la implementación de la skip list en db/skiplist.h.

📱 ¿Te gusta este contenido? Únete a nuestro canal de Telegram @programacion donde publicamos a diario lo más relevante de tecnología, IA y desarrollo. Resúmenes rápidos, contenido fresco todos los días.