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, te encantará mi libro.
