Skip lists

De qué trata este capítulo

El bloque de árboles nos dio operaciones ordenadas en O(log n), pero solo a través de la enredada lógica de rotaciones de los árboles AVL y rojo-negro — código que de verdad cuesta trabajo dejar bien. La skip list logra la misma búsqueda, inserción y eliminación en O(log n) usando nada más que listas ligadas y volados. En lugar de rebalancear con cuidado después de cada cambio, deja que el azar haga el balanceo: a cada elemento se le asigna una "altura" aleatoria, y esas alturas dan como resultado, en esperanza, exactamente la estructura por capas que hace que la búsqueda sea logarítmica. Este capítulo construye la skip list, observa cómo una búsqueda se sube a sus carriles exprés hacia el objetivo tocando apenas un puñado de nodos, y muestra cómo le gana a una lista ligada ordenada simple por 1,500× en pasos de búsqueda con 100,000 elementos — todo con código muchísimo más simple que el de un árbol balanceado. Esa simplicidad es la razón por la que sistemas reales (Redis, LevelDB) usan skip lists donde un libro de texto echaría mano de un árbol balanceado.

Un poco de historia

William Pugh presentó las skip lists en 1989, en un artículo cuyo subtítulo lo decía todo: "A Probabilistic Alternative to Balanced Trees". El argumento de Pugh era tanto de ingeniería de software como de algoritmos — demostró que las skip lists igualan las cotas O(log n) de los árboles balanceados y a la vez son muchísimo más fáciles de implementar, de razonar y de volver concurrentes. Una inserción en un árbol balanceado puede disparar una cascada de rotaciones con muchos casos que hay que manejar correctamente; una inserción en una skip list tira un volado y empalma un par de apuntadores. Esa simplicidad, sobre todo para acceso concurrente (una skip list es mucho más fácil de volver lock-free que un árbol balanceado, porque las actualizaciones son empalmes locales de apuntadores), convirtió a las skip lists en favoritas de la programación de sistemas. Son la estructura ordenada detrás de los sorted sets de Redis, de las memtables de LevelDB y RocksDB, del ConcurrentSkipListMap de Java y de los índices de MemSQL. El punto más profundo de Pugh — que la aleatorización puede sustituir al balanceo determinista y enredado, cambiando una garantía de peor caso por una esperada igual de buena y una fracción de la complejidad — conecta a las skip lists con la misma filosofía del filtro de Bloom del capítulo anterior y de las estructuras aleatorizadas del siguiente: a veces la respuesta simple y suficientemente buena le gana a la compleja y perfecta.

La intuición

Una lista ligada ordenada es el problema: es simple, pero la búsqueda es O(n) porque tienes que recorrer todos los nodos hasta llegar a tu objetivo — no hay manera de brincar hacia adelante. Las skip lists agregan carriles exprés. Conserva la lista ordenada completa como carril inferior (nivel 0), pero construye listas más dispersas encima: el nivel 1 podría contener uno de cada dos elementos, el nivel 2 uno de cada cuatro, y así, cada una una lista ligada que se salta muchos elementos. Ahora busca de arriba hacia abajo. Empieza en el carril más disperso de hasta arriba y avanza a la derecha hasta que el siguiente nodo se pasaría de tu objetivo — entonces baja un carril, donde ahora quedas justo antes del objetivo entre un conjunto más denso de nodos, y continúa. Cada bajada te deja en un carril con el doble de densidad pero solo dentro del tramo pequeño al que ya redujiste la búsqueda, así que cada nivel más o menos parte a la mitad la distancia restante. Eso es O(log n), la misma estrategia de divide y vencerás de la búsqueda binaria, lograda subiéndote a los carriles exprés para bajar hasta el carril local cerca de tu objetivo.

Lo elegante es cómo se construyen los carriles sin llevar ninguna contabilidad. Cuando insertas un elemento, tiras un volado para decidir su altura: siempre entra al nivel 0; con probabilidad ½ también sube al nivel 1; si sube, otra vez con probabilidad ½ al nivel 2; y así sucesivamente. Entonces la mitad de los elementos tienen altura 0, un cuarto llega a altura 1, un octavo llega a altura 2 — una distribución geométrica que hace que cada carril esté más o menos a la mitad de poblado que el de abajo, que es exactamente la estructura de carriles exprés que da búsqueda logarítmica. Ningún elemento necesita moverse ni rebalancearse jamás; su altura queda fija al insertarlo, por los volados, y las probabilidades garantizan la forma correcta en promedio. Insertar y eliminar es nada más empalmar apuntadores dentro de (o fuera de) cada carril que ocupa el elemento, encontrados en el camino hacia abajo. Toda la estructura se balancea sola estadísticamente, y por eso el código no tiene ni un solo caso de rotación.

Complejidad: cómo escala

Búsqueda, inserción y eliminación son todas O(log n) esperado: la estructura mide O(log n) carriles de alto en esperanza (un nodo alcanza el nivel k con probabilidad 1/2^k, así que la altura máxima es ~log₂ n), y cada carril aporta O(1) pasos esperados hacia la derecha antes de bajar. El espacio es O(n) esperado — el número total de apuntadores es n × (1 + ½ + ¼ + …) = 2n. Estas son cotas esperadas, no de peor caso: una mala racha de volados podría en principio producir una estructura degenerada y altísima, pero la probabilidad es astronómicamente pequeña (como el peor caso de una hash table), y a diferencia de una hash table no existe entrada adversaria que lo fuerce, porque la aleatoriedad es de la estructura misma, no de los datos. El duelo muestra el costo de búsqueda contra la lista ligada ordenada simple a la que mejora:

La línea de la lista ligada sube linealmente — la búsqueda visita en promedio la mitad de los elementos — mientras que la línea de la skip list apenas se levanta, creciendo de forma logarítmica. Con 100,000 elementos la lista ligada ordenada tomó alrededor de 48,000 pasos para encontrar un elemento aleatorio; la skip list tomó unos 32 — una diferencia de 1,500 veces, y la brecha se ensancha sin límite porque una es lineal y la otra logarítmica. La skip list logra esto solo con los carriles exprés: los mismos datos, los mismos nodos de lista ligada, más un puñado de apuntadores hacia adelante asignados por volados. Ese es todo el costo de convertir una estructura O(n) en una O(log n), y empata con lo que te daría un árbol balanceado — con código que podrías escribir bien al primer intento.

En qué es buena y en qué no

Las skip lists son la elección correcta para un mapa o conjunto ordenado cuando quieres el desempeño de un árbol balanceado sin la complejidad de un árbol balanceado — sobre todo en escenarios concurrentes, donde sus empalmes locales de apuntadores son mucho más fáciles de volver lock-free que las rotaciones de un árbol (el ConcurrentSkipListMap de Java es el ejemplo estándar). Soportan todo lo que hace un árbol balanceado — iteración ordenada, consultas por rango, predecesor/sucesor, rango (rank) — y su papel como memtable en LevelDB/RocksDB y como índice en los sorted sets de Redis son justamente esas cargas de trabajo de operaciones ordenadas a escala. Además son sencillamente agradables de implementar: cuando necesitas una estructura ordenada y no quieres depurar rotaciones rojo-negro, una skip list te lleva ahí con confianza. Y como se degradan con gracia y no tienen peor caso adversario, son robustas ante entradas no confiables de una forma en que las hash tables ingenuas no lo son.

Donde no son tan ideales: usan más memoria que un árbol balanceado simple (los apuntadores extra hacia adelante, ~2n en total) y más que una hash table para pura membresía; son más lentas que una hash table para acceso clave-valor sin orden (una hash table es O(1), una skip list O(log n)); y sus cotas son esperadas, así que un sistema de tiempo real duro que necesite una garantía estricta de peor caso podría preferir un árbol balanceado (aunque el mal caso de la skip list es prácticamente imposible). Para datos ordenados puramente estáticos, un arreglo ordenado simple con búsqueda binaria (bisect) es más cache-friendly y compacto que los nodos dispersos de una skip list. Las skip lists brillan específicamente con datos dinámicos y ordenados donde la simplicidad y la concurrencia importan; para datos estáticos o acceso sin orden, otras estructuras quedan mejor.

Los datos, o las entradas

El duelo cuenta los pasos de búsqueda de la skip list contra una lista ligada ordenada simple, conforme el número de elementos crece hasta 100,000 (el costo de la lista ligada se calcula analíticamente a partir del rango ordenado para evitar una construcción O(n²)). La correctitud se verifica tratando la skip list como un conjunto ordenado bajo cientos de secuencias aleatorias de inserción/eliminación: su carril inferior siempre debe ser igual al conjunto ordenado de valores presentes, y las consultas de membresía deben coincidir con un conjunto de referencia en cada prueba. La animación busca el valor 23 en una skip list pequeña (diez elementos, varios carriles), mostrando cómo la búsqueda recorre el carril exprés superior hacia la derecha y baja hacia el objetivo.

Constrúyela, una función a la vez

La skip list — niveles aleatorios por volado, búsqueda bajando por los carriles, inserción/eliminación por empalme:

class SkipList:
    """A skip list over comparable values. `level` is the current highest lane in use; `header` is a
    sentinel reaching every lane. p = 0.5 means each element is promoted to the next lane with
    probability 1/2, so lane heights are geometric and the structure is O(log n) tall in expectation."""

    def __init__(self, max_level=16, p=0.5):
        self.max_level = max_level
        self.p = p
        self.header = Node(None, max_level)
        self.level = 0

    def _random_level(self):
        """Flip coins: keep promoting to a higher lane while heads come up. Gives level 0 half the
        time, level 1 a quarter, level 2 an eighth, … — the geometric distribution that makes the
        express lanes exponentially sparser going up."""
        lvl = 0
        while random.random() < self.p and lvl < self.max_level:
            lvl += 1
        return lvl

    def search(self, value, trace=None):
        """Start in the top lane; at each lane move right while the next node is still < value, then
        drop down a lane. After dropping through the bottom lane, the next node is the answer (or a
        larger value / None if absent). O(log n) expected — each lane skips ~half the remaining span."""
        cur = self.header
        for i in range(self.level, -1, -1):
            while cur.forward[i] is not None and cur.forward[i].value < value:
                cur = cur.forward[i]              # move right along this express lane
                if trace is not None:
                    trace.append(("right", i, cur.value))
            if trace is not None:
                trace.append(("down", i, cur.value if cur.value is not None else "head"))
        cur = cur.forward[0]
        return cur is not None and cur.value == value

    def insert(self, value):
        """Insert, keeping every lane sorted. Walk down recording, at each lane, the last node before
        `value` (the `update` array — where new links must be spliced). Then coin-flip the new node's
        height and splice it into every lane up to that height. No rebalancing."""
        update = [self.header] * (self.max_level + 1)
        cur = self.header
        for i in range(self.level, -1, -1):
            while cur.forward[i] is not None and cur.forward[i].value < value:
                cur = cur.forward[i]
            update[i] = cur
        if cur.forward[0] is not None and cur.forward[0].value == value:
            return                                # already present — no duplicates
        lvl = self._random_level()
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.header           # new top lanes start from the header
            self.level = lvl
        node = Node(value, lvl)
        for i in range(lvl + 1):
            node.forward[i] = update[i].forward[i]
            update[i].forward[i] = node           # splice into lane i

    def delete(self, value):
        """Remove `value` by unlinking it from every lane it appears in, then trimming any now-empty
        top lanes."""
        update = [self.header] * (self.max_level + 1)
        cur = self.header
        for i in range(self.level, -1, -1):
            while cur.forward[i] is not None and cur.forward[i].value < value:
                cur = cur.forward[i]
            update[i] = cur
        target = cur.forward[0]
        if target is None or target.value != value:
            return False
        for i in range(self.level + 1):
            if update[i].forward[i] is target:
                update[i].forward[i] = target.forward[i]
        while self.level > 0 and self.header.forward[self.level] is None:
            self.level -= 1                       # trim empty top lanes
        return True

Míralo funcionar

Aquí tienes una skip list de diez elementos buscando el 23. El carril inferior (nivel 0) tiene todos los elementos; los carriles de arriba son los carriles exprés, cada uno más disperso que el de abajo, y H es el header que alcanza todos los carriles. La búsqueda empieza arriba a la izquierda, en el carril más disperso, y avanza a la derecha mientras el siguiente nodo siga siendo menor que 23 (el naranja marca el nodo actual, el azul los ya visitados). Cuando el siguiente nodo se pasaría de 23, baja un carril — cayendo entre nodos más densos, pero solo dentro del tramo estrecho al que ya llegó — y sigue a la derecha. Observa cómo desciende por los carriles en escalera hacia el objetivo, y fíjate en qué pocos nodos toca: encuentra el 23 habiendo visitado solo 3 nodos de 10, porque los carriles exprés le permiten saltarse todo lo que está a la izquierda en un par de brincos. Esa escalera es la misma partición a la mitad de la búsqueda binaria, hecha con listas ligadas y volados:

El código completo

La pestaña desde cero es la skip list completa — niveles aleatorios, búsqueda, inserción, eliminación; la pestaña de librería es la lista ligada ordenada simple a la que mejora (la línea base O(n) y una referencia de correctitud), con una nota sobre el sortedcontainers de producción y las skip lists dentro de Redis y LevelDB. Alterna entre las dos — la skip list es la lista ligada más un volado y un arreglo de apuntadores hacia adelante, y esa pequeña adición es toda la diferencia entre O(n) y O(log n).

"""Skip list — a sorted structure with the O(log n) search, insert, and delete of a balanced tree,
built from nothing but linked lists and coin flips. It's the answer to a frustration from the trees
tier: AVL and red-black trees achieve O(log n) but only through intricate rotation logic that's
genuinely hard to get right. A skip list gets the same performance with almost no cleverness —
randomization does the balancing for you.

The idea is express lanes. A plain sorted linked list forces you to walk element by element — O(n) to
find anything. A skip list stacks several linked lists on top of each other: the bottom level holds
every element, and each level above is a sparser "express lane" that skips over many elements. To
search, you start at the top (sparsest) lane and move right until the next node would overshoot your
target, then DROP DOWN a level and continue — each drop lands you in a denser lane near the target,
halving the remaining distance. The magic is how the lanes are built: when you insert an element, you
flip a coin to decide how many levels tall it is (heads → promote it one lane up, repeat). No
balancing, no rotations — just probability, which makes the levels geometrically sparser and the
expected search O(log n).
"""
import random


class Node:
    __slots__ = ("value", "forward")

    def __init__(self, value, level):
        self.value = value
        self.forward = [None] * (level + 1)       # a forward pointer per level this node reaches


# region: skiplist
class SkipList:
    """A skip list over comparable values. `level` is the current highest lane in use; `header` is a
    sentinel reaching every lane. p = 0.5 means each element is promoted to the next lane with
    probability 1/2, so lane heights are geometric and the structure is O(log n) tall in expectation."""

    def __init__(self, max_level=16, p=0.5):
        self.max_level = max_level
        self.p = p
        self.header = Node(None, max_level)
        self.level = 0

    def _random_level(self):
        """Flip coins: keep promoting to a higher lane while heads come up. Gives level 0 half the
        time, level 1 a quarter, level 2 an eighth, … — the geometric distribution that makes the
        express lanes exponentially sparser going up."""
        lvl = 0
        while random.random() < self.p and lvl < self.max_level:
            lvl += 1
        return lvl

    def search(self, value, trace=None):
        """Start in the top lane; at each lane move right while the next node is still < value, then
        drop down a lane. After dropping through the bottom lane, the next node is the answer (or a
        larger value / None if absent). O(log n) expected — each lane skips ~half the remaining span."""
        cur = self.header
        for i in range(self.level, -1, -1):
            while cur.forward[i] is not None and cur.forward[i].value < value:
                cur = cur.forward[i]              # move right along this express lane
                if trace is not None:
                    trace.append(("right", i, cur.value))
            if trace is not None:
                trace.append(("down", i, cur.value if cur.value is not None else "head"))
        cur = cur.forward[0]
        return cur is not None and cur.value == value

    def insert(self, value):
        """Insert, keeping every lane sorted. Walk down recording, at each lane, the last node before
        `value` (the `update` array — where new links must be spliced). Then coin-flip the new node's
        height and splice it into every lane up to that height. No rebalancing."""
        update = [self.header] * (self.max_level + 1)
        cur = self.header
        for i in range(self.level, -1, -1):
            while cur.forward[i] is not None and cur.forward[i].value < value:
                cur = cur.forward[i]
            update[i] = cur
        if cur.forward[0] is not None and cur.forward[0].value == value:
            return                                # already present — no duplicates
        lvl = self._random_level()
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.header           # new top lanes start from the header
            self.level = lvl
        node = Node(value, lvl)
        for i in range(lvl + 1):
            node.forward[i] = update[i].forward[i]
            update[i].forward[i] = node           # splice into lane i

    def delete(self, value):
        """Remove `value` by unlinking it from every lane it appears in, then trimming any now-empty
        top lanes."""
        update = [self.header] * (self.max_level + 1)
        cur = self.header
        for i in range(self.level, -1, -1):
            while cur.forward[i] is not None and cur.forward[i].value < value:
                cur = cur.forward[i]
            update[i] = cur
        target = cur.forward[0]
        if target is None or target.value != value:
            return False
        for i in range(self.level + 1):
            if update[i].forward[i] is target:
                update[i].forward[i] = target.forward[i]
        while self.level > 0 and self.header.forward[self.level] is None:
            self.level -= 1                       # trim empty top lanes
        return True
# endregion


# region: levels
def dump_levels(sl):
    """Return, for each lane, the list of values reachable in it — for drawing the express lanes."""
    lanes = []
    for i in range(sl.level, -1, -1):
        vals, cur = [], sl.header.forward[i]
        while cur is not None:
            vals.append(cur.value)
            cur = cur.forward[i]
        lanes.append((i, vals))
    return lanes
# endregion

"""The contrast and the reference. Two comparisons:

- `SortedLinkedList` is a plain sorted singly-linked list — the structure a skip list upgrades. Its
  search is O(n): no express lanes, you walk every node. It's the baseline that shows what the skip
  list's random levels buy, and (being obviously correct) a correctness reference.
- Python's `bisect` on a list, and the third-party `sortedcontainers`, are what you'd use in practice
  for a sorted collection; Redis sorted sets and LevelDB use skip lists internally for the same job.
  `bisect`-based membership is a second correctness oracle.

    import bisect
    i = bisect.bisect_left(sorted_list, x); present = i < len(sorted_list) and sorted_list[i] == x
"""


# region: linkedlist
class _LLNode:
    __slots__ = ("value", "next")

    def __init__(self, value):
        self.value = value
        self.next = None


class SortedLinkedList:
    """A sorted singly-linked list: search walks node by node until it reaches or passes the value —
    O(n). The skip list is this plus randomized express lanes. Used to count comparisons against the
    skip list's search."""

    def __init__(self):
        self.head = None

    def insert(self, value):
        node = _LLNode(value)
        if self.head is None or self.head.value >= value:
            if self.head is not None and self.head.value == value:
                return
            node.next = self.head
            self.head = node
            return
        cur = self.head
        while cur.next is not None and cur.next.value < value:
            cur = cur.next
        if cur.next is not None and cur.next.value == value:
            return
        node.next = cur.next
        cur.next = node

    def search(self, value):
        """Returns (found, comparisons) — the linear walk that skip lists improve on."""
        cur, comparisons = self.head, 0
        while cur is not None and cur.value < value:
            comparisons += 1
            cur = cur.next
        comparisons += 1
        return (cur is not None and cur.value == value), comparisons
# endregion

Desde cero vs librería

La lección de la skip list es que el azar puede sustituir a la astucia. Un árbol balanceado se gana su O(log n) con rotaciones deterministas y muchos casos manejados con cuidado; la skip list se gana la misma cota tirando volados y confiando en las probabilidades — y el resultado es código que puedes escribir bien sin una referencia abierta a un lado. Esa es una filosofía de diseño genuinamente distinta, y hace eco del filtro de Bloom del capítulo anterior (cambiar exactitud por espacio) y anticipa las ideas de reservoir sampling y algoritmos aleatorizados que vienen: introducir aleatoriedad a propósito, de tu lado y no del adversario, con frecuencia compra simplicidad, robustez ante entradas de peor caso y concurrencia sencilla, a costa de convertir una garantía de peor caso en una esperada abrumadoramente probable. La victoria de 1,500× del duelo sobre la lista ligada ordenada es lo que compran los carriles exprés; la comparación contra un árbol balanceado — mismo desempeño, código mucho más simple — es la razón por la que las skip lists están en Redis y LevelDB. En producción usarías sortedcontainers o lo que traiga integrado tu base de datos; construir la skip list tú mismo es lo que convierte "aleatorización en lugar de rotaciones" en una estructura que viste funcionar y no en un eslogan.

Dónde te la vas a encontrar

Las skip lists corren en sistemas muy usados precisamente por su simplicidad y por lo bien que se llevan con la concurrencia. Redis implementa sus sorted sets (ZSET) con una skip list, lo que impulsa leaderboards, colas de prioridad y consultas por rango en uno de los almacenes de datos más desplegados del mundo. LevelDB y RocksDB usan skip lists para sus memtables en memoria (el buffer de escritura antes de que los datos se vacíen a disco). La librería estándar de Java incluye ConcurrentSkipListMap y ConcurrentSkipListSet como sus colecciones ordenadas concurrentes escalables. Apache Lucene, HBase y varias bases de datos las usan para índices y estructuras en memoria. Aparecen en programación concurrente lock-free y wait-free como la estructura ordenada de cabecera, y en sistemas de redes y de consultas por rango donde hay que buscar datos ordenados y dinámicos bajo acceso concurrente. En cualquier lugar donde quisieras un árbol balanceado pero valoras más la simplicidad de implementación o la concurrencia sencilla que una garantía estricta de peor caso, una skip list es una elección común y excelente.

Puntos clave

Una skip list es una pila de listas ligadas ordenadas — un carril inferior completo más carriles exprés geométricamente más dispersos encima — donde la altura de cada elemento la fijan los volados, lo que da búsqueda, inserción y eliminación en O(log n) esperado sin rotaciones. La búsqueda avanza a la derecha por cada carril exprés y baja cerca del objetivo, la misma partición a la mitad que la búsqueda binaria; le ganó a una lista ligada ordenada por 1,500× con 100,000 elementos. Iguala el desempeño de los árboles balanceados con una fracción del código y una concurrencia muchísimo más fácil, cambiando una garantía de peor caso por una esperada abrumadoramente probable — y como la aleatoriedad es suya, ninguna entrada adversaria puede forzar mal desempeño. Es el ejemplo canónico de la aleatorización sustituyendo a la complejidad determinista.

El siguiente capítulo construye una estructura concreta y omnipresente combinando dos que ya conoces. Un cache LRU (least-recently-used) — la política de desalojo detrás de los caches de CPU, los caches web y los administradores de memoria de todo el mundo — necesita búsqueda en O(1) y seguimiento del orden de acceso en O(1), algo que ni una hash table ni una lista ligada dan por sí solas, pero su combinación sí: un hash map para búsqueda instantánea más una lista doblemente ligada para reordenamiento instantáneo, la composición clásica que convierte dos estructuras simples en exactamente la interfaz que un cache necesita.