une valeur intercalaire similaire soit insérée peu après.

Si la référence à retirer est la première de la page, alors il faut en sus modifier la page de navigation. Elle même pouvant provoquer la mise à jour de la page de navigation de niveau supérieur si jamais elle constituait, la première référence de cette page, et ainsi de suite ! En outre, et comme nous le verrons par la suite, si la référence de navigation doit changer et que le type de données est de taille variable, il est alors possible de se trouver dans une situation ou la référence ne peut être insérée dans la page et doit être placée dans une page annexe.

Certes, pour ce dernier cas, on plonge dans la Loi de Murphy3, mais en matière informatique nous savons qu’elle est omniprésente et la Loi des grands nombres augmente sa fréquence d’apparition en fonction du volume des données et de la fréquence des mises à jour ! Ainsi, au fil des suppressions, des trous apparaissent dans les pages de l’index. Mais à tout bien réfléchir, ce problème est le moins pire : l’index reste d’un volume comparable à sa structure originelle et la lecture des trous n’est pas vraiment pénalisante. Reste que bien reconstruit, l’index sera plus rapide à scruter.