Les index des bases de données sont traités par indexation afin de trouver au plus vite leur enregistrement dans une base de données. Voici une série d’exercice traitant ce problème. Le cours sur les arbres binaires de recherche traite aussi ce problème en théorie des graphes.
Exercice indexation simple
Rappelons quelques définitions :
- Index = table permettant d’associer à une clé d’article (donnée d’application) l’adresse relative de cet article (position dans le fichier)
- Méthodes d’accès indexé = façon d’aller chercher des articles (données d’application) dans un fichier à partir d’organisation indexée (è index primaire)
- Densité d’un index = quotient du nombre de clés dans l’index sur le nombre d’articles du fichier. Ainsi, un index dense possède autant de clés qu’il y a d’articles dans le fichier. Si le fichier est trié, on peut utiliser un index non dense (ex : la clé la plus grande des articles de chaque bloc avec l’adresse relative du bloc)
- Index hiérarchisé = index sur un index, sur un index, … pour accélérer la recherche de la clé dans l’index
- Index discriminants ou non = sur une donnée discriminante ou non (identifiant un article de manière unique ou non)
- Index plaçant = qui range les articles dans l’ordre des clés et les restitue dans l’ordre en lecture séquentielle de la mémoire
- Index primaire = qui est basé sur la clé des articles, permet de les ranger en mémoire (au passage, accélère l’accès sur clé)
- Index secondaire = un accélérateur d’accès, cet index est non-discriminant
Les organisations indexées nécessitent la création d’un index trié sur lequel sont appliquées les recherches dichotomiques d’une valeur de clé discriminante ou non. Le fichier étant lui-même trié sur clé, l’index correspondant est de type primaire non dense. Cet index peut être vu comme une table de couples (val_clé, adr_page) où val_clé est la plus petite clé des articles stockés dans la page référencée par adr_page. Lorsque l’index est de grande taille, on le décompose en une arborescence dont chaque nœud a une taille inférieure ou égale à une page. Le nœud sommet de l’arborescence est appelé racine de l’index.
Lors de la recherche d’une valeur de clé dans l’index, un examen de la racine permet de déterminer la partie de l’arbre dans laquelle se poursuivra la recherche en renvoyant sur un nœud de niveau immédiatement inférieur. L’examen de ce nœud permet à son tour d’affiner l’intervalle de recherche. Ce processus récursif s’applique jusqu’à rencontrer un nœud ou une feuille (nœud de plus bas niveau de l’arbre) contenant la valeur de clé cherchée et l’adresse de la page associée. Les organisations arborescentes se différencient par le principe suivant lequel est gérée la dynamicité de l’index hiérarchique.
Ce principe détermine les performances obtenues tant au niveau du nombre d’E/S nécessaires pour parcourir l’index qu’au niveau du taux d’occupation de chaque nœud de la hiérarchie.
Un arbre balancé est également appelé arbre-B, B-tree ou arbre équilibré. Intuitivement, il est possible de construire une arborescence dynamique de la façon suivante. Lorsqu’un index est de grande taille, il est possible d’indexer à son tour le fichier contenant cet index et ce, de façon récursive jusqu’à ce que l’index de plus haut niveau (la racine) tienne sur une seule page. Compte tenu de la dynamicité de l’index, la racine elle-même peut croître et ne plus tenir dans une page.
On rajoute alors un niveau à la hiérarchie d’index. La hiérarchie grossit donc par la racine de telle sorte que tous les chemins de la racine aux feuilles ont même longueur. La définition formelle d’un arbre-B est donnée ci-dessous et est illustrée sur l’exemple de la Figure 1.
Un arbre-B d’ordre m est un arbre tel que
(i) chaque nœud contient k clés triées, avec m <= k <= 2m sauf la racine pour laquelle k vérifie 1<= k <= 2m.
(ii) tout nœud non feuille a (k+1) fils. Le ième fils a des clés comprises les (i-1)ème et ième clés du père.
(iii) l’arbre est équilibré.
Question 1
Compte tenu de la définition formelle des arbre-B, quelle seront les hauteurs minimale et maximale (nombre de niveaux) d’un arbre-B d’ordre m contenant n clés ?
Question 2
Quels sont les critères de choix de l’ordre d’un arbre-B si l’on utilise cette structure pour construire un index ?
Question 3
Quel est l’intérêt que la structure d’un index arborescent soit équilibrée ?
Question 4
Dans les applications réelles, les clés d’accès peuvent être de taille variable. En déduire le format de stockage du nœud d’un arbre-B. Quelle est l’utilité des bornes m et 2m fixées pour le nombre k de clés par nœud et comment faut-il interpréter ces bornes dans de cas de clés de taille variable ?
Question 5
Représenter l’arbre-B de la Figure 1 après insertion des clés 37 puis 36.
Question 6
Représenter l’arbre-B de la Figure 1 après suppression des clés 17 puis 31.
Question 7
De nombreuses applications exécutent des traitements séquentiels triés sur leurs fichiers. La structure d’arbre-B est-elle bien adaptée à ce type de traitements ? Combien d’E/S nécessite un parcours séquentiel trié de toutes les clés de l’arbre-B présenté Figure 1 ? Proposer une optimisation de cette structure permettant de lire uniquement les feuilles de l’arbre lors d’un parcours séquentiel trié. Cette organisation est connue sous le nom arbre-B+. Discuter des avantages des arbres B+ par rapport aux arbres B.
Question 1
La hauteur d’un arbre-B évolue de façon logarithmique par rapport au nombre de clés stockées dans l’arbre. En effet, dans un arbre-B d’ordre m, chaque nœud possède entre (m+1) et (2m+1) fils. On peut donc stocker, au niveau i+1 de l’arbre-B, entre (m+1) et (2m+1) fois plus de clés qu’au niveau i, suivant que l’arbre est faiblement ou fortement occupé. Les formules de calcul de la hauteur minimale et maximale d’un arbre-B, en fonction de son ordre et du nombre de clés qu’il contient, sont donc:
h_min » log_(2m+1) n h_max » log_(m+1) n
Par exemple, un arbre-B d’ordre 100 peut contenir plus de 8 millions de clés sur seulement trois niveaux.
Question 2
Lors d’une recherche (ou d’une écriture) dans un index, l’accès à chaque nœud traversé dans l’arborescence génère une E/S. Les hauteurs minimale et maximale de l’arborescence bornent donc le coût en E/S de recherche d’une clé dans l’index. Or, il a été montré dans la question précédente que plus l’ordre de l’arbre-B est grand, plus sa hauteur est faible. D’autre part, on a montré que le nombre de comparaisons engendrées par la recherche d’une clé dans un arbre-B est indépendant de l’ordre de cet arbre-B.
Il est donc intéressant de choisir un ordre aussi grand que possible afin de stocker un maximum de clés par nœud et minimiser la hauteur de l’index. Ce choix doit cependant tenir compte de la taille maximale des nœuds d’arbre-B. Cette taille est bornée par la taille d’une page disque afin d’assurer que la lecture d’un nœud nécessite une seule E/S.
Question 3
Une arborescence équilibrée garantit un coût d’accès constant à toute valeur de clé indépendamment de la distribution des clés. Il est donc possible de borner le nombre d’E/S nécessaire à la recherche ou à l’écriture d’un article. Cette propriété est particulièrement importante en bases de données. En effet, lorsque plusieurs chemins d’accès peuvent être empruntés pour accéder à un article, un SGBD doit être capable de faire automatiquement le choix optimal.
Question 4
Un nœud d’arbre-B contient un ensemble de couples (clé, pointeur fils) et un pointeur additionnel référençant le premier nœud fils (un nœud contenant n clés possède n+1 fils), comme illustré Figure 1. Si la taille des clés est fixe, cette taille est stockée dans le descripteur d’index. Si la taille des clés est variable, deux solutions sont envisageables:
– les clés sont encadrées par un caractère spécial. Ce caractère, appelé séparateur, doit avoir un codage binaire différent de tous les octets susceptibles d’être contenus dans une clé. De plus, la lecture de la ième clé d’un nœud nécessite la lecture octet par octet de toutes les clés la précédant dans ce nœud.
– les clés sont précédées d’un champ longueur. Cette technique est la seule applicable si le codage binaire des clés couvre l’ensemble des codes binaires possibles. La ième clé d’un nœud peut ainsi être accédée en sautant de champ longueur en champ longueur.
Figure 1. Format de stockage d’un noeud d’arbre-B
Les bornes m et 2m assurent que le taux de remplissage d’un nœud varie entre 50% et 100% (et est donc en moyenne de 75%). Dans la définition des arbres-B, ce taux de remplissage k est exprimé en nombre de clés par nœud. Lorsque l’on utilise des arbres-B contenant des clés de taille variable, le taux de remplissage d’un nœud doit alors être exprimé en nombre d’octets plutôt qu’en nombre de clés.
Question 5
Les insertions des clés 37 puis 36 sont illustrées sur la Figure. L’insertion de la clé 36 provoque l’éclatement de la feuille où elle doit être insérée. La remontée de la clé médiane 37 provoque à son tour l’éclatement du nœud père de cette feuille. L’arbre-B croît donc par le haut et reste équilibré.
Figure 2. Insertion des clés 37 puis 36
Question 6
La suppression de la clé 17 entraîne une sous-occupation de la feuille contenant la clé 17. On choisit ici de fusionner cette feuille avec sa sœur droite (feuille appartenant au même nœud père). La clé médiane 24 redescend dans la feuille résultat de la fusion. La fusion de deux feuilles peut être suivie d’un ré-éclatement si la feuille résultat de la fusion se trouve sur-occupée. Lors de la fusion de 2 nœuds (resp. feuilles), le choix du frère (resp. sœur) avec lequel effectuer la fusion peut être systématique (frère droit ou frère gauche à chaque fois) ou bien dynamique.
Un choix dynamique permet de fusionner avec le nœud (resp. feuille) qui produira un résultat de fusion le plus stable possible, c’est-à-dire ni sur-occupé ni sous-occupé. Cette optimisation nécessite cependant la lecture des deux frères (resp. sœurs) pour un gain hypothétique.
Figure 3. Suppression des clés 17 puis 31
La suppression de la clé 31 introduit un problème particulier du fait qu’elle n’appartient pas à une feuille. Pour supprimer une clé dans un nœud non feuille, on la remplace par la plus grande clé du sous-arbre gauche (clé 29 dans l’exemple précédent) ou par la plus petite clé du sous-arbre droit (clé 32 dans l’exemple) dont la clé à supprimer est racine. La clé choisie doit à son tour être supprimée de la feuille en utilisant la procédure de suppression classique.
Question 7
La structure d’arbre-B permet les accès séquentiels triés puisque les clés sont triées dans l’arborescence. Cependant, un parcours séquentiel trié de l’arbre-B nécessite, après lecture de toutes les clés d’une feuille (resp. d’un nœud), de remonter au nœud père pour accéder à la feuille sœur droite (nœud frère droit) afin de continuer la lecture des clés dans l’ordre trié. Ainsi, un nœud père sera accédé sur disque à chaque lecture de l’un de ses fils, afin de récupérer l’adresse de ce fils. Il en résulte qu’une lecture séquentielle triée des 12 nœuds et feuilles de l’arbre-B présenté nécessite au total 20 E/S.
Une optimisation de la structure d’arbre-B pour les parcours séquentiels triés consiste à dupliquer toutes les clés stockées dans les nœuds non feuille au niveau des feuilles puis à chaîner ces feuilles entre elles dans l’ordre du tri. L’adresse de la première feuille peut de plus être stockée dans le descripteur de fichier. Ainsi, un parcours séquentiel trié ne nécessite que la lecture des feuilles de l’arbre. Ce type d’arbre est appelé arbre-B+ [Comer79]. L’arbre-B+ correspondant à l’arbre-B est présenté Figure 4.
Figure 4. Arbre-B+ correspondant à l’arbre-B de la figure 2
Exercice index mutliples
Dans le domaine des bases de données, les recherches d’articles se font généralement sur des critères multiples (exemple: rechercher les voitures de puissance supérieure à 10 cv et de marque Citroën). Les organisations de fichier indexées avec un seul index privilégient le traitement du critère de recherche le plus fréquemment employé sur un fichier, en ordonnançant les articles sur disque en fonction de ce critère. Pour traiter efficacement des recherches multi-critères, il est possible de gérer plusieurs indexes pour un même fichier.
La solution consiste à utiliser un index principal plaçant (les données sont triées selon cet index) et des indexes annexes, appelés indexes secondaires. Un index secondaire est constitué sur un attribut (ou plusieurs) discriminant ou non et donne pour chaque valeur de l’attribut les identifiants (souvent les adresses relatives) des articles ayant cette valeur. L’attribut (ou le groupe d’attributs) ainsi indexé est appelé clé secondaire.
Lors d’une recherche sur clé secondaire, l’accès à l’index secondaire (un arbre B ou B+) délivre les identifiants de tous les articles satisfaisant le critère de recherche. Ces articles sont ensuite récupérés un à un via leurs identifiants, à raison d’au plus une E/S par article. La création d’un index secondaire introduit un coût de stockage important. De plus, toute mise à jour du fichier de données entraîne la mise à jour de tous les index secondaires portant sur ce fichier. L’utilisation d’index secondaires doit donc être restreinte à des critères de recherche fréquents.
Question 1
On désire utiliser une organisation basée sur une technique d’arbre-B+ pour indexer les articles d’un fichier selon plusieurs attributs, A1 étant clé primaire (plaçante) et A2, A3, … Ap étant des clés secondaires. Précisez comment doivent être modifiées les algorithmes d’insertion, mise-à-jour et suppression d’articles en fichiers.
Question 2
Dans le même contexte où le fichier est placé sur A1 et indexé sur les clés secondaires A2, A3, … Ap, précisez l’algorithme d’exécution d’une restriction de critère ( A1 = v1 & A2 = v2 … & Ap = vp). Comment peut-on optimiser la recherche des articles pertinents ? Comment modifier l’algorithme si certains « et » ( & ) sont remplacés par des « ou » ( | ), en supposant une forme normale disjonctive (et de ou) ?
Question 3
Dans le même contexte où le fichier est placé sur A1 et indexé sur les clés secondaires A2, A3, … Ap, précisez l’algorithme d’exécution d’une restriction de critère ( A1 = v1 & A2 = v2 … & Ap = vp & B1 = v’1 & B2 = v’2 & …), les Bi étant des attributs non indexés. Compte tenu d’une fréquence prévisionnelle d’interrogation et de mise à jour sur un attribut, précisez comment choisir si un attribut gagne à être indexé ou non ?
Les algorithmes de gestion des arbre-B+ introduits font l’hypothèse d’un tri mono-critère (c-à-d, prenant en compte un seul attribut). Afin de prendre en compte plusieurs attributs dans la méthode de placement, il suffit d’adapter la fonction Rech_dichoto à un tri multi-critères. La clé à utiliser dans le tri est la concaténation des attributs A1, A2, …, An. La comparaison de 2 clés s’effectue d’abord sur l’attribut A1. En cas d’égalité, on prend en compte la valeur de l’attribut A2 et ainsi de suite. Une clé c1 est donc considérée comme supérieure à une clé c2 si ($i / c1.Ai > c2.Ai) et (i=1 ou « j<i c1.Ai = c2.Ai).
Cette méthode ne traite pas les différents attributs de façon équitable. Ainsi, si le critère de tri choisi est A1, A2, …, An, il est possible d’accélérer les recherches en fonction d’une clé complète ou en fonction d’une clé partielle à condition que cette clé partielle préserve les premiers attributs de la clé complète. Ainsi, une recherche de tous les articles tels que (A1=valeur1 et A2= valeur2) est possible. Par contre, une recherche de tous les articles tels que (A2=valeur1 et A3= valeur2) sans préciser de valeur pour A1 ne peut pas être accélérée par l’arbre-B+.
