Capítulo 4. Aplicación de los árboles B

Este trabajo se ha traducido utilizando IA. Agradecemos tus opiniones y comentarios: translation-feedback@oreilly.com

En el capítulo anterior, hablamos de los principios generales de la composición de formatos binarios, y aprendimos a crear celdas, construir jerarquías y conectarlas a páginas mediante punteros. Estos conceptos son aplicables tanto a las estructuras de almacenamiento de actualización in situ como a las de sólo anexión. En este capítulo, tratamos algunos conceptos específicos de los Árboles B.

Las secciones de este capítulo se dividen en tres grupos lógicos. En primer lugar, tratamos la organización: cómo establecer relaciones entre claves y punteros, y cómo implementar cabeceras y enlaces entre páginas.

A continuación, tratamos los procesos que tienen lugar durante los descensos de raíz a hoja, es decir, cómo realizar la búsqueda binaria y cómo recoger migas de pan y hacer un seguimiento de los nodos padre por si más adelante tenemos que dividir o fusionar nodos.

Por último, tratamos las técnicas de optimización (reequilibrado, anexión sólo a la derecha y carga masiva), los procesos de mantenimiento y la recogida de basura.

Cabecera de página

La cabecera de la página contiene información sobre la página que puede utilizarse para la navegación, el mantenimiento y las optimizaciones. Suele contener banderas que describen el contenido y el diseño de la página, el número de celdas de la página, los desplazamientos inferior y superior que marcan el espacio vacío (utilizados para añadir desplazamientos de celdas y datos), y otros metadatos útiles.

En el ejemplo , PostgreSQL almacena el tamaño de página y la versión de diseño en la cabecera. En MySQL InnoDB, la cabecera de página almacena el número de registros de la pila, el nivel y algunos otros valores específicos de la implementación. En SQLite, la cabecera de página almacena el número de celdas y un puntero a la derecha.

Números mágicos

Un de los valores que suelen colocarse en la cabecera del archivo o de la página es un número mágico. Suele ser un bloque multibyte, que contiene un valor constante que puede utilizarse para señalar que el bloque representa una página, especificar su tipo o identificar su versión.

Los números mágicos se utilizan a menudo para la validación y las comprobaciones de sanidad de [GIAMPAOLO98]. Es muy improbable que la secuencia de bytes de un desplazamiento aleatorio coincida exactamente con el número mágico. Si coincide, es muy probable que el desplazamiento sea correcto. Por ejemplo, para verificar que la página está cargada y alineada correctamente, durante la escritura podemos colocar el número mágico 50 41 47 45 (hexadecimal para PAGE) en la cabecera. Durante la lectura, validamos la página comparando los cuatro bytes de la cabecera de lectura con la secuencia de bytes esperada.

Punteros derechos

Las claves separadoras del árbol B tienen invariantes estrictos: se utilizan para dividir el árbol en subárboles y navegar por ellos, por lo que siempre hay un puntero más a páginas hijas que claves. De ahí viene el +1 mencionado en "Contar llaves".

En "Claves separadoras", describimos las invariantes de las claves separadoras. En muchas implementaciones, los nodos se parecen más a los que se muestran en la Figura 4-2: cada clave separadora tiene un puntero hijo, mientras que el último puntero se almacena por separado, ya que no está emparejado con ninguna clave. Puedes comparar esto con la Figura 2-10.

dbin 0402
Figura 4-2. Puntero derecho

Este puntero extra puede almacenarse en la cabecera como, por ejemplo, se implementa en SQLite.

Si el hijo situado más a la derecha se divide y la nueva celda se añade a su padre, hay que reasignar el puntero del hijo situado más a la derecha. Como se muestra en la Figura 4-3, tras la división, la celda anexada al padre (en gris) tiene la clave promovida y apunta al nodo dividido. El puntero al nuevo nodo se asigna en lugar del puntero anterior situado más a la derecha. En SQLite se describe e implementa un enfoque similar.1

dbin 0403
Figura 4-3. Actualización del puntero derecho durante la división de nodos. La clave promovida se muestra en gris.

Claves altas del nodo

Nosotros podemos adoptar un enfoque ligeramente distinto y almacenar el puntero más a la derecha de la celda junto con la clave alta del nodo. La clave alta representa la clave más alta posible que puede haber en el subárbol bajo el nodo actual. Este enfoque lo utiliza PostgreSQL y se denomina Blink-Trees(para conocer las implicaciones de este enfoque para la concurrencia, consulta "Blink-Trees").

Los árboles B tienen claves N (denotadas con Ki) y punteros N + 1 (denotados con Pi). En cada subárbol, las claves están delimitadas por Ki-1 ≤ Ks < Ki. El K0 = -∞ está implícito y no está presente en el nodo.

Los Blink-Trees añaden una KN+1 clave a cada nodo. Especifica un límite superior de claves que pueden almacenarse en el subárbol al que apunta el puntero PN y, por tanto, es un límite superior de los valores que pueden almacenarse en el subárbol actual. Ambos enfoques se muestran en la Figura 4-4: (a) muestra un nodo sin clave alta, y (b) muestra un nodo con clave alta.

dbin 0404
Figura 4-4. Árboles B sin (a) y con (b) clave alta

En este caso, los punteros pueden almacenarse por pares, y cada celda puede tener un puntero correspondiente, lo que podría simplificar el manejo del puntero derecho, ya que no hay tantos casos de perímetro que considerar.

En la Figura 4-5, puedes ver la estructura esquemática de la página para ambos enfoques y cómo el espacio de búsqueda se divide de forma diferente para estos casos: llegando hasta +∞ en el primer caso, y hasta el límite superior de K3 en el segundo.

dbin 0405
Figura 4-5. Utilizar +∞ como clave virtual (a) frente a almacenar la clave alta (b)

Páginas de desbordamiento

El tamaño de los nodos y los valores de fanout del árbol son fijos y no cambian dinámicamente. También sería difícil dar con un valor que fuera universalmente óptimo: si hay valores de tamaño variable en el árbol y son lo suficientemente grandes, sólo caben unos pocos en la página. Si los valores son diminutos, acabamos desperdiciando el espacio reservado.

El algoritmo del Árbol B especifica que cada nodo guarda un número determinado de elementos. Como algunos valores tienen tamaños diferentes, podemos encontrarnos en una situación en la que, según el algoritmo del Árbol B, el nodo aún no está lleno, pero no hay más espacio libre en la página de tamaño fijo que contiene este nodo. Redimensionar la página requiere copiar datos ya escritos en la nueva región y suele ser poco práctico. Sin embargo, aún tenemos que encontrar la forma de aumentar o ampliar el tamaño de la página.

Para implementar nodos de tamaño variable sin copiar datos en la nueva región contigua, podemos construir nodos a partir de varias páginas enlazadas. Por ejemplo, el tamaño de página por defecto es de 4 K, y después de insertar algunos valores, su tamaño de datos ha crecido más de 4 K. En lugar de permitir tamaños arbitrarios, se permite que los nodos crezcan en incrementos de 4 K, por lo que asignamos una página de extensión de 4 K y la enlazamos desde la original. Estas extensiones de páginas enlazadas se denominan páginas de desbordamiento. Para mayor claridad, en el ámbito de esta sección llamaremos página primaria a la página original.

La mayoría de las implementaciones de B-Tree permiten almacenar sólo hasta un número fijo de bytes de carga útil en el nodo B-Tree directamente y derramar el resto en la página de desbordamiento. Este valor se calcula dividiendo el tamaño del nodo por el desbordamiento. Utilizando este enfoque, no podemos llegar a una situación en la que la página no tenga espacio libre, ya que siempre tendrá al menos max_payload_size bytes. Para más información sobre las páginas de desbordamiento en SQLite, consulta el repositorio de código fuente de SQLite; consulta también la documentación de MySQL InnoDB.

Cuando la carga útil insertada es mayor que max_payload_size, se comprueba si el nodo ya tiene alguna página de desbordamiento asociada. Si ya existe una página de desbordamiento y tiene suficiente espacio disponible, los bytes extra de la carga útil se vierten allí. En caso contrario, se asigna una nueva página de desbordamiento.

En la Figura 4-6, puedes ver una página primaria y una página de desbordamiento con registros que apuntan desde la página primaria a la de desbordamiento, donde continúa su carga útil.

dbin 0406
Figura 4-6. Páginas de desbordamiento

Las páginas de desbordamiento requieren una contabilidad adicional, ya que pueden fragmentarse al igual que las páginas primarias, y tenemos que ser capaces de recuperar este espacio para escribir nuevos datos, o descartar la página de desbordamiento si ya no se necesita.

Cuando se asigna la primera página de desbordamiento, su ID de página se almacena en la cabecera de la página principal. Si una sola página de desbordamiento no es suficiente, se enlazan varias páginas de desbordamiento almacenando el ID de la siguiente página de desbordamiento en la cabecera de la anterior. Puede que haya que recorrer varias páginas para localizar la parte de desbordamiento para la carga útil dada .

Como las claves suelen tener una cardinalidad alta, almacenar una parte de una clave tiene sentido, ya que la mayoría de las comparaciones pueden hacerse en la parte recortada de la clave que reside en la página primaria.

En el caso de los registros de datos, tenemos que localizar sus partes de desbordamiento para devolvérselas al usuario. Sin embargo, esto no importa mucho, ya que es una operación poco frecuente. Si todos los registros de datos están sobredimensionados, merece la pena plantearse un almacenamiento de blobs especializado para valores grandes.

Búsqueda binaria

En ya hemos hablado del algoritmo de búsqueda del Árbol B (ver "Algoritmo de búsqueda del Árbol B") y hemos mencionado que localizamos una clave buscada dentro del nodo utilizando el algoritmo de búsqueda binaria. La búsqueda binaria sólo funciona para datos ordenados. Si las claves no están ordenadas, no pueden buscarse de forma binaria. Por eso es esencial mantener las claves ordenadas y conservar una invariante de ordenación.

El algoritmo de búsqueda binaria recibe una matriz de elementos ordenados y una clave buscada, y devuelve un número. Si el número devuelto es positivo, sabemos que se ha encontrado la clave buscada y el número especifica su posición en la matriz de entrada. Un valor de retorno negativo indica que la clave buscada no está presente en la matriz de entrada y nos da un punto de inserción.

El punto de inserción es el índice del primer elemento mayor que la clave dada. Un valor absoluto de este número es el índice en el que se puede insertar la clave buscada para preservar el orden. La inserción puede hacerse desplazando los elementos una posición, a partir de un punto de inserción, para dejar espacio al elemento insertado [SEDGEWICK11].

La mayoría de las búsquedas en niveles superiores no dan como resultado coincidencias exactas, y nos interesa la dirección de la búsqueda, en cuyo caso tenemos que encontrar el primer valor que sea mayor que el buscado y seguir el enlace hijo correspondiente en el subárbol asociado.

Búsqueda binaria con punteros de dirección

Las celdas de la página del Árbol B se almacenan en el orden de inserción, y sólo los desplazamientos de celda conservan el orden lógico de los elementos. Para realizar una búsqueda binaria a través de las celdas de la página, elegimos el desplazamiento de celda del medio, seguimos su puntero para localizar la celda, comparamos la clave de esta celda con la clave buscada para decidir si la búsqueda debe continuar hacia la izquierda o hacia la derecha, y continuamos este proceso recursivamente hasta encontrar el elemento buscado o el punto de inserción, como se muestra en la Figura 4-7.

Propagar divisiones y fusiones

Como hemos comentado en capítulos anteriores, las divisiones y fusiones del Árbol B pueden propagarse a niveles superiores. Para ello, necesitamos poder recorrer una cadena de vuelta al nodo raíz desde la hoja que divide o un par de hojas que fusionan.

Los nodos del Árbol B pueden incluir punteros al nodo padre. Como las páginas de niveles inferiores siempre se paginan cuando se hace referencia a ellas desde un nivel superior, ni siquiera es necesario que esta información persista en disco.

Al igual que los punteros a hermanos (ver "Enlaces a hermanos"), los punteros a padres deben actualizarse siempre que cambie el padre. Esto ocurre en todos los casos en que la clave separadora con el identificador de página se transfiere de un nodo a otro: durante las divisiones, fusiones o reequilibrios del nodo padre.

Algunas implementaciones (por ejemplo, WiredTiger) utilizan punteros padre para recorrer las hojas, para evitar los bloqueos que pueden producirse al utilizar punteros hermanos (véase [MILLER78], [LEHMAN81]). En lugar de utilizar punteros hermanos para recorrer los nodos hoja, el algoritmo emplea punteros padre, como vimos en la Figura 4-1.

Para dirigirnos a un hermano y localizarlo, podemos seguir un puntero desde el nodo padre y descender recursivamente hasta el nivel inferior. Siempre que lleguemos al final del nodo padre tras recorrer todos los hermanos que comparten el padre, la búsqueda continúa recursivamente hacia arriba, llegando finalmente hasta la raíz y continuando de nuevo hacia abajo hasta el nivel de las hojas.

Reequilibrio

Algunas implementaciones del Árbol B de intentan posponer las operaciones de división y fusión para amortizar sus costes, reequilibrando los elementos dentro del nivel, o moviendo los elementos de los nodos más ocupados a los menos ocupados durante el mayor tiempo posible antes de realizar finalmente una división o fusión. Esto ayuda a mejorar la ocupación de los nodos y puede reducir el número de niveles dentro del árbol, con un coste de mantenimiento del reequilibrio potencialmente mayor .

El equilibrio de carga puede realizarse durante las operaciones de inserción y borrado [GRAEFE11]. Para mejorar la utilización del espacio, en lugar de dividir el nodo por desbordamiento, podemos transferir algunos de los elementos a uno de los nodos hermanos y hacer espacio para la inserción. Del mismo modo, durante la eliminación, en lugar de fusionar los nodos hermanos, podemos optar por trasladar algunos de los elementos de los nodos vecinos para asegurarnos de que el nodo esté al menos medio lleno.

Los Árboles B* siguen distribuyendo datos entre los nodos vecinos hasta que ambos hermanos están llenos [KNUTH98]. Entonces, en lugar de dividir un único nodo en dos medio vacíos, el algoritmo divide dos nodos en tres nodos, cada uno de los cuales está lleno en dos tercios. SQLite utiliza esta variante en la implementación. Este enfoque mejora la ocupación media al posponer las divisiones, pero requiere una lógica adicional de seguimiento y equilibrio. Una mayor utilización también significa búsquedas más eficientes, porque la altura del árbol es menor y hay que atravesar menos páginas en el camino hacia la hoja buscada.

La Figura 4-9 muestra la distribución de elementos entre los nodos vecinos, donde el hermano izquierdo contiene más elementos que el derecho. Los elementos del nodo más ocupado se trasladan al menos ocupado. Como el equilibrado cambia la invariante mín/máx de los nodos hermanos, tenemos que actualizar claves y punteros en el nodo padre para preservarla.

dbin 0409
Figura 4-9. Equilibrio del Árbol B: Repartir elementos entre el nodo más ocupado y el menos ocupado

El equilibrio de carga es una técnica útil que se utiliza en muchas implementaciones de bases de datos. Por ejemplo, SQLite implementa el algoritmoequilibrio-hermanos, que es algo parecido a lo que hemos descrito en esta sección. El equilibrio puede añadir cierta complejidad al código, pero como sus casos de uso son aislados, puede implementarse como una optimización en una fase posterior.

Añadir sólo a la derecha

Muchos sistemas de bases de datos utilizan valores autoincrementados monotónicamente crecientes como claves de índice primario. Este caso abre una oportunidad de optimización, ya que todas las inserciones se producen hacia el final del índice (en la hoja más a la derecha), por lo que la mayoría de las divisiones se producen en el nodo más a la derecha de cada nivel. Además, como las claves se incrementan monotónicamente, dado que la proporción de añadidos frente a actualizaciones y borrados es baja, las páginas no hoja también se fragmentan menos que en el caso de claves ordenadas aleatoriamente.

PostgreSQL llama a este caso fastpath. Cuando la clave insertada es estrictamente mayor que la primera clave de la página más a la derecha, y la página más a la derecha tiene espacio suficiente para contener la entrada recién insertada, la nueva entrada se inserta en la ubicación apropiada de la hoja más a la derecha almacenada en caché, y se puede saltar toda la ruta de lectura.

SQLite tiene un concepto similar y lo denomina quickbalance. Cuando la entrada se inserta en el extremo derecho y el nodo de destino está lleno (es decir, se convierte en la entrada más grande del árbol tras la inserción), en lugar de reequilibrar o dividir el nodo, asigna el nuevo nodo situado más a la derecha y añade su puntero al padre (para más información sobre la implementación del equilibrado en SQLite, consulta "Reequilibrado"). Aunque esto deja la página recién creada casi vacía (en lugar de medio vacía en el caso de una división de nodos), es muy probable que el nodo se llene en breve.

Carga a granel

Si en tenemos datos preclasificados y queremos cargarlos en bloque, o tenemos que reconstruir el árbol (por ejemplo, para desfragmentarlo), podemos llevar aún más lejos la idea de añadir sólo a la derecha. Como los datos necesarios para la creación del árbol ya están ordenados, durante la carga masiva sólo tendremos que añadir los elementos que se encuentren en la posición más a la derecha del árbol.

En este caso, podemos evitar totalmente las divisiones y fusiones y componer el árbol de abajo arriba, escribiéndolo nivel a nivel, o escribiendo nodos de nivel superior en cuanto tengamos suficientes punteros a nodos de nivel inferior ya escritos.

Una forma de aplicar la carga masiva es escribir los datos preclasificados en el nivel de hoja por páginas (en lugar de insertar elementos individuales). Una vez escrita la página hoja, propagamos su primera clave al padre y utilizamos un algoritmo normal para construir niveles superiores del Árbol B [RAMAKRISHNAN03]. Como las claves añadidas se dan en el orden ordenado, todas las divisiones en este caso se producen en el nodo situado más a la derecha.

Como los Árboles B siempre se construyen empezando por el nivel inferior (hoja), se puede escribir el nivel hoja completo antes de componer cualquier nodo de nivel superior. Esto permite tener a mano todos los punteros hijos en el momento en que se construyen los niveles superiores. Las principales ventajas de este planteamiento son que no tenemos que realizar ninguna división o fusión en disco y, al mismo tiempo, sólo tenemos que mantener en memoria una parte mínima del árbol (es decir, todos los padres del nodo hoja que se está llenando en ese momento) para el momento de la construcción.

Los Árboles B inmutables pueden crearse de la misma manera pero, a diferencia de los Árboles B mutables, no requieren una sobrecarga de espacio para modificaciones posteriores, ya que todas las operaciones sobre un árbol son definitivas. Todas las páginas pueden llenarse completamente, lo que mejora la ocupación y se traduce en un mejor rendimiento.

Compresión

Almacenar los datos en bruto, sin comprimir, puede inducir una sobrecarga significativa, y muchas bases de datos ofrecen formas de comprimirlos para ahorrar espacio. El compromiso aparente aquí es entre la velocidad de acceso y el ratio de compresión: los ratios de compresión mayores pueden mejorar el tamaño de los datos, permitiéndote obtener más datos en un solo acceso, pero pueden requerir más RAM y ciclos de CPU para comprimirlos y descomprimirlos.

La compresión puede hacerse a distintos niveles de granularidad. Aunque comprimir archivos enteros puede producir mejores ratios de compresión, tiene una aplicación limitada, ya que hay que volver a comprimir un archivo entero en una actualización, y una compresión más granular suele ser más adecuada para conjuntos de datos más grandes. Comprimir un archivo de índice completo es poco práctico y difícil de aplicar con eficacia: para abordar una página concreta, hay que acceder a todo el archivo (o a su sección que contiene metadatos de compresión) (para localizar una sección comprimida), descomprimirlo y ponerlo a disposición.

Una alternativa es comprimir los datos por páginas. Se adapta bien a nuestro debate, ya que los algoritmos que hemos estado discutiendo hasta ahora utilizan páginas de tamaño fijo. Las páginas pueden comprimirse y descomprimirse independientemente unas de otras, lo que te permite acoplar la compresión a la carga y descarga de páginas. Sin embargo, una página comprimida en este caso sólo puede ocupar una fracción de un bloque de disco y, como las transferencias suelen hacerse en unidades de bloques de disco, puede ser necesario paginar bytes adicionales [RAY95]. En la Figura 4-10, puedes ver una página comprimida (a) que ocupa menos espacio que el bloque de disco. Cuando cargamos esta página, también paginamos bytes adicionales que pertenecen a la otra página. Con páginas que abarcan varios bloques de disco, como (b) en la misma imagen, tenemos que leer un bloque adicional.

dbin 0410
Figura 4-10. Compresión y relleno de bloques

Otro enfoque de es comprimir sólo los datos, ya sea por filas (comprimiendo registros de datos enteros) o por columnas (comprimiendo columnas individualmente). En este caso, la gestión de páginas y la compresión están desacopladas.

La mayoría de las bases de datos de código abierto revisadas al escribir este libro tienen métodos de compresión enchufables, utilizando bibliotecas disponibles como Snappy, zLib, lz4 y muchas otras.

Como los algoritmos de compresión dan resultados diferentes según el conjunto de datos y los objetivos potenciales (por ejemplo, la relación de compresión, el rendimiento o la sobrecarga de memoria), no entraremos en detalles de comparación e implementación en este libro. Hay muchos resúmenes disponibles que evalúan distintos algoritmos de compresión para distintos tamaños de bloque (por ejemplo, Squash Compression Benchmark), que suelen centrarse en cuatro métricas: sobrecarga de memoria, rendimiento de compresión, rendimiento de descompresión y relación de compresión. Es importante tener en cuenta estas métricas a la hora de elegir una biblioteca de compresión.

Aspiración y mantenimiento

Así que hasta ahora hemos hablado sobre todo de las operaciones orientadas al usuario en los Árboles B. Sin embargo, hay otros procesos que ocurren en paralelo a las consultas que mantienen la integridad del almacenamiento, recuperan espacio, reducen la sobrecarga y mantienen las páginas en orden. Realizar estas operaciones en segundo plano nos permite ahorrar algo de tiempo y evitar pagar el precio de la limpieza durante las inserciones, actualizaciones y eliminaciones.

El diseño descrito de las páginas ranuradas (ver "Páginas ranuradas") requiere que se realice un mantenimiento de las páginas para mantenerlas en buen estado. Por ejemplo, las divisiones y fusiones posteriores en los nodos internos o las inserciones, actualizaciones y eliminaciones en el nivel de hoja pueden dar lugar a una página que tenga suficiente espacio lógico, pero que no tenga suficiente espacio contiguo, ya que está fragmentada. La Figura 4-11 muestra un ejemplo de una situación de este tipo: la página aún tiene algo de espacio lógico disponible, pero está fragmentado y se divide entre los dos registros borrados (basura) y algo de espacio libre restante entre los punteros de cabecera/celda y las celdas.

dbin 0411
Figura 4-11. Ejemplo de página fragmentada

Los Árboles B se navegan desde el nivel raíz. Los registros de datos a los que se puede acceder siguiendo los punteros hacia abajo desde el nodo raíz están vivos (direccionables). Se dice que los registros de datos no direccionables son basura: estos registros no se referencian en ninguna parte y no se pueden leer ni interpretar, por lo que su contenido está como anulado.

Puedes ver esta distinción en la Figura 4-11: las celdas que aún tienen punteros son direccionables, a diferencia de las eliminadas o sobrescritas. El llenado a cero de las áreas de basura a menudo se omite por razones de rendimiento, ya que, de todos modos, estas áreas acaban siendo sobrescritas por los nuevos datos.

Fragmentación causada por actualizaciones y borrados

Consideremos en qué circunstancias las páginas llegan al estado en que tienen datos no direccionables y tienen que ser compactadas. A nivel de hoja, los borrados sólo eliminan los desplazamientos de celda de la cabecera, dejando intacta la celda en sí. Una vez hecho esto, la celda ya no es direccionable, su contenido no aparecerá en los resultados de la consulta, y no es necesario anularla ni mover las celdas vecinas.

Cuando se divide la página, sólo se recortan los desplazamientos y, como el resto de la página no es direccionable, las celdas cuyos desplazamientos se truncaron no son alcanzables, por lo que se sobrescribirán cada vez que lleguen los nuevos datos, o se recogerán como basura cuando se inicie el proceso de vacío.

Nota

Algunas bases de datos confían en la recogida de basura, y dejan en su lugar las celdas eliminadas y actualizadas para el control de concurrencia multiversión(ver "Control de concurrencia multiversión"). Las celdas permanecen accesibles para las transacciones que se ejecutan simultáneamente hasta que finaliza la actualización, y pueden recogerse en cuanto ningún otro subproceso acceda a ellas. Algunas bases de datos mantienen estructuras que realizan un seguimiento de los registros fantasma, que se recogen en cuanto finalizan todas las transacciones que hayan podido verlos [WEIKUM01].

Como los borrados sólo descartan los desplazamientos de celda y no reubican las celdas restantes ni eliminan físicamente las celdas de destino para ocupar el espacio liberado, los bytes liberados pueden acabar dispersos por la página. En este caso, decimos que la página está fragmentada y requiere desfragmentación.

Para realizar una escritura, a menudo necesitamos un bloque contiguo de bytes libres donde quepa la celda. Para volver a juntar los fragmentos liberados y arreglar esta situación, tenemos que reescribir la página.

Las operaciones de inserción dejan las tuplas en su orden de inserción. Esto no tiene un impacto tan significativo, pero tener las tuplas ordenadas de forma natural puede ayudar con el prefetch de la caché durante las lecturas secuenciales.

Las actualizaciones se aplican sobre todo al nivel de las hojas: las claves internas de las páginas se utilizan para la navegación guiada y sólo definen los límites de los subárboles. Además, las actualizaciones se realizan por clave y, por lo general, no provocan cambios estructurales en el árbol, aparte de la creación de páginas de desbordamiento. En el nivel de las hojas, sin embargo, las operaciones de actualización no cambian el orden de las celdas e intentan evitar la reescritura de páginas. Esto significa que pueden acabar almacenándose varias versiones de la celda, de las que sólo una es direccionable.

Desfragmentación de páginas

El proceso que se encarga de la recuperación de espacio y las reescrituras de página se denomina compactación, vacío o simplemente mantenimiento. La reescritura de páginas se puede hacer de forma sincrónica al escribir si la página no tiene suficiente espacio físico libre (para evitar crear páginas de desbordamiento innecesarias), pero la compactación se conoce sobre todo como un proceso distinto y asincrónico de recorrer páginas, realizar la recogida de basura y reescribir su contenido.

Este proceso recupera el espacio ocupado por las celdas muertas, y reescribe las celdas en su orden lógico. Cuando se reescriben las páginas, también pueden reubicarse en nuevas posiciones en el archivo. Las páginas en memoria no utilizadas quedan disponibles y se devuelven a la caché de páginas. Los ID de las nuevas páginas disponibles en disco se añaden a la lista de páginas libres (a veces llamada lista libre3). Esta información debe persistir para sobrevivir a las caídas y reinicios del nodo, y para garantizar que no se pierde ni se filtra espacio libre.

Resumen

En este capítulo, hemos tratado los conceptos específicos de las implementaciones del Árbol B en disco, como:

Encabezado de página

Qué información se suele almacenar allí.

Punteros derechos

No se emparejan con llaves separadoras, y cómo manejarlas.

Claves altas

Determina la clave máxima permitida que puede almacenarse en el nodo.

Páginas de desbordamiento

Te permiten almacenar registros de tamaño superior y variable utilizando páginas de tamaño fijo.

Después, repasamos algunos detalles relacionados con los recorridos de raíz a hoja:

  • Cómo realizar una búsqueda binaria con punteros de indirección

  • Cómo seguir las jerarquías de los árboles utilizando punteros a los padres o migas de pan

Por último, repasamos algunas técnicas de optimización y mantenimiento:

Reequilibrio

Mueve elementos entre nodos vecinos para reducir el número de divisiones y fusiones.

Añadir sólo a la derecha

Añade la nueva celda situada más a la derecha en lugar de dividirla, suponiendo que se llenará rápidamente.

Carga a granel

Una técnica para construir eficazmente Árboles B desde cero a partir de datos ordenados.

Recogida de basuras

Un proceso que reescribe las páginas, pone las celdas en orden clave y recupera el espacio ocupado por las celdas no direccionables.

Estos conceptos deberían tender un puente entre el algoritmo básico del Árbol B y una implementación del mundo real, y ayudarte a comprender mejor cómo funcionan los sistemas de almacenamiento basados en Árboles B.

1 Puedes encontrar este algoritmo en la función balance_deeper del repositorio del proyecto.

2 Puedes leer más sobre ello en el repositorio del proyecto: https://databass.dev/links/21.

3 Por ejemplo, SQLite mantiene una lista de páginas no utilizadas por la base de datos, donde las páginas troncales se mantienen en una lista enlazada y contienen direcciones de páginas liberadas.

Get Internos de la base de datos now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial