Accueil / Articles PiApplications. / La plate-forme Java / Utilisation de classes particulières

Création et emploi d'un fichier index.

Un fichier index est un fichier constitué de deux colonnes : la clef et une donnée référencée par cette clef. La clef est l'information qui permet d'accéder rapidement à une donnée.

Idéalement, s'il était toujours possible de trier le fichier sur disque dans l'ordre des clefs, il suffirait de la transposer en mémoire puis de faire une recherche dichotomique sur les clefs pour accéder très vite à la donnée cherchée. Hélas, dès que le nombre de clefs commence à dépasser la dizaine de milliers, la réorganisation d'un fichier lors de chaque insertion de clef exige un coût en temps prohibitif en raison du très grand nombre d'entrées/sorties que le ré ordonnancement exige.

Ce problème est résolu classiquement par un arbre B+ persistant sur disque. Ce type d'algorithme est complexe et donc coûteux à mettre au point. On trouve d'ailleurs assez peu de librairies "libres" sur ce sujet dans le monde Java.

Une solution de contournement rapide est d'utiliser SQLLite qui dispose d'un pilote JDBC "natif" également dans le monde "libre". SQLLite est une solution séduisante car le "moteur" est constitué d'une simple librairie dynamique. Le pilote JDBC "natif" s'appuie, quant à lui, sur une seconde librairie en code natif avec intégration JNI à toute JVM. Cela fait de SQLLite un moyen de persistance léger, facile à intégrer et multi plate-forme. Il n'est donc pas étonnant que que ce soit le choix fait par Android dès qu'il faut répondre à un besoin de persistance. Après avoir mis cette solution en oeuvre, on constate malheureusement que l'insertion n'est pas des plus performantes. Sur notre machine, chaque insertion (clef aléatoire) consomme environ 8 ms. Ainsi, 100 000 tuples nécessitent pratiquement un délai de 2 minutes.

C'est pourquoi nous avons décidé de concevoir un moyen de persistance 100% Java. Pour éviter le développement from scratch nous allons reprendre aux arbres B+ le principe des pages de clefs mais en nous appuyant sur la classe TreeMap<K,T>. Voici le schéma de principe du fonctionnement de cet index :

Principe du fonctionnement de l'index.

Une page 'résumé' décrit l'arbre des pages. Avec 1000 pages de 1000 clefs, on peut déjà créer un index d'un million d'entrées. La page résumé est donc relativement concise en mémoire alors qu'elle permet de référencer des dizaines de milliers de clefs. Dans la pratique, dans une page de 512 kio, on peut stocker plus de 2000 clefs de type chaînes d'environ 256 caractères chacune.

La page 'résumé' est la seule page gérée par la classe IndexFile. Elle dresse la liste des pages identifiées par leur numéro unique référencée par une clef qui est la clef la plus petite de la page référencée. L'arbre binaire de la page 'résumé' permet donc de reconstruire virtuellement un index linéaire dans lequel toutes les clefs seraient ordonnées. Comme toute page de clef, elle dérive de la classe KeyPage.

Chacune des pages référencée ne peut contenir au maximum qu'un nombre donné de clefs. Comme l'index n'exige jamais plus de deux pages en mémoire simultanément (en plus de la page 'résumé'), le choix de ce nombre maximum de clefs associé à la taille constante de chacune des clefs permet la maîtrise de la consommation de mémoire. La taille des clefs est constante car elle sont stockées sous une forme binaire (tableau d'octets) de taille constante (sérialisation et désérialisation imposées par l'interface IBinaryData<T>). cela ne veut pas dire que pour une classe donnée de clef elle doivent toute faire la même taille (le même nombre de caractères par exemple si la clef est de classe String). Cela veut simplement dire qu'elles doivent toutes pouvoir se sérialiser dans un tableau de cette taille. Le choix d'une taille constante permet de lire très vite la page sans être obligé de perdre du temps à chercher les délimiteurs.

Chaque entrée d'une page de clefs référence un entier qui est un pointeur sur le 1er octet de la donnée référencée par la clef dans le fichier de données (adressage indirect). Notez que ce mécanisme n'impose pas que le fichier de données ait des entrée de taille constante. Les entrées du fichier de données peuvent être de taille quelconque tant que l'on est capable de situer l'adresse dans le fichier du 1er octet de chaque entrée au moment de son ajout à l'index.

Lorsque l'on insère une nouvelle clef, l'objet de classe IndexFile cherche la page dont la clef est immédiatement à la clef à insérer. Si la page courante n'est pas cette page, il charge la nouvelle page qui devient la page courante. Si la page d'insertion dispose encore de place (nombre maximum d'entrées non encore atteint), la clef est ajoutée à la page. Notez que pour des raisons de performance, la page n'est pas sauvegardée sur disque à ce moment là. Elle est sauvegardée chaque fois qu'elle est déchargée de la mémoire.

Mais que ce passe-t-il lorsque la clef à insérer doit se faire dans une page dont le nombre maximum de clefs est atteint ? Cette page est alors scindée en deux. La classe IndexFile cherche ensuite laquelle de ces deux pages devient la page d'insertion puis insère la nouvelle clef. C'est lors de ce mécanisme que les deux pages doivent être chargées en mémoire simultanément (la consommation de mémoire est toutefois identique à la précédente puisque chacune des pages contient la moitié des clefs de la page initiale.

La performance provient du fait que l'on ne réorganise finalement jamais les clefs, que l'on minimise les écritures sur disque et que l'on ne cherche pas à affecter les numéros de page pour refléter leur ordonnancement. Notez également qu'aucun descripteur de fichier ne reste ouvert une fois la page chargée en mémoire. Ces descripteurs ne sont ouverts qu'au chargement et au déchargement de chaque page et refermés immédiatement après.

D'autre part, il est possible d'adjoindre à un index de ce type, un cache (classe Cache) qui en fonction de la mémoire disponible peut accélérer fortement les performances. A titre indicatif, la création d'un index de 100 000 clefs (tirées aléatoirement) sérialisables dans un tampon de 128 octets avec des pages d'au maximum 10 000 clefs nécessite sur notre machine environ 13 ms par clef sans emploi d'un cache. Avec un cache de 100 pages de clefs d'une capacité de libération des 10 pages les moins invoquée et les plus anciennes, ce temps tombe à 36 µs montrant par là, le poids des écritures disques. Chaque page sur disque est d'un volume moyen de 600 kio.

(c) PiApplications 2016