S.G.B.D. relationnel : fichier Comptes et arbre B

Fichier Comptes et arbre B indexant le fichier Comptes sur le montant, avec au maximum quatre entrées par nœud. En réalité, la capacité d'un nœud est celle d'un bloc sur disque. Elle est couramment de 50 à 100 entrées par nœud. Chaque entrée de cet index est un couple (m,@) où m est un montant et @, l'adresse dans le fichier Comptes d'un n-uplet ayant pour montant m. Pour accéder aux comptes ayant pour montant m, il faut traverser l'arbre depuis la racine jusqu'aux feuilles ; ensuite, pour chaque compte ayant pour montant m, en un accès disque on accède au compte lui-même connaissant son adresse. Supposons qu'on recherche les comptes de montant compris entre 2 150 et 3 300 euros. Sans l'existence d'index, il faudrait balayer tous les blocs du fichier et tester pour chaque n-uplet de chaque bloc si le montant du compte est dans les bornes. En traversant l'arbre, on diminue considérablement le nombre de blocs à parcourir : on recherche d'abord les comptes de montant 2 150 euros. Pour cela, on parcourt les entrées de la racine. En comparant 2 150 à 8 900, on sait qu'il faut suivre la branche de gauche et parcourir les entrées de la racine du sous-arbre. Après comparaison de 2 150 à 3 802, on suit encore la branche de gauche. On lit alors un bloc avec deux entrées : 2 034 et 3 200. Comme 2 150 est compris entre 2 034 et 3 200, on accède à la feuille de l'arbre contenant les montants 2 145, 2 289, 2 988 et 3 200. À chaque montant est associée une adresse de n-uplet dans le fichier Comptes ayant le montant en question (flèches en tireté). On parcourt alors en séquence les montants et, pour chacun, on accède au(x) n-uplet(s) dans le fichier en lisant le bloc correspondant du fichier. On accède alors à la feuille suivante, qui est chaînée. La recherche s'arrête quand un montant est supérieur à 3 300 (3 456 est en dehors des bornes). La recherche aura coûté cinq accès de nœuds/feuilles de l'index et quatre lectures de blocs du fichier.