Les nœuds feuilles de l'index sont stockés dans un ordre arbitraire en ce sens que la position sur le disque ne correspond pas à la position logique suivant l'ordre de l'index. C'est comme un annuaire téléphonique avec les pages mélangées. Si vous recherchez « Dupont » mais que vous ouvrez l'annuaire à « Canet », il n'est pas garanti que Dupont suive Canet. Une base de données a besoin d'une deuxième structure pour trouver rapidement une donnée parmi des pages mélangées : un arbre de recherche équilibré (en anglais, un « Balanced Tree Search ») ou, plus court, un B-tree.
Figure 1.2 La structure du B-tree
La Figure 1.2 montre un exemple d'index avec 30 entrées. La liste doublement chaînée établit l'ordre logique entre les nœuds feuilles. La racine et les nœuds branches permettent une recherche rapide parmi les nœuds feuilles.
Le graphique distingue le nœud branche et les nœuds feuilles auxquels il fait référence. Chaque entrée de nœud branche correspond à la valeur la plus grosse dans le nœud feuille référencé. Par exemple, la valeur 46 dans le premier nœud feuille pour que la première entrée du nœud branche soit aussi 46. Ceci est toujours vrai pour les autres nœuds feuilles. À la fin, le nœud branche a les valeurs 46, 53, 57 et 83. Suivant cette méthode, un niveau de branche est construit jusqu'à ce que tous les nœuds feuilles soient couverts par un nœud branche.
Le prochain niveau est construit de façon similaire, mais au-dessus du premier niveau de branche. La procédure se répète jusqu'à ce que toutes les clés remplissent un nœud seul, le nœud racine. La structure est un arbre de recherche équilibré car la profondeur de l'arbre est identique à chaque position. La distance entre le nœud racine et les nœuds feuilles est identique partout.
Remarque
Un B-tree est un arbre équilibré — pas un arbre binaire.
Une fois créée, la base de données maintient automatiquement
l'index. Elle applique chaque commande INSERT,
DELETE et UPDATE à l'index et
conserve la propriété équilibrée de l'arbre, ce qui cause une surcharge de
maintenance pour les opérations d'écriture. Le Chapitre 8, « Modifier les données » explique cela en
détails.
Figure 1.3 Parcours d'un B-Tree
La Figure 1.3 montre un fragment d'index pour illustrer une recherche sur la clé 57. Le parcours de l'arbre commence au nœud racine du côté gauche. Chaque entrée est traitée dans l'ordre ascendant jusqu'à ce qu'une valeur identique ou plus grande (>=) que la valeur recherchée (57) soit trouvée. Dans ce graphique, il s'agit de la valeur 83. La base de données suit la référence au nœud branche correspondant et répète la même procédure jusqu'à ce que le parcours atteigne un nœud feuille.
Important
L'index B-tree permet de trouver un nœud feuille rapidement.
Le parcours de l'arbre est une opération très efficace. C'est même si efficace que j'en parle comme de la première puissance de l'indexation. C'est presque instantané, y compris sur de très gros volumes de données. Ceci est principalement dû à la propriété équilibrée d'un arbre, ce qui permet d'accéder à tous les éléments avec le même nombre d'étapes, mais aussi au grossissement logarithmique de la profondeur de l'arbre. Cela signifie que la profondeur de l'arbre grossit très lentement en comparaison au nombre de nœuds feuilles. De vrais index avec des millions d'enregistrements ont une profondeur d'arbre de quatre ou cinq. Il est très rare de rencontrer une profondeur de cinq ou six dans un arbre. L'encart « Complexité logarithmique » décrit cela en détails.
