« Un index accélère la requête » est l'explication la plus simple que j'ai pu voir pour un index. Bien qu'elle décrive parfaitement l'aspect le plus important d'un index, cela n'est malheureusement pas suffisant pour ce livre. Ce chapitre décrit la structure d'un index d'une façon moins superficielle, mais sans trop entrer dans les détails. Il fournit suffisamment d'informations pour comprendre tous les aspects relatifs aux performances en SQL, aspects qui seront détaillés tout au long de ce livre.
Un index est une structure séparée dans la base de données, construite
en utilisant l'instruction create index. Il nécessite son
propre espace sur le disque et détient une copie des données de la table.
Cela signifie qu'un index est une redondance. Créer un index ne modifie pas
les données de la table. Cela crée une nouvelle structure de données faisant
référence à la table. En fait, un index de base de données ressemble très
fortement à l'index d'un livre : il occupe de la place, il est redondant et
il fait référence aux informations réelles stockées ailleurs.
Rechercher dans un index de base de données ressemble à rechercher dans un annuaire téléphonique. L'idée est que toutes les informations sont rangées dans un ordre bien défini. Trouver des informations dans un ensemble de données triées est rapide et simple car l'ordre de tri détermine la position de chaque donnée.
Néanmoins, un index de base de données est plus complexe qu'un
annuaire car l'index est constamment modifié. Mettre à jour un annuaire
imprimé pour chaque changement est impossible car il n'y a pas d'espace
entre chaque information pour en ajouter de nouvelles. Un annuaire imprimé
contourne ce problème en gérant des mises à jours accumulées lors de la
prochaine impression. Une base de données ne peut pas attendre aussi
longtemps. Elle doit traiter les commandes INSERT,
DELETE et UPDATE immédiatement, tout
en conservant l'ordre de l'index sans déplacer de gros volumes de
données.
La base de données combine deux structures de données pour parvenir à ce résultat : une liste doublement chaînée et un arbre de recherche. Ces deux structures expliquent la plupart des caractéristiques de performances des bases de données.
