par Guillaume Lelarge.

L'arbre de recherche (B-Tree) rend l'index rapide


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 rapide­ment 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 double­ment 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.

Complexité logarithmique

En mathématique, le logarithme d'un nombre sur une base donnée est la puissance ou l'exposant avec laquelle la base doit être élevée pour produire le résultat [Wikipedia].

Dans un arbre de recherche, la base correspond au nombre d'entrées par nœud branche et l'exposant à la profondeur de l'arbre. L'index en exemple dans Figure 1.2 contient jusqu'à quatre entrées par nœud et a une profondeur d'arbre de 3. Cela signifie que l'index peut contenir jusqu'à 64 entrées (43). S'il grossit d'un niveau, il peut déjà contenir 256 entrées (44). À chaque ajout d'un niveau, le nombre maximum d'entrées quadruple. Le logarithme inverse cette fonction. La profondeur de l'arbre est donc log4(nombre-d-entrées-index).

Profondeur de l'arbreEntrées d'index
364
4256
51,024
64,096
716,384
865,536
9262,144
101,048,576

L'augmentation logarithmique permet de rechercher parmi un million d'en­trées dans dix niveaux de l'arbre, mais un index réel est encore plus efficace. Le facteur principal qui influe sur la profondeur de l'arbre, et du coup ces performances, est le nombre d'entrées dans chaque nœud de l'arbre. Ce nombre correspond, mathématique­ment, à la base du logarithme. Plus grande est la base, plus large sera l'arbre et plus rapide sera le parcours.

Les bases de données exploitent ce concept le plus possible et placent autant d'entrées que possible dans chaque nœud, souvent des centaines. Cela signifie que chaque nouveau niveau d'index supporte une centaine de fois plus d'entrées.

À propos de l'auteur

Photo de Markus Winand

Markus Winand teaches efficient SQL—inhouse and online. He minimizes the development time using modern SQL and optimizes the runtime with smart indexing—for that he also published the book SQL Performance Explained.

“Use The Index, Luke!” by Markus Winand and translated by Guillaume Lelarge is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
Mentions légales | Contact | NO WARRANTY | Marque déposée | Privacy | CC-BY-NC-ND 3.0 license