Les nouvelles méthodes d’indexation

Retrouver de l’information à partir de mots clés, naviguer dans les bases de données, faire des statistiques sur des sous-ensembles de données, voici quelques usages des index. Les bases de données modernes permettent d’effectuer ces fonctions tout en cachant à l’utilisateur l’usage qui est fait des index. Ceci fait que seuls les concepteurs d’applications utilisant les bases de données « connaissent » les index, et encore, on leur reproche souvent, de ne pas les connaître assez bien pour les utiliser de façon performante !
Or les systèmes de gestion des bases de données les plus utilisés aujourd’hui (DB2 et Oracle) remontent à une vingtaine d’années, les systèmes d’indexation qu’ils utilisent aussi. Les index classiques sont des fichiers qui contiennent un « résumé ordonné » de certaines informations d’une base de données. Ces fichiers résident sur des disques et leur structure a été conçue pour tenir le moins de place possible sur ces disques.
Il y a 20 ans, la mémoire sur disque coûtait plus de 100 fois plus cher que la mémoire électronique d’un PC d’aujourd’hui ; même en comptant le prix du PC qui permet d’ailleurs de consulter sa mémoire 10 fois plus vite que le faisaient les gros ordinateurs à l’époque. Il y a 20 ans, 4 milliards de caractères constituaient une grande base de données (de 10 millions de clients avec adresses etc.). Aujourd’hui on peut acheter un PC avec 4 milliards de caractères de mémoire vive, pour quelques centaines d’Euros.
En fonction de ces remarquables progrès technologiques, les index d’hier sont-ils les mieux adaptés pour les bases de données d’aujourd’hui ? Y a-t-il des techniques permettant d’utiliser ces progrès pour faire de la recherche de données beaucoup plus performante ? Comment implémenter ces techniques dans des applications utilisant les bases de données standards ?

Les index classiques aujourd’hui

Les fournisseurs de SGBD ont bien compris qu’une des clés des performances était le fait de rendre les index immédiatement accessibles en les faisant pratiquement résider en mémoire.
C’est ainsi que DB2, le SGBD d’IBM, offre des tailles de buffers sans cesse croissantes pour ses index et permettra, dès la prochaine version, d’utiliser des clés de taille variable (donc plus compactes).
Il n’en reste pas moins que les index classiques ont du mal à suivre les besoins insatiables des utilisateurs (par exemple en recherche multicritères) et que la multiplicité des index rend leur mise à jour difficile, la mise à jour d’une ligne de base de données pouvant entraîner celle d’une entrée de chacun des index.
L’index classique a donc tendance à devenir l’objet le plus critique de l’exploitation d’un SGBD. Les réorganisations d’index, en particulier, sont plus nombreuses et globalement plus coûteuses que les réorganisations des tables elles-mêmes.

Les nouveaux index

Les techniques utilisées pour les index modernes ne sont pas si récentes que cela. L’auteur avait mis en œuvre il y a 25 ans une technique de signature booléenne sous le nom « d’index à masques aléatoires » en l’utilisant pour une sous indexation de bases de données d’assurances. Ce sont les progrès technologiques et la diminution des coûts associés qui ont permis de généraliser leurs applications.

La structure

Parce que l’index peut être mis en mémoire, il n’est plus nécessaire de limiter la quantité d’informations qui est consultée. Ainsi, dans une base de données SQL de noms et adresses, on pourrait avoir un index sur les noms ainsi qu’un index sur les codes postaux. La recherche de « MARTIN 75015 » consisterait à :

• extraire du premier index les numéros de ligne des « MARTIN » en lisant la portion de l’index qui les contient ;
• extraire du second les numéros de ligne des « 75015 » en lisant la portion de l’index qui les contient ;
• fusionner les listes pour obtenir les numéros de lignes communs.

En mémoire, il peut être plus simple de constituer une liste (index) d’entrées contenant chacune le nom, le code postal et le numéro de la ligne correspondante (de la base de données). La recherche consiste alors à examiner toutes les lignes en ne retenant que celles contenant « MARTIN 75015 ».
La mise en mémoire permet de réaliser un index unique contenant une entrée pour chaque ligne, cette entrée contenant toutes les informations « indexables » de la ligne. Ces entrées peuvent être chaînées par homonyme facilitant les recherches. Un tel index est mis à jour beaucoup plus facilement car il n’y a pas de problème de voisinage des informations (un « MARTIN » n’a pas à être physiquement voisin d’un autre).
Parce que ces recherches consomment une seule ressource, l’unité centrale, il est préférable de placer chaque index sur un ordinateur dédié de type PC qui devient alors un serveur d’indexation.

Le parallélisme

Le parallélisme de la recherche peut être obtenu en morcelant (virtuellement) la base de données de manière artificielle, chaque morceau ayant son index propre (partition). Chacune des partitions d’index réside sur un ordinateur différent ; ce qui permet à la fonction de recherche d’interroger simultanément chaque partition.
Avec 10 ordinateurs ainsi en parallèle les temps de recherche sont divisés par 10. Le fait de partitionner un index n’impose aucunement de partitionner physiquement la base de données. Une base de données peut ainsi croître indéfiniment sans que les temps de recherche n’augmentent.

La signature booléenne

Quand la plupart des informations d’une base de données peuvent servir à l’indexation, l’index contient pratiquement autant d’informations que la base, ce qui le rend quelque peu redondant mais surtout contribue à allonger les temps de recherche.
On obtient un index réduit en remplaçant chaque mot clé d’une entrée par sa signature booléenne qui est une chaîne de bits de longueur fixe dont la plupart sont des zéros, puis en faisant un « ou logique » de chacune des chaînes obtenues. On obtient ainsi la signature booléenne de l’entrée d’index.
Pour rechercher les entrées contenant par exemple 3 mots clés, on calcule la signature de chacune, on fait un « ou logique » des trois et on ne retient que les entrées d’index dont la signature « contient logiquement » le résultat. Pour ces seules entrées, on examine soit l’index total s’il existe, soit la base de données, sachant qu’une entrée peut « contenir » le résultat par hasard.
La génération de la signature booléenne est basée sur des fonctions pseudo aléatoires (randomisation) et le nombre de bits à 1 dépend de la fréquence du critère. Un critère fréquent (par exemple satisfait par une ligne sur 10) ne comportera que 2 ou 3 bits à 1 (signature fine), un critère rare pourra aller jusqu’à 20 bits à 1 (signature grasse).
La taille d’une signature est typiquement de quelques centaines de bits (quelques dizaines de caractères) ; ce qui la rend nettement moins encombrante qu’une ligne de base de données. Ainsi cette méthode apporte un gain de performances très important du fait de la simplicité du test d’appartenance (contenance logique) et de l’encombrement réduit.

Application aux bases existantes

L’utilisation de SGBD relationnels n’est pas remise en cause par ces méthodes d’indexation. Ceux-ci ont en effet des avantages indéniables comme la sécurité des données, l’intégrité référentielle, l’existence de facilités d’accès on line et off line et d’utilitaires performants ainsi que le partage des ressources.
Ces SGBD peuvent toutefois tirer avantage d’index ad hoc particulièrement dans le domaine de la recherche documentaire et chaque fois que des recherches multicritères sont utilisées.
La méthode consiste alors à utiliser un ou plusieurs serveurs d’index qui recevront les mouvements de mise à jour de la base de données, et sauront répondre à des questions telles que « donnez-moi la liste des lignes susceptibles de contenir les critères suivants… ». Ce dispositif devient alors un accélérateur de SQL utilisable aussi bien par un infocentre que par des applications de gestion aux besoins pointus.

Contact :

Bernard CONNES-LAFFORET
Tél. +33 (0)1 48 97 38 38
bernard.lafforet@infotel.com

retour au sommaire