Qué estructura de datos para qué problema

La mayoría del material sobre estructuras de datos está organizado por la estructura: aquí está el árbol, aquí está el heap, aquí están las operaciones.

Eso es útil para estudiar e inútil para decidir. En la práctica, tienes un problema, no una estructura. Este artículo invierte el orden.

"Necesito encontrar por clave exacta, muy rápido"#

Hash table. Tiempo constante para insertar, buscar y eliminar.

El coste: ningún orden. Pierdes rango, ordenación, menor, mayor, anterior y siguiente.

Y dos detalles que aparecen en producción: cuando la tabla se llena, se duplica y recalcula todo, lo que explica ese pico esporádico de latencia. Y la calidad de la función de hash importa: un hash malo concentra colisiones y degrada a tiempo lineal.

"Necesito rango, ordenación o vecinos"#

Árbol de búsqueda balanceado. Logarítmico para todo, y el orden sale gratis.

AVL está más rígidamente balanceado, mejor para lectura pesada. El rojo-negro es más flojo, con menos rotaciones en la escritura: es lo que usa la mayoría de las bibliotecas estándar.

Skip list es una alternativa elegante: listas enlazadas en varios niveles, con balanceo probabilístico. Rendimiento parecido al del árbol, implementación bastante más simple, y más fácil de hacer concurrente. Es lo que usa Redis en los sorted sets.

Y, en disco, la respuesta es B+tree, por los motivos del artículo anterior.

"Necesito siempre el menor (o el mayor)"#

Heap o cola de prioridad. Insertar y eliminar el extremo en tiempo logarítmico; mirar el extremo en tiempo constante.

Dónde aparece: planificador de tareas, algoritmo de Dijkstra, "los N mayores" de un flujo, timers del sistema.

Un detalle útil: para mantener los N mayores de un flujo gigante, usas un heap de tamaño N: memoria constante, independiente del tamaño del flujo.

"Necesito autocompletado o prefijo"#

Trie, el árbol de prefijos. Cada nodo es un carácter; los caminos compartidos ahorran espacio y la búsqueda por prefijo es natural.

El coste es memoria, y es significativo. Las variantes comprimidas (radix tree, árbol PATRICIA) resuelven parte de eso.

Dónde aparece: autocompletado, enrutamiento de IP, diccionario de palabras.

"Necesito saber si ya vi esto antes, con poca memoria"#

Filtro de Bloom. Responde "definitivamente no" o "quizás". Unos diez bits por elemento para un uno por ciento de falsos positivos.

El patrón mental: filtro barato antes de la operación cara. Antes de ir al disco, antes de llamar a la API, antes de consultar la caché remota.

Dónde aparece: LSM-tree, CDN, verificación de URL maliciosa en el navegador.

"Necesito contar cosas distintas a una escala absurda"#

HyperLogLog. Estima cardinalidad (cuántos valores únicos) con un error de alrededor del dos por ciento usando pocos kilobytes, sin importar si el conjunto tiene mil o mil millones de elementos.

Contar visitantes únicos de forma exacta exige guardar todos los identificadores. HyperLogLog cambia precisión por memoria, y para métrica de producto ese cambio casi siempre es bueno.

Count-Min Sketch es el primo: estima la frecuencia de cada elemento, también en espacio fijo. Sirve para encontrar los elementos más frecuentes de un flujo: los productos más vistos, las IP más activas.

Ambos sobrestiman y nunca subestiman, lo cual es una propiedad útil de conocer al interpretar el número.

"Necesito comparar dos conjuntos grandes y encontrar la diferencia"#

Árbol de Merkle. Un árbol de hashes, donde cada nodo es el hash de sus hijos. Comparando las raíces, sabes si algo cambió. Bajando por las ramas que divergen, encuentras exactamente qué, sin comparar todo.

Dónde aparece: sincronización entre réplicas en Cassandra y DynamoDB, Git, blockchain, sincronización de archivos.

"Necesito relaciones"#

Grafo, y la elección de la representación importa más de lo que parece.

Lista de adyacencia (cada nodo guarda sus vecinos): eficiente en memoria para grafos dispersos, que es el caso casi siempre. Es la opción por defecto.

Matriz de adyacencia: consulta "¿existe arista entre A y B?" en tiempo constante, y ocupa espacio cuadrático. Solo vale para grafos densos y pequeños.

"Necesito una cola de alto rendimiento entre hilos"#

Ring buffer: un array circular de tamaño fijo. Sin asignación, sin basura, y amigable con la caché del procesador porque la memoria es contigua.

Combinado con operaciones atómicas, permite una cola sin locks. Es la base del LMAX Disruptor, que procesaba millones de mensajes por segundo en un solo hilo.

1. Hash tableclave exactaTiempo constante. El coste es perder todo orden: rango, ordenación, anterior y siguiente.
2. Árbol balanceadorango y ordenLogarítmico para todo, y el orden sale gratis. En disco, se vuelve B+tree.
3. Heapel extremoEl menor o el mayor en tiempo constante. Los N mayores de un flujo caben en un heap de tamaño N.
4. TrieprefijoAutocompletado y enrutamiento de IP. El coste es memoria, y es significativo.
5. Filtro de Bloom¿ya vi esto?Definitivamente no, o quizás. Filtro barato antes de la operación cara.
6. HyperLogLogcuántos únicosCardinalidad con 2% de error en pocos kilobytes, sean mil o mil millones de elementos.
7. Árbol de Merklequé cambióCompara las raíces, baja solo por las ramas que divergen. Es Git y la sincronización de réplicas.

Lo que ya usas por debajo#

Vale la pena notar cuánto de esto ya está en tu día a día:

→ El diccionario de tu lenguaje es una hash table.

→ El índice de tu base de datos es un B+tree.

→ El sorted set de Redis es una skip list.

→ Git es un árbol de Merkle con hashes de contenido.

→ El enrutamiento de IP es una trie.

→ El planificador del sistema operativo usa heap o árbol.

→ Cassandra usa LSM-tree con filtro de Bloom y árbol de Merkle.

No vas a implementar casi ninguna de ellas. Pero conocer los nombres cambia la forma en que lees documentación, eliges herramienta y explicas una decisión.

La pregunta que resuelve entrevista, y proyecto#

Cuando alguien te pida elegir una estructura, la buena respuesta no empieza por el nombre. Empieza por tres preguntas:

1. ¿Qué operaciones son frecuentes? ¿Búsqueda por clave, por rango, inserción, eliminación, "el mayor"?

2. ¿Cabe en memoria, o va al disco? Eso cambia completamente el criterio.

3. ¿Necesito respuesta exacta, o una aproximación resuelve? Si la aproximación resuelve, las estructuras probabilísticas cambian el orden de magnitud del coste.

Respondidas esas tres, la estructura casi se elige sola. Y demuestras lo que de verdad importa: que sabes razonar sobre el compromiso, no solo recitar la O grande.