Algo de los índices B-tree

Muchas veces, usamos los índices de acuerdo a las búsquedas que se están haciendo delimitando la información por la parte Where de una consulta. Sin embargo, no sabemos cómo es que se usa o cómo es que funciona dicho índice por dentro. Aquí una breve, resumida pero nutritiva explicación al respecto. Espero les guste.

Ok, vamos a pensar que tenemos varios números para alimentar una estructura. Los números son:

7  4  12  10  3  1 5

Búsqueda en un arreglo (tabla)

Al meter los números mencionados en un arreglo ordenado, quedarían como sigue:

Ahora, para buscar un número en dicho arreglo, no tenemos otra que compararlo contra cada uno de los elementos del mismo. Para encontrar un elemento de esta forma, se tiene que si el arreglo tiene n elementos, entonces, por promedio demoraremos n/2 comparaciones en encontrar el número que buscamos.

Así, en nuestro arreglo, tardaremos 3.5 comparaciones en promedio en encontrar cualquier número. Es decir, podríamos demorar una comparación si buscamos el 1 y 7 comparaciones si buscamos el 12.

Este arreglo nos simula una búsqueda de tipo FULL TABLE ACCESS en una tabla que NO tiene índices o cuya búsqueda se hace por un campo de una tabla que no está indexado.

Ok, entonces, ¿de qué forma podemos realizar una búsqueda más rápida?

Búsqueda en un árbol binario

¿Qué pasa si como van llegando nuestros números de prueba, los metemos en un árbol binario?

Hay que recordar que conforme lleguen los elementos, se pone el de valor intermedio en el nodo raíz y de ahí, los elementos mayores a ese nodo, se colocan a la derecha y los elementos menores, se colocan a la izquierda. Si es necesario, se balancea el árbol para que quede con las hojas repartidas equitativamente. Así, obtenemos un árbol como el que sigue:

Para realizar una búsqueda en este árbol se realizará mucho más rápido que en nuestro ejemplo anterior. Por ejemplo, para buscar el número 1, tendremos que hacer 3 comparaciones para encontrarlo, primero contra 5, después contra el 3 y finalmente contra el 1.

Después de comparar el número a buscar contra cada nodo, se sabrá para dónde ir: a la izquierda si es menor al nodo o a la derecha si es mayor al nodo.

Si buscamos el número 12, también se realizan 3 comparaciones: primero contra el 5, después contra 10 y al final, contra el mismo 12. Como se puede ver, se agiliza la búsqueda.

Pero, otra vez, ¿qué será más rápido?

Búsqueda en un árbol B-Tree (B* o B+)

Para responder a la última pregunta del punto anterior, tenemos que recurrir a los árboles B-Tree o B+ como se puede encontrar referencia a ellos. Prácticamente todos los índices de los RBDMS más famosos y comunes, entre ellos Oracle; se basan en este tipo de árboles. La tecnología detrás de estos árboles no es parte de este post; pero si, una explicación general

¿Cómo es un árbol de este tipo? En la siguiente imagen, vemos un ejemplo del mismo:

Es muy similar a un árbol binario. Sólo que cada uno de los nodos es un arreglo de n elementos. Y de cada elemento de dicho arreglo, se deriva un nuevo nodo hijo con los mismos n elementos. En RDBMS como Oracle, Informix, DB2; n vale 128.

Nota. Hay que recordar que hablando ya de índices, cada uno de los elementos de cada nodo será un registro.

De este forma en el 1er nivel del árbol podemos guardar:

128 elementos o registros

En el 2o nivel, tendremos 128 x 128 registros, es decir:

16,384 registros

En el 3er nivel, tendremos 128 x 128 x 128, es decir:

2’097,152 registros

En total, en un árbol con 3 niveles, tendremos capacidad para guardar:

2’113,664 elementos o registros

Ahora, ¿cuánto nos tardamos en encontrar un elemento en un árbol de estas dimensiones? Supongamos que nuestro elemento se encuentra en el nivel más bajo de este árbol.

Para encontrar nuestro registro, comparamos contra los elementos en el nodo raíz. Si recordamos nuestra comparación en arreglos, tardaremos n/2 comparaciones en saber cuál es el nodo hijo al que tendremos que ir. Basado en el tamaño de n, sabremos que en promedio, tardaremos 64 comparaciones en cada nodo.

Bajo nuestro supuesto de que el registro que buscamos está hasta el 3er nivel, tendremos en total 64 comparaciones x 3 nodos. Es decir:

¡ 192 comparaciones para encontrar un registro en una tabla de 2’113,664 registros !

¡Imaginen! si agregamos un nivel más de elementos, será un índice de 270’549,120 registros y para encontrar un registro, nos demorará ¡sólo 256 comparaciones!

Conclusiones

Creo que queda bastante claro, que en las consultas que lanzamos a la base de datos, el mejor camino es de acuerdo al tema que estamos viendo en este post; usar campos que se encuentran indexados para poder acceder a la información vía los índices B-tree.

Si la información de este post te ha sido de utilidad o quieres que agregue algo más, deja por favor un comentario, contestaré a la brevedad.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: