Base de données interne

Chapitre 6. Variantes de l'arbre B

Cet ouvrage a été traduit à l'aide de l'IA. Tes réactions et tes commentaires sont les bienvenus : [e-mail]

Les variantes de B-Tree ont quelques points communs : la structure de l'arbre, l'équilibrage par le biais de scissions et de fusions, et les algorithmes de recherche et de suppression. D'autres détails, liés à la concurrence, à la représentation des pages sur le disque, aux liens entre les nœuds frères et sœurs et aux processus de maintenance, peuvent varier d'une implémentation à l'autre.

Dans ce chapitre, nous discuterons de plusieurs techniques qui peuvent être utilisées pour mettre en œuvre des B-Trees efficaces et des structures qui les emploient :

• Lesarbres B Copy-on-write sont structurés comme des arbres B, mais leurs nœuds sont immuables et ne sont pas mis à jour sur place. Au lieu de cela, les pages sont copiées, mises à jour et écrites à de nouveaux emplacements.

• LesB-Trees paresseux réduisent le nombre de demandes d'E/S provenant d'écritures ultérieures sur le même nœud en mettant en mémoire tampon les mises à jour des nœuds. Dans le chapitre suivant, nous aborderons également les arbres LSM à deux composants (voir "Arbre LSM à deux composants"), qui poussent la mise en mémoire tampon un peu plus loin pour mettre en œuvre des B-Trees entièrement immuables.

• Les FD-Trees adoptent une approche différente de la mise en mémoire tampon, quelque peu similaire aux LSM Trees (voir "LSM Trees"). Les FD-Trees ...