Comment un index arrive t-il à  se fragmenter,

une page de données. Comme dans le cas de la table, chaque page contient un nombre de lignes variables ordonnées. Les lignes peuvent être de longueur différentes si vos types de données dans l’index sont de taille variable (par exemple un VARCHAR). Un index est dit dense si les pages sont remplies au maximum. Ce maximum n’est jamais 100 %, sauf hasard extraordinaire, car il y a presque toujours dans chaque page un petit espace résiduel ou plus aucune ligne ne peut se loger.

Un index dense est rapide à lire car il occupe moins de place et donc coûte moins cher en lecture qu’un index grevé de "trous". S’il est dense et parfaitement ordonné, alors on dit de l’index qu’il est optimum. Imaginons un index dense, ordonné, donc optimum, couvrant pour une requête considérée, donc parfait pour notre exemple. Que peut-il lui arriver au fur et à mesure de sa vie ? Puisque cet index est dense, chaque nouvelle insertion va provoquer le scindement de la page de données dans laquelle la référence doit être insérée en deux nouvelles pages. On appelle se phénomène le "split" de page. L’une des pages contiendra toutes les données avant cette référence, l’autre toutes les données après, et l’une des deux (si possible la moins remplie si l’algorithme est bien fait) contiendra en outre la nouvelle référence.

Bien entendu le phénomène a toutes les chances de se reproduire pour les pages de navigation, car ces dernières peuvent aussi être remplies à 100 % (ou tout au moins avec une valeur ne permettant pas l’ajout d’une nouvelle entrée de navigation). En effet, puisque la page feuille a été scindée en deux, il faut bien ajouter une nouvelle référence pour s’aiguiller sur l’adresse de la nouvelle page. Pour peu que l’index comporte différents niveaux de pages de navigation, ce phénomène peut se reproduire jusqu’au sommet, voire provoquer l’apparition d’un niveau supplémentaire dans la structure arborescente de l’index ! N’oublions pas que l’on parle d’arbre équilibré, c’est à dire d’arbres dont les feuilles sont toutes au même niveau, ce qui oblige le système à certaines contorsions algorithmiques pour maintenir la structure d’aplomb.

Bref, au fur et à mesure des insertions, de nombreuses pages vont se scinder provoquant une augmentation sensible du volume de l’index. La lecture, comme la recherche de l’index sera donc plus longue et moins efficace que dans notre index originel dit optimum.