4. Les composants de l'architecture d'un système de bases de données
133
Définition de
l’arbre B
Arbre multiple (B-tree, en anglais)
Les deux propriétés suivantes caractérisent un arbre multiple,
appelé aussi arbre B d'ordre n :
il est entièrement équilibré (chaque chemin connectant la racine
à une feuille quelconque a une même longueur fixe) ;
chaque nœud (excepté le nœud racine) et chaque feuille de
l'arbre possède au moins n mais au plus 2*n entrées dans la page
de données associée.
La deuxième propriété de l'arbre multiple peut encore
s'interpréter comme suit : d'une part, puisque chaque nœud, sauf la
racine, contient au moins n entrées, il possède au moins n sous-arbres.
D'autre part, chaque nœud admet au plus 2*n sous-arbres, car il
contient au maximum 2*n entrées.
Exemple d’un
arbre B d’ordre 2
Considérons à titre d'exemple notre table EMPLOYÉ dont la clé
est le numéro d'employé E#. Nous utilisons cette clé pour construire
une structure d'accès qui sera un arbre multiple d'ordre n = 2,
représenté dans la figure 4-11. Par conséquent, les nœuds et les
feuilles de l'arbre ne doivent pas contenir plus de quatre entrées. Nous
admettons implicitement que les pages associées aux nœuds et aux
feuilles contiennent non seulement les valeurs de la clé choisie, mais
aussi des pointeurs qui renvoient aux pages de données où sont
stockés les enregistrements de données proprement dits. L'arbre
construit à la figure 4-11 représente donc un arbre d'accès, et non
point une technique de gestion des tuples ou enregistrements de
données dans la table EMPLOYÉ.
Construction d’un
arbre équilibré
Dans notre exemple, le nœud racine de l'arbre multiple A1
contient les quatre valeurs de la clé E# en ordre croissant, E1, E4, E7
et E19. Pour insérer une nouvelle valeur de clé E3, nous devons
scinder le nœud racine parce qu’il n'admet plus d'entrées
additionnelles. L'éclatement doit s'effectuer de manière à produire un
arbre équilibré. La valeur de clé E4 reste associée au nœud racine, car
elle partage l'ensemble des valeurs restantes en deux parties égales. Le
sous-arbre de gauche contient des valeurs de clé telles que «E# est
inférieur à E4» (c'est-à-dire E1 et E3 dans notre cas) tandis que le
133
Définition de
l’arbre B
Arbre multiple (B-tree, en anglais)
Les deux propriétés suivantes caractérisent un arbre multiple,
appelé aussi arbre B d'ordre n :
il est entièrement équilibré (chaque chemin connectant la racine
à une feuille quelconque a une même longueur fixe) ;
chaque nœud (excepté le nœud racine) et chaque feuille de
l'arbre possède au moins n mais au plus 2*n entrées dans la page
de données associée.
La deuxième propriété de l'arbre multiple peut encore
s'interpréter comme suit : d'une part, puisque chaque nœud, sauf la
racine, contient au moins n entrées, il possède au moins n sous-arbres.
D'autre part, chaque nœud admet au plus 2*n sous-arbres, car il
contient au maximum 2*n entrées.
Exemple d’un
arbre B d’ordre 2
Considérons à titre d'exemple notre table EMPLOYÉ dont la clé
est le numéro d'employé E#. Nous utilisons cette clé pour construire
une structure d'accès qui sera un arbre multiple d'ordre n = 2,
représenté dans la figure 4-11. Par conséquent, les nœuds et les
feuilles de l'arbre ne doivent pas contenir plus de quatre entrées. Nous
admettons implicitement que les pages associées aux nœuds et aux
feuilles contiennent non seulement les valeurs de la clé choisie, mais
aussi des pointeurs qui renvoient aux pages de données où sont
stockés les enregistrements de données proprement dits. L'arbre
construit à la figure 4-11 représente donc un arbre d'accès, et non
point une technique de gestion des tuples ou enregistrements de
données dans la table EMPLOYÉ.
Construction d’un
arbre équilibré
Dans notre exemple, le nœud racine de l'arbre multiple A1
contient les quatre valeurs de la clé E# en ordre croissant, E1, E4, E7
et E19. Pour insérer une nouvelle valeur de clé E3, nous devons
scinder le nœud racine parce qu’il n'admet plus d'entrées
additionnelles. L'éclatement doit s'effectuer de manière à produire un
arbre équilibré. La valeur de clé E4 reste associée au nœud racine, car
elle partage l'ensemble des valeurs restantes en deux parties égales. Le
sous-arbre de gauche contient des valeurs de clé telles que «E# est
inférieur à E4» (c'est-à-dire E1 et E3 dans notre cas) tandis que le