Cómo encontrar una cosa entre millones, y rápido

Guardar información también tiene forma, y a esa forma la llamamos recipiente. Los mismos datos toman una forma distinta según si los guardas como una fila, una tabla o una rama. No eliges cualquier recipiente; eliges el que encaja con la tarea. Para recorrer cosas en orden, una fila va bien; para encontrar algo por nombre rápido, una tabla va bien. Y ningún recipiente hace todo igual de bien. Algunas acciones son rápidas y otras lentas. Por eso elegir el recipiente correcto es el comienzo de un programa rápido. En las próximas lecciones conoceremos los recipientes principales uno por uno.

Un arreglo es un casillero donde las casillas numeradas van juntas, una al lado de otra. Das un número y saltas directo a esa casilla, sacandola muy rápido. Una lista son casillas esparcidas, cada una con una nota que guarda la dirección de la siguiente. Así que para llegar a la quinta debes seguir las notas desde el principio, casilla por casilla, lo cual es más lento. Pero para meter una casilla nueva en medio solo arreglas dos notas, así que es fácil. El arreglo, en cambio, tiene que empujar todas las casillas posteriores, lo cual es un fastidio. ¿Necesitas acceso rápido? Elige un arreglo; ¿insertas en medio a menudo? Elige una lista. Cambias una cosa por la otra.

Una pila es apilar platos. Pones uno encima, y al sacar uno, sale el de arriba (el último que metiste). Así que lo que entró al final sale primero. Una cola es hacer fila. Te pones al fondo, y al sacar uno, sale el de adelante (el que llegó primero). Así que lo que entró primero sale primero. ¿Dónde las usamos? Cuando quieres deshacer lo que acabas de hacer o retroceder, una pila encaja perfecto, porque la última acción se cancela primero, en orden. Cuando quieres atender con justicia por orden de llegada, una cola encaja, como una cola de impresión o un ticket numerado. Apilar es ultimo-primero, hacer fila es primero-primero, esa sola línea es todo lo que hay que recordar.

Una base de datos es un almacen gigante que guarda la informacion de forma ordenada. Normalmente la ordena en una tabla, donde una linea (una fila) es un registro y una ranura vertical (una columna) es un campo como el nombre o la edad. Cuando llega informacion nueva, va ordenada a la columna correcta de la tabla correcta. Se diferencia de simplemente escribir en un archivo en dos cosas. Una, guarda muchos datos a salvo de una vez. Dos, encuentra rapido el que quieres aun entre cientos de millones. Por eso, cuando manejas mucha informacion, usas una base de datos en vez de un archivo.

La forma más simple en que una base de datos encuentra algo es un escaneo completo: leer desde el principio, fila por fila, hasta el final. Cuando los datos son pocos, es bastante rápido. Pero cuando la cuenta explota a cientos de millones, hay muchas más filas que escanear, así que se vuelve lento. Por eso construimos un índice de antemano. Un índice es como una lista ordenada de etiquetas, así que en vez de escanear todo, saltas directo al lugar en uno o dos clics. Para la misma cuenta, un índice encuentra la respuesta en muchos menos pasos que un escaneo completo. Cómo se construyen los índices en realidad (índice, hash, árbol) continúa en las próximas lecciones.

Hashing decide un número de casilla a partir del valor con un cálculo, y luego mete y halla justo en esa casilla. Llega en un paso en vez de recorrer casilla por casilla, así que es muy rápido. Se usa el mismo cálculo al meter y al buscar, así la casilla donde guardaste coincide con la que buscas. También hay un pero. Dos valores distintos pueden dar el mismo número e ir a la misma casilla, una colisión. Entonces lo resolvemos aparte, juntándolos en una casilla o empujando uno a la casilla vecina. En resumen, hashing decide la casilla por cálculo para hallarla de una, y resuelve las colisiones por separado.

En vez de poner los datos en una sola fila larga, dales forma de arbol: desde una raiz se divide en ramas y baja. Si tu objetivo es mayor que el sitio actual, vas por una rama; si es menor, por la otra. Asi cada paso hacia abajo reduce a la mitad los candidatos a revisar. Por eso, incluso miles se encuentran en pocos pasos. El numero de pasos, la profundidad del arbol, marca la velocidad. Cuando los datos se duplican, la profundidad crece solo un paso, asi que aun con muchisimos se hace mas profundo despacio. Es igual que abrir un diccionario por el medio y reducir a la mitad.

Un arbol es rapido cuando encuentra cosas partiendo por la mitad a lo largo de sus ramas. Pero si insertas valores solo en orden, las ramas nunca se dividen y crecen largas por un lado, volviendose casi una sola linea y haciendose lentas. Un arbol equilibrado evita esto. Cuando un lado se pone pesado al insertar o borrar, vuelve a colocar los nodos por si mismo, lo que llamamos una rotacion. Al mantener ambos lados con una profundidad parecida mediante rotaciones, la profundidad crece despacio (log) por mucho que se acumulen los datos. Asi siempre garantiza encontrar algo en unos pocos pasos. Solo tenemos que insertar y quitar, y el arbol cuida su equilibrio por su cuenta.

Cuando hay muchos datos, recorrerlos desde el inicio es lento. Un indice es como la busqueda al final del libro, un mapa hecho de antemano para que la base de datos salte directo al lugar correcto. Hay dos tipos. Un indice hash localiza un valor exacto de un solo paso. Un indice de arbol mantiene los valores ordenados, asi que va bien para recorrer un rango. Pero no es gratis. Un indice ocupa espacio extra, y cuando los datos cambian el indice tambien hay que actualizarlo. Aun asi, bien usado, hace las busquedas mucho mas rapidas.

Un grafo guarda las cosas como puntos y las relaciones entre ellas como líneas. Pon a las personas como puntos y las amistades como líneas, y las conexiones se ven de un vistazo. Desde un punto, seguir una línea da un vecino, y seguir la línea del vecino da al amigo de un amigo. Extendiéndote por las líneas así, puedes recorrer todo un grupo conectado. Para tareas donde la relación es lo central, como recomendar o hallar conexiones, lo que una tabla te haría buscar una y otra vez, un grafo lo alcanza con solo seguir líneas. En resumen, los puntos son cosas, las líneas son relaciones, y sigues a los vecinos. Eso es un grafo.

SQL es el lenguaje con que le preguntas a una base de datos para obtener lo que quieres. Solo dices dos cosas. Primero eliges qué columnas mirar. Una tabla tiene muchas columnas y conservas solo las que quieres ver. Esto se llama SELECT. Luego pones una condición sobre qué filas conservar. No todas las filas, solo las que cumplen la condición. Esto se llama WHERE. Cuando las columnas elegidas se encuentran con las filas conservadas, sale una pequeña tabla de resultado que encaja con la condición exactamente. Tomar una tabla y preguntar eligiendo columnas y filtrando filas, y recibir la respuesta como una tabla, eso es lo básico de SQL.

Los datos suelen estar repartidos en varias tablas. Los pedidos en una tabla de pedidos, la info de personas en una de clientes, aparte. Mirar una sola tabla no responde preguntas que cruzan tablas. Por eso buscamos una columna común que ambas comparten, como el número de cliente. Emparejar filas cuyo valor en esa columna es igual enlaza las dos tablas en una línea. Enlazadas así, se tratan como una tabla y responden preguntas como el nombre detrás de un pedido. En resumen, un join enlaza tablas dispersas emparejando filas por una columna común.

La normalización es el ordenamiento donde tomas la información que se repite en una tabla, la separas en otra tabla y las vuelves a enlazar por una columna común. En vez de escribir el nombre del cliente en cada pedido, escribe el cliente una sola vez en una tabla de clientes y deja solo un número de cliente en la tabla de pedidos. Así, si el número cambia, corriges una fila en la tabla de clientes y listo, sin que surja ningún desajuste. Tampoco se olvida una fila dispersa al corregirlas una por una. Pero si separas demasiado fino, cada vez que miras algo debes volver a unir muchas tablas, lo que puede ser lento. Entonces a veces fusionas a propósito la información que se ve junta a menudo en una sola tabla, lo que se llama desnormalización. Al final, la normalización es el equilibrio de separar repeticiones y enlazar por relación, fusionando de nuevo cuando se separa demasiado fino.

Una transaccion trata varios cambios como un solo paquete para que ocurran todos o ninguno. Cuando una resta y una suma son un par, como en una transferencia, solo cuando ambas terminan se aplica de verdad. Si la luz se corta o algo sale mal a medias, no deja la mitad hecha sino que revierte todo al estado anterior. Esto se llama rollback. Y cuando varias personas intentan cambiar el mismo saldo a la vez, las atiende una por una para que no se sobrescriban. El enredo del todo a la vez se vuelve una fila ordenada. En resumen: todo o nada, rollback ante un tropiezo, y sin enredos aun a la vez. Estas tres cosas son la transaccion.

Caching guarda una copia de los datos de uso frecuente en un sitio cercano. Un almacén lejano es lento porque el viaje de ida y vuelta es largo. Pero con una copia cerca, desde entonces la sacas por un camino corto al instante. Si lo que quieres está en la cache, lo llamamos acierto y lo traes rápido. Si no, lo llamamos fallo, vas hasta el sitio lejano, lo traes, y dejas esa copia en la cache. Así la próxima vez es un acierto. También hay un pero. Aunque el original cambie, la copia vieja sigue en la cache y puede entregar un valor viejo. Decimos que la cache quedó obsoleta. Por eso de vez en cuando rellenamos la cache o la descartamos tras un tiempo, para frenar los valores viejos. En resumen, guarda una copia cerca para que el acierto sea rápido, y refresca la cache cuando el original cambia, eso es caching.

La compresión es el arte de guardar la misma información en menos espacio. Hay dos habilidades. Una es recortar la repetición. Cuando lo mismo se alarga como AAAA, escribir A cuatro veces lo acorta. La otra es dar un código corto a un trozo que aparece a menudo. Cambiar un trozo largo por un símbolo corto encoge el conjunto. Y una copia comprimida, al deshacerla, es exactamente el original; nada se tiró. Esto se llama sin pérdida. Comprime más fuerte y queda más pequeño, pero comprimir y descomprimir lleva más tiempo. Así que negocias entre cuán pequeño y cuán rápido. En resumen, recorta la repetición y da códigos cortos para guardarlo pequeño, mientras que deshacerlo devuelve el original; eso es la compresión.

Cuando los datos crecen demasiado para una maquina, los cortas en piezas y los repartes entre varias. Esto se llama distribucion, o sharding. Cada maquina guarda solo parte del todo, asi que juntas pueden guardar datos muy grandes. Y para que nada se rompa cuando una maquina muere, copias los mismos datos en varias maquinas. Esto se llama replicacion. La distribucion, que reparte, y la replicacion, que copia, son ideas distintas. La distribucion trocea la carga y la reparte; la replicacion guarda la misma carga en varios sitios. Para este manejo enorme y rapido, un contenedor que afloja la forma estricta de la tabla se llama NoSQL. Es como una version mucho mayor del contenedor de hash que mete y halla un valor directo por su clave, asi que se vuelve un puente hacia los datos enormes que maneja la siguiente area, la inteligencia artificial.