Cómo encuentra las cosas una base de datos

Al principio busca fila por fila

Antes aprendimos que una base de datos
se ordena en filas, como una tabla.
La forma más simple de encontrar algo
dentro de ella es esta.
Empieza por la fila de arriba y baja,
una fila a la vez, revisando cada una.
Cuando das con una fila que coincide, paras.
Mirar desde el principio hasta el final
así se llama un escaneo completo.

Toca el valor que quieres encontrar. Escanea hacia abajo una celda a la vez y cuenta cuántas revisó para llegar.

Un valor cerca de arriba
se encontró en pocas revisiones.
Pero un valor cerca del fondo
se alcanzó solo tras pasar todos los de arriba.
Si el valor está al final del todo,
acabas mirando cada fila.
Cuando hay pocas filas, incluso esto
es bastante rápido y no da problema.
Entonces, ¿qué pasa cuando las filas crecen muchísimo?

Cuando los datos explotan, escanear se vuelve lento

Una base de datos real
tiene una cantidad enorme de filas.
Millones, incluso cientos de millones, son comunes.
Para hallar el último valor, un escaneo completo
debe mirar cada una de esas filas.
Así que si las filas se duplican,
el número de revisiones también se duplica.
A medida que crecen las filas,
el costo de buscar crece junto a ellas.
Este es el límite de un escaneo completo.

Haz clic para aumentar la cantidad de filas. La barra muestra cómo trepan las revisiones para hallar el último valor con escaneo completo.

Cuanto más aumentas la cuenta,
más se disparó la barra hacia arriba.
Lo que era trivial en una tabla pequeña
se vuelve una carga pesada en una grande.
Mientras escanees de principio a fin cada vez,
este costo no se puede evitar.
Entonces, ¿hay una forma de ir directo
al lugar sin escanear nada?
Por suerte, hay una forma lista.

Construye un índice y salta directo

Imagina el índice al final de un libro.
Las palabras están ordenadas,
con el número de página al lado de cada una.
En vez de hojear todo el libro,
señalas una palabra en el índice
y abres directo a esa página.
Una base de datos también puede construir
tal lista de antemano.
La llamamos un índice.

Toca una etiqueta en el índice ordenado. Sin escanear la tabla, saltas directo a esa fila en uno o dos clics.

Al señalar el índice,
fuiste directo sin escanear la tabla.
Incluso un valor al final del todo
tomó solo un clic o dos.
El secreto es que el índice
se mantiene bien ordenado de antemano.
Cuando está ordenado, puedes estrechar rápido
y señalar más o menos dónde está.
La necesidad de mirar todo desapareció.

Compara escaneo completo e índice

Pongamos los dos métodos lado a lado
y comparémoslos con la misma cuenta.
Un escaneo completo debe revisar
tantas veces como filas haya.
Un índice usa el orden
y termina en muy pocas revisiones.
Incluso con la misma cuenta, el resultado
es la diferencia entre el cielo y la tierra.
Así que para datos que buscas a menudo,
vale la pena construir un índice.

Elige una cuenta y ejecuta ambas búsquedas. Compara lado a lado cuántas revisiones tomó cada uno, el escaneo completo y el índice, para hallar el mismo valor.

Cuanto más aumentaste la cuenta,
la barra del escaneo completo se disparó,
pero la barra del índice quedó casi plana.
Es justo esta brecha
la que hace brillar al índice en datos grandes.
Claro que un índice no es gratis.
Cuesta esfuerzo construirlo de antemano
y mantenerlo ordenado.
Aun así, si buscas a menudo, vale lo que cuesta.

Resumamos

Reunido en una línea, es esto.
La búsqueda más simple es un escaneo completo,
es decir, escanear todas las filas desde el principio.
Si los datos son pocos, basta.
Pero cuando explota a cientos de millones,
el costo de escanear trepa de golpe.
Por eso construimos un índice de antemano
y saltamos directo en uno o dos clics.
Para la misma cuenta, el índice mira muchas menos.

Toca los puntos clave en orden para repasar. (escanear fila por fila → los datos explotan → saltar con un índice → escaneo completo vs índice)

Ahora sabes por qué una base de datos
pasa de un escaneo completo
a un índice.
Pero ese índice,
¿cómo se construye en realidad?
Más allá de una lista ordenada,
hay formas como un hash y un árbol.
Sigamos esas estructuras de índice listas
una por una en las próximas lecciones.