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 programmation | Nom |
|---|---|
| Java | java.util.LinkedList |
| Framework .NET | System.Collections.Generic.LinkedList |
| C++ | std::list |
Les bases de données utilisent des listes doublement chaînées pour connecter 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.
