Cours complet pour apprendre les systèmes de gestion de bases de données

Le programmeur travaillant au niveau du langage machine, ainsi que les modules méthodes d'accès, accèdent au noyau du gestionnaire de fichiers à l'aide d'un ensemble d'instructions de manipulation de fichiers. Tout d'abord, deux instructions permettent de créer et de détruire un fichier. Puis, avant de lire ou d'écrire des données dans un fichier, il faut contrôler son identité et ouvrir un chemin pour les données entre le programme effectuant les lectures-écritures et la mémoire secondaire. Cette opération est généralement effectuée par une instruction d'ouverture : ouvrir. L'opération inverse est exécutée lorsque le programme se désintéresse du fichier par une instruction de fermeture : fermer.

Un fichier étant généralement discontinu sur mémoire secondaire, il est utile de pouvoir adresser son contenu à l'aide d'une adresse continue de 0 à n appelée adresse relative. Cela présente l'intérêt de disposer d'un repérage indépendant de la localisation du fichier sur mémoire secondaire (en cas de recopie du fichier, l'adresse relative ne change pas) et de pouvoir assurer que l'on travaille bien à l'intérieur d'un fichier sans risque d'atteindre un autre fichier (il suffit de contrôler que l'adresse relative ne dépasse pas la taille du fichier).

Pour réaliser l'adressage relatif, on divise généralement le fichier en pages (on trouve également selon les implantations les termes de bloc, groupe, intervalle) : une adresse relative octet se compose alors d'un numéro de page suivi d'un numéro d'octet dans la page. Pour éviter un nombre trop important d'entrées-sorties, la taille de la page est choisie de façon à contenir plusieurs enregistrements physiques et des tampons d'une page sont utilisés. La taille de la page, fixée dans le système ou lors de la création du fichier, est le plus souvent de l'ordre de quelques kilos (K) octets (par exemple, 4K). Elle dépend parfois de l'organisation du fichier. Celle d'un enregistrement physique dépasse rarement quelques centaines d'octets.

Ainsi, l'analyseur d'un gestionnaire de fichiers offre généralement la possibilité d'accéder à une ou plusieurs pages d'adresse relative (numéro de page) donnée dans un fichier. Il peut aussi permettre d'accéder directement aux octets, donc de lire une suite d'octets à partir d'une adresse relative en octets dans le fichier. L'analyseur se compose essentiellement d'algorithmes d'allocation de mémoire secondaire et de conversion d'adresse relative page en adresse réelle de l'enregistrement physique (secteur sur disque), et réciproquement. Finalement, il permet de banaliser toutes les mémoires secondaires en offrant un accès par adresse relative uniforme, avec quelques restrictions cependant : il est par exemple interdit d'accéder autrement qu'en séquentiel à une bande magnétique.

Les articles de l'usager sont alors implantés dans les pages par les méthodes d'accès selon l'organisation choisie. Si plusieurs articles sont implantés dans une même page, on dit qu'il y a blocage. Dans le cas où les articles sont implantés consécutivement sans trou à la suite les uns des autres, on dit qu'il y a compactage : aucune place n'est alors perdue sur la mémoire secondaire, mais des articles peuvent être à cheval sur plusieurs pages.

La taille d'un fichier est fixée soit de manière statique lors de sa création, soit de manière dynamique au fur et à mesure des besoins. Des solutions intermédiaires sont possibles avec une taille initiale extensible par paliers. Dans tous les cas, il est nécessaire de réserver des zones de mémoires secondaires continues pour le fichier. Ces zones sont appelées régions.

Comme les fichiers vivent et sont de tailles différentes, les régions successivement allouées à un fichier ne sont généralement pas contiguës sur une mémoire secondaire. Le gestionnaire de fichiers doit alors pouvoir retrouver les régions composant un fichier. Pour cela, il peut soit garder la liste des régions allouées à un fichier dans une table, soit les chaîner, c'est-à-dire mettre dans une entrée d'une table correspondant à chaque région l'adresse de la région suivante.

La taille d'une région peut varier à partir d'un seuil minimal appelé granule (par exemple une piste, etc.). Il devient alors possible d'allouer des régions de taille variable à un fichier, mais toujours composées d'un nombre entier de granules consécutifs. Un granule est souvent choisi de taille égale à une piste ou à une fraction de piste.

Lorsqu'un fichier est détruit ou rétréci, les régions qui lui étaient allouées et qui ne sont plus utilisées sont libérées. Les granules composants sont alors libérés et introduits dans la liste des granules libres. Afin de maximiser la proximité des granules alloués à un fichier, plusieurs méthodes d'allocations ont été proposées. Nous allons étudier ci-dessous quelques algorithmes d'allocation des régions aux fichiers.

Il est nécessaire de pouvoir identifier un volume. En effet, lorsqu'un volume amovible n'est pas actif, il peut être enlevé. Il faut donc une intervention manuelle pour monter/démonter un volume sur un tourne-disque. Cette opération est exécutée par un opérateur. Celui-ci reconnaît un volume grâce à un numéro (ou nom) attribué à chaque volume. Pour pouvoir contrôler les opérateurs lors des montages/démontages de volume et éviter les erreurs, ce numéro est écrit sur le volume dans le label du volume.

Lorsqu'on a retrouvé et monté le volume supportant un fichier, il faut retrouver le fichier sur le volume. Pour cela, chaque fichier possède un ensemble de données descriptives (nom, adresse début, localisation, etc.) regroupées dans un descripteur du fichier.

Il est important que l'ensemble des descripteurs de fichiers contenu sur un volume définisse tous les fichiers d'un volume. On obtient ainsi des volumes autodocumentés, donc portables d'une installation à une autre. Pour cela, les descripteurs de fichiers d'un volume sont regroupés dans une table des matières du volume appelée catalogue.

Le catalogue est soit localisé en un point conventionnel du volume (par exemple, à partir du secteur 1), soit écrit dans un fichier spécial de nom standard. Le descripteur de ce premier fichier peut alors être contenu dans le label du volume. En résumé, la figure III.5 illustre l'organisation des informations étudiées jusqu'à présent sur un volume.

Quand le nombre de fichiers d'une installation devient élevé, on est conduit à classer les descripteurs de fichiers dans plusieurs catalogues, par exemple un par usager. Les descripteurs des fichiers catalogues peuvent alors être maintenus dans un catalogue de niveau plus élevé. On aboutit ainsi à des catalogues hiérarchisés qui sont implantés dans de nombreux systèmes [Daley65].

Dans un système à catalogues hiérarchisés, chaque niveau de catalogue est généralement spécialisé. Par exemple, le niveau 1 contient un descripteur de fichier catalogue par usager. Pour chaque usager, le niveau 2 peut contenir un descripteur de fichier par application. Enfin, pour chaque couple <usager-application>, le niveau 3 peut contenir la liste des descripteurs de fichiers de données. La figure III.6 illustre un exemple de catalogue hiérarchisé. Le descripteur du catalogue de niveau 1 est appelé racine.

La présence de catalogue hiérarchisé conduit à introduire des noms de fichiers composés. Pour atteindre le descripteur d'un fichier, il faut en effet indiquer le nom du chemin qui mène à ce descripteur. Voici des noms de fichiers possibles avec le catalogue représenté figure III.6 :

• PIERRE
• PIERRE > BASES-DE-DONNEES
• PIERRE > BASES-DE-DONNES > MODELES

Afin d'éviter un cloisonnement trop strict des fichiers, les systèmes à catalogues hiérarchisés permettent en général l'introduction de liens. Un lien est simplement un descripteur qui contient un pointeur logique sur un autre descripteur, éventuellement dans une autre branche de la hiérarchie. Par exemple, le descripteur de nom > LIONEL > BASES-DE-DONNEES > LANGAGES pourra être un descripteur de type lien indiquant qu'il est un synonyme du descripteur > PIERRE > BASES-DE-DONNEES > LANGAGES. Les noms d'usagers étant généralement fournis par le système, des descripteurs de type lien permettent le partage des fichiers entre usagers.

Pour simplifier la nomination des fichiers, les systèmes à catalogues hiérarchisés gèrent bien souvent la notion de catalogue de base, encore appelé catalogue courant. Lors du début de session (login), le système positionne le catalogue courant par exemple sur les applications de l'usager. Celui-ci peut alors se déplacer par rapport à ce catalogue courant. Par exemple, Pierre passera au catalogue bases-de-données par le nom > Bases-de-données. Celui-ci deviendra alors son catalogue courant. L'accès au fichier modèles se fera alors par le nom > Modèles. Le retour au catalogue initial de Pierre s'effectuera par < < ; en effet, les noms de répertoires sont déterminés de manière unique quand on remonte la hiérarchie.

Le noyau d'un gestionnaire de fichiers inclut également des fonctions de contrôle des fichiers : partage des fichiers, résistances aux pannes, sécurité et confidentialité des données. Nous n'étudions pas ici ces problèmes, qui font l'objet de nombreux développements dans le contexte des bases de données, donc dans les chapitres suivants.

Il existe différentes stratégies d'allocation de la mémoire secondaire aux fichiers. Une bonne stratégie doit chercher :

1. À minimiser le nombre de régions à allouer à un fichier pour réduire d'une part les déplacements des bras des disques lors des lectures en séquentiel, d'autre part le nombre de descripteurs de régions associés à un fichier ;
2. À minimiser la distance qui sépare les régions successives d'un fichier, pour réduire les déplacements de bras en amplitude.

Les stratégies peuvent être plus ou moins complexes. La classe la plus simple de stratégies alloue des régions de taille fixe égale à un granule, si bien que les notions de granule et région sont confondues. Une classe plus performante alloue des régions de tailles variables, composées de plusieurs granules successifs. Nous allons approfondir ces deux classes ci-dessous.

Auparavant, il est nécessaire de préciser que toutes les méthodes conservent une table des granules libres ; une copie de cette table doit être stockée sur disque pour des raisons de fiabilité. La table elle-même peut être organisée selon différentes méthodes :

• liste des granules ou régions libres, ordonnée ou non ; l'allocation d'une région consiste alors à enlever la région choisie de cette liste pour l'associer au descripteur du fichier ;
• table de bits dans laquelle chaque bit correspond à un granule ; l'allocation d'un granule consiste alors à trouver un bit à 0, le positionner à 1 et à adjoindre l'adresse du granule alloué au descripteur du fichier.

Ces stratégies confondent donc les notions de région et de granule. Elles sont simples et généralement implantées sur les petits systèmes. On peut distinguer :

• La stratégie du premier trouvé : le granule correspondant à la tête de liste de la liste des granules libres, ou au premier bit à 0 dans la table des granules libres, est choisi.
• La stratégie du meilleur choix : le granule le plus proche (du point de vue du déplacement de bras) du dernier granule alloué au fichier est retenu.

Ces stratégies permettent d'allouer des régions composées de plusieurs granules consécutifs, selon les besoins des fichiers. Le noyau du gestionnaire de fichiers reçoit alors des demandes d'allocation et libération de régions de tailles variables. Dans le cas où aucune région de la taille demandée ne peut être constituée par des granules consécutifs, la demande peut éventuellement être satisfaite par plusieurs régions. Parmi les stratégies par région, on peut distinguer :

• La stratégie du plus proche choix. Deux régions libres consécutives sont fusionnées en une seule. Lors d'une demande d'allocation, la liste des régions libres est parcourue jusqu'à trouver une région de la taille demandée ; si aucune région de la taille demandée n'est libre, la première région de taille supérieure est découpée en une région de la taille cherchée qui est allouée au fichier et une nouvelle région libre correspondant au reste.
• La stratégie des frères siamois. Elle offre la possibilité d'allouer des régions de 1, 2, 4, 8… 2^K granules. Des listes séparées sont maintenues pour les régions libres de dimensions 2⁰, 2¹… 2^K granules. Lors d'une demande d'allocation, une région libre peut être extraite de la liste des régions libres de taille 2ⁱ⁺¹ pour constituer deux régions libres de taille 2ⁱ. Lors d'une libération, deux régions libres consécutives (deux siamoises) de taille 2ⁱ sont fusionnées afin de constituer une région libre de taille 2ⁱ⁺¹. L'algorithme de recherche d'une région libre de taille 2ⁱ consiste à chercher cette région dans la liste des régions de taille 2ⁱ. Si cette liste est vide, on recherche alors une région de taille 2ⁱ⁺¹ que l'on divise en deux. S'il n'y en a pas, on passe alors au niveau suivant 2ⁱ⁺², etc., jusqu'à atteindre le niveau k ; c'est seulement dans le cas où les listes 2ⁱ à 2^K sont vides que l'on ne peut satisfaire la demande par une seule région. Cet algorithme, qui est emprunté aux mécanismes d'allocation de segments dans les systèmes paginés [Lister84], est sans doute le plus efficace ; il est aussi très bien adapté à certaines méthodes d'accès.

En résumé, les stratégies par région de tailles variables sont en général plus efficaces du point de vue du déplacement de bras et taille de la table des régions d'un fichier. Un problème commun à ces stratégies peut cependant survenir après des découpages trop nombreux s'il n'existe plus de régions de taille supérieure à un granule. Dans ce cas, l'espace disque doit être réorganisé (ramassage des miettes). Ce dernier point fait que les stratégies par granule restent les plus utilisées.

La première organisation hachée dynamique a été proposée pour des tables en mémoire [Knott71]. Puis plusieurs techniques fondées sur le même principe, mais différentes ont été proposées pour étendre les possibilités du hachage à des fichiers dynamiques [Fagin79, Larson78, Litwin78, Larson80, Litwin80]. Le principe de base de ces différentes techniques est la digitalisation progressive de la fonction de hachage : la chaîne de bits résultant de l'application de la fonction de hachage à la clé est exploitée progressivement bit par bit au fur et à mesure des extensions du fichier.

Plus précisément, les méthodes dynamiques utilisent une fonction de hachage de la clé h(K) générant une chaîne de N bits, où N est grand (par exemple 32). La fonction est choisie de sorte qu'un bit quelconque de h(K) ait la même probabilité d'être à 1 ou à 0. Lors de la première implantation du fichier haché, seuls les M premiers bits de h(K) (avec M petit devant N) sont utilisés pour calculer le numéro de paquet dans lequel placer un article. Ensuite, lorsque le fichier est considéré comme saturé (par exemple, lorsqu'un premier paquet est plein), une partie du fichier (par exemple le paquet plein) est doublée : une nouvelle région est allouée pour cette partie et les articles de l'ancienne partie sont distribués entre l'ancienne partie et la nouvelle en utilisant le bit M+1 de la fonction de hachage. Ce processus d'éclatement est appliqué chaque fois que le fichier est saturé, de manière récursive. Ainsi, les bits (M+1), (M+2), (M+3)… de la fonction de hachage sont successivement utilisés et le fichier peut grandir jusqu'à 2^N paquets. Une telle taille est suffisante sous l'hypothèse que N soit assez grand.

Les méthodes de hachage dynamique diffèrent par les réponses qu'elles apportent aux questions suivantes :

• (Q1) Quel est le critère retenu pour décider qu'un fichier haché est saturé ?
• (Q2) Quelle partie du fichier faut-il doubler quand un fichier est saturé ?
• (Q3) Comment retrouver les parties d'un fichier qui ont été doublées et combien de fois ont-elles été doublées ?
• (Q4) Faut-il conserver une méthode de débordement, et si oui laquelle ?

Nous présentons ci-dessous deux méthodes qui nous paraissent des plus intéressantes : le hachage extensible [Fagin79] et le hachage linéaire [Litwin80]. Vous trouverez des méthodes sans doute plus élaborées dans [Larson80], [Lomet83], [Samet89] ainsi que des évaluations du hachage extensible dans [Scholl81] et du hachage linéaire dans [Larson82].

Le hachage extensible [Fagin79] apporte les réponses suivantes aux questions précédentes :

• (Q1) Le fichier est étendu dès qu'un paquet est plein ; dans ce cas, un nouveau paquet est ajouté au fichier.
• (Q2) Seul le paquet saturé est doublé lors d'une extension du fichier. Il éclate selon le bit suivant du résultat de la fonction de hachage appliquée à la clé h(K). Les articles ayant ce bit à 0 restent dans le paquet saturé, alors que ceux ayant ce bit à 1 partent dans le nouveau paquet.
• (Q3) La fonction de hachage adresse un répertoire des adresses de paquets ; la taille du répertoire est 2**(M+P) où P est le niveau du paquet qui a éclaté le plus grand nombre de fois. Chaque entrée du répertoire donne l'adresse d'un paquet. Les 2**(P-Q) adresses correspondant à un paquet qui a éclaté Q fois sont identiques et pointent sur ce paquet. Ainsi, par l'indirection du répertoire, le système retrouve les paquets.
• (Q4) La gestion de débordement n'est pas nécessaire.

Le hachage extensible associe donc à chaque fichier un répertoire des adresses de paquets. Au départ, M bits de la fonction de hachage sont utilisés pour adresser le répertoire. À la première saturation d'un paquet, le répertoire est doublé, et un nouveau paquet est alloué au fichier. Le paquet saturé est distribué entre l'ancien et le nouveau paquet, selon le bit suivant (M+1) de la fonction de hachage. Ensuite, tout paquet plein est éclaté en deux paquets, lui-même et un nouveau paquet alloué au fichier. L'entrée du répertoire correspondant au nouveau paquet est mise à jour avec l'adresse de ce nouveau paquet si elle pointait encore sur le paquet plein. Sinon, le répertoire est à nouveau doublé. En résumé, le hachage extensible peut être défini comme suit :

Cette organisation est illustrée figure III.9. Nous montrons ici un répertoire adressé par 3 bits de la fonction de hachage. Le fichier avait été créé avec deux paquets et était adressé par le premier bit de la fonction de hachage (celui de droite). Puis le paquet 1 a éclaté et a été distribué entre le paquet 01 et 11. Le paquet 11 a éclaté à son tour et a été distribué entre le paquet 011 et le paquet 111. Le répertoire a donc été doublé deux fois (P = 2 alors que M = 1).

Un fichier haché extensible est donc structuré en deux niveaux : le répertoire et les paquets. Soit P le niveau d'éclatement maximal du fichier. Le répertoire contient un en-tête qui indique la valeur de M+P, le nombre de bits de la fonction de hachage utilisés pour le paquet ayant le plus éclaté. Après l'en-tête figurent des pointeurs vers les paquets. Les M+P premiers bits de la fonction de hachage sont donc utilisés pour adresser le répertoire. Le premier pointeur correspond à la valeur 0 des (M+P) premiers bits de la fonction de hachage, alors que le dernier correspond à la valeur 2**(M+P) - 1, c'est-à-dire aux (M+P) premiers bits à 1. Soit Q le nombre d'éclatements subis par un paquet. À chaque paquet sont associés dans le répertoire 2**(P-Q) pointeurs qui indiquent son adresse. Le répertoire pointe ainsi plusieurs fois sur le même paquet, ce qui accroît sa taille.

L'insertion d'un article dans un fichier haché extensible nécessite tout d'abord l'accès au répertoire. Pour cela, les (M+P) bits de la clé sont utilisés. L'adresse du paquet dans lequel l'article doit être placé est ainsi lue dans l'entrée adressée du répertoire. Si le paquet est plein, alors celui-ci doit être doublé et son niveau d'éclatement Q augmenté de 1 ; un paquet frère au même niveau d'éclatement doit être créé ; les articles sont répartis dans les deux paquets selon la valeur du bit (M+Q+1) de la fonction de hachage. Le mécanisme d'éclatement de paquet est illustré figure III.10. Si le niveau du répertoire P est supérieur à Q, alors le répertoire doit simplement être mis à jour, 2**(P-Q+1) pointeurs étant forcés sur l'adresse du nouveau paquet. Si P est égal à Q, alors le répertoire doit être doublé.

En cas de suppression dans un paquet adressé par M+Q bits de la fonction de hachage, il est possible de tenter de regrouper ce paquet avec l'autre paquet adressé par M+Q bits s'il existe. Ainsi, la suppression d'un article dans un paquet peut théoriquement conduire à réorganiser le répertoire. En effet, si le paquet concerné est le seul paquet avec son frère au niveau d'éclatement le plus bas et si la suppression d'un article laisse assez de place libre pour fusionner les deux frères, la fusion peut être entreprise. Le niveau d'éclatement du répertoire doit alors être réduit de 1 et celui-ci doit être divisé par deux en fusionnant les blocs jumeaux.

Le hachage linéaire [Litwin80] apporte les réponses suivantes aux questions déterminantes d'une méthode de hachage dynamique :

• (Q1) Le fichier est étendu dès qu'un paquet est plein, comme dans le hachage extensible ; un nouveau paquet est aussi ajouté au fichier à chaque extension.
• (Q2) Le paquet doublé n'est pas celui qui est saturé, mais un paquet pointé par un pointeur courant initialisé au premier paquet du fichier et incrémenté de 1 à chaque éclatement d'un paquet (donc à chaque saturation) ; lorsque ce pointeur atteint la fin de fichier, il est repositionné au début du fichier.
• (Q3) Un niveau d'éclatement P du fichier (initialisé à 0 et incrémenté lorsque le pointeur courant revient en début de fichier) est conservé dans le descripteur du fichier ; pour un paquet situé avant le pointeur courant, (M+P+1) bits de la fonction de hachage doivent être utilisés alors que seulement (M+P) sont à utiliser pour adresser un paquet situé après le pointeur courant et avant le paquet 2**(M+P).
• (Q4) Une gestion de débordement est nécessaire puisqu'un paquet plein n'est en général pas éclaté ; il le sera seulement quand le pointeur courant passera par son adresse. Une méthode de débordement quelconque peut être utilisée.

En résumé, il est possible de définir le hachage linéaire comme suit :

La figure III.11 illustre un fichier haché linéairement. Le pointeur courant est situé en début du 3^e paquet (paquet 10). Les paquets 000 et 001, 100 et 101 (c'est-à-dire 0, 1, 4 et 5) sont adressés par les trois premiers bits de la fonction de hachage, alors que les paquets 10 et 11 (c'est-à-dire 2 et 3) sont seulement adressés par les deux premiers bits. Lors du prochain débordement, le paquet 10 (2) éclatera, quel que soit le paquet qui déborde.

Notons que le hachage linéaire peut aussi s'implémenter avec un répertoire. Dans ce cas, le pointeur courant est un pointeur sur le répertoire : il référence l'adresse du paquet suivant à éclater. L'avantage du hachage linéaire est alors la simplicité de l'algorithme d'adressage du répertoire ; on utilise tout d'abord M+P bits de la fonction de hachage ; si l'on est positionné avant le pointeur courant, on utilise un bit de plus, sinon on lit l'adresse du paquet dans le répertoire. À chaque éclatement, le répertoire s'accroît d'une seule entrée. L'inconvénient est bien sûr la nécessité de gérer des débordements.

L'insertion d'un article dans un fichier haché linéairement se fait très simplement : si P est le niveau d'éclatement du fichier, (M+P) bits de la clé sont tout d'abord pris en compte pour déterminer le numéro de paquet. Si le numéro obtenu est supérieur au pointeur courant, il est correct ; sinon, un bit supplémentaire de la fonction de hachage est utilisé pour déterminer le numéro de paquet. L'insertion s'effectue ensuite de manière classique, à ceci près que lorsqu'un paquet est saturé, le paquet pointé par le pointeur courant est éclaté ; ce pointeur courant est augmenté de 1 ; s'il atteint le paquet 2**(M+P) du fichier, il est ramené au début et le niveau d'éclatement du fichier est augmenté de un.

De manière analogue au répertoire du hachage extensible, la suppression d'article dans un paquet peut amener la fusion de deux paquets et donc le recul de 1 du pointeur courant. Attention : en général, les paquets fusionnés n'incluent pas le paquet dans lequel a lieu la suppression ; la fusion peut amener des distributions d'articles en débordement.

Une variante de cette méthode consistant à changer la condition d'éclatement a été proposée dans [Larson80]. La condition retenue est l'atteinte d'un taux de remplissage maximal du fichier, le taux de remplissage étant le rapport de la place occupée par les articles sur la taille totale du fichier.

En résumé, les méthodes de hachage dynamique sont bien adaptées aux fichiers dynamiques, c'est-à-dire de taille variable, cependant pas trop gros pour éviter les saturations de paquets trop nombreuses et les accroissements de la taille du catalogue. Leurs limites sont encore mal connues. Le hachage extensible paraît plus robuste face aux mauvaises distributions de clés que le hachage linéaire. Par contre, la gestion d'un répertoire est plus lourde que celle d'un pointeur courant.

Le grand problème des méthodes par hachage reste l'absence de possibilités efficaces d'accès ordonné pour un tri total ou pour des questions sur des plages de valeur. Telle est la limite essentielle, qui nécessite l'emploi d'autres méthodes.

Le principe de base des organisations et méthodes d'accès indexées est d'associer à la clé d'un article son adresse relative dans le fichier à l'aide d'une « table des matières » du fichier. Ainsi, à partir de la clé de l'article, un accès rapide est possible par recherche de l'adresse relative dans la table des matières, puis par un accès en relatif à l'article dans le fichier. Les principales méthodes d'accès indexées se distinguent par le mode de placement des articles dans le fichier et par l'organisation de la table des matières, appelée index.

La figure III.12 illustre cette notion d'index. Le fichier contient les articles a5, a2, a57, a3 et a10. L'index est rangé en fin de fichier comme le dernier article du fichier. Il contient une entrée par article indiquant la clé de l'article et son adresse relative dans le fichier. L'index d'un fichier peut en général être rangé dans le fichier ou plus rarement dans un fichier spécial.

Les étapes successives exécutées pour l'accès à un article dans un fichier indexé sont les suivantes :

1. Accès à l'index qui est monté en mémoire dans un tampon.
2. Recherche de la clé de l'article désiré en mémoire afin d'obtenir l'adresse relative de l'article ou d'un paquet contenant l'article.
3. Conversion de l'adresse relative trouvée en adresse absolue par les couches internes du système de gestion de fichiers.
4. Accès à l'article (ou au paquet d'articles) sur disques magnétiques et transfert dans un tampon du système.
5. Transfert de l'article dans la zone du programme usager.

En général, l'accès à un article dans un fichier indexé nécessite une à trois entrées-sorties pour monter l'index en mémoire, puis une entrée-sortie pour monter l'article en mémoire. Différentes variantes sont possibles, selon l'organisation des articles dans le fichier et de l'index.

Les variantes se distinguent tout d'abord par l'organisation de l'index. Celui-ci peut être trié ou non. Le fait que l'index soit trié autorise la recherche dichotomique. Ainsi, un index contenant n clés, divisé en blocs (d'une page) de b clés, nécessitera en moyenne n/2b accès pour retrouver une clé s'il n'est pas trié ; il suffira de log₂n/b accès s'il est trié. Par exemple, avec n = 10⁶, b = 100 clés, on obtient 10 accès si l'index est trié contre 5 000 accès sinon.

Un index d'un fichier indexé peut contenir toutes les clés (c'est-à-dire celles de tous les articles) ou seulement certaines. Un index qui contient toutes les clés est appelé index dense. Afin de différencier plus précisément les méthodes d'accès obtenues, il est possible d'introduire la notion de densité d'un index.

La densité d'un index varie entre 0 et 1. Un index dense a donc une densité égale à 1. Dans le cas d'index non dense, toutes les clés ne figurent pas dans l'index. Aussi, les articles du fichier ainsi que l'index sont triés. Le fichier est divisé en paquets de tailles fixes et chaque paquet correspond à une entrée en index contenant le doublet : <plus grande clé du paquet-adresse relative du paquet>. La figure III.13 illustre un index non dense et le fichier correspondant. Le paquet 1 contient les articles de clé 1, 3 et 7. La plus grande clé (7) figure dans l'index non dense, etc. L'index est composé ici d'un seul bloc contenant trois clés, la plus grande de chaque paquet.

Comme le fichier peut être trié ou non trié, et l'index dense ou non dense, trié ou non trié, diverses variantes sont théoriquement possibles. Deux méthodes sont particulièrement intéressantes : le fichier séquentiel non trié avec index trié dense, historiquement à la base de l'organisation IS3, et le fichier trié avec index non dense trié, sur lequel sont fondées des organisations telles ISAM, VSAM et UFAS. Il est impossible d'associer un index non dense à un fichier non trié.

Un index peut être vu comme un fichier de clés. Si l'index est grand (par exemple plus d'une page), la recherche d'une clé dans l'index peut devenir très longue. Il est alors souhaitable de créer un index de l'index vu comme un fichier de clés. Cela revient à gérer un index à plusieurs niveaux. Un tel index est appelé index hiérarchisé.

Un index hiérarchisé à un niveau est un index trié, généralement non dense, composé de paquets de clés. Un index hiérarchisé à n niveaux est un index hiérarchisé à n - 1 niveaux, possédant lui-même un index à un niveau. La figure III.14 illustre un index hiérarchisé à 3 niveaux. Le niveau 1 comporte trois paquets de clés. Le niveau 2 en comporte deux qui contiennent les plus grandes clés des paquets du niveau inférieur. Le niveau 3 est la racine et contient les plus grandes clés des deux paquets du niveau inférieur. La notion d'index hiérarchisé est indépendante du nombre de niveaux, qui peut grandir autant que nécessaire.

Afin de mieux caractériser la notion d'index hiérarchisé et de la rendre indépendante des particularités d'implantation, on a été amené à introduire une structure d'arbre, avec un nombre variable de niveaux. Cette structure, appelée arbre B [Bayer72, Comer79], peut être introduite formellement comme suit :

La figure III.15 représente un arbre balancé d'ordre 2. La racine a deux fils. Les deux autres nœuds non-feuilles ont trois fils.

Un arbre B peut être utilisé pour constituer un index hiérarchisé d'un fichier. Dans ce cas, les nœuds représentent des pages de l'index. Ils contiennent des clés triées par ordre croissant et des pointeurs de deux types : les pointeurs internes désignent des fils et permettent de définir les branches de l'arbre, alors que les pointeurs externes désignent des pages de données (en général, des adresses relatives d'articles). La figure III.16 précise la structure d'un nœud. Une clé xi d'un nœud interne sert de séparateur entre les deux branches internes adjacentes (Pi-1 et Pi). Un nœud contient entre m et 2m clés, à l'exception de la racine qui contient entre 1 et 2m clés.

De plus, l'ensemble des clés figurant dans l'arbre B doit être trié selon l'ordre postfixé induit par l'arbre, cela afin de permettre les recherches en un nombre d'accès égal au nombre de niveaux. Plus précisément, en désignant par K(Pi) l'ensemble des clés figurant dans le sous-arbre dont la racine est pointée, on doit vérifier que :

1. (x1, x2…xK) est une suite croissante de clés ;
2. Toute clé y de K(P0) est inférieure à x1 ;
3. Toute clé y de K(P1) est comprise entre xi et xi+1 ;
4. Toute clé y de K(PK) est supérieure à xk.

La figure III.17 représente un exemple d'index sous forme d'arbre B d'ordre 2. Cet arbre contient les valeurs de clé de 1 à 26. Les flèches entre les nœuds représentent les pointeurs internes, les traits courts issus d'une clé les pointeurs externes vers les articles. Dans la suite, nous omettrons les pointeurs externes, qui seront donc implicites.

La recherche d'une clé dans un arbre B s'effectue en partant de la racine. En règle générale, les valeurs contenues dans un nœud partitionnent les valeurs possibles de clés en un nombre d'intervalles égal au nombre de branches. Ainsi, si la valeur cherchée est inférieure à la première clé du nœud, on choisit la première branche ; si elle est comprise entre la première clé et la deuxième clé, on choisit la deuxième branche, etc. Si une clé n'est pas trouvée après recherche dans un nœud terminal, c'est qu'elle n'existe pas.

Le nombre de niveaux d'un arbre B est déterminé par son degré et le nombre de clés contenues. Ainsi, dans le pire des cas, si l'arbre est rempli au minimum, il existe :

• une clé à la racine ;
• deux branches en partent avec m clés ;
• (m+1) branches partent de ces dernières avec m clés ;
• etc.

Pour un arbre de niveaux h, le nombre de clés est donc :

soit, par réduction du développement limité :

D'où l'on déduit que pour stocker N clés, il faut :

Par exemple, pour stocker 1 999 999 clés avec un arbre B de degré 99, h = 1 + log₁₀₀10⁶ = 4. Au maximum, quatre niveaux sont donc nécessaires. Cela implique qu'un article d'un fichier de deux millions d'articles avec un index hiérarchisé organisé comme un arbre B peut être cherché en quatre entrées-sorties.

L'insertion d'une clé dans un arbre B est une opération complexe. Elle peut être définie simplement de manière récursive comme suit :

1. Rechercher le nœud terminal qui devrait contenir la clé à insérer et l'y insérer en bonne place ;
2. Si le nombre de clés après insertion de la nouvelle clé est supérieur à 2 m, alors migrer la clé médiane au niveau supérieur, en répétant la procédure d'insertion dans le nœud supérieur.

À titre d'exemple, la figure III.18 représente les étapes nécessaires à l'insertion de la clé (25) dans l'arbre B représenté figure III.17. Tout d'abord, la place de la clé 25 est recherchée. Celle-ci doit être insérée dans le dernier nœud à droite (étape a). Cela provoque un éclatement du nœud qui a maintenant plus de 2 m clés, soit 4. La clé médiane 24 doit être remontée au niveau supérieur. Elle est alors insérée après 21 (étape b). Le nœud ayant trois clés, aucun autre éclatement n'est nécessaire.

La suppression d'une clé soulève également des problèmes. Tout d'abord, si l'on supprime une clé non terminale, il faut remonter la clé suivante pour garder le partitionnement. De plus, si un nœud a moins de m clés, il faut le regrouper avec le précédent de même niveau afin de respecter la définition et de conserver entre m et 2m clés dans un nœud non racine.

Une variante de l'arbre B tel que nous l'avons décrit pour réaliser des index est l'arbre B* [Knuth73, Comer79], dans lequel l'algorithme d'insertion essaie de redistribuer les clés dans un nœud voisin avant d'éclater. Ainsi, l'éclatement ne se produit que quand deux nœuds consécutifs sont pleins. Les deux nœuds éclatent alors en trois. Les pages des index de type arbre B* sont donc en général mieux remplies que celles des index de type arbre B.

L'utilisation des arbres B pour réaliser des fichiers indexés tels que décrits ci-dessus conduit à des traitements séquentiels coûteux. En effet, l'accès selon l'ordre croissant des clés à l'index nécessite de nombreux passages des pages externes aux pages internes. Pour éviter cet inconvénient, il a été proposé de répéter les clés figurant dans les nœuds internes au niveau des nœuds externes. De plus, les pages correspondant aux feuilles sont chaînées entre elles. On obtient alors un arbre B+. L'arbre B+ correspondant à l'arbre B de la figure III.17 est représenté figure III.19. Les clés 11, 8 et 21 sont répétées aux niveaux inférieurs. Les pointeurs externes se trouvent seulement au niveau des feuilles.

Les arbres B+ peuvent être utilisés pour réaliser des fichiers à index hiérarchisés de deux manières au moins :

• L'arbre B+ peut être utilisé pour implémenter seulement les index. Autrement dit, les articles sont stockés dans un fichier séquentiel classique et l'arbre B+ contient toutes les clés ainsi que les adresses d'articles. Une telle organisation est proche de celle proposée par IBM sur les AS 400. Pour des raisons historiques, cette méthode s'appelle IS3.
• L'arbre B+ peut être utilisé pour implémenter fichiers et index. Dans ce cas, les pointeurs externes sont remplacés par le contenu des articles. Les articles sont donc triés. Seules les clés sont déplacées aux niveaux supérieurs qui constituent un index non dense. Cette méthode correspond à l'organisation séquentielle indexée régulière d'IBM sur MVS connue sous le nom de VSAM, et également à celle de BULL sur DPS7, connue sous le nom de UFAS.

Il s'agit de l'organisation IBM utilisée dans les systèmes DOS, OS/VS, MVS et connue sous le nom ISAM (Indexed Sequential Access Method) [IBM78]. Le fichier est organisé physiquement selon un découpage en pistes et cylindres. Cette méthode très ancienne reste populaire malgré son manque d'indépendance physique.

Un fichier ISAM comporte trois zones logiques :

• une zone primaire où l'on écrit les articles à la première écriture ;
• une zone de débordement où l'on transfère les articles lors des additions au fichier ;
• une zone d'index où l'on écrit les index.

Ci-dessous, nous étudions successivement chacune des zones.

La zone primaire se compose de cylindres successifs dont certaines pistes sont réservées pour l'index et les zones de débordement. En zone primaire, les articles sont enregistrés par ordre croissant des clés. Ils peuvent être bloqués ou non. Lors de la première écriture du fichier, les articles doivent être délivrés au système de fichiers par ordre croissant des clés. La figure III.21 illustre un fichier ISAM après une première écriture. Ce fichier est composé de deux cylindres. Chaque cylindre comporte deux pistes de données et une piste réservée pour les index.

Il existe deux types de zones de débordement : la zone de débordement de cylindre composée de quelques pistes sur chaque cylindre et la zone de débordement indépendante, composée des derniers cylindres du fichier (voir figure III.22).

En zone de débordement, les articles ne sont pas bloqués. Ils sont chaînés entre eux afin de reconstituer la piste qui a débordé de manière logique. Quand un article est inséré, on recherche sa séquence dans la piste logique. S'il est placé en zone primaire, les articles suivants sont déplacés et le dernier est écrit en zone de débordement. Les chaînages sont mis à jour. S'il vient en zone de débordement, il est écrit dans cette zone et est inséré en bonne place dans la chaîne des articles en débordement.

La zone de débordement de cylindre est tout d'abord utilisée. Lorsqu'elle est saturée, la zone de débordement indépendante est utilisée. Dans ce cas, comme le chaînage est effectué par ordre croissant des clés, il est possible qu'il parte de la zone de débordement de cylindre, pointe en zone de débordement indépendante, puis revienne en zone de débordement de cylindre, etc. Alors, la méthode devient particulièrement peu performante pour rechercher un article dans une piste ayant débordé, du fait des déplacements de bras.

Il existe obligatoirement deux niveaux d'index et optionnellement trois : les index de pistes, les index de cylindres et le (ou les) index maître(s).

Le premier niveau d'index obligatoire est l'index de piste. Il en existe un par cylindre, en général contenu sur la première piste du cylindre. Chaque entrée correspond à une piste du cylindre et fournit la plus grande clé de la piste logique en zone de débordement, ainsi que l'adresse du premier article en zone de débordement s'il existe. La figure III.23 illustre le format de l'index de piste. Chaque piste est décrite par une double entrée comportant, en plus des adresses, la plus grande clé en zone primaire et la plus grande clé en zone de débordement.

Le deuxième niveau de l'index obligatoire est l'index de cylindre. Il existe un index de cylindre par fichier. Cet index contient une entrée par cylindre comportant la plus grande clé du cylindre ainsi que l'adresse du cylindre. L'index de cylindre est généralement rangé dans une zone particulière, par exemple en début de zone de débordement indépendante. Cet index permet, à partir d'une clé d'article, de sélectionner le cylindre où doit se trouver l'article.

Le troisième niveau d'index est optionnel : c'est l'index maître. Il est utilisé quand l'index de cylindre est trop grand afin d'accélérer les recherches. Il existe une entrée en index maître par piste de l'index de cylindre. Cette entrée contient l'adresse de la piste et la valeur de la plus grande clé dans la piste.

La figure III.24 donne une vue d'ensemble d'un fichier ISAM après insertion d'articles, avec seulement deux niveaux d'index. Bien que seulement les chaînages du premier cylindre soient représentés, on notera le grand nombre de chaînages. La première piste logique est constituée des articles a0, a1, a2 et a4 ; a0, a1, a2 sont en zone primaire ; a3 et a4 sont en zone de débordement de cylindre. Les articles a5, a6, a7, a8 et a9 sont rangés dans la deuxième piste logique ; a8 est en débordement de cylindre et a9 en zone de débordement indépendante.

Les avantages de la méthode sont que le fichier est trié, ce qui facilite l'accès en séquentiel trié, ainsi que les temps d'accès tant que le fichier n'a pas débordé (3 E/S pour lire un article). Les inconvénients sont essentiellement liés aux débordements. La gestion des débordements est complexe et dégrade les performances, de sorte qu'il est nécessaire de réorganiser périodiquement les fichiers ayant débordé. Le fait que la méthode d'accès ne soit pas indépendante des caractéristiques physiques du support (pistes, cylindres…) améliore les performances, mais rend le changement de support difficile. En fait, les performances dépendent des débordements. Si une piste comporte des articles en débordement, une lecture nécessitera approximativement 3+[d/2] entrées-sorties alors qu'une écriture demandera 2+[d/2]+4 entrées-sorties, cela afin de trouver la position de l'article, de l'écrire et de mettre à jour les chaînages. Cela peut devenir très coûteux.

Il s'agit de l'organisation IBM utilisée dans les systèmes IBM et connue sous le nom de VSAM (Virtual Sequential Access Method) [IBM87]. À la différence de ISAM, VSAM assure l'indépendance des fichiers au support physique et une réorganisation progressive du fichier, sans gestion de débordement. VSAM est une organisation basée sur les principes des arbres B+.

Afin d'assurer l'indépendance des fichiers aux supports physiques, des divisions logiques sont introduites. Le fichier est divisé en aires, une aire étant un ensemble de pistes du même cylindre ou de cylindres contigus. Chaque aire est elle-même divisée en intervalles, un intervalle étant généralement composé d'une partie de piste (ou de plusieurs pistes consécutives) lue(s) en une seule entrée-sortie. L'intervalle correspond à la feuille de l'arbre B+. Lorsqu'un intervalle est saturé, il éclate en deux intervalles ; lorsqu'une aire est saturée, elle éclate aussi en deux aires, si bien que le fichier se réorganise de lui-même par incréments.

Cette organisation résulte d'une étude critique de ISAM. Cette fois, le fichier est plus indépendant de la mémoire secondaire : la piste est remplacée par l'intervalle qui peut être une fraction de piste ou plusieurs pistes, le cylindre est remplacé par la notion d'aire. Les débordements ne perturbent plus l'organisation puisque le mécanisme de débordement est celui de l'arbre B+, c'est-à-dire qu'un intervalle ou une aire saturés éclatent en deux.

Cette zone qui contient les articles est donc divisée en intervalles et aires, comme sur la figure III.25. Lors de la première écriture, comme avec des fichiers séquentiels indexés ISAM, les articles sont enregistrés triés, c'est-à-dire que le programme doit les délivrer à la méthode d'accès dans l'ordre croissant des clés. Cette fois, les mises à jour sont prévues : de la place libre est laissée dans chaque intervalle et des intervalles libres sont laissés dans chaque aire afin de permettre les insertions de nouveaux articles.

À titre d'exemple, le fichier de la figure III.25 a été créé avec les paramètres suivants :

• pourcentage d'octets libres par intervalle = 25 ;
• pourcentage d'intervalles libres par aire = 25.

Lors de la première écriture, le programme créant le fichier a délivré au système les articles suivants (dans l'ordre) : 1, 5, 7, 9, 15, 20, 22, 27, 30, 31, 33, 37, 40, 43, 47, 51, 53.

L'algorithme d'insertion d'un article consiste à déterminer, grâce aux index, l'intervalle qui doit contenir l'article. Ensuite, deux cas sont possibles :

• a) Si l'intervalle n'est pas plein, alors l'article est rangé dans l'intervalle, en bonne place dans l'ordre lexicographique des clés. Par exemple, l'insertion de l'article de clé 10 conduira à la substitution d'intervalle représentée figure III.26.
   
• b) Si l'intervalle est plein, alors il éclate en deux intervalles à demi pleins. Deux sous-cas sont encore possibles :
• b1) s'il existe un intervalle libre dans l'aire, celui-ci est utilisé afin de stocker l'un des deux intervalles résultant de l'éclatement. Par exemple, l'insertion de l'article de clé 13 dans le fichier obtenu après insertion de l'article de clé 10 (Fig. III.26) conduit au fichier représenté figure III.27,
• b2) s'il n'existe pas d'intervalle libre dans l'aire, on alloue alors une aire vide au fichier et on éclate l'aire saturée en deux à demi pleines ; pour cela, la moitié des intervalles contenant les articles de plus grandes clés sont recopiés dans l'aire nouvelle. Par exemple, l'insertion des articles de clés 11 et 12 dans le fichier de la figure III.27 conduit au fichier représenté figure III.28. Une nouvelle aire a été créée afin de dédoubler la première aire du fichier qui était saturée.
     

Il peut exister deux ou trois niveaux d'index. Le premier est appelé index d'intervalles. Il en existe un par aire. Chaque entrée contient la plus grande clé de l'intervalle correspondant ainsi que son adresse. Le deuxième niveau est appelé index d'aires. Il en existe un par fichier. Chaque entrée contient la plus grande clé de l'aire correspondante ainsi que l'adresse de l'aire. Il est également possible, dans le cas où l'index d'aire est trop grand (par exemple plus d'une piste), de faire gérer au système un index de troisième niveau appelé index maître et permettant d'accéder directement à la partie pertinente de l'index d'aire. À titre d'illustration, la figure III.29 représente les index d'intervalles et d'aires du fichier représenté figure III.28. Chaque entrée représente une clé suivie d'une adresse d'intervalle ou d'aire.

La figure III.30 donne une vue d'ensemble d'un autre fichier VSAM composé de deux aires, avec seulement deux niveaux d'index. Chaque aire possède donc un index d'intervalles. L'index d'aires constitue ici la racine de l'arbre B+. Il indique que 17 est la plus grande clé de l'aire 0, alors que 32 est la plus grande de l'aire 1.

Les avantages de la méthode sont que le fichier est physiquement trié, ce qui facilite les accès en séquentiel trié, ainsi que les temps d'accès à un article : la lecture s'effectue en général en trois entrées-sorties. Les inconvénients sont peu nombreux.

Cependant, l'écriture peut parfois être très longue dans le cas d'éclatement d'intervalles ou, pire, dans le cas d'éclatement d'aires. En fait, les écritures ne s'effectuent pas en un temps constant : certaines sont très rapides (4 E/S lorsqu'il n'y a pas d'éclatement), d'autres sont très longues (lorsqu'il y a éclatement d'aire).

Une méthode simple est le placement multiattribut statique. La méthode consiste à concaténer les résultats des fonctions de hachage dans un ordre prédéfini. La chaîne binaire obtenue est alors directement utilisée comme adresse de paquet. On obtient donc un hachage statique à partir d'une fonction portant sur plusieurs attributs. Si A1, A2 … An sont les attributs de placement, chacun est transformé par application d'une fonction de hachage en bi bits de l'adresse du paquet. Si hi est la fonction de hachage appliquée à l'attribut bi, le numéro de paquet où placer un article est obtenu par a = h1(A1) || h2(A2) || … hn(An), où la double barre verticale représente l'opération de concaténation. Le nombre total de bits du numéro de paquet est B = b1+b2+… bn. Pour retrouver un article à partir de la valeur d'un attribut, disons Ai, le système devra seulement balayer les paquets d'adresse x || hi(Ai) ||y, où x représente toute séquence de b1 +… bi-1 bits et y toute séquence de bi+1+ … bn bits. Ainsi, le nombre de paquets à balayer sera réduit de 2**B à 2**(B-bi). Le nombre optimal de bits à allouer à l'attribut Ai dépend donc de la fréquence d'utilisation de cet attribut pour l'interrogation. Plus cette fréquence sera élevée, plus ce nombre sera important ; l'attribut sera ainsi privilégié aux dépens des autres.

L'utilisation de techniques de hachage dynamique est aussi possible avec des méthodes de placement multiattribut. L'approche la plus connue est appelée fichier grille, ou grid file en anglais [Nievergelt84]. La méthode peut être vue comme une extension du hachage extensible. Une fonction de hachage est associée à chaque attribut de placement. L'adresse de hachage multidimensionnelle est constituée d'un nombre suffisant de bits choisi en prélevant des bits de chacune des fonctions de hachage de manière circulaire. Cette adresse sert de pointeur dans le répertoire des adresses de paquets. Tout se passe donc comme avec le hachage extensible, mais avec une fonction de hachage multiattribut mixant les bits des différentes fonctions composantes.

Afin de clarifier la méthode, une représentation par une grille multidimensionnelle du fichier est intéressante. Pour simplifier, supposons qu'il existe seulement deux attributs de placement A1 et A2. Au départ, le fichier est composé d'un seul paquet qui délimite la grille (voir figure III.31.afigure III.31.b). Quand le fichier grossit au fur et à mesure des insertions, le paquet sature. Il est alors éclaté en deux paquets B0 et B1 selon la dimension A1 (voir ). Pour ce faire, le premier bit de la fonction de hachage appliquée à A1 (h1(A1)) est utilisé. Quand l'un des paquets, disons B0, est plein, il est à son tour éclaté en deux paquets B00 et B01, cette fois selon l'autre dimension. Le premier bit de la fonction de hachage appliquée à A2 (h2(A2)) est utilisé. Si l'un des paquets B00 ou B01 devient plein, il sera à son tour éclaté, mais cette fois selon la dimension A1. Le processus d'éclatement continue ainsi alternativement selon l'une ou l'autre des dimensions.

Pour retrouver un article dans un paquet à partir de valeurs d'attributs, il faut appliquer les fonctions de hachage et retrouver l'adresse du ou des paquets correspondants dans le répertoire des paquets. Pour cela, la méthode propose un répertoire organisé comme un tableau multidimensionnel. Chaque entrée dans le répertoire correspond à une région du fichier grille. Le répertoire est stocké continûment sur des pages disques, mais est logiquement organisé comme un tableau multidimensionnel. Par exemple, avec un placement bidimensionnel, l'adresse d'un paquet pour la région (i,j) sera déterminée par une transformation d'un tableau bidimensionnel à un répertoire linéaire : l'entrée 2**N*i + j sera accédée, N étant le nombre maximal d'éclatements dans la dimension A1. Ainsi, lors d'un éclatement à un niveau de profondeur supplémentaire d'une dimension, il faut doubler le répertoire selon cette dimension. Cela peut s'effectuer par recopie ou chaînage. En résumé, on aboutit à une gestion de répertoire complexe avec un répertoire qui grossit exponentiellement en fonction de la taille des données.

Pour améliorer la gestion du répertoire et obtenir une croissance linéaire avec la taille des données, plusieurs approches ont été proposées. Une des plus efficaces est utilisée par les arbres de prédicats [Gardarin83]. Avec cette méthode, l'ensemble des fonctions de hachage est ordonné selon les fréquences décroissantes d'accès (les attributs les plus souvent documentés lors des interrogations d'abord). Pour simplifier, supposons que l'ordre soit de A0 à An. Un arbre de placement permet d'illustrer les éclatements de paquets (voir figure III.32). Au premier niveau, les paquets éclatent progressivement selon les bits de la fonction de hachage h(A1). Quand tous les bits sont exploités, on utilise la fonction h2(A2), etc. Ainsi, chaque paquet est une feuille de l'arbre de placement caractérisée par une chaîne de bits plus ou moins longue correspondant aux éclatements successifs. Cette chaîne de bits est appelée signature du paquet.

Le répertoire contient des doublets <signature de paquet, adresse de paquet>. Le répertoire est organisé lui-même comme un fichier placé par un arbre de prédicats correspondant aux bits de la signature (chaque bit est considéré comme un attribut haché par l'identité). Sa taille est donc linéaire en fonction du nombre de paquets du fichier de données. Pour rechercher un article à partir d'attributs connus, un profil de signature est élaboré. Les bits correspondant aux attributs connus sont calculés et les autres mis à la valeur inconnue. Ce profil est utilisé pour accéder au répertoire par hachage. Il permet de déterminer les paquets à balayer. Des évaluations et des expérimentations de la méthode ont démontré son efficacité en nombre d'entrées-sorties [Gardarin83]. D'autres méthodes similaires ont été proposées afin de réduire la taille du répertoire et de profiter d'un accès sélectif [Freeston87].