Internos de la base de datos

Capítulo 6. Variantes del Árbol B

Este trabajo se ha traducido utilizando IA. Agradecemos tus opiniones y comentarios: [e-mail]

Las variantes de B-Tree tienen algunas cosas en común: la estructura de árbol, el equilibrio mediante divisiones y fusiones, y los algoritmos de búsqueda y eliminación. Otros detalles, relacionados con la concurrencia, la representación de páginas en el disco, los enlaces entre nodos hermanos y los procesos de mantenimiento, pueden variar entre implementaciones.

En este capítulo, hablaremos de varias técnicas que pueden utilizarse para implementar Árboles B eficientes y de las estructuras que los emplean:

• Los Árboles B de copia-en-escritura están estructurados como Árboles B, pero sus nodos son inmutables y no se actualizan in situ. En su lugar, las páginas se copian, actualizan y escriben en nuevas ubicaciones.

• Los árboles B perezosos reducen el número de solicitudes de E/S de escrituras posteriores en el mismo nodo, almacenando en búfer las actualizaciones de los nodos. En el próximo capítulo, también trataremos los árboles LSM de dos componentes(ver "Árbol LSM de dos componentes"), que llevan el almacenamiento en búfer un paso más allá para implementar árboles B totalmente inmutables.

• Los Árboles FD tienen un enfoque diferente del almacenamiento en búfer, algo similar a los Árboles LSM(ver "Árboles LSM"). Los Árboles FD almacenan las actualizaciones en un pequeño Árbol B. En cuanto este árbol se llena, su contenido se escribe ...