De l’intérêt des index

données statiques. En effet si le volume des index double celui de la base, le gain apporté par ces derniers est diminué par l’encombrement du cache. Il y a donc un équilibre à trouver. En d’autres termes, trop d’index tue l’index23 !

En effet, si l’index est intéressant en lecture parce qu’il va réduire drastiquement les temps de réponse, il s’avère coûteux en mise à jour (INSERT, UPDATE, DELETE) car il oblige chaque ligne manipulée à autant d’entrées à ajouter, supprimer ou modifier suivant le nombre d’index. Par exemple une table dotée de quatre index dans laquelle nous faisons l’insertion d’une ligne induit fatalement quatre données à insérer dans les quatre index en sus de l’insertion de la ligne dans la table. Mais au fait, qu’est-ce qu’un index ? Imaginez que je vous invite chez moi à dîner et que je vous affirme habiter aux Champs Elysées à Paris24.

Avec cette seule indication, vous avez intérêt à venir de bonne heure car il va vous falloir aller d’immeuble en immeuble, sonner à toutes les portes afin de savoir si un certain Brouard habite ici. Il est bien certain que si je vous avais indiqué le numéro dans la rue, vous auriez trouvé plus facilement. Or comme un fait exprès, les immeubles des rues de nos villes ont été numérotés en séquence25, dans le sens de la marche. Tant est si bien que trouver le bon immeuble s’avère un jeu d’enfant et économise du temps et des souliers. Et bien c’est cela un index: une information supplémentaire qui permet de retrouver une donnée le plus rapidement possible.

Nous utilisons couramment une quantité phénoménale d’index sans le savoir : le répertoire de votre téléphone mobile, le calendrier, le numéro des chaînes de TV, un dictionnaire, le bottin des pages jaunes, la table des matières d’un livre… sont autant d’index ! Dans une base de données, un index consiste à redonder une ou plusieurs colonnes en les triant. Mais il faut faire référence à l’origine de ces données c’est-à-dire la table. Une structure d’index contient donc à la fois les données indexées et une référence à la ligne de la table dans laquelle on trouve cette donnée.

En fait un index est une structure de données annexe à la table, devant être en permanence synchrone avec les données de la table. La structure de stockage qui est aussi la méthode de tri permettant des recherches rapides, est basée sur ce que l’on appelle un arbre équilibré, c’est-à-dire une arborescence ou toutes les données (autrement dit les feuilles de l’arbre) sont situées au même niveau. Ainsi, que l’on cherche Amandine ou Zoé, l’effort de parcours de l’index doit être le même. Cet arbre est donc constitué d’une racine, c’est-à-dire du point d’entrée dans l’index, de pages de navigation, c’est-à-dire d’aiguillages et enfin de pages de données que sont les feuilles de l’arbre26.

À noter que la racine est aussi une page de navigation, donc d’aiguillage. Il y a donc deux natures de pages dans un index : celles qui permettent de naviguer et celles qui contiennent les données. Rendons-nous compte à quel point un index bien formé peut minimiser le temps de recherche d’une donnée. Imaginons une table contenant des employés avec tout un tas de rubriques comme la clef primaire de type entier auto incrémenté, un nom, un prénom, un matricule, un numéro de sécurité sociale, une date de naissance, une adresse, des moyens de contacts…

Assurons-nous que la clef, comme c’est souvent le cas, ait généré un index qui a permis de trier la table sur cette donnée. Admettons que dans cette table la longueur de la ligne soit de 200 octets, qu’en particulier la clef soit de 4 octets, et le nom de 16 caractères donc 16 octets en moyenne. Suggérons qu’il y ait 100 000 lignes dans cette table. Pour rechercher toutes les lignes dont le nom est Brouard, il faudra parcourir toute la table soit plus de 19 Mo. En fait il faut lire 2 500 pages27. Créons maintenant un index sur cette colonne. Il faudra 100 000 x (16 + 4) octets28, soit 1,9 Mo.

Nous avons donc déjà minimisé la recherche au 10e de ce qu’elle était à l’origine. Cependant, nous savons que les données dans un index sont ordonnées. Autrement dit le coût d’une recherche n’est pas linéaire mais logarithmique… Par exemple chacune de nos pages de données concernant cet index comporte environ 366 lignes29. Il faut donc 274 pages pour stocker toutes les entrées de cet index30. Pour les pages de navigation de cet index une seule page suffit. En effet, une ligne d’une page de navigation d’index est constituée par la référence du premier nom de la page de données, associé au numéro de cette page de données, soit à nouveau 22 octets. Or la page racine peut adresser jusqu’à 366 pages de données.

Tant est si bien que la recherche de notre nom dans l’index ne nécessite jamais que la lecture de 2 pages et non plus 274 comme si l’on devait lire tout l’index. C’est bien évidemment radicalement moindre que le balayage de toutes les données de la table soit 2 500 pages ! Pour notre cas de figure un rapport 1 250 fois moindre… Dans les faits, on a l’habitude de dire qu’un index bien choisi doit diviser par cent à mille les temps de réponse. Bien entendu SQL Server pose sans vous le dire des index lorsque cela s’avère nécessaire.

Chaque fois que vous placez une contrainte de clef primaire, SQL Server créé un index de type cluster afin de minimiser la durée de vérification de l’unicité. Chaque fois que vous définissez une contrainte d’unicité SQL Server pose, pour les mêmes nécessités, un index non cluster. Reste qu’aucun autre index n’est automatiquement posé par SQL Server sur les intégrités référentielles alors qu’il est bon de poser de manière quasi systématique des index sur toutes les contraintes de clefs étrangères et sur les colonnes les plus fréquemment recherchées. Par exemple dans notre table des employés, les colonnes nom, matricule et numéro de sécurité sociales devraient avoir chacune un index. J’ai parlé de cluster, mais qu’est-ce qu’un index cluster ? C’est un index qui mélange la table et l’index.