3. Structures d’index: l’arbre B¶

Quand une table est volumineuse, un parcours séquentiel est une opération relativement lente et pénalisante pour l’exécution des requêtes, notamment dans le cas des jointures où ce parcours séquentiel doit parfois être effectué répétitivement. La création d’un index permet d’améliorer considérablement les temps de réponse en créant des chemins d’accès aux enregistrements beaucoup plus directs. Un index permet de satisfaire certaines requêtes (mais pas toutes) portant sur un ou plusieurs attributs (mais pas tous). Il ne s’agit donc jamais d’une méthode universelle qui permettrait d’améliorer indistinctement tous les types d’accès à une table.

L’index peut exister indépendamment de l’organisation du fichier de données, ce qui permet d’en créer plusieurs si on veut être en mesure d’optimiser plusieurs types de requêtes. En contrepartie la création sans discernement d’un nombre important d’index peut être pénalisante pour le SGBD qui doit gérer, pour chaque opération de mise à jour sur une table, la répercussion de cette mise à jour sur tous les index de la table. Un choix judicieux des index, ni trop ni trop peu, est donc un des facteurs conditionnant la performance d’un système.

Ce chapitre présente les structures d’index les plus classiques utilisées dans les systèmes relationnels. Après un introduction présentant les principes de base des index, nous décrivons en détail une structure de données appelée arbre-B qui est à la fois simple, très performante et propre à optimiser plusieurs types de requêtes: recherche par clé, recherche par intervalle, et recherche avec un préfixe de la clé. Le « B » vient de balanced en anglais, et signifie que l’arbre est équilibré: tous les chemins partant de la racine vers une feuille ont la même longueur. L’arbre B est utilisé dans tous les SGBD relationnels.

Pour illustrer les techniques d’indexation d’une table nous prendrons deux exemples.

Exemple des films

Le premier est destiné à illustrer les structures et les algorithmes sur un tout petit ensemble de données, celui de la table Film, avec les 16 lignes du tableau ci-dessous. Nous ne donnons que les deux attributs titre et année qui seront utilisés pour l’indexation.

Titre	Année	(autres colonnes)
Vertigo	1958	…
Brazil	1984	…
Twin Peaks	1990	…
Underground	1995	…
Easy Rider	1969	…
Psychose	1960	…
Greystoke	1984	…
Shining	1980	…
Annie Hall	1977	…
Jurassic Park	1992	…
Metropolis	1926	…
Manhattan	1979	…
Reservoir Dogs	1992	…
Impitoyable	1992	…
Casablanca	1942	…
Smoke	1995	…

Exemple d’une grosse collection

Le deuxième exemple est destiné à montrer, avec des ordres de grandeur réalistes (quoique modestes selon les normes actuelles), l’amélioration obtenue par des structures d’index, et les caractéristiques, en espace et en temps, de ces structures. Nous supposerons que la table contient un million (1 000 000) de films, la taille de chaque enregistrement étant de 1200 octets. Pour une taille de bloc de 4 096 octets, on aura donc au mieux 3 enregistrements par bloc. Il faut donc 333 334 blocs (\(\lfloor 1000000/3 \rfloor\)) occupant un peu plus de 1,3 Go (1 365 336 064 octets, le surplus étant imputable à l’espace perdu dans chaque bloc). Pour simplifier les calculs, on arrondira à 300 000 blocs. C’est sur ce fichier que nous allons construire nos index.

Exercices¶

Exercice ex-dense-nondense: index dense ou non-dense

Soit un fichier de données tel que chaque bloc peut contenir 10 enregistrements. On indexe ce fichier avec un niveau d’index, et on suppose qu’un bloc d’index contient 100 entrées [valeur, adresse].

Si n est le nombre d’enregistrements, donnez le nombre minimum de blocs en fonction de n pour un index dense et un index non-dense.

Correction

Le fichier est constitué d’au moins \(\frac{n}{10}\) blocs. Un index dense contient n entrées et occupe donc \(\frac{n}{100}\) blocs. Pour un index non-dense il faut seulement \(\frac{n}{10}\) entrées donc \(\frac{n}{1000}\) blocs.

Exercice ex-construction: construction d’un arbre B

Soit la liste des départements suivants, à lire de gauche à droite et de bas en haut.
3  Allier; 36 Indre; 18 Cher; 75 Paris
39 Jura; 9  Ariège; 81 Tarn; 11 Aude
12 Aveyron; 25 Doubs; 73 Savoie; 55 Meuse;
15 Cantal; 51 Marne; 42 Loire; 40 Landes
14 Calvados; 30 Gard; 84 Vaucluse; 7 Ardèche
Questions:

Construire, en prenant comme clé le numéro de département, un index dense à deux niveaux sur le fichier contenant les enregistrements dans l’ordre indiqué ci-dessus, en supposant 2 enregistrements par bloc pour les données, et 8 par bloc pour l’index.

Construire un index non-dense sur le fichier trié par numéro, avec les mêmes hypothèses.

Construire un arbre-B sur les numéros de département, en supposant qu’il y a au plus 4 entrées par bloc dans l’index, et en insérant les enregistrements dans l’ordre donné ci-dessus.

Construire un arbre-B sur les noms de département, en supposant qu’il y a au plus 4 entrées par bloc dans l’index, et en insérant les enregistrements dans l’ordre donné ci-dessus.

Correction

Voir la Fig. 3.12. Notez que deux entrées proches dans l’index (3 et 7) peuvent référencer des enregistrements très distincts

Fig. 3.12 L’index dense à deux niveaux.¶

La Fig. 3.13 montre l’arbre B sur les numéros, après l’insertion du 42. Le complément est laissé à titre d’exercice. Les différents types de pointeurs sont montrés avec des graphies distinctes: trait plein pour le liens entre niveaux, trtait plein, tête blanche pour les liens des feuilles, traits pointillés pour les liens entre index et données.

Fig. 3.13 L’arbre B sur les numéros (jusqu’au 42, à compléter)¶

Exercice ex-arbreb1: propriétés d’un arbre B

Soit un fichier de 1 000 000 enregistrements répartis en blocs de 4 096 octets. Chaque enregistrement fait 45 octets et il n’y a pas de chevauchement de blocs. Répondez aux questions suivantes en justifiant vos réponses (on suppose que les blocs sont pleins).

Combien faut-il de blocs? Quelle est la taille du fichier?

Quelle est la taille d’un index de type arbre-B si la clé fait 32 octets et une adresse 8 octets? Détaillez le calcul niveau par niveau.

Même question si la clé fait 4 octets.

Si on suppose qu’une lecture coûte 10 ms, quel est le coût moyen d’une recherche d’un enregistrement par clé unique, avec index et sans index dans le pire des cas?

Correction

Dans un bloc on met \(\lfloor \frac{4096}{45} \rfloor=91\) enregistrements. Il faut donc \(\lceil \frac{1000000}{91} \rceil = 10\,990\) blocs, donc 45 Mo.
Une entrée d’index fait 40 octets. Donc on met \(\lfloor \frac{4096}{40}\rfloor =102\) entrées par bloc. L’ordre de l’arbre est donc 51.

Il faut indexer 1 000 000 enregistrements pour le niveau des feuilles, soit \(\lceil \frac{1\,000\,000}{102} \rceil = 9\,804\) blocs. Ensuite il faut indexer chacun des 9,804 blocs, soit \(\lceil \frac{9\,804}{102} \rceil =97\) blocs supplémentaires, que pour finir on indexe avec un seul bloc, la racine.

Donc il faut 9,804 + 97 + 1 blocs pour constituer l’index.
Si la clé n’occupe que 4 octets, une entrée occupe 4+8=12 octets. On met \(\lfloor \frac{4096}{12} \rfloor =341\) entrées par bloc. Le niveau des feuilles contient \(\lceil \frac{1\,000\,000}{341} \rceil = 2\,933\) blocs, le niveau suivant \(\lceil \frac{2\,933}{341} \rceil =9\) blocs, et on les indexe avec la racine. On a beaucoup gagné!
Recherche avec index: trois lectures dans l’index, puis une lecture dans le fichier. Soit 40 ms s’il n’y a que des lectures physiques.
Sans index, en moyenne il faut lire la moitié du fichier, soit 5 495 blocs, soit plus de 50 secondes s’il n’y a que des lectures physiques et des accès aléatoires (ce qui est un cas extrêmement défavorable).

Exercice ex-arbreb2: hauteur et efficacité d’un arbre B

On reprend les hypothèses précédentes, et on indexe maintenant le fichier avec un arbre-B dont chaque bloc peut contenir au maximum 100 entrées. Les feuilles de l’arbre contiennent des entrées référençant des enregistrements dans le fichier, et les nœuds internes contiennent des entrées référençant d’autres nœuds.

Quel est l’ordre de cet arbre B et quel est sa hauteur théorique obtenue par la formule donnée en cours?

On suppose maintenant qu’un bloc d’arbre B est plein à 70% et contient donc 70 entrées pour un fichier de 1 000 000 d’enregistrements. En effectuant un calcul niveau par niveau, donnez (1) le nombre de blocs du niveau des feuilles, (2) le nombre minimal de blocs utilisés par la fichier et l’index, (3) le nombre de niveaux de l’arbre , (4) le nombre de lectures pour rechercher un enregistrement par sa clé.

On effectue maintenant une recherche par intervalle ramenant 1 000 enregistrements. Décrivez la recherche et donnez le nombre de lectures dans le pire des cas.

Correction

L’ordre de cet arbre B est 50. En appliquant la formule \(\lceil log_{50} (10^6) \rceil\) on trouve une hauteur théorique de 4.
Le niveau des feuilles de l’arbre B indexe un million d’enregistrements, il est donc stocké sur \(\lceil \frac{10^6}{70} \rceil = 14 286\) blocs. Le niveau indexant les feuilles est non dense et contient donc 14 286 entrées qui sont stockées (toujours à 70 entrées par nœud) dans 204 blocs. Il faut encore 3 blocs au niveau supérieur, et 1 bloc pour la racine. Il y a donc \(14\,286+204+3+1\) blocs dans l’arbre B` plus au moins 100 000 blocs de données.

On trouve bien 4 niveaux d’index. Il faut donc lire 4+1 blocs pour accéder à un enregistrement par sa clé.
Pour une recherche par intervalle on parcourt d’abord l’arbre jusqu’à trouver l’entrée au niveau des feuilles qui correspond à la borne inférieure de l’intervalle (4 blocs à lire). Il faut ensuite lire 1 000 entrées, soit \(\lceil \frac{1000}{70} \rceil = 15\) blocs en parcourant le niveau des feuilles de l’arbre. Pour chaque adresse des 1 000 entrées il faut lire un bloc dans le pire des cas, soit 1 000 blocs. Total: 1018 blocs. Le coût (théorique) des accés aléatoires au fichier de données est le plus pénalisant.

Exercice ex-arbreb3: encore des calculs sur l’arbre B

Un arbre B indexe un fichier de 300 enregistrements.

Dans un premier temps, on suppose que l’ordre de l’arbre est de 5. Chaque nœud stocke donc au plus 10 entrées. Quelle est la hauteur minimale de l’arbre et sa hauteur maximale? (Un arbre constitué uniquement de la racine a pour hauteur 0).

Inversement, on ignore l’ordre de l’arbre mais on constate qu’il a deux niveaux. Quel est l’ordre maximal compatible avec cette constatation? Et l’ordre minimal?

Correction

Hauteur minimale: pour atteindre la minimalité il faut que tous les blocs soient pleins, avec 10 entrées. Donc il faut 30 blocs au niveau des feuilles, 3 au niveau intermédiaire, et un bloc avec 3 pointeurs pour la racine. La hauteur est 2. Hauteur maximale: il n’y a que 5 entrées par bloc. Donc il faut 60 blocs feuilles, 12 blocs au niveau intermédiaire, 3 au dessus, et un pour la racine. La hauteur est 3.

Si la hauteur est de 1: le nombre d’entrées au niveau des feuilles est \(n^2\), où n est le nombre d’entrées par bloc.

Pour que n soit maximal, il faut que ce soit le plus grand entier tel que \(n < 300\) (sinon il n’y aurait qu’un seul niveau) et \(n^2 \geq 300\) (sinon il y aurait 3 niveaux), soit \(n=299\), et un ordre égal à la moitié, soit 149..

n minimal: le plus petit n tel que \(n^2 \geq 300\), soit \(n=18\) et un ordre égal à 9.

Exercice ex-arbreb4: indexation des séquences

On indexe une table par un arbre B+ sur un identifiant dont les valeurs sont fournies par une séquence. À chaque insertion un compteur est incrémenté et fournit la valeur de clé de l’enregistrement inséré.

On suppose qu’il n’y a que des insertions dans la table. Montrez que tous les nœuds de l’index qui ont un frère droit sont exactement à moitié pleins.

Correction

Au moment d’un éclatement, on se retrouve avec deux blocs remplis à moitié. Celui qui a un frère droit ne contient que des valeurs de clés inférieures à celui de ce frère droit. Comme on n’insère que des valeurs supérieures à toutes celles existantes, un nœud qui a un frère droit ne sera jamais modifié.

Exercice ex-arbreb5: index ou parcours séquentiel?

Soit un fichier non trié contenant n enregistrements de 81 octets chacun. Il est indexé par un arbre-B, comprenant 3 niveaux, chaque entrée dans l’index occupant 20 octets. On utilise des blocs de 4 096 octets, sans entête, et on suppose qu’ils sont remplis à 100% pour le fichier et à 70% pour l’index.

On veut effectuer une recherche par intervalle dont on estime qu’elle va ramener m enregistrements. On suppose que tous les blocs sont lus sur le disque pour un coût uniforme.

Donnez la fonction de n et m exprimant le nombre de lectures à effectuer pour cette recherche avec un parcours séquentiel.

Donnez la fonction exprimant le le nombre de lectures à effectuer en utilisant l’index.

À partir de quelle valeur de m la recherche séquentielle devient-elle préférable à l’utilisation de l’index, en supposant un temps d’accès uniforme pour chaque bloc?

En déduire le pourcentage d’enregistrements concernés par la recherche à partir duquel le parcours séquentiel est préférable. On pourra simplifier les équations en éliminant les facteurs qui deviennent négligeables pour des grandes valeurs de n et de m.

Correction

Nombre d’enregistrements dans chaque bloc: \(\lfloor 4096/81 \rfloor = 50\). Nombre de blocs du fichier: \(\lceil \frac{n}{50} \rceil\). Il faut lire tout le fichier pour une recherche par intervalle.
Pour une rercherche avec l’index, il faut lire la racine de l’arbre, puis un bloc du niveau intermédiaire, avant d’arriver à la feuille contenant l’adresse de la borne inférieure de l’intervalle. Il faut alors tenir compte du nombre d’entrées par bloc de l’arbre-B, égal en moyenne, d’après l’énoncé, à \(0,7 \times \lfloor 4096/20 \rfloor = 143\). Il faudra donc parcourir un nombre de feuilles de l’arbre égal à \(\lceil m / 143 \rceil\) et pour chaque adresse rencontrée aller lire le bloc correspondant dans le fichier de données. On en déduit le nombre de lectures nécessaires:

\[2 + \lceil \frac{m}{143} \rceil + m\]
Avec l’hypothèque d’un temps de lecture uniforme des blocs, il vaut mieux utiliser une lecture séquentielle quand le nombre de blocs à lire en passant par l’index est supérieur à la taille du fichier, soit:

\[\lceil \frac{n}{50} \rceil < 2 + \lceil \frac{m}{143} \rceil + m\]

Pour une grande valeur a, on va poser \(\lceil a \rceil = a\), cela simplifie l’équation:

\[\frac{n}{50} < 2 + \frac{m}{143} + m\]

Soit \(m > \frac{1}{1 + 1/143} \times (\frac{n}{50} - 2)\). On pose \(m = p \times n\) où p est le pourcentage d’enregistrements ramenés par la recherche. On a donc:

\[p > \frac{1}{1 + 1/143} \times (\frac{1}{50} - \frac{2}{n})\]

Pour une valeur de n élevée, le facteur 2/n (correspondant à la descente dans l’arbre) devient négligeable. On peut également ignorer \(\frac{1}{143}\) qui correspond au parcours des feuilles de l’arbre. Bref: le parcours de l’index compte pour peu de choses, les accès aléatoires au fichier étant prépondérants. On constate qu’au-delà de 2% des enregistrements ramenés par une recherche, un parcours séquentiel est préférable.

C’est un calcul instructif même s’il s’appuie sur des hypothèses très simplificatrices. En pratique le placement dans un cache des blocs du fichier de données réduit l’effet de dispersion des lectures aléatoires engendrées par le parcours d’index. Mais en contrepartie la lecture séquentielle du fichier de données est bien plus efficace qu’une série d’accès aléatoires.

Exercice ex-arbreb6: utilité des index sur les clés primaires et étrangères

Soit les deux tables suivantes:

create table R (idR varchar(20) not null,
          primary key (idR));

create table S (idS int not null,
        idR varchar(20) not null,
          primary key (idS),
         foreign key idR references R);

Indiquez, pour les ordres SQL suivants, quels index peuvent améliorer les performances ou optimiser la vérification des contraintes primary key et foreign key.

select * from R where idR = 'Bou'
select * from R where idR like 'B%'
select * from R where length(idR) = 3
select * from R where idR like '_ou'
insert into S values (1, 'Bou')
select * from S where idS between 10 and 20
delete from R where idR like 'Z%'

Correction

La première requête est optimisée par l’index sur la clé primaire
La seconde est une recherche par préfixe sur la clé primaire: idem.
La troisième applique une fonction à la clé: l’index ne peut pas être utilisé car la critère de recherche n’est plus une valeur de clé
La quatrième est une recherche par suffixe: l’index n’est pas utilisable
L’insertion tire partie de l’index sur la clé primaire sur S: il faut vérifier que la valeur de clé n’existe pas déjà. En l’absence d’index il faudrait parcourir toute la table à chaque insertion. La clé sur R.idR est également utile pour vérifier la contrainte d’intégrité.
La requête par intervalle peut tirer partie de l’index, si l’intervalle est limité.
Enfin la destruction dans R implique la vérification qu’il n’existe pas de nuplet référençant dans S, sinon la contrainte d’intégrité serait violée. L’index sur la clé étrangère est ici très utile (en plus bien sûr de l’index sur la clé primaire de R pour trouver les n-uplets à détruire).

3. Structures d’index: l’arbre B¶

S1: Indexation de fichiers¶

Structure et contenu des index¶

Comment chercher avec un index¶

Index non-dense¶

Index dense¶

Index multi-niveaux¶

Quiz¶

S2: L’arbre-B¶

Structure de l’arbe B¶

Construction de l’arbre B¶

Recherches avec un arbre-B¶

Recherche par clé¶

Recherche par intervalle¶

Recherche par préfixe¶

Création d’un arbre B¶

Propriétés de l’arbre B¶

Quiz¶

Exercices¶

Table Of Contents

Recherche