de Martin LE TARNEC.

El árbol de búsqueda (B-tree) hace el índice rápido


Los nodos hojas del índice están almacenados en un orden aleatorio, es decir su posición en el disco no corresponde a la posición lógica según el orden del índice. Es lo mismo que una guía telefónica con las hojas mezcladas. Si buscas “Sánchez” pero primero abres la guía telefónica por “Rodríguez”, nada nos asegura que Rodríguez siga a Sánchez. Una base de datos necesita una segunda estructura para encontrar rápidamente los datos dentro de las hojas mezcladas: un árbol de búsqueda equilibrado, o sea, un B-Tree.

Figura 1.2 La estructura del B-tree

Figura 1.2 muestra un ejemplo de un índice con 30 entradas. La lista doblemente enlazada establece el orden lógico entre los nodos hojas. La raíz y sus ramas permiten hacer una búsqueda rápida entre los nodos hojas.

En la ilustración destaca el nodo rama y sus nodos hojas a los que hace referencia. Cada entrada del nodo rama corresponde al valor más grande respecto a su nodo hoja. Por ejemplo, el valor más grande en el primer nodo hoja es 46, que está almacenado en su propia entrada del nodo rama. Lo mismo sucede para todos los nodos hojas, que al final de su nodo rama tienen los valores 46, 53, 57 y 83. De acuerdo con este plan, un nivel de rama está construido hasta que todos los nodos hojas estén cubiertos por un nodo rama.

El siguiente nivel está construido de manera similar, pero encima del primer nivel de rama. Se repite este procedimiento hasta que todas las llaves llenan un único nodo, el nodo raíz. La estructura es un árbol de búsqueda equilibrado porque la profundidad del árbol es idéntica en cada posición; la distancia entre el nodo raíz y los nodos hojas es idéntica en todas las partes del árbol.

Nota

Un B-tree es un árbol equilibrado, no como un árbol binario.

Una vez creado el índice, la base de datos lo mantiene automáticamente. Se aplican cada insert, delete y update al índice y se conserva el árbol equilibrado, lo que genera una sobrecarga de mantenimiento para las operaciones de escritura. El Capítulo 8, “Modificando los datos, explica este tema con más detalles.

Figura 1.3 Recorrido de un índice B-Tree

Figura 1.3 es una muestra de un fragmento de un índice para ilustrar la búsqueda de la llave “57”. El recorrido del árbol empieza desde el nodo raíz del lado izquierdo. Cada entrada esta procesada en el orden ascendente hasta encontrar un valor superior o igual (>=) al valor buscado (57). En esta ilustración, se trata del valor 83. La base de datos sigue la referencia sobre el nodo rama correspondiente y repite el proceso hasta que el recorrido del árbol alcanza un nodo hoja.

Importante

El índice B-tree permite encontrar un nodo hoja rápidamente.

El recorrido del árbol es una operación muy eficiente. De hecho es tan eficiente que me refiero a ella como la primera potencia de la indexación. Funciona de manera casi instantánea incluso con grandes volúmenes de datos. Ello se debe principalmente a la característica equilibrada del árbol, lo que permite tener acceso a todos los elementos con el mismo número de etapas, y en segundo lugar, al crecimiento logarítmico de la profundidad del árbol. Eso significa que la profundidad del árbol crece lentamente en comparación al número de hojas. Hay índices reales con millones de registros que tienen una profundidad de cuatro o cinco. Es poco común encontrar una profundidad de seis. El apartado sobre la Escalabilidad logarítmica lo describe más en detalle.

Si te gusta mi manera de explicar las cosas, te encantará mi libro.

Escalabilidad logarítmica

En matemáticas, el logaritmo de un número sobre una base es el exponente al cual hay que elevar la base para obtener dicho resultado.[Wikipedia].

En un árbol de búsqueda, la base corresponde al número de entradas por nodo rama y el exponente a la profundidad del árbol. Por ejemplo, el índice de la Figura 1.2 contiene hasta 4 entradas por nodo y tiene una profundidad de árbol de 3. Eso significa que el índice puede contener hasta 64 entradas (43). Si el índice crece de un nivel, podría ya contener hasta 254 entradas (44). Cada vez que se agrega un nivel, el máximo número de entradas se cuadruplica. El logaritmo invierte esta función. Por tanto, la profundidad del árbol es log4 (número de entradas del índice)

Profundidad del árbolEntradas del índice
364
4256
51 024
64 096
716 384
865 536
9262 144
101 048 576

El crecimiento logarítmico permite buscar dentro de varios millones de entradas en un árbol de diez niveles, pero un índice en el mundo real es aún más eficiente. El factor determinante que influye sobre la profundidad del árbol, por lo tanto el desempeño, es el número de entrada de cada nodo del árbol. Este número corresponde – desde el punto de vista matemático – a la base del logaritmo. Cuanto más grande es la base, menos profundo será el árbol y más rápido será el recorrido.

Las bases de datos usan este concepto al máximo agregando entradas tanto como sea posible dentro de cada nodo, a menudo centenares. Eso significa que cada nuevo nivel de índice soporta un centenar de entradas más.

Acerca del autor

Foto de Markus Winand

Markus Winand enseña eficientemente SQL, en casa y online. Minimiza el tiempo de desarrollo utilizando moderno SQL y optimiza el tiempo de ejecución con indexación inteligente. Para ello también ha publicado el libro SQL Performance Explained.

“Use The Index, Luke” de Markus Winand se halla bajo licencia Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
Aspectos legales | Contacto | SIN GARANTÍA | Marcas | Privacy | CC-BY-NC-ND 3.0 licencia