par Guillaume Lelarge.

Les nœuds feuilles d'un index


Le but principal d'un index est de fournir une représentation ordonnée des données indexées. Néanmoins, il n'est pas possible de stocker les données séquentiellement car une commande INSERT nécessiterait le déplacement des données suivantes pour faire de la place à la nouvelle donnée. Déplacer de gros volumes de données demande beaucoup de temps, ce qui causerait des lenteurs importantes pour une commande INSERT. La solution à ce problème revient à établir un ordre logique qui est indépendant de l'ordre physique en mémoire.

L'ordre logique est établi grâce à une liste doublement chaînée. Chaque nœud a un lien vers les deux nœuds voisins, un peu comme une chaîne. Les nouveaux nœuds sont insérés entre deux nœuds existants en mettant à jour leurs liens pour référencer le nouveau nœud. L'emplacement physique du nouveau nœud n'a aucune importance car la liste doublement chaînée maintient l'ordre logique.

Cette structure de données est appelée une liste doublement chaînée car chaque nœud fait référence aux nœuds précédent et suivant. La base de données peut ainsi lire l'index en avant et en arrière suivant le besoin. Il est du coup possible d'insérer de nouvelles entrées sans déplacer de gros volumes de données, seuls les pointeurs sont changés.

Les listes doublement chaînées sont aussi utilisées pour les collections (conteneurs) dans de nombreux langages de développement.

Langage de programmationNom
Javajava.util.LinkedList
Framework .NETSystem.Collections.Generic.LinkedList
C++std::list

Les bases de données utilisent des listes doublement chaînées pour con­necter des nœuds feuilles d'index. Chaque nœud feuille est stocké dans un bloc de la base de données (aussi appelé page), autrement dit, la plus petite unité de stockage de la base de données. Tous les blocs d'index sont de la même taille, généralement quelques kilo-octets. La base de données utilise l'espace dans chaque bloc du mieux possible, et stocke autant d'entrées d'index que possible dans chaque bloc. Cela signifie que l'ordre de l'index est maintenu sur deux niveaux différents : les enregistrements de l'index à l'intérieur de chaque nœud feuille, et les nœuds feuilles entre elles en utilisant une liste doublement chaînée.

Figure 1.1 Nœuds feuilles de l'index et données de la table

La Figure 1.1 illustre les nœuds feuilles de l'index et leur connexion aux données de la table. Chaque enregistrement de l'index consiste en des colonnes indexées (la clé, la colonne 2) et fait référence à la ligne correspondante dans la table (via ROWID ou RID). Contrairement à l'index, les données de la table sont stockées dans une structure appelée heap et n'est pas du tout triée. Il n'existe aucune relation entre les lignes stockées dans le même bloc de table, pas plus qu'il n'y a de connexions entre les blocs.

À 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