El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Búsqueda y Ordenación en Grandes Volúmenes de Datos

Siguiente ►
►

Tercer caso de estudio. En 06-01 el reto era encadenar algoritmos; en 06-02, modelar un dominio nuevo; aquí el reto es el tamaño: Rutalia lleva años operando y ha acumulado 200 millones de registros históricos de entregas (~40 GB) que Dirección quiere consolidar y analizar. Los algoritmos de búsqueda y ordenación del módulo 4 siguen siendo la base, pero hay un supuesto silencioso que se rompe: que los datos caben en RAM y que acceder a un elemento cuesta lo mismo que a cualquier otro. Cuando eso deja de ser cierto, la variable que gobierna el diseño ya no es el número de comparaciones sino el número de accesos a disco, y de ese cambio de moneda nacen la ordenación externa, los árboles B, MapReduce y las estructuras probabilísticas que veremos aquí.

Contenido

  1. Cuando los datos no caben en RAM: la jerarquía de memoria
  2. Ordenación externa: runs ordenados + mezcla k-vías
  3. Índices: por qué las bases de datos no hacen búsqueda binaria
  4. MapReduce: el paradigma divide-agrupa-combina
  5. Estructuras probabilísticas: el filtro de Bloom y sus primos
  6. Top-K en streaming: los 10 códigos postales con más entregas
  7. El caso completo: el plan para los 200 millones de registros

Cuando los datos no caben en RAM: la jerarquía de memoria

Todo el análisis de complejidad del curso (01-01, 01-02) contaba operaciones asumiendo coste uniforme de acceso a memoria. La realidad del hardware es una jerarquía con saltos de varios órdenes de magnitud:

Nivel Latencia aproximada En escala humana (1 ns = 1 s)
Caché L1 ~1 ns 1 segundo
RAM ~100 ns ~2 minutos
SSD (lectura aleatoria) ~100 µs ~28 horas
Disco magnético (seek) ~10 ms ~4 meses
Red entre centros de datos ~50-150 ms años

Dos consecuencias de diseño que explican todo lo que sigue:

  • Un acceso a disco vale ~1000-100 000 accesos a RAM. Un algoritmo con más comparaciones pero menos lecturas de disco gana. La complejidad relevante pasa a medirse en operaciones de E/S (modelo de memoria externa).
  • El acceso secuencial a disco es enormemente más barato que el aleatorio (el disco/SSD sirve bloques contiguos a gran velocidad). Los buenos algoritmos externos leen y escriben en flujos secuenciales de bloques grandes, nunca saltando de registro en registro.

Con esta moneda nueva, revisitemos las dos operaciones del módulo 4.

Ordenación externa: runs ordenados + mezcla k-vías

¿Cómo ordenas 40 GB con 1 GB de RAM? El algoritmo clásico, external merge sort, es mergesort (04-02) repensado para minimizar E/S, y reutiliza dos piezas que ya tienes:

  1. Fase 1 — generar runs: lee el fichero en trozos que quepan en RAM, ordena cada trozo en memoria (Timsort, 04-02) y escríbelo como un fichero temporal ya ordenado (un run). Con 1 GB de RAM y 40 GB de datos: 40 runs.
  2. Fase 2 — mezcla k-vías: mezcla los 40 runs en una sola pasada con un heap (01-04), exactamente la mezcla k-vías que hiciste con heapq.merge en 04-02: en cada momento solo necesitas en RAM el "frente" de cada run.

Cada fase lee y escribe los datos una vez: 2 pasadas completas ≈ 4·N/B operaciones de E/S (N datos, B tamaño de bloque), frente a las ~N·log₂N lecturas aleatorias de un quicksort ingenuo sobre disco, que sería miles de veces más lento. Simulémoslo con ficheros de verdad a pequeña escala:

import heapq
import os
import random
import tempfile

random.seed(3)
dir_trabajo = tempfile.mkdtemp()

# --- Datos: 100.000 "registros de entrega" (id_num;minutos) desordenados ---
crudo = os.path.join(dir_trabajo, "entregas.txt")
with open(crudo, "w") as f:
    for i in random.sample(range(100_000), 100_000):
        f.write(f"{i};{random.randint(5, 120)}\n")

MEMORIA = 10_000   # registros que "caben en RAM" (simulado)

# --- Fase 1: generar runs ordenados ---
def generar_runs(fichero, memoria):
    runs = []
    with open(fichero) as f:
        while True:
            trozo = [linea for _, linea in zip(range(memoria), f)]
            if not trozo:
                break
            trozo.sort(key=lambda l: int(l.split(";")[0]))   # Timsort, en RAM
            ruta = os.path.join(dir_trabajo, f"run_{len(runs)}.txt")
            with open(ruta, "w") as out:
                out.writelines(trozo)
            runs.append(ruta)
    return runs

# --- Fase 2: mezcla k-vías con heap ---
def mezclar_runs(runs, salida):
    ficheros = [open(r) for r in runs]
    # Cada run se envuelve en un GENERADOR de (clave, línea):
    # en RAM solo vive una línea de cada run a la vez (el frente del heap)
    def con_clave(f):
        for linea in f:
            yield (int(linea.split(";")[0]), linea)
    with open(salida, "w") as out:
        for _, linea in heapq.merge(*(con_clave(f) for f in ficheros)):
            out.write(linea)
    for f in ficheros:
        f.close()

runs = generar_runs(crudo, MEMORIA)
print(f"Generados {len(runs)} runs de <= {MEMORIA} registros")
ordenado = os.path.join(dir_trabajo, "entregas_ordenado.txt")
mezclar_runs(runs, ordenado)

# Verificación: el fichero final está ordenado
with open(ordenado) as f:
    claves = [int(l.split(";")[0]) for l in f]
print("¿Ordenado?", all(claves[i] <= claves[i+1] for i in range(len(claves)-1)))

Fíjate en que con_clave(f) es un generador, no una lista: si materializaras cada run con list(f) volverías a meter todos los datos en RAM y el algoritmo perdería su razón de ser. La disciplina de "todo en flujos" es la mitad del trabajo en algoritmos externos.

Puntos finos del algoritmo real:

  • ¿Y si hay demasiados runs? Con RAM para k frentes de run, la mezcla admite k flujos. Si salen más de k runs, se mezcla en varias rondas (mezclas de k en k): el número de pasadas es ⌈log_k(nº runs)⌉ — logarítmico con base enorme (k suele ser cientos o miles), así que en la práctica 2-3 pasadas bastan para casi cualquier tamaño.
  • Este es, literalmente, el algoritmo que ejecutan las bases de datos en un ORDER BY que no cabe en memoria, y la pieza central de la fase shuffle de MapReduce (siguiente sección).

Índices: por qué las bases de datos no hacen búsqueda binaria

Ya tienes los datos ordenados en disco. ¿Buscar un registro con búsqueda binaria (04-01)? Correcto en comparaciones (log₂ de 200 millones ≈ 28), desastroso en E/S: 28 lecturas aleatorias de disco, cada una a una posición imprevisible. Y peor: mantener un array ordenado en disco ante inserciones diarias es inviable (desplazar millones de registros por cada inserción, como viste al analizar la inserción en arrays en 01-02).

La solución de las bases de datos es el árbol B (y su variante B+): la generalización a disco del árbol binario de búsqueda que conociste en 01-04.

  • Cada nodo ocupa un bloque de disco (4-16 KB) y contiene cientos de claves ordenadas, no una.
  • Un nodo con m claves tiene m+1 hijos: el árbol es bajísimo. Con ramificación ~500, 200 millones de claves caben en altura 3-4.
  • Buscar = leer 3-4 bloques (y la raíz y el segundo nivel viven cacheados en RAM: a menudo 1-2 lecturas reales). Dentro de cada bloque sí se hace búsqueda binaria (04-01) — pero eso es CPU, que es gratis comparado con la E/S.
  • El árbol se mantiene equilibrado por construcción (los nodos se parten al llenarse), con inserciones y borrados en O(log n) bloques.
flowchart TD
    R["raíz: [P-08M | P-95M]<br>1 bloque, en RAM"] --> A["[P-01M ... P-07M]"]
    R --> B["[P-09M ... P-90M]"]
    R --> C["[P-96M ... P-200M]"]
    B --> H1["hoja: registros<br>P-42.000.000 ..."]
    B --> H2["hoja: ..."]
    B --> H3["hoja: ..."]

La comparación completa, conectando con 01-04 y 04-01:

Estructura Búsqueda exacta Búsqueda por rango Inserciones Coste en E/S (búsqueda)
Array ordenado + búsqueda binaria (04-01) O(log n) excelente O(n) — inviable ~28 lecturas aleatorias
Árbol binario equilibrado (01-04) O(log n) buena O(log n) ~28 (un nodo por bloque desaprovechado)
Árbol B/B+ O(log n) excelente (hojas enlazadas) O(log n) 3-4 lecturas, 1-2 en la práctica
Índice hash (01-04) O(1) no soporta rangos O(1) amortizado 1-2 lecturas

Regla de decisión: consultas de igualdad pura y a máxima velocidad → hash; rangos, ordenación, prefijos (WHERE fecha BETWEEN ...) → árbol B. Por eso el índice por defecto de casi todas las bases de datos relacionales es un B+; los índices hash existen pero son el caso especial. Es la misma disyuntiva hash-vs-árbol de 01-04, decidida ahora por la moneda de E/S y por el patrón de consultas.

MapReduce: el paradigma divide-agrupa-combina

Cuando ni siquiera un disco basta —o una máquina tarda demasiado—, se reparte el trabajo entre muchas. MapReduce (Google, 2004) impuso una disciplina simple: si expresas tu cálculo como dos funciones puras, el framework se encarga de distribuir, reintentar fallos y mover datos.

  • map(registro) → lista de (clave, valor): se aplica a cada registro en paralelo, en la máquina donde ya viven los datos.
  • shuffle (lo hace el framework): agrupa todos los valores de la misma clave — internamente, una ordenación externa distribuida como la de la sección 2.
  • reduce(clave, valores) → resultado: combina los valores de cada clave, en paralelo por clave.

El "hola mundo" es contar palabras; nuestro caso es idéntico con otra clave: total de entregas y retraso medio por zona sobre el histórico. Simulamos el paradigma en Python para ver el flujo de datos (el valor real aparece con cientos de máquinas, pero el contrato es este):

from collections import defaultdict

# Registros históricos ficticios: (id_pedido, zona, minutos_entrega)
registros = [
    ("P-001", "ALM", 22), ("P-002", "CEN", 35), ("P-003", "ALM", 41),
    ("P-004", "UNI", 18), ("P-005", "CEN", 52), ("P-006", "ALM", 30),
]   # ... imagina 200 millones de estos

def map_fn(registro):
    _, zona, minutos = registro
    return [(zona, minutos)]                 # clave = zona

def reduce_fn(zona, valores):
    return {"zona": zona, "entregas": len(valores),
            "min_medio": sum(valores) / len(valores)}

# --- Lo que haría el framework ---
# 1) map en paralelo sobre trozos del fichero
intermedios = [par for r in registros for par in map_fn(r)]
# 2) shuffle: agrupar por clave (= ordenación externa distribuida)
grupos = defaultdict(list)
for clave, valor in intermedios:
    grupos[clave].append(valor)
# 3) reduce en paralelo por clave
resultado = [reduce_fn(z, vs) for z, vs in grupos.items()]
print(resultado)

Por qué esto escala y qué exige a cambio:

  • Escala porque map y reduce son independientes por registro/clave: añadir máquinas divide el tiempo casi linealmente, y el único punto de contacto (el shuffle) es una ordenación externa, problema ya resuelto.
  • Exige que las funciones sean puras y las operaciones de reduce asociativas en la práctica (poder combinar parciales). Contar, sumar, max, medias (como suma+conteo): perfecto. Algoritmos con estado global fuertemente acoplado: mal encaje.
  • El heredero moderno es Apache Spark, que generaliza el modelo (cadenas de map/filter/reduce/join manteniendo datos en RAM entre pasos) — pero el modelo mental divide-agrupa-combina es el mismo, y saber reconocer cuándo tu cálculo lo admite es la habilidad transferible.

Como siempre en este curso: divide y vencerás (01-03, 04-02) no era solo un truco de recursión; a esta escala es una arquitectura.

Estructuras probabilísticas: el filtro de Bloom y sus primos

A veces la pregunta no exige exactitud. "¿He visto ya este id de pedido?" sobre 200 millones de ids exige un set de varios GB… salvo que aceptes una probabilidad pequeña y controlada de falso positivo. El filtro de Bloom ofrece exactamente ese trato: memoria ~10 bits por elemento (¡independiente del tamaño de los ids!) a cambio de que "sí lo he visto" sea a veces mentira — "no lo he visto" es siempre verdad.

Mecánica: un array de m bits y k funciones hash (la herramienta de 01-04). Insertar x: poner a 1 los k bits hash_i(x) % m. Consultar x: si alguno de sus k bits es 0, seguro que no está; si los k son 1, probablemente está (pudieron encenderlos otros elementos — ese es el falso positivo).

import hashlib

class FiltroBloom:
    def __init__(self, m_bits, k_hashes):
        self.m, self.k = m_bits, k_hashes
        self.bits = bytearray(m_bits // 8 + 1)

    def _posiciones(self, item):
        # k hashes a partir de un solo digest (técnica del doble hash)
        d = hashlib.sha256(item.encode()).digest()
        h1 = int.from_bytes(d[:8], "big")
        h2 = int.from_bytes(d[8:16], "big") | 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def agregar(self, item):
        for p in self._posiciones(item):
            self.bits[p // 8] |= 1 << (p % 8)

    def contiene(self, item):
        return all(self.bits[p // 8] >> (p % 8) & 1
                   for p in self._posiciones(item))

# ¿Hemos procesado ya este pedido? (deduplicación en ingesta)
bloom = FiltroBloom(m_bits=1_000_000, k_hashes=7)   # ~122 KB para 100k items
for i in range(100_000):
    bloom.agregar(f"P-{i:09d}")

print(bloom.contiene("P-000000042"))    # True (está)
falsos = sum(bloom.contiene(f"X-{i:09d}") for i in range(100_000))
print(f"Falsos positivos: {falsos / 100_000:.4%}")   # típicamente < 1 %

Con m/n = 10 bits por elemento y k ≈ 7, la tasa de falsos positivos teórica es ≈ (1 − e^(−kn/m))^k ≈ 0,8 % — y el experimento lo confirma. Uso canónico: filtro barato delante de un recurso caro (¿consulto la base de datos por este id? solo si el Bloom dice "quizá"), eliminando de golpe la inmensa mayoría de búsquedas de elementos inexistentes.

La familia completa, para reconocerlas cuando aparezcan:

Estructura Pregunta que responde Error Memoria típica
Filtro de Bloom ¿pertenece x al conjunto? falsos positivos (nunca negativos) ~10 bits/elemento
HyperLogLog ¿cuántos elementos distintos he visto? (clientes únicos del año) ±2 % en el conteo ~1,5 KB total, para miles de millones
Count-min sketch ¿cuántas veces ha aparecido x? (frecuencias aproximadas) sobreestima, nunca infraestima KBs, fijo

El patrón común: cambiar exactitud por memoria, con el error acotado matemáticamente. Es la misma filosofía de las heurísticas del módulo 2 —renunciar al óptimo con criterio—, aplicada ahora al espacio en vez de al tiempo.

Top-K en streaming: los 10 códigos postales con más entregas

Última pieza: "los 10 códigos postales con más entregas del histórico". El reflejo de ordenar los ~10 000 códigos postales por conteo funciona, pero es un caso particular de un patrón que merece nombre, porque aparece constantemente con streams: para un top-K no hace falta ordenar todo — mantén un min-heap de tamaño K (01-04, y la misma jugada de la mezcla k-vías de 04-02):

import heapq
from collections import Counter

# Fase 1 (una pasada, O(1) por registro): contar por clave
conteos = Counter()
def procesar(registro):
    _, cp = registro
    conteos[cp] += 1

# ... tras procesar el stream completo ...
conteos = Counter({f"CP-{i:05d}": random.randint(1, 1_000_000)
                   for i in range(10_000)})   # simulación

# Fase 2: top-10 con un min-heap de tamaño 10 — O(n log K), no O(n log n)
top10 = heapq.nlargest(10, conteos.items(), key=lambda kv: kv[1])
for cp, c in top10:
    print(cp, c)

heapq.nlargest hace por dentro lo que harías a mano: recorre los n conteos manteniendo un min-heap con los K mejores vistos; si el nuevo supera al mínimo del heap, lo sustituye. Coste O(n log K) con memoria O(K) — con K=10 y n=10 000, unas 15 veces menos comparaciones que ordenar, y la diferencia crece con n. Y si ni siquiera los conteos exactos caben (claves de cardinalidad brutal, como una clave por cliente), se combina con el count-min sketch de la tabla anterior: conteos aproximados + heap top-K exacto sobre ellos.

El caso completo: el plan para los 200 millones de registros

Cerremos el caso de Rutalia con el plan de ingeniería, pieza a pieza:

Necesidad de negocio Solución Sección / lección
Consolidar los ficheros históricos por fecha External merge sort (runs + mezcla k-vías) §2, 04-02, 01-04
Deduplicar pedidos en la ingesta Filtro de Bloom delante de la comprobación exacta §5
Buscar cualquier pedido por id o por rango de fechas Árbol B+ (id) — o hash si solo hubiera igualdad §3, 01-04, 04-01
Entregas y retraso medio por zona Agregación divide-agrupa-combina (Spark en real) §4
Clientes únicos por trimestre HyperLogLog §5
Los 10 CP con más entregas Counter + min-heap top-K §6

Nada de esta tabla es un algoritmo nuevo: es el módulo 1 y el módulo 4 recotizados en la moneda de la E/S. Y las salidas de este pipeline no son un fin: la tabla de agregados por zona es exactamente el tipo de dataset del que salieron los perfiles de demanda de 05-05 y las matrices de coste de 06-01 — el big data de hoy alimenta la optimización y el ML de mañana.

Errores Comunes y Consejos

  • Contar comparaciones cuando la moneda es la E/S. Un algoritmo "óptimo" en RAM puede ser miles de veces más lento en disco que uno secuencial "peor". Pregunta siempre: ¿cuántas pasadas sobre los datos hago y cuánto acceso aleatorio?
  • Materializar generadores. list(fichero) sobre 40 GB mata el proceso. En pipelines de datos, todo lo que pueda ser generador/iterador debe serlo — la mezcla k-vías funciona precisamente porque solo el frente de cada run vive en RAM.
  • Usar un filtro de Bloom donde los falsos positivos son inaceptables. "Probablemente lo he visto" está bien para saltarse una consulta cara; está mal para decidir que un pago está duplicado y rechazarlo. El Bloom filtra, la verificación exacta decide.
  • Dimensionar el Bloom a ojo. La tasa de error depende de m/n y k; si insertas 10 veces más elementos de los previstos, el filtro se satura y dice "sí" a casi todo. Calcula m para la n máxima esperada.
  • Ordenar todo para un top-K. O(n log n) y memoria O(n) donde bastaban O(n log K) y O(K). Con streams, además, ordenar es directamente imposible: el heap es la herramienta.
  • Consejo: antes de distribuir (Spark, clúster), agota la máquina única — un buen external sort y un buen índice en una sola máquina resuelven volúmenes sorprendentemente grandes con una fracción de la complejidad operativa.

Ejercicios

  1. Pasadas de mezcla. Tienes 25 000 runs tras la fase 1 y RAM para mezclar k = 50 flujos a la vez. ¿Cuántas rondas de mezcla necesitas y cuántas pasadas completas de lectura/escritura sobre los datos supone (contando la fase 1)? ¿Y si duplicas la RAM (k = 100)?
  2. Dimensiona un filtro de Bloom para 200 millones de ids de pedido con una tasa de falsos positivos objetivo del 1 %. Usa las aproximaciones m ≈ −n·ln(p)/(ln 2)² y k ≈ (m/n)·ln 2. ¿Cuánta memoria es en MB y cuántos hashes k usas? Compárala con un set de Python de esos 200 millones de strings (estima ~100 bytes por entrada).
  3. Mediana aproximada en una pasada. Los 200 millones de minutos_entrega (enteros 0-300) no caben en RAM, pero quieres la mediana exacta. Diseña un método de una sola pasada con memoria O(1) respecto a n. Pista: la clave está en el rango de los valores, y ya viste la idea en counting sort (04-02).

Soluciones

  1. Cada ronda divide el número de runs entre k: 25 000 → 500 → 10 → 1, es decir 3 rondas (⌈log₅₀ 25 000⌉ = 3). Pasadas completas: 1 (fase 1) + 3 (mezclas) = 4 pasadas de lectura+escritura. Con k = 100: 25 000 → 250 → 3 → 1, siguen siendo 3 rondas (⌈log₁₀₀ 25 000⌉ = 3, aunque por muy poco: con 10 000 runs habrían bastado 2). Moraleja: k grande aplana el logaritmo rapidísimo; la RAM invertida en anchura de mezcla se amortiza entera.
  2. m ≈ −2·10⁸ · ln(0,01) / (ln 2)² ≈ 2·10⁸ · 4,605 / 0,4805 ≈ 1,92·10⁹ bits ≈ 229 MB, con k ≈ (m/n)·ln 2 ≈ 9,6·0,693 ≈ 7 hashes. El set exacto: 200 M × ~100 B ≈ 20 GB. El Bloom usa ~85 veces menos memoria a cambio de un 1 % de "quizá" que resuelves consultando el almacén exacto solo en esos casos.
  3. Como los valores viven en un rango pequeño y discreto (0-300), mantén un histograma de 301 contadores (la tabla de counting sort de 04-02) y actualízalo en una pasada: O(1) de memoria respecto a n. Al final, recorre acumulando hasta superar n/2: ese valor es la mediana exacta (y de paso tienes cualquier percentil). La lección: "no cabe en RAM" se refiere a los registros; a veces el resumen suficiente de los datos es diminuto — reconocerlo evita desplegar un clúster para un problema de 301 enteros.

Conclusión

Has visto qué les pasa a los algoritmos del módulo 4 cuando los datos desbordan la RAM: la moneda cambia de comparaciones a operaciones de E/S, y de ese cambio salen el external merge sort (Timsort + mezcla k-vías con heap, 04-02 y 01-04, aplicados a ficheros), los árboles B (el árbol de búsqueda de 01-04 engordado al tamaño de un bloque de disco), el paradigma divide-agrupa-combina de MapReduce/Spark (divide y vencerás como arquitectura), y las estructuras probabilísticas —con el filtro de Bloom implementado— que compran memoria a cambio de un error acotado, más el top-K en streaming con heap. El caso de los 200 millones de registros de Rutalia quedó resuelto con una tabla de decisiones, no con fuerza bruta. Y esos agregados no son el final del camino: son la materia prima de los modelos del módulo 5. Justamente ahí va la última lección del módulo: qué pasa cuando esos modelos de aprendizaje automático salen del notebook y entran en producción — drift, monitorización, fallos célebres y las obligaciones éticas de decidir sobre personas.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados