Indices: hacer rapidas las busquedas

Un libro tiene un indice al final

Antes vimos como una base de datos
encuentra la fila que quiere.
Pero cuando hay muchos datos,
recorrerlos de inicio a fin es lento.
Es igual que cazar una palabra
en un libro grueso desde la primera pagina.
Por eso un libro tiene un indice al final.
Un numero de pagina va junto a cada palabra,
asi saltas directo a esa pagina.

Compara recorrer el texto desde el inicio con saltar usando el indice. ¿Cuantos pasos toma cada uno?

Saltar con el indice
lo encontro en muchos menos pasos.
El indice de una base de datos
es exactamente esta busqueda.
Es un mapa hecho de antemano
para hallar los datos rapido.
Pero los indices vienen en tipos.
Hallar un valor exacto
y hallar un rango son distintos.

Para un valor exacto, un indice hash

A veces quieres hallar
solo un valor exacto, como "Kim".
Para eso, un indice hash va bien.
Un hash toma el nombre
y calcula un numero de casilla al instante.
Asi, sin recorrer fila por fila,
salta a esa casilla en un paso.
Es como saber el numero de un casillero
y abrir justo ese.

Toca un nombre y el hash calcula un numero de casilla, saltando a esa caja en un paso.

Con solo un nombre
hallo el lugar de una vez.
Un indice hash es asi de rapido
para hallar un valor exacto.
Pero tiene un punto debil.
Un hash dispersa los valores,
asi que hallar por un rango,
como "de 20 a 30 anos",
lo hace mal. Ahi hace falta otro indice.

Para un rango, un indice de arbol

A veces quieres hallar
por un rango, como "de 20 a 30 anos".
Para eso, un indice de arbol va bien.
Un indice de arbol mantiene los valores
ordenados de menor a mayor.
Asi, una vez hallado el valor inicial,
puedes correr justo a su lado,
recorriendo en orden los valores del rango.
Es como un diccionario en orden alfabetico.

Toca para fijar el rango a hallar. El indice de arbol ordenado halla el valor inicial y recorre el rango.

Como esta ordenado,
el rango corrio suave hacia el lado.
Un hash localiza un punto,
un arbol recorre una linea.
Asi que el indice correcto depende
de lo que buscas a menudo.
Muchos valores exactos, usa hash;
muchos rangos, usa arbol.
Pero un indice no es gratis.

Un indice no es gratis

Un indice tambien tiene desventajas.
Primero, ocupa espacio extra.
Como la busqueda se escribe aparte,
usa ese tanto mas de sitio.
Segundo, cuando los datos cambian
el indice debe cambiar con ellos.
Si anades o borras una fila,
la busqueda hay que actualizarla para que cuadre.
Asi que crear muchos a ciegas es una perdida.

Anade o borra una fila. Cada vez que los datos cambian, el indice tambien se actualiza, y el espacio que usa crece.

Cada vez que los datos cambiaban
el indice se movia con ellos.
Y ocupaba mas y mas espacio.
Por eso hacemos un indice
solo para valores que buscamos a menudo.
Sopesamos la ganancia de velocidad
contra el costo de espacio y actualizaciones
en una balanza.
Bien elegido, las busquedas van mucho mas rapidas.

Resumamos

Reunido en una linea, es esto.
Un indice, como la busqueda al final del libro,
es un mapa que te deja saltar rapido.
Un indice hash localiza un valor exacto
de un solo paso,
y un indice de arbol, al estar ordenado,
va bien para recorrer un rango.
Pero usa espacio extra
y hay que actualizarlo cuando los datos cambian.

Toca los puntos clave en orden para repasar. (busqueda del libro -> hash para exacto -> arbol para rango -> no es gratis)

Ahora sabes como un indice
hace rapidas las busquedas.
Hemos visto como hallar datos rapido,
asi que ahora pasamos a manejar
los datos de forma segura.
¿Que pasa cuando muchas personas
tocan los mismos datos a la vez?
Resolvamos ese problema delicado
juntos en la proxima leccion.