THÈSE
présentée à
L'UNIVERSITÉ PARIS IX DAUPHINE
par
Jean KOUACOU KOUADIO
pour obtenir
LE GRADE DE DOCTEUR 3- CYCLE
Spécialité: Inform.tiqu".,..,.",.-.
..."...,...--
~---
~C()NSEIL AFRICAIN ET·MALGACHE '1
. POUR L'ENSEIGNE;~.'\\ENT SUPERiEUR.
C. A. M. E. S. -
OUAGA~~UGOU
Sujet de la thèse:
1Arr.~é:~h·; .1-~.~U)N.19
..... ,.
1 EIl,og'l)"e sou,,_n ·~O·D·6··6·0· 1
,
.. _
•. _ - - - _ . _ - . _
,
-
> .
_.-.~_.__
. -
ADRESSAGE D'INFORMATIONS STRUCTURÉES
Soutenue le 27 Janvier 1986 devant la Commission composée de:
MM.
C.
BERTHET
Président
E.
DIDAV
G.
LÉVY
Examinateurs
W.
UTWIN

---

L'UNIVERSITE N'ENTEND DONNER AUCUNE APPROBATION NI IMPROBATION
AUX OPTIONS EMISES DANS
LES THESES. CES OPINIONS DOIVENT ETRE
. CONSIDEREES COMME PROPRES A LEURS AUTEURS.

---

Nous remercions très sincèrement:
Monsieur le Professeur Charles BERTHET d'avoir bien voulu accepter la
présidence du jury de cette thèse.
Monsieur le Professeur Gérard LEVY de nous avoir intéressés aux problèmes de
gestion de fichiers et de nous avoir soutenu dans ce travai 1.
Monsieur Witold L1TWIN, Ingénieur de recherche, Directeur du projet SESAME
de l'INRIA, grâce à qui ce travail a pu s'accomplir. Il a su quelquefois préciser nos
idées mieux que nous mêmes.
Nous voudrions lui exprimer notre profonde
gratitude.
Monsieur le Professeur Edwin DIDAY d'avoir bien voulu accepter de participer au
jury.
Monsieur Lionel DELAFOSSE, Ingénieur de recherche, pour ses nombreuses
critiques et suggestions.
Les membres du projet SABRE de l'INRIA, tout particulièrement Messieurs
Rodolphe MICHEL, Max JEANOEL, THOMAS et Mohamed DRIOUCHE. Les
précieuses discussions avec cette équipe nous ont faci 1ité "implémentation de
. notre méthode.
Monsieur Didier BOUDIGUES, Ingénieur de recherche, de nous avoir prêté son
poste de travai 1sur l'ordinateur SM9D pour l'implémentation de notre méthode.
Mademoiselle Mireille REGNIER du projet ALGO de l'INRIA. Les échanges de
points de vue avec elle nous ont permis d'orienter et de mieux préciser nos
algorithmes.
Enfin, tous nos collègues du projet SESAME pour le soutien moral et surtout
l'aide qu'i Is nous ont apportés durant "élaboration de ce document.

---

SOMMAIRE
Résumé
1
Généra 1ités
2
1. Organisation séquentielle
2
2. Organisation relative
2
3. Organisation aléatoire
2
4. Organisat ion indexée
2
Objectif de la thèse
:
3
Plan de la thèse
4
Chapitre 0
6
';F';z ".: ...>
r,:.<:y\\\\-
I(~I-"
.
o~.
<, él!,.•
1. La structure d'arbre
~. .c
:~
6
~.
"tl
-1 M
c'
2. Le hachage
%-....•••••• 1 € .~
'':;'
8
~
.:t,
2.1 Rappel
~
8
.
~.
~
2.2 Que1ques fonct ions de hachage
~1).alt7eI'llS~~\\e................... .. 9
2.3 Caractéristiques du fichier géré par hachage
11
2.4 Méthodes de résolutions des coll isions
'1
2.5 Les différentes sortes de hachage
16
2.5. 1 Le hachage c1assique
16
2.5.2 Le hachage dynam ique
16
2.5.2.1 Les tendances du hachage dynamique
17
2.5.2.1. 1 Fichiers désordonnés à index ou table auxi 1iaire..17
2.5.2.1.2 Fichiers sans index
17
2.5.2.1.3 Fichiers à arbre digital
19
3. Autres méthodes d'adressage
19
3.1 L'arbre B
2D
3.1.1 L'arbre B+
21
3.2 ISAM
22

---

3.3 VSAM et UFAS
22
Chapitre 1 Le hachage digital
25
1.1 Concepts généraux
25
2. L'algorithme
25
2.1 Représentation d'un noeud de l'arbre digital
25
2.2 Constitution de l'arbre digital
~
26
2.4 Performances de l'algorithme
33
Chapitre 2 Le hachage digital binaire
35
2.1. Introduction
35
2.2 Ltarbre digital binaire
36
2.3 L'algorithme de constitution de l'arbre digital binaire
36
2.4 Propriétés des tables B et T
41
2.5 Recherche d'un article: exploration de l'arbre digital
42
2.5.1 Description formelle
42
2.5.2 Recherche dans B
43
2.5.3 Recherche dans T
45
2.6 Requêtes à intervaJ les
46
2.6.1 Notion
46
2.6.2 Traitement de requêtes à intervalles
.47
2.6.2.1 1nterva Ile fermé
48
2.6.2.2 Intervalle ouvert
48
2.6.2.3 Intervalle fermé inférieurement
49
2.6.2.4 Intervalle fermé supérieurement
49
2.7 Insertion
50
e e • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •
2.7.1 Algorithme général
50
2.7.1 .1 Procédure éc 1ater
Il
Il............ 51
2.7.1.2 Procédure création de noeud 'nil'
52
2.8 Fus ion des cases
52
2.8.1 Définitions
53
2.6.2 Fusion des cases.
53
2.9 Le problème des noeuds 'nil'
57

---

3. Implémentation
!
56
3.1 Proposition de solution pour les noeuds 'ni l'
58
3.2 Détection des emplacements 1ibres dans le fichier
SB
3.3 Application pratique: réalisation d'un SGF
59
3.3.1 Le noyau ..........................•........................................ 59
3.3.2 La couche externe
59
Chapitre 3: Evaluation des performances
60
1 Pourcentage et influence des noeuds 'ni!'
60
2 Taux de rempl issage
62
3 Encombrement de la fonction de hachage
63
3.1 Tab 1e des bits
63
3.2 Table des pclnteurs
63
3.3 Autre facteur
63
3.3.1 Cas oû n est en mémoire centrale
63
3.3.2 Cas oû n est sur le disque
64
4 Graphes de la fonction de hachage
65
5 Performances dl acoès
66
6 Analys.e comparative
66
6.1 Comparaison avec le hachage digita1 original
61
6.2 Comparaison avec les autres algorithmes d'adressage
61
Chapitre 4 : Conclusions et orientations futures
69
1 Domaines dlappl ioations
69
2 Conclusions
69
3 Travaux futurs
7D
Annexes
1. Codifioation Pasoal de l'algorithme de reoherohe d'une adresse .. 11
2. Résultats des simulations
75

---

3. Courbes
96
. 3.1 Taux de rempl issage
91
3.2 Fonctlon de hachage
1D2
3.2.1 Tai Ile de la table des bits B
1D3
3.2.2 TaiIle de la table des pointeurs T
H]7
Bibl iographie
'11

---

RESUME
Le hachage digital
est
une nowelle technique de gestion des fichiers
dynamiques introduit par W. LIT'NIN. Elle requiert au plus un accès disque pour
conclure qu'un article appartient ou non au fichier; et cela pour des fichiers ayant
plus d'un million d'articles. Le taux de remplissage de la mémoire auxiliaire (le
disque ) est de l'ordre de 70%. Un fichier géré par cette méthode est totalement
ordonné, propriété que n'assurent pœ les autres méthodes de gestion de fichiers.
l\\Ious étudions ici une version de cet algorithme que nous avons appelée
séquentielle binaire à pointeurs séparés. L'analyse des performances montre
que cette version a l'avantage d'avoir les mêmes propriétés que l'algorithme
original. En outre, elle permet d'obtenir une structure de données beaucoup plus
compacte powant résider en mémoire centrale même pour des fichiers de très
grande taille. Du fait que cette version se ·contente de très peu de mémoi re
centrale, elle peut être implémentée sur la quasi totalité des microordinateurs
professionnels actuels.
Ces propriétés font du hachage digital et de sa version séquentielle binaire -
qui est l'objet de notre thèse-, de bons choix parm i les nombreuses méthod~ du
hachage dynamique connues actuellement.
1

---

Générat ités
Un fichier est un ensemble d'informations portant sur un type d'Obit donné.
L'unité du fichier s'appelle article (record en ~nglais). L'ertlcle est co posé de
plusieurs attributs. Chaque article est identifié dans le fichier par un ou plusieurs
,
attributs qu'on appelle clé primaire (primary key en anglais) de l' rticle. II
ex iste une seule clé primaire par article. Les clients d'une banque identlfi
chacun
par un numéro de client constituent un exemple de fichier. Les empl
és d'une
entreprise identifiés chacun par leur numéro de sécurité sociale const tuent un
l
autre exemple def i c h i e r . .
Dans ce qui suit... la clé primai re est appelée simplement clé ... car no
ne nous
intéressons pas à la gestion des clés dites seccndel res qui n' identifie~t pas un
article{plusieurs articles pewent avoir la même valeur de clé secondaire). 1
1
La façon de structurer et de gérer un fichier est appelée organis,tion du
1
flch le r . 1L existe plusieurs façons d'organiser un fichier,
1
1. Organisation séguentielle
1
cr~.tion
Les articles sont classés dans le fichier suivant leur ordre de
ou
suivant l'ordre croissant de leurs clés (cas général).
i
2. Organisation relative
1
Les articles sont classés séquentiellement avec" associé à chacun q'eux... un
numéro d'ordre qui est leur rang dans le fichier. Ce numero d'ordre est a~pelé clé
relative de l'article.
l,
'3. Organisation aléatoire
1
1
Chaque article du fichier est logé à une adresse précise... calculée à l'ai~e d'une
fonction. Par rapport à l'organisation relative" plusieurs adresses physiques pewent
être associées à la même valeur de clé. Nous étudierons plus loin cette fonction qui
fait l'objet de notre thèse.
4. Organisation indexée
2

---

Dans certains ces. on crée à parti r des clés et des adresses. une structure
parallèle appelée index. Le fichier géré de cette manière est appelé fichier
indexé. Les ertlctes sont ordonnés suivant leurs clés et il existe un index par clé.
L'index permet d'établir la correspondance entre la clé et l'adresse de l'article.
Quand l'index est petrt, il peut résider en mémoire centrale; en examinant d'abord
l'lndex~ on accélère la recherche d'un article de clé donnée. Mais dès que l'index
devient grand et qu' i 1 ne peut plus résider en mémoi re centrale. on en déporte une
partie sur ,la mémoire auxiliaire; les performances d'accès au fichier deviennent
moins bonnes.
L'index est interne au système; il constitue lui même un fichier. Il peut y avoir
plusieurs index sur un fichier; ceci veut di re que l'index est constitué de sous- index
pointant successivement les uns vers les autres. On parle alors d'index à plusieurs
niveaux.
Les opérations usuelles sur un fichier sont : l'insertion, la lecture" l'
écriture et la suppression
d'un article étant donné sa clé. L'opération
d'insertion est très lmportente,
en ce sens qu'un-article doit être logé dans un .
fichier de telle sorte qu'on puisse le retrouver très facilement et très rapidement
pendant l'exploitation du fichier. Les suppressions d'articles dans le fichier pewent
entrainer la réorganisation des structures des données. Cette réorganisation
consiste à ramener la taille des structures des données au besoin réel d'utilisation;
elfe doit d'une part être faite à moindres coûts, d'autre part éviter que le fichier
soit indisponible pendant longtemps. Un autre besoin d'exploitation très important
est la recherche séquentielle
ordonnée
ou encore lecture en ordre des
articles d'un fichier; la recherche séquentielle est une recherche dont le résultat
doit produire les ~rticles dans l'ordre de leurs clés. Elle est nécessaire dans de très
nombreuses applications.
Objectif de la thèse.
L'objectif principal de cette thèse est l'étude et la réalisation d'une version du
hachage digital de Lltwln, que nous avons appelée SEQUENTIELLE BINAIRE A
POINTEURS SEPARES. Le bénéfice à retirer de notre méthode est qu'avec les
mêmes performances d'accès, nous arrivons à gérer unfichier de taille plus grande.
3

---

i
Dans les prochains chapitres, nous décrivons la fonction de hachage.. ~Uis les
algorithmes de recherche, d'insertion et de suppression de notre méthodt. Nous
étudions l'encombrement de la -fonction de hachage en mémoire principal~ et les
performances de la méthode à travers dessimulations. 1\\ ressort de cette ét~de que
les structures de données employées: peuvent résider dans la mémoire prihcipale
d'un microordinateur pour des fichiers de plue d'un million d'articles. Enfik nous
proposons
une méthode de recherche séquentielle que nous avons ,ppelée
REQUETES A .INTERVALLES.
1
Cette étude s'intègre dans le cadre du projet SESAME de l'Institut Natj~nal de
Recherche en Informatique et Automatique (INRIA).
Plan de la thèse
l\\Iotre travai 1 est organisé en cinq chapitres :
Le prem ter chapitre (chapitre 0) est consacré aux rappels des méthodes
d'adressage en général, et en particulier des principaux concepts et propri~'tés du
hachage dynamique. Nous présentons d'abord dans ce chapitre la structure d arbre;
la structure d'arbre est l'une des structures de données les plus utilisées d rIS les
méthodes d'adressage. Ensuite, nous présentons le hachage et ses caractéris1iques.
Nous décrivons quelques fonctions de hachage -
les plus usuelles-. PUi! nous
décrivons quelques algorithmes de hachage dynamique. Enfin, nous déclrivons
d'autres méthodes d'adressage, en l'occurrence les arbres B et leurs variantek. Une
1
brève conclusion est faite à la fin du chapitre pour faire ressortir les critères de
jugement d'un algorithme d'adressage.
1
1
Le chapitre suivant (le chapitre 1) présente la description du hachage digital
introduit par Litwin.
Dans le chapitre 2, nous présentons la version séquentielle binaire du hachage
digital. Nous décrivons les algorithmes de recherche et d' insertion d'un artlqle, de
construction de la structure de données. Nous proposons des algorithmes de l~cture
séquentielle dans l'ordre des clés. Notre méthode permet d'avoir une structJre de
données peu encombrante.
Dans le chapitre 3, nous analysons d'abord les performances de la méthode: les
propriétés ont été étudiées à travers des programmes de simulation. Puis nous
comparons les résultats obtenus par simulation à ceux des autres méthodes d'accès.
Les critères pris en compte pour évaluer notre méthode sont: l'encombrement de
4

---

la fonction de hachage, le nombre d'entrées-sorties nécessai res pour rechercher un
ertlcte, et le taux de remplissage.
Le chapitre 4 conclut la thèse.
•
5

---

Chapitre 0
1 La structure d'arbre
Un arbre est un ensemble fini de points appelés noeuds, associés à un e emble
fini de lignes appelées arcs ou branches. Chaque branche relie un noeud à u autre
noeud.
Exemple 1.1
A
o
A,B,C,D,E,F,G,H,I sont les noeuds de "arbre.
Le noeud origine A est appelé racine
de l'arbre.
Les ensembles
et 2
entourés sur le schéma sont appelés sous arbres.
Les noeuds B et C sont des noeuds rattachés à des sous arbres; on les appelle des
noeuds internes. E,F,G,H) et 0 sont des noeuds rattachés à aucun sous arbre; on
les appelle des noeuds terminaux ou des feuilles.
Les arbres permettent de représenter des informations sur lesquelles il y a une
hiérarchie.
6

---

Exemple 1.2
Directeur Général
Di recteur
Di recteur
Di recteur
Informatique
Commercial
Adm inistratif
~
Chef de
~
Chef de ~
Chef de
projet
vente
service
Un arbre binaire est un arbre dont chaque noeud n'est rattaché au plus qu'à deux
sous arbres dits sous-arbre gauche et sous-arbre droit.
A
c
1
-.
J.
K
Explorer ou parcourir un arbre consiste à examiner une seule fois chacun de ses
noeuds, dans un certain ordre. Les ordres de parcours usuels sont le préordre et le
postordre.
En préordre, on visite d'abord la racine, puis le sous arbre gauche, et enfin le
sous arbre droit. En postordre, on examine d'abord le sous arbre gauche, puis le sous
arbre droit et enfin la racine.
7

---

Le parcours en préordre de l'arbre binai re précédent est
le SUfant :
A,8,C,D,E~F~G~H,I~J~K. Ce parcours est encore appelé parcours séquenti 1. De
la même manière, on représente un arbre sous forme séquentielle.
La structure d'arbre est la structure de données la plus employée par les
algorithmes d'adressage.
2 _Le hachage
Le hachage ou encore adressage calculé (hash coding ou hashing en angl~is) est
une technique utlûsée pour la gestion des fichiers et pour accéder à des tables en
1
mémoi re centrale. Les tables des symboles en assembleur et les compi lateurs sont
des exemples d'organIsations par hachage. Les systèmes de gestion des bf:es de
données uti 1isent sowent le hachage pour organiser leurs informations. Le ut du
hachage est d'accélérer- la recherche des articles en mémoire centrale et ur les
mémoires externes. C'est l'une des techniques d'adressage les plus répandues et les"
plus étudiées par les chercheurs. Tout livre informatique ayant dans ses chapitres la
gestion de la mémoi re, discute la technique du hachage. On le trouve également
dans la documentation des constructeurs d'ordlneteurs, chez qui des fonctilons de
hachage sont sowent câblées. Dans cette thèse, nous nous intéressons Uniquerent à
l'accès par hachage aux mémoires externes, disques en l'occurrence.
!
i
•
2.1 Rgp,pel
Au moment de la création ou de l'exploitation du fichier ~ les articles sont
,
insérés ou retrouvés sur la mémoire auxiliaire (généralement le disque), à pa'rtir de
leur adresse qui est fournie par un calcul sur leur clé. Une fonction dite fonct'on de
hach~ge
est générée à cet effet. D'une manière générale~ une telle fonction
tranche de la clé, une certaine information et l'utilise ensuite comme base de
recherche. Le 'tronçonnage' peut consister en un choix de certains bits ou
caractères; mais il peut être aussi complexe.
Exemple 1.3
8

---

99
article
article
1499
1499
calcul par
....._ - algorithme hash --.........
adresse 99 - _...
Ici la méthode consiste à
diviser la clé 1499 par 100 et à utiliser le reste
comme adresse pour stocker ou rechercher l'article.
Proposons nous par exemple de construire un fichier avec les articles dont les
clés suivent:
JULES, JULlENI\\lE, JULUS, JULLIANA
Nous powons nous contenter des quatre premiers caractères; car les trois
prem iers étant identiques, ils généreraient les mêmes adresses.
D'une manière générale, il faut choisi r les caractères qui sont les plus
uniformément distribués sur l'ensemble des clés. La méthode est d'autant plus
efficace que le nombre des synoNymes est faible.
Une bonne fonction de hachage doit avoir les propriétés suivantes:
a) son calcul doit être rapide
b) elle doit m inim iser la génération des synoryrnes. On dit d'une telle
fonction qu'elle est uniforme.
De très nombreuses fonctions de hachage ont été proposées. La discussion
détai liée
peut
être
trouvé
notamment
dans
Guiho,
Knot75,
Knuth(73),
Litwin(78,19,80,8 1,82) Larson(19) ... etc.
2.2 Quelques fonctions de hachage
9

---

Parm i les nombreuses fonctions de hachage qui ont été conçues, nous
citer les suivantes, particul ièrement usitées:
8 _ la somme des positions dans l'alphabet des premières lettres de la clé. Si
par exemple JULES est une clé, et si nous ne prenons en compte que 1
trois
prem iers caractères, alors nous aurons par cette fonction:
:
:
42
:
JULES
/r\\
43
JULES
44
.
:
10
21
12
:
:
10+21+ 12 == 43
'1
L'article dont la clé est JULES est logé à l'adresse 43 dans le fichier.
b_ la méthode du milieu des carrés: la clé numérique est étévée au carré
et l'adresse est obtenue en supprimant un certain nombre de chiffres au débpt et à
la fin du résultat. On ne conserve donc que le milieu du carré; bien ente~du, on
conservera à chaque calcul les chiffres de même rang.
c_ la fonction de multiplication: soit w == 2K où k est le nombre de bits
des mots de l'ordinateur(nombre de bits codant un entier). Et soit v un nombre
entier prem ier par rapport à w. La fonction de multipl ication a pour expressij·n f(c)
- M*(v*c/w) mod 1 où c est une clé numérique et M -= 21 (i.2 0).
..
Cette fonction paratt un peu compliquée à mettre en oeuvre mals son
exécution est très rapide(Knuth 73).
d_ la fonction de division ou fonction modulo: c'est la fonction f telle que
f: n-->n mod M où n et M sont des entiers tels que n > 0 et M » 1. Par cette
fonction, la clé n est divisée par M et on utilise le reste comme adresse.
Cette fonction est une des meilleures fonctions de hachage à cause de sa
simpl icité à mettre en oeuvre et deses performances.
10

---

2.3 Caractéristigues du fichier géré par hachage
Comme nous l'avons dit plus haut, un fichier géré par hachage est stocké
sur une mémoire auxiliaire edresseble, généralement le disque. Il est constitué de
eases (buckets en anglais) appelées aussi pages. Les pages ou cases sont en
général numérotées 0,1,2,..n. Chaque numéro qui représente l'adresse d'une case,
est encore appelé adresse logique d'un article.
Une case contient un nombre fixe d'articles qui représente sa capacité.
Toutes les cases ont la même capacité que nous noterons b par la suite.
Une case est un secteur ou une piste du disque. Elle est accessible
individuellement. Elle constitue une unité de transfert
(lecture ou écriture)
entre le disque et la mémoi re principale. En d'autres termes, la partie de la
mémoi re adressée par la fonction de hachage est la .cese. Une unité de transfert
s'appelle un accès-disque.
En algorithmique, on cherchera à minimiser le
nombre d'accès-disque pour retrower l'adresse d'un article. Plus ce nombre est
petit, plus l'algorithme est bon. Les algorithmes actuels ont des performances
d'accès de l'ordre de 1 à 2 accès disque.
Au moment de la recherche d'un article (c'est à di re du calcul d'adresse),
seule la clé est prise en compte; les autres attributs de l'article ne sont pas
considérés. De sorte que dans cette thèse, nous parlerons indifféremment de clé ou
d'article.
En général, l'adressage par hachage est pseudc-r etéetotre, il peut alors se
trower qu'un article doit être rangé à une adresse déjà occupée ou pleine. Cette
situation s'appelle une collision
ou un débordement. Ranger l'article dans ces
conditions s'appelle résoudre la collision. Il existe plusieurs méthodes de
résolution de collisions. Nous exposons les plus usel/es dans les lignes qui suivent.
2.4 Méthodes de résolution des collisions
Jusqu'en 1975, les méthodes de résolution des collisions powaient se
résumer en trois groupes qui sont:
a) Résolution par chainage séparé
, 1

---

i
Les articles d'une case qui débordent sont chatnés comme ceci: le idernier
article de la case
pointe vers l'adresse du premier article qui déborde, ~elui ci
pointe vers le deuxième ... etc. Cette méthode est appelée chaînage sépar~. Dans
cette méthode, l'espace de débordement est globalement alloué pour toutes les
cases.
Pendant les recherches d'articles... si un article ne se trouve pas dans la case
indiquée par la fonction de hachage, on consulte la chaine de débordement; la
consultation des chaines de débordement détériore les performances d'accès. En
.
gros, si les cases principales ont des chaines de débordement de longueur moy~nne l,
le coût d'une recherche est de 1/2 accès-disque.
1
L'algorithme d'insertion dans un fichier utilisant le chainage séparé est domme
suit:
prQcédure insertiQn(clé)
début
case := h(clé);
.§icase non pleine alQrs insérer clé dans case
12

---

sinon
debut
tant gue case.succ o 'nil' faire case:= case.succ;
choisir un ernplecernent vide dans l'espece de débordément
case.succ : = deb;
deb.succ := 'nil '.
insérer clé dans deb;
fin
b) Résolution par chainage de cases
Si une case déborde, on lui chaîne une autre case en général de capacité plus
petite (mais supérieure à 1}, comme le montre la figure ci après :
rO----O-{]
1
,1
D'où le nom de la mé.thode : chaÎnage de cases. Dans cette méthode, chaque
case du fichier dispose de son propre espace de débordément. Au fur et à mesure des
débordements, la chaine s'allonge. L'espace de débordement est finalement une
liste de cases. Les performances d'accès se détériorent à la consultation des
chaînes mais elles restent mei lIeures par rapport à la méthode précédente, de sorte
que la méthode est beaucoup plus uti lisée pour Jes fichiers.
L'algorithme de recherche dans un fichier util isant le chainage de cases est le
suivant:
13

---

procédure recherche(clé)
début
case := h(clé);
chercher clé dans case;
si clé est dans case ~ sorti r ("'succès"')
sinon
début
tant gye case.succ <> 'nil' f.2!m
début
case: - case.succ;
il clé est dans case .mm. sorti r ("'succès"')
un.
sortir ("'echec"')
fin
c) Résolution par adressage ouvert
1
Pour éviter les ch~ines et l'allocation de mémoire.. le dernier groupe rahge les
articles qui débordent dans les autres cases du fichier. Ces articles seront adressés
par une certaine fonction appelée fonction de débordement. Si la première case
désignée par cette fonction est pleine, on cherche une autre .. etc. ~a plus simple
fonction de débordement est:
a (--(a+ 1) mod N où a· est l'adresse tentée
(initialement donnée par la fonction de hachage) et N le nombre de cases du fiçhier.
L'avantage est que l'on n'a plus de chaînes de débordements mais Jn seul
ensemble de cases à gérer. Mais les inconvénients laissent à désirer: en particulier,
le nombre d'insertions est
limité
. et les suppressions sont pratiquement
impossibles. En effet, on ne connait pas l'adresse de la case dans laquelle les
articles qui débordent ont été finalement insérés.
L'algorithme d'insertion est décrit comme suit:
procédure insertion(clé)
M = nombre de cases du fichier
14

---

début
case := h{clé);
si case non pleine alors insérer clé dans case
sinon
début
; :== (adresse+ 1) mod Mi
tant gue i pleine ~
début
si i:- case alors sortir (*échec*)
sinon i := (i+ 1) mod M
fin
insérer clé dans i
fin
fin
Chacune des méthodes ci dessus présente des avantages et des inconvénients
que discutent L1t~ln (thèse de Doctorat ès sciences). Régnier (thèse de troisième
cycle), Guiho(72 Etude des collisions dans les méthodes de hash-coding) et Knuth
(The Art of Computer Programm ing Vo11).
Récemment, un autre groupe de méthodes appelée Résolution de collision
par éclatement, a été proposé dont le principe est le suivant:
quand une coll ision a lieu,
- on alloue une nouvelle case au fichier
-
on éclate la case qui déborde: cela signifie qu'on partage lés articles de la
case qui déborde (y compris celui qui cause le débordement), entre cette dernière et
la nowelle case. "n'y
a donc pas de chaînes de débordement. Au cours d'une
recherche, la fonction de hachage se transforme dynamiquement et l'article
recherché se trouve à une seule adresse possible, celle indiquée par la fonction de
hachage; s'il n'y est pas, alors on peut conclure qu'il n'est pas dans le fichier. Pour
cela,
un seul accès disque suffit. Cette méthode est à la base des techniques
d'adressage dites de hachage virtuel, dynamique ou extensible(Litwin, Larson,
Fagin}.
15

---

2.5 Les différentes sortes de hachage
Les méthodes du htlchtlge s'eppt iquent tlussi bien il des ensembles de données
statiques qu'à des ensembles de données dynamiques. Dans le premier cas, on
parle de hachage statique ou classique, et dans le second cas, on parle de hachage
dynamique. C'est à ce dernier que nous nous intéressons particUlièrement dans
cette thèse.
2,5.1 Le hachage classiQue
Le hachage classique est une technique adaptée à la gestion des fichiers très
peu volatiles. Il faut connaître à l'avance le nombre d'articles à insérer dans le
fichier; puis on crée une table qui permet d'accéder au fichier. La taille de la table
est choisie en fonttion de la capacité d'une case et du nombre d'articles. De sorte
qu'on obtient de très bonnes performances.
L'inconvénient prtnclpel du htlchage clesslque est qu'une fois que le fichier a été
créé, on ne peut presque plus y Insérer ou supprimer d'articles. Et cela est
exlrêmement
gênant.
Une solution
à ce problème consiste à réorganiser
périodiquement le fichier en augmentant la taille de la table et en rehechent tous
les articles qui étaient dans le fichier avec une nowelle fonction de hachage; mais
cette procédure rend le fichier indisponible pendant longtemps. Une autre solution
est
de choisir à l'avance une grande table de manière à faire moins de
réorganisations; mais cette solution n'est guère meilleure car il y a gaspillage de
l'espace disque.
2.5.2 Le hachage gynamique
Le hachage dynamique a été introduit récemment, vers 1978-1979. A
l'irwerse du hachage classique, le fichier géré par hachage dynamique grossit et se
rétrécit selon les besoins d'utilisation. En particul ier à la création, le fichier n'a
qu'une seule case, et la fonction de hachage se transforme dynam iquement au fur et
à mesure que le fichier grossit ou se retrécit. Il n'y a donc plus de problèmes de
réorganisations périodiques ni de gaspillage d'espace disque. Cette technique
s'adapte beaucoup plus à la réalité des applications actuelles; c'est une des raisons
16

---

pour
tequeue, elle fllit
l'objet de beeucoup d'investigations de la part des
chercheurs.
2.5.2.1 Les tendances du hachage qynamigue
Plusieurs algorithmes de hachage dynamique ont été conçus qui pewent être
résumés,en trois grands courants d'idées:
2.5.2.1.1 Fichiers désordonnés à index ou table auxiliaire
Le premier groupe d'algorithmes utilise un index et ou une table de bits pour
transformer les clés en adresse disque. Table de bits et index sont conservés en
mémoire centrale. Leur taille varie suivant l'évolution du fichier. S'ils peuvent
être gardés en mémoire centrale,. l'accès à une adresse nécessite un seul accès
disque; sinon l'accès de l'index peut nécessiter plusieurs accès disques. Pour
résoudre les coll isions,. plusieurs cases sont allouées à la fois. Dans le hachage
virtuel (Litwin 79),. l'index est une table de pointeurs où les éléments pointent les
uns vers les autres. Dans le hachage extensible de Fagin, la structure de données est
un index sur le disque.
2.5.2. 1.2 Fichiers désordonnés sans index
Ce groupe est basé sur l'idée du hachage 1inéai re( Litwin 80). Les propriétés des
algorithmes correspondants étant très intéressants,. nous allons détai 11er le principe
du hachage Iinéai re.
Hahage 1inéai re (Litwin 1980)
Le principe de cet algorithme est basé sur les propriétés de la fonction
modulo: quel que soit i
N,. on peut écrire
- so it i mod 2n = i mod n
- soit i mod 2n = i mod n+n.
Ceci veut dire que si une fonction de hachage
hO( hO: c-->c mod n) est
remplacée par une autre fonction de hachage h1( h1: c-->c mod zn). alors quel
17

---

que soit l'enregistrement r, r aura soit la même adresse, soit une nouvelle adresse
qui est hO(c)+n.
Les éclatements des cases se font de manière cyclique (case 0, puis c.ase 1,
case 2, ... etc, C8Se N). En d'autres termes, la case qui va éclater à la prochaine.
collision est connue d'avance et n'est pas nécessairement celle qui déborde. Un
pointeur indique la prochaine case à éclater. L'allocation dé LI 'espace mémoire se
fait case par case.
Illustrons l'algorithme par un exemple:
hO
hO
hO
hO
hO
~
~
~
J.
~
ITI
[IJ
]
1
o
46
99
t pointeur
Sur le schéma ci dessus, la taille originale du fichier est de 100 cases ( de 0 à
99). Le pointeur indique la case 0 qui sera la case à éclater à la prochainé collision.
La première collision a lieu à l'adresse 46.
Sur la figure ci dessous, la case 100 a été allouée. Certains articles de la case 0
sont transférés dans la case 100. On crée un débordement à l'adresse 46. Après
l'éclatement, le pointeur indique la casesuivante ( la prochaine case à éclater).
~ hl ~ hO
~ hO ~ hl
o
1
46
99
100
tpointeur
Quand toutes les cases ont éclaté, le fichier a doublé de tai Ile; on recommence
alors le processus d'éclatement cyclique (la première case, puis la seconde ... etc,
1e

---

IG 199). Le hecheqe llnéeire est très perfnrrnent du f~it qu'il utilise très peu de
mémoi re centrale.
Plusieurs algorithmes du hachage dynamique s'inspirent du hachage linéaire,
notamment le hachage avec expansions partielles décrit par Larson(80) et
l'algorithme de M. Régnier, puis l'algorithme de Burkhard dont la propriété
remarquable est d'offrir l'accès multiattribut .
2.5.2.1.3 Fichiers ordonnés à arbre digital
Dans ce groupe d'idées, apparaissent à la fois une structure de tableau et une
structure d'arbre. Les feuilles de l'arbre pointent les adresses sur le disque. La
recherche d'une adresse revient à un parcours d'arbre. Larson et Litwin ont utilisé
une structure arborescente qui i Is ont appelée respectivement prefix binary tree
et trie ou arbre digital. Nous décrirons l'arbre digital d~ns le chapitre 1.
Ces algorithmes créent des fichiers ordonnés parti cul ièrement rapides à
accéder.
Parmi les verientes de ces algorithmes qui ont été publiées, nous pouvons citer:
DE JONGE(84) et Litwin(84).
Une des tendances actuelles est de proposer des algorittlmes qui utilisent des
structures de données très compactes, pouvant être conservées en mémoire
centrale pendant l'exploitation du fichier. Ceci dans le but d'effectuer toutes les
recherches en mémoire centrale, et de n'accéder à la mémoire secondaire que pour
lire ou écrire une case.
3. Autres méthodes d'adressage
Le hachage n'est pas la seule technique d'adressage; il ex iste d'autres procédés
qui le concurrencent. L'ouvrage de
Knuth cité plus haut, fait une très bonne
synthèse de ces techniques. Parmi celles ci, on peut citer les arbres M-aires et
leurs variantes dynam iques, les arbres_B _
Le principe des arbres M-ai res est le suivant:
pour dim inuer le nombre
d'accès disques, les noeuds de l'arbre sont groupés en pages. Plus la p~ge est grande,
plus les performances d'accès sont bonnes. Cependant, pour retrouver un article, il
faut au minimum deux accès disques(5 accès disques dans le pi re des cas), quel que
19

---

soit le nombre d'articles présents dans le fichier; même si ce nombre est
très
petit.
L'arbre M-aire peut être statique ou dynamique. Dans ce dernier cas l'arbre
augmente par des éclatements de cases. La méthode bien connue dite ISAM est la
plus représentative du cas statique. Les méthodes dites VSAM et UFAS sont
représentatives du cas dynami
~
,CAt'!E'?t'
'c.~
"'1'
y.'
/
,;/
3.1 L'arbre 8
':;
""
CAME
( ) ~
<.1
S
•
,lb
L 1Irbre_B (B_tr 11"
angl·;.,"
la structure de doméessowent utilisée
,'
Sv"
dans la gestion des fichiers" r Jas
\\ ds ordinateurs. Un arbre_B d'ordre m est
un arbre ayant les propriétés suivantes ( Knuth 73):
-
si un noeud contient k clés, alors ce noeud contiendra k+ 1 pointeurs (à
l'exception des feui Iles).
- les feuilles se trouvent toutes au même niveau; c'est le niveau le plus bas.
-
ehaque noeud, ~auf la raclne et I~ feuill~, a au moins m clés et au plus
2m clés {bornes comprises}.
-
la racine ou
la feui Ile a au moins une clé et au plus 2m clés (bornes
comprises).
La structure d'un tel arbre est la suivante:
Dans cette structure, on distingue deux sortes de pointeurs: un pointeur qu'on
appelle pointeur de noeud. Le pointeur de noeud désigne un autre noeud. Il permet
20

---

de passer d'un noeud à un autre noeud. L'autre pointeur qu'on appelle pointeur de
donnée permet d'accéder à une donnée. Il est associé à une clé d'article du noeud.
Il contient l'adresse de l'article sur le fichier.
Pour rechercher un erttele de clé donnée, on compare successivement les clé
avec chacune des clés de la racine:
1°_ s'il y a égalité, on accède directement à l'article grâce au pointeur de
donnée.
2°_ si la clé recherchée est inférieure, on accède au noeud de niveau plus bas à
l'aide du pointeur de noeud 8 gauche de la clé du noeud.
30 _
si elle est supérieure, on la compare avec la clé suivante du même noeud.
,
Puis on réitère 1° et si nécessaire 2° et 3°. Si dans le même noeud, tes comparaisons
nous amènent jusqu'" la dernière clé, alors on accède au noeudsuivant du niveau plus
bas grâce au pointeur de noeud à droite de cette dernière clé.
Si une clé n'est pas trouvée après recherche dans un noeud terminal, c'est
qu'elle n'existe pas dans le fichier. On montre(Comer79 et Bayer77} que dans une
organisation de type arbre_B, le nombre d'entrées-sorties nécessaires pour lire un
article dans un fichier de N articles est inférieur ou égal à 1+ log(m+ 1)«N+ 1}/2}.
L'occupation de la mémol re secondai re d'un fichier géré par arbre_B est de 7D % si
les clés sont générées aléatoirement, et de 50% si les clés som générées en ordre
ascendant. A titre d'exemple, un fichier d'un million d'articles géré per un arbre_B
d'ordre 100(ayant 100 clés par noeud), requiert envi ron quatre entrées-rsortles
pour retrouver un article.
La discussion plus approfondie des arbres_B peut être trouvée dans Bayer(17
ACM Transactions on Database systeme, vol.2, n01 pages1 1-26} et dans Comer(79
The Ubiquitous 8_tree ACM Computer Surveys, Vol. 11, n02, pages 121- 137}.
3.1.1 L'arbre B+
Un arbre_B+ est un art;Jre_8 dans lequel les pointeurs de données sont tous
sur le dernier niveau de l'arbre. En plus, les noeuds du dernier niveau sont chaînés
séquentiellement. La recherche d'un article de clé donnée se fait de la même
manière que précédemment; sauf qu'en cas d'égal ité, la recherche continue sur le
niveau inférieur indiqué par le pointeur de noeud gauche, jusqU'à ce qu'on arrive au
dernier niveau; auquel cas, l'égalité des clés donne l'adresse de l'article recherché.
21

---

L'arbre a+ permet de diminuer le coût d'accès à un article.
3.2ISAM
ISAM (Indexed
Sequential Acces
Method)
est une technique largement
employée- par les constructeurs d'ordinateurs. ISAM est un arbre M-aire avec
quelques aménagements au niveau de l'index pour permettre le maximum de travail
en une rotation du disque. Les articles gérés par ISAM doivent être triés en ordre
croissant. Un 'fichier ISAM est divisé en trois zones logiques qui sont:
-
une zone primaire composée de cylindres successifs où sont écrits les
articles à la première écriture. Les articles sont enregistrés par ordre croissant
des clés.
- une zone de débordement composée de pistes. Les. articles qui débordent sont
chainés.
-
une zone d'index où l'on écrit les index. Il existe au moins deux niveaux
d'index: les index de pistes et les index de cyl indres.
La méthode ISAM permet l'accès séque.ntielle trié. Le temps d'accês est de
3 entrées-sorties tant qu'il n'y a pas de débordement. Mais le 'fait que l'accès
dépende des caractéristiques du support phySique (pistes et cylindres) est un
inconvénient sérieux. En outre, la gestion des débordements est très complexe et
dégrade les performances; de ce fait, le fichier ISAM a besoin d'être réorganisé
périodiquement.
3.3 VSAM et UFAS
VSAM
(Virtual
Sequential
Acces Method) et UFAS ont été
introduits
respectivement par IBM et
CIIHB.
VSAM et UFAS sont
des arbre_B où des
optimisations ont été introduites au niveau de l'Index.
Les articles sont stockés
dans l'arbre_B au niveau le plus bas; seules les clés restent au niveau supérieur.
Puis certains niveaux sont dupliqués pour accélérer la recherche(qui se 'fait alors en
une rotation du disque}. Une étude très élaborée de V$AM se trowe dans Keehn(76
VSAM Data Set Design Parameters. IBM System Journal n03, 1974, pages
186-212}.
22

---

Toutes les méthodes d'adressage autres que le hachage ont des performances
d'accès 'typiquement comprises entre 2 et 5 entrées-sorties, ~ cause de la tai Ile de
l'index qui suit l'évolution de la taille du fichier. En effet, au fur et à mesure des
insertions, l'index grossit; et très tôt il ne peut plus être conservé en mémoire
centrale. Ce qui oblige à en déporter une partie sur la mémoire secondaire: cela
requiert des accès supplémentai res pour rechercher un article.
Pour éviter ces accès supplémentai res, la méthode d'adresSage doit proposer
unè structure de données qui peut être conservée en mémoire secondaire quelle que
soit la taille du fichier. Seul le hachage permet d'atteindre cet objectif pour des
grands fichiers.
Comme il est apparu dans l'exposé qui précède, beaucoup de problèmes sont
rattachés aux méthodes d'adressage, en l'occurence:
8 _ l'uniform ité et l'encombrement de la fonction de hachage.
Comme nous
l'avons dit plus haut, la fonction doit ranger approximativement le même nombre
d'articles dans les cases, pour évIter que certaines cases soient pleInes alors que
d'autres sont presque vides. La structure de données doit powoir être en mémoire
centrale pendant l'exploitation du fichier.
b_ les collisions (ou débordements) et leur résolution. Un bon algorithme doit
proposer des méthodes de réorganisations peu coûteuses en temps et surtout en
espace mémoire. On tient aussi compte de plus en plus de la simplicité
de la
méthode de réorganisation.
c_le nombre d'entrées-sorties {accès disque} pour insérer ou retrower un article.
d_ le taux d'occupation ou de remplissage qui apprécie l'utilisation de la place
mémoire disque. Nous rappelons que le taux de remplissage est égal au nombre
d'articles effectivement présents dans le fichier, divisé par le nombre d'articles
que pourrait conteni r le fichier.
nombre d'artIcles du fichier
taux
==
nombre d'artIcles que devrait contenir le fichIer
nombre d'articles du fichier
=------------------
b .. nombre de cases du flcnler
23

---

Des formules beaucoup plus sophistiquées prennent le taux moyen.. sa
variance.. etc selon la méthode étudiée. D'une manière générale, un algorithme est
d'~utant meilleur que son taux de remplissage s'approche de 100%.
Les méthodes de hachage dynamique ont retenu une grande attention, si l'on en
Juge par le nombre de publications correspondantes. Parmi celles cl, le hachage
digital de Litwin (Litw 82 et 84)
a
suscité beaucoup d'intérêt auprès des
chercheurs et a conduit de ce fait ~plusieurs investigations: Flejolet, Wiebren De
Jonge et Andrew Tanenbaum. Delafosse a proposé tout récemment un algorithme
pour améliorer le taux de remplissage du hachage digital. Il nous a aussi intéressé à
cause du fait qu' i1 crée un fichier ordonné.
Dans le chapitre qui suit, nous discutons cet algorithme en détails.
•
24

---

Chapitre 1 : LE HACHAGE plGITAL
1 Concepts généraux
La structure de données uti 1iséé dans le hachage digital (trie hashing en anglais)
est un arbre binaire.
Une clé
c a la forme sulvente.
c = dOd,d2 ..... dk-,dk
où les di sont des
digits et i le numéro du digit. i est encore appelé niveau de clé. J; est la longueur
de la clé.
Le digit peut être soit alphabétique, soit numérique. Les digits et donc les clés
sont tctelernent ordonnés. Desns l'ordre ASCII, on a:
es<b<c<d<..... œ eycz.
Dans une case, les· articles sont stockés dans l'ordre de leurs clés. Cela signifie
que si deux clés
c1 et c2 sont telles que c1 < c2 alors c, précède c2 dans la
case.
..
La recherche d'un article de clé donnée consiste en
'0) le calcul de son adresse, c'est à dire le numéro de la case susceptible de le
contenir. L'algorithme correspondant sera détaillé plus loin.
2°) le transfert de cette case en mémoire centrale;
3°) l'examen des articles présents d~u1S la case 51in de constater la présence ou
l'absence de l'article recherché.
2. L'algorithme
2.' Représentation d'un noeud de l'arbre digitllli
La fonction de hachage décrit dynamiquement une structure de données appelée
trie ou arbre digital. L'arbre digital est un ensemble de noeuds reliés per des
pointeurs; les noeuds sont numérotés de 0, , ,2 ... , à N; le numéro d'un noeud est son
adresse. Un noeud a la structure suivante:
25

---

UP
DY
DN
LP
Les zones UP (upper pointer)
et LP (Iower pointer) sont des pointeurs
respectivement dits supérieur et inférieur . Un pointeur est soit interne soit
externe. Un pointeur interne pointe un autre noeud. On admet que si un pointeur
pointe un noeud d'adresse m, alors sa valeur sere notée -m. Autrement dit, si la
valeur d'un pointeur est négative, alors ce pointeur désigne un autre noeud.
Un
pointeur externe indique soit une case soit aucune case. S'il indique une case, alors
sa valeur est positive et cette valeur est l'adresse de la case. S'il n'Indique aucune
case" alors sa valeur est la valeur spéciale 1 nil '.
Les zones DV (Digit Value) et ON (Digit Number) désignent respectivement
la valeur d'un digit de la clé, et le numéro (c'est à di re la position) de ce digit
dans la clé.
Cette représentation de noeud a été appelée représentation standard par
L1twin.
2.2 Constitution de l'arbre digital
L'arbre digital se crée dynamiquement par les insertions successives d'articles
dans le fichier:
1°) Etape initiale
L'arbre digital est vide (il ne contient aucun noeud);
On alloue la prem ière case au fichier (la case d'adresse 0);
Au cours des b premières insertions, il n' y a pas de calcul d'adresse; tous les
articles sont insérées à l'adresse o. La première collision arrive quand nous tentons
d'insérer le (b+ 1)ème article.
26

---

2°) règle 1 : Résolution de collision: .
D'une manière générale pour résoudre la colllslon. nous choisissons la plus
courte séquence de caractères c'oc' 1... c'k telle que nous ayons pour certaines clés
contenues dans cette case, la relation
cQc1 ... ck -( c'OC'1 ... c'k. C'est" dire qu'il
faut choisi r parm i les b+ 1 clés, la clé C' qui est telle que pour certaines clés ci,
a_ on ait ci =( c'
et pour d'autres clés Cj,
b_ on ait Cj >c'.
Le. clé c' recherchée est en fe.it la clé médiane.
Pour la première cculslon. l'examen du premier cëi"ractère(k=O) de chaque clé
suffit én général pour trouver la clé médiane.
3°) On alloue une nouvelle case au fichier.
4°) règle 2 : Partage des clés, réorganisation.
Parmi les b+ 1 clés, celles qui satisfont la condition b
ci dessus sont
transférées dans la nouvelle case. Les autres restent dans l'ancienne case.
5°) règle 3: Création du nouveau noeud.
Un nouveau noeud est adjoint à l'arbre digital{vide initialement). Pour la
première cotuston, ce noeud est comme suit:
1
val,O
o
Le pointeur supérieur a la valeur 1; d'une manière générale, c'est l'adresse des
ertlctes dont les clés sont supérieures" la clé médiane. Le pointeur inférieur a la
valeur 0; c'est l'adresse des articles dont les clés sont inférieures ou égales à la clé
médiane.
La zone DV que nous avons matérialisée par 'val' va contenir la valeur du digit
qui a permis l'éclatement.
La zone ON contient la veleur 0; c'est le numéro ou la position (ici le premier)
du digit.
La représentation graphique du noeud est la suivante:
27

---

ci (= c'
) c'
6°) règle 4: insertions suivantes.
L'arbre digital n'est plus vide. Pour les irfertions suivantes dans le fichier, on
compare le digit d'indice 0 (le premier digit>1 des clés à insérer au digit de valeur
1
'val':
si
cO =( 'val',
alors on loge l'article dans la case pointée par LP;
présentement c'est la case d'adresse 0; ceci correspond à emprunter sur le
graphique l'arc gauche. Si Co > 'val' alors on I~ge l'article dans la case pointée par
UP; présentement c'est la case d'adresse 1; ceci correspond à emprunter l'arc droit
sur le graphique.
7°) règle 5 : cas de noeud nil.
Il peut arriver que le digit suivant ne pe~mette pas de choisir la clé médiame;
c'est le cas où ce digit suivant est le même pour toutes les clés. Dans ce cas, on
crée un noeud 'nil' et on réitère la règle 1.
2.3 Exemple de constitution d'un fichier
Construisons un fichier sur un exemple av~c les mots français suivants comme
clés d'articles:
NOTRE, SA, TA, LUI, LEU~.. TU, LEURS, TES, NEUTRE, NIAIS,
NUIT,NATURE.
Nous fixons arbitrairement la capacité b Id'une case à 4.
1
on alloue la case d'adresse 0
les quatre premières clés sont insérées en ordre croissant dans cette case et
donnent
28

---

TA
SA
NOTRE
. LUI
o
case du fichier
La première collision arrive quand on essaie de loger la clé LEUR.
2_ La clé NOTRE est la clé médiane. En effet~ le premier digit N de cette clé
permet d'établir les relations de la règle t, il suffit donc pour créer l'éclatement.
3
On alloue une nouvelle case au fichier
4_ On partage les articles entre les deux cases en appliquant la règle 2. On
obtient:
1
NOTRE
N~O
LUI
TA
LEUR
SA
,
o
o
cases du fichier
Structure du nOeud
Graphe de l'arbre digital
29

---

L'Insertion des autres clés donne la structure suivante du fichier:
NOTRE
TU
LUI
TES
LEURS
TA
LEUR
SA
o
L'Insertion de la clé NEUTRE cause une autre collision sur la case d'adresse o.
En appliquant les règles précédentes, on constate que la clé médiane est LEUR et on
obtient:
1
1
2
TU
LUI
TES
N,a
L,O
LEURS
TA
NOTRE
LEUR
SA
NEUTRE
-1
0
a
1
2
o
Structure du fichier
Structure des' noeuds
Graphe de l'arbre digital.
30

---

Dans le noeud numéro 0.. le pointeur iniérieur a la valeur -1; celà signifie qui i 1
désigne le noeud d'adresse 1.
En continuant les insertions.. on voit que les clés NIAIS et NUIT sont logées à
l'adresse 2. La structure du fichier est :
TU
NUIT
LUI
TES
NOTRE
(1)
LEURS
TA
NIAIS
LEUR
SA
NEUTRE
,
o
2
L'insertion de la dernière clé NATURE crée une collision à l'adresse 2. La clé
.1
médiane est NIAIS. La règle 1 sélectionne en effet les digits NI; N étant déjà dans
l'arbre.. le digit suivant 1 donne lieu à un nouveau noeud.
L'éclatement donne: .
1
-2
3
LUI
TU
LEURS
TES
NIAIS
N,a
L,O
1..1
TA
NEUTRE
NUIT
LEUR
SA
NATURE
NOTRE
-1
a
2
,
o
1
2
3
a
2
Structure du fichier
Evolution des noeuds
31

---

Evolution de l'arbre digital.
Dans le noeud numéro 2" I~ zone DN a la valeur 1; c'est le numéro du digit qui a
permis l'éclatement.
Supposons maintenant que dans la case 21 de (1).. les clés avaient été NANTI,
NAGER, NARQUOIS, et NAVIGUER, le deuXi~me digit (qui serait dans ce cas A)
n'aurait pas suffit à choisir la clé médiane. Il eut fallu se reférer au troisième digit
pour choisir la clé médiane (NARQUOIS danslce C,8S). Ceci conduirait à la création
d'un noeud nit. Nous aurions eu comme résulta~ la structure suivante:
32

---

TU
LUI
NAVIGUER
TES
LEURS
TA
NANTI
NATURE
Evolution du fichier
LEUR
SA
NAGER
NARQUOIS
o
1
2
3
1
-2
nil
3
N,O
L,O
A,1
R,2
Evolution du noeud
-1
0
-3
2
Evolution de l'arbre digital
2.4 Performances de l'algorithme.
Les
performances
de
l'algorithme
ont
été
étudiées
par
simulations
Mekouar(83). Cette étude révèle que:
33

---

1
-le taux de remplissage est de 70% pour les insertions aléatoires, et de 66%
pour les insertions ascendantes.
-le nombre de noeuds 'nil' est négligeabl1.
-l'arbre digital peut être de ce fait ep mémoire centrale même pour des
fichiers de l'ordre 106 articles. Il en résulte que :
-\\e nombre d'accès disque pour trow,r un article présent dans le fichier
est de 1.
-le nombre d'accès disque pour concl'. re qu'un article n'appartient pas
au fichier est de 1.
i
1
En ce qui concerne l'arbre digital:
1
La représentation discutée ci-dessus né~essite en pratique 6 octets par noeud.
De ce fait, un tampon de 64k en mémoire suffit à un fichier ayant 10900 cases. Si la
capacité d'une case vaut 100 articles, alors 01 peut insérer jusqu'à 760000 articles.
34

---

Chapitre 2 : LE HACHAGE DIGITAL BINAIRE
2.1 Introduction
Nous avons vu au chapitre précédent que dans la représentation standard, la
tai Ile des noeuds(un noeud est représenté sur 6 octets) ne permet pas d'envisager le
traitement des fichiers de plus de 104 cases avec les performances d'un accès
disque par recherche. Pour augmenter le nombre de cases correspondant 8 une
même taille physique(en octets) de l'arbre digital" il faut diminuer la taille d'un
noeud. La reflex ion sur cette voie nous a amené à deux principes:
(a)- on considère qu'un digit est un bit; ce qui signifie d'une clé est une suite de
bits.
(b)- supprimer les pointeurs des noeuds internes; l'arbre digital est alors
représenté d'une manière séquentielle.
Dans ce chapitre, nous définissons une méthode d'accès basée sur ces principes.
Nous montrerons qu'elle atteint les objectifs fixés. En effet" la taille d'un noeud est
presque égale à la taille d'un pointeur; en pratique, elle vaut 2 octets et 1 bit pour
les noeuds externes" et de 1 bit pour les noeuds internes.
Dans ce qui suit, nous décrivons les algorithmes de notre méthode, en
t'occurence l'algorithme de recherche d'une clé" d'insertion d'un article et de
compactage de la structure des données. A cette fin" nous commençons par la
description de l'évolution de l'arbre dIgital binaire généré par notre algorithme puis
nous définissons les algorithmes discutés.
Pour le calcul d'adresse, nous utilisons l'équivalent binaire des clés. Une clé
sera donc une chaine de bits
(Os
et
1s). Une clé c est de la forme: c =
bOb1.··bk- 1bk où les bi sont les bits de la clé.
Nous résolvons nos collisions par la méthode de l'éclatement. L'allocation des
cases est incrémentielle et se fait une par une.
35

---

2.2 L'tubre digit"l bin"j re
Notre fonction de hachage génère un arbre digital binaire dont les feuilles
1
(noeuds terminaux) pointent vers les cases sur le gisque.
Les noeuds de l'arbre sont des bits (Os et 11$)' Cet arbre est conservé en
1
mémoire centrale pendant l'exptoitettcn (recherche, insertion, suppression) du
fichier. Toutefois, comme nous le montreront, leS feuilles pewent être déportées
sur le disque pour de très grands fichiers.
Nous avons choisi de matérialiser ce: arbre ~inaire en mémoire centrale par
deux tables de longueur dynam lque.
- l'une notée 8, représente la structure de l'arbre. 8 est donc une table de bits.
- l'autre notée T, contient les feuilles. T est.~ppelée table des pointeurs.
Les éléments de 8 et T sont dans l'ordre du parcours postfixé (ou préordre) de
l'arbre.
2.3 L'algorithme de constitution de l '"rore digit'"
i
Etape initiale:
L'arbre digital est vide(i 1 ne contient aucun n~eUd).
1
- On alloue la première case au fichieri c'est la case d'adresse O.
- On affecte T(O)=O.
,
Pour les b premières insertions, il n' y a ~as de calcul d'adresse, tous les
!
,
articles sont insérés à l'adresse O.
L'insertion dr la (b+ 1)eme clé provoque une
collision.
1
Seconde étape, résolution de la collision: examen des clés.
Règle 1
1
On crée une nouvelle case à la suite du fichier~case d'adresse 1 présentement).
On exam ine le bit suivant de chaque clé (y compris celle qui déborde). Pour
la première collision, le bit examiné en premier sera le bit d'indice D, c'est à dire 'e
premier bit.
36

---

Si ce bit vaut 1, alors la clé examinée sera logée dans la nouvelle case (à
l'adresse 1 présentement).
Si ce bit vaut D, la clé examinée reste dans l'ancienne case. ( à l'adresse 0
présentement).
Troisième étape: éclatement.
Règle 2
On insère deux bits, le bit 0 et le bit 1, dans la table des bits B; il en sera ainsi
pour chaque éclatement de l'arbre digital.
On insère l'edresse de la nowelle case dans la table T; il en sera ainsi pour
chaque éclatement de l'arbre digital. C'est la case qui contient l'adresse 1 dans le
cas de la première résolution de collision. On fait le partage des clés suivant les
résultats de la seconde étape. Sct'lématiquement, on obtient pour ce premier
éclatement:
CD
1 0 1 1
o
1
Graphe de l'arbre digital
Table T
Table 8
cases
du fichier
Règle 3
/1 arrive quelques rares fois que l'examen du bit suivant des clés ne permette
pas de résoudre la collision. C'est le cas où toutes les clés ont la même valeur du
bit; el les doivent de ce fait être logées dans la même case: la coll ision n'est donc
pas résolue. Dans ce cas:
a_ On insère deux bits ( bit 0 puis bit 1) dans la table B.
b_On insère une case dans la table des pointeurs T;
on met la valeur
particulière 'nil' dans cette case de la table Ti elle correspond au noeud externe
'nil'. Puis l'on réitère l'opération.
37

---

1
Exemple
1
. Supposons que bO =1 pour les b+ 1 clés examlnées, puis que b1= 1 seulement
pour certaines de ces clés. Alors, pour le premier éclatement, l'évolution de l'arbre
digital et des tables B et T est comme suit:
1
1
(a) après l'examen de bO
Graphe de l'arbre digital
Table T
Table B
(b) après examen de b1
Graphe définitif de l'arbre digital
Table T
Table B
Le graphe ci dessus correspond au cas ù le bit suivant de tous les articles
exam inés ont la valeur 1. Ils sont donc di rigés ers la case pointée par le noeud droit
de l'arbre: Il ya eu formation de noeud 'nil'. ~a valeur 'nil' signifie que cet élément
de T ne pointe pas de case dans le fichier.
1
SI pour tout c examiné, bQ-O, alors les jrticles auraient été logés dans la case
pointée par le noeud gauche de l'arbre; et nous aurions eu le cas de graphe suivant:
1
38

---

1 0 1 1
Graphe de l'arbre digital
Table T
Table B
1 0 0 11 1
Graphe définitif de l'arbre digital
Table T
Table B
les insertions dans les tables B et T sont faites de manière à préserver l'ordre
ascendant des noeuds. Si par exemple, le noeud numéro 0 de la figure 1 ci-dessus
venait à éclater, nous obtiendrons le graphe suivant:
000111
Graphe de l'arbre digital
Table T
Table B
39

---

La figure 2 ci-dessous nous montre une configuration d'une table B avant et
après l'éclatement d'un noeud externe:
001101
avant éclatement
00110011
après éclatement.
fig. 2
L'arbre digital change de configuration au fur et à mesure des éclatements.
Après plusieurs insertions" nous powons obtenir par exemple la configuration
suivante:
Graphe de l'arbre digital
0001100 11101000 111 1
Table T
Table 8
40

---

Schématiquement, les correspondances entre les éléments de B, de T et les
cases du fichier s'établissent comme suit:
0 0 0 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1
8
T
o 1
2
3
4
5
6
7
Fichier
2.4 Proeriétés des tables 8 et T
On peut observer de l'évolution du graphe, les propriétés importantes suivantes
des tables B et T :
1. Dans la table B, un bit représente un noeud externe, si et seulement si son
suivant est un bit 1 .
2. Le dernier bit de B représente un noeud externe.
3. Chaqueéclatement insère dans 8 un couple de bits 01.
4. L' indice i dans T du ième pointeur est égal au numéro, soit j, du jème bit
représentant un noeud externe.

---

La figure 3 de ce chapitre illustre ces propriétés. Elles sont à la base des
algorithmes de notre méthode.
2,5 Seeheche d'yn article; exploration de l'arbre digital,
2.5.1 Description Informelle
D'une manière générale, la recherche d'un article de clé donnée consiste dans
a) la transformation de cette clé sous sa forme binaire,
b) le calcul de son adresse dans le fichier,
c} le transfert de la case correspondante en mémoire centrale,
d) l'examen des articles présents dans cette case pour constater la présence ou
l'absence de l'article recherché.
Au cours de la recherche d'un article, si l'adresse fournie par (b) est la valeur
particulière • nil' , alors nous concluons que l'article n'est pas dans le fichier,
Le calcul (b) consiste à parcourir l'erbre binaire jusqu'à atteindre un noeud
terminal. Pendant cette exploration, la clé concernée est examinée bit par bit. A
chaque noeud interne, nous devons choisir entre la branche gauche et la branche
droite de l'arbre. Ce choix nous est guidé par la valeur du bit courant dans la clé. Si
ce bit vaut 0, on emprunte la branche gauche; sinon (il vaut donc 1>., on emprunte la
branche droite.
Exemple: Les cinq clés dont les configurations binaires sont respectivement
0001001
0100110
0010011
0101100
1100100
auront pour adresse respective 0,2,5,3,7
dans l'arbre digital de la figure 3 ci
dessus. Nous décri rons ultérieurement la procédure de recherche dans ta table B.
Un fait est à remarquer dans l'exploration de l'arbre digital: à chaque fois que
nous rencontrons un bit 1 dans la clé, nous empruntons la branche droite de l'arbre;
ce mowement à droite correspond au saut du sous arbre gauche de l'arbre. Et à
chaque fois que nous rencontrons un bit 0 dans la clé, nous empruntons la branche
gauche de l'arbre; ce mouvement à gauche correspond à une exploration séquentielle
42

---

de l'arbre digital. Ce fait sera important pour la définition formelle de l'algorithme
de recherche présenté plus loin.
L'arbre digital est donc représenté par les tables B et T. Ces deux
tables sont séparées, d'où le nom de la méthode: SEQUENTIELLE BINAIRE A
POINTEURS SEPARES.
2.5.2 Recherche dans 8
Au moment de l'exploration de la table B, il faut reconnaître les sous arbres et
pOUt/air les sauter quand cela est nécessaire (quand le bit examiné de la clé vaut 1).
Pour cele nous utilisons un compteur que nous evcns eppelé nML'r"
dans
l'algorithme. Ce compteur nous donne le niveau auquel nous nous trowons dans
l'arbre, et nous permet de nous arrêter au bon niveau et à la bonne feuille de
l'arbre.
Les algorithmes: qui permettent de calculer une adresse sont comme suit:
Données:
clebit = clé sous forme de.bit;
18 -= entier = longueur de la table B;
Procédure exploration
Cette procédure sert à déterminer l'indice du bit représentant le noeud
ex te me recherché.
Vari"bles:
indB=entier= indice de la table B;
indc=entier=indice de la clé.
début
-si clebit[indc) -= 1 alors sauter le sous arbre;
-si B[indB+ '1] = 1 QY. indB = 18 àlQ.Œ lire T pour avoir l'adresse
-sinon fai re
43

---

début
indB :=indB+ 1;
indc:= indc+1;
explcretton,
fin
Prooédure sauter
CeUe procédure sert à sauter un sous arbre.· Elle fait appel à 2 autres
procédures descente et remontée. Comme nous l'avons vu, le saut d'un sous arbre
correspond à 2 mowements: le saut de la branche gauche, puis le saut de la branche
droite.
Le
premier mouvement est effectué par
descente et le deuxième
mowement est effectué par remontée."
Variables:
cpt,nlveau=entler;
début
-cpt := 0;
-niveau: = 0;
-descente(cpt,nlveau);
- remontée{niveau};
ün
procédure remontée{compt-entier)j
nivau=entier;
début
tant gue compt <> 1 faire
début
indB:= indB+ 1;
44

---

compt : = compt- 1;
si B[indB:] = 0 ~
début
descente{compt.n ivau);
compt :==nivau;
fln
procédyre descente(cpt=entier: variable nivo=entier):
début
tant gue
B[indB] = 0 faire
début
indB:= indB+ 1;
cpt:= cpt+ 1;
fin
nivo:=cpt;
fin
2.5.3 Recherche dans T
Cette recherche a pour but de trouver à partir de "indice indB de B l'élément
de la table T qui contient l'adresse sur le fichier. Elle est basée sur la propriété(4).
fonction casedeT: entier;
Donnée:
indB-indice déterminé en 252
Variables:
indexe~indt == entier;
début
indt:1=: 0;
45

---

indt :- 0;
indexe:= 0;
tant gue indexe =<indBfaire
début
~ B[indexe+ 1] = 1 ou indexe = 18 alors indt :=indt+ 1;
indexe:" indexe+ 1;
fin
casedeT: =indt;
fin
Une codification
en langage de programmation Pascal de la procédure de
recherche est donnée en annexe.
2.6 Reguêtes à intervalles
2.6. 1 Notion
On peut vouloi r local iser dans le fichier tous les articles dont la clé, soit C., est
dans un intervalle donné de valeurs de clés. Par exemple, on peut demander tous les
articles dont la clé commence par la lettre L. Ceci correspondrait à la recherche
de tous les articles tels que:
'L tic <' .,...,.
•
Une telle requête est appelée reguête à intervalle. Selon la définition, il peut
s'agir de l'intervallefermé,ououvertousemi owert.
Une
requête à Intervalle n'est satisfaite avec efficacité que dans un fichier
ordonné.
En effet, les clés correspondantes sont groupées dans des cases
logiquement consécutives, peut être même dans une même case.
L'ordre étant
connu, Il suffit de déterminer la case correspondante à la borne Inférieure et de
suivre les adresses logiquement' consécutives jusqu'à la case correspondant à la
borne supérieure. On peut alors satisfaire la requête en n'examinant que quelques
cases, une à la limite. Par contre, dans un fichier désordonné, il est facile de voir
qu'il faut examiner toutes les cases. D'où l'intérêt de fichiers ordonnés.
46

---

Dans l'arbre digital de notre méthode, la requête à intervalles définit un sous
arbre dont les feuilles pointent les cases qui contiennent les articles recherchés. On
peut observer (fig. 3) que ce sous-arbre définit également un intervalle d'adresses
dans la table T. Les contenus des éléments de T correspondants, s'ils ne sont pas
'n1I'~ pointent les cases à examiner. Le coût de la requête, en accès disque est
exactement le nombre
de cases
recherchées. Un arbre_S nécessite davantage
d'accès, étant donné au moins le nombre d'accès nécessaire pour trouver la case
correspondant à la borne inférieure.
T
o
2.0.2 Traitement de requêtes à intervalle
Soit l
"Intervalle et soient cll!,-Int" et cll!,-slIp respectivement les valeurs
inférieure et supérieure de /. Nous noterons respectivement '-in'let '-SlJI.7 les
adresses dans T correspondant respectivement à I.~/~,-in'" et c/~,-$"P. Soit Inf:'-bit
la représentation binaire de cf~,-Inf et Slip_bit celle de cll!,-sup. Soit enfin fgCfl!.
la longueur max imale en bits d'une clé d'article.
L'algorithme général de traitement d'une requête à intervalle est comme suit:
début
47

---

- déterminer '--in!";
- déterm iner '--sup;
- examen des Casesi
fin
T in!" et '--'BUp sont calculées toujours comme s'il s'agissait de trouver les
articles ayant comme clés respectivement cle,-inf et cle,-sup. Par contre.. les
détails de l'examen des cases dépend du type de la requête. On recherche
simplement tout c correspondant à l'une des conditions suivantes :
- ( cle,-inf 1. c s cle,-sup) pour l'intervalle fermé
- ( cle,-inl <' 1.": <' cle,-sup) pour l'intervalle ouvert
- ( ete__ inl i c « cte__sup) pour l'intervalle fermé inférieurement.
- ( ete__ inl ( C s cle,-sup) pour l'intervalle fermé supérieurement.
2.6.2. 1 Intervalle fermé
L'examen de cases se fait comme suit:
début
pour j:= '--inf à '--slip faire
.§.i T(i] oni 1alors
début
1ire(F,T[1]);
case := (F..T[il);
pour j := 1 à b faire
si (case(j] >=cle_lnf) ill (case(j] <=cle_sup) à.l.Q.ri écrl re(case[j]);
fin
2.6.2.2 Intervalle ouvert
début
RQY!. i:- T_in!" à '--sup fai re
..iL T(i] 0 ni1.è.l.Q.r.i
début
48

---

1i re(F, T[i]);
case:=(F,T[i]);
pourj:=1 à b faire
~
si (case[j] >cle_inf) et (case[j] <cle_sup) alors ecri re(case[j]);
fin
2.6.2.3 Intervalle fermé inférieurement<semi owert en bas}
Les clés qui satisfont la requête sont données par la procédure suivante:
début
Q.Q..YL i := ~inf à ~sup ~
.!l. T[i] onil alors
début
1i re(F, T[i]);
case: = (F,T[i]);
QQYL j : = 1 à b :fàJ.œ.
li (case[j] >cle_inf) et (case[j]< =cle_sup) alors écri re(case[j]);
fin
2.6.2.4 Intervalle fermé sueérieurement(sem i owert en haut)
Les articles qui satisfont la requête sont donnés par la procédure suivante:
début
pour i:- '-in!" il '-sup~
iL T[i] Onil alors
début
1ire(F,T[i]);
case:=(F,T[i]);
pour j:= 1 à b faire
~ (case[j] >=cle_inf) et (case[j] <cle_sup) Sl!.Q.Œ écri re(case[j]);
fin
49

---

2.7 Insertion
Quand un nouvel article {nous vérifions auparavant qu'il n'est pas déjà dans le
fichier) doit être Inséré dans le fichier.. Il peut arriver trois situations:
1°) l'adresse fournie par la fonction de hachage correspond à une case qui n'est
pas pleine. Dans ce CDS l'insertion est triviale: la case est lue en mémoire centrale,
le nowel article est inséré dans la case, et enfin la case est réécrite sur le disque.
2°) l'adresse fournie par la fonction de hachage est un noeud 'nil'. Dans ce cas on
alloue une case au fichier (car les noeuds 'nil' n'ont pas d'espace disque qui leur sont
alloué). Puis l'adresse 'nil' de la table des pointeurs est transformée en l'adresse de
la case que nous venons d'allouer. Enfin, l'article est logé dans la case et celle-ci
est écrite sur le disque.
3°) l'adresse correspond à une case pleine. C'est le cas d'une collision. Nous
résolvons les coll isions en observant les règles établies au paragraphe 2. 1 de ce
chapitre.
2.7.1 Algorithme général
Variables
indc=entier=indice de la clé.
début
-si l'adresse correspond à un noeud 'nil' alors
début
-allouer une case à la suite du fichier
-remplacer l'adresse 'nil' par le numéro de la nowelle case
- insérer l'article dans cette nowetle case
-écrire cette case
fin
-sinon
-§l J'adresse correspond à une case pleine J!.Q.r!
début
50

---

- 1ire 1a case
-indc=O
-examiner le bit de chaque clé
-si les bits examinés sont tous égaux à 1 .Q.Y.à a alors creation
de noeud nil
-éclater la case
-écri re les 2 cases
fin
-sinon
début.
-lire la case
-insérer l'article dans la case
-réécrire la case
fin
2.7.1. 1 procédure éclater (partage des articles)
Cette procédure sert à éclater une case.
Données
Cd = clé qui cause le débordément;
case1 = case qui déborde;
caseZ == nouvelle case allouée;
b = capacité d'une case;
Variables
i - entier;
Ci = ième clé examinée dans la case;
début
-allouer une case à la suite du fichier
- pour i - 1 à b faire
début
-si le bit suivant de Ci = 1 alors insérer Ci dans caseZ
S1

---

-effacer Ci dans case1;
fin
-si le bit suivant de Cd = 1 alors insérer Cd dans case2
sinon
insérer Cd dans case 1
fin
2.7.1.2 procédyre création de noeud nll
début
- insérer 2 bits dans B;
-insérer 1 pointeur nil dans T;
-indc=indc+ 1 (incrémenter l'indice de la clé);
-examiner le bit de chaque clé;
-si les bits sont tous égaux à 1~ à 0 alors création de noeud ni 1;
fin
2.8 Fusion des cqses
La fusion des cases est une opération sous jacente aux suppressions d'articles du
fichier. Au fur et à mesure des suppressions d'articles, les cases se vident et le taux
de remplissage du fichier baisse. Pour conserver un bon taux de rempl issage, il faut
fusionner et 1ibérer si possible les cases vides ou à moitié vides.
Nous proposons deux stratégies :
-La première consiste à envisager la fusion des cases à chaque suppression
d'article. Les cases résultant de cette stratégie seront à 100% pleines.
-La seconde stratégie consiste à n'envisager une fusion que lorsque la case
courante est à moitié vide.
Si le nombre d'articles par case est conservé sur le disque (comme nous le
verrons ultérieurement), l'opération de fusion des cases demandera des accès
disques supplémentaires pour envisager une fusion. Or cet examen peut s'avérer
impossible. Si le nombre d'articles de chaque case est conservé en mémol re
centrale, on n'accèdera au disque que lorsque la fusion est possible; mais la
conservation du nombre d'articles en mémoire centrale requiert de la place
mémoire.
52

---

La fusion des cases du fichier entraine la fusion des noeuds de l'arbre digital. La
fusion de deux ou de plusieurs noeuds externes consiste à les combiner en un nombre
de noeuds plus petit.
2.8.1 Définition et propriétés
Définition: Nous dirons que deux noeuds de l'erbre digital sont des frères
gauche et droit:
'0) s'ils sont des noeuds terminaux
2°) s'i Is sont issus directement du même noeud interne (appelé père).
a
c
Les noeuds a et c ci-dessus sont desfrères. a est le frère gauche et c est le
frère droit. b n'a p~ de frère.
Proppriétés: Dans la table des bits B:
1°} si un noeud externe correspond à un bit 0,. alors son frère s'il existe
est son suivant et vaut 1. " s'agit alors de son frère droit. Cela se traduit
formellement par:
iLB(i)=O alors son frère existe aLB(I+ 1)=1 fi B(I+2}=1.
2°) si un noeud externe correspond à un bit 1, alors son frère s'il existe est
son prédécesseur et vaut o. Il s'agit alors de son frère gauche. Cela se traduit
formellement par:
..!i. B{i)= 1 alors son frère existe ssi B{i-1 )=0.
2.8.2 Principe de la fusion des cases
S3

---

Nous ne fusionnons que des cases vers lesquelles pointent des noeuds externes
frères. Ces cases sont dites cases logiquement consécutives. Sur la figure 3
précédente, les cases 0 et 5 sont logiquement consécutives. Il en est de même des
cases 2 et 3.
Cette fusion des cases induit celle des noeuds externes frères. Après la fusion
des noeuds, seul le frère gauche reste à la place du père. 1/ peut cependant arriver
que l'opération de fusion soit impossible, parce qUe le noeud concerné n'a pas de
frère; dans ce cas, si la case correspondante est vide, on porte ce noeud InW et on
1ibère la case.
Dans le cas où la fusion des noeuds est possible, la table des bits B rétrécit de
deux bits et la table des pointeurs T rétrécit d'un élément.
Illustrons ces principes par des exemples :
Exemple'
(a)
~loo'oO'" 1 o 1 2 3 -4
Table T
Table 8
Cases du fichier
54

---

lb)
o
Z
3
Table T
Cases du fiéhier
Imaginons que sur la figure 6 -a ci-dessus, la case 0 devienne vide à la suite de
suppressions répétées dans celle-ci. Le noeud correspondant ne peut pas être
fusionné, parce qu'il n'a p. de frère. Sur lafigure 6-b, ce noeud est porté 'ni!'. Les
ertlcles de I~ dernière case (ici
I~ case 4) sont transférés d~ns I~ case
correspondant à ce noeud (ici la case 0). Cette dernière case est restituée au
système. La table T est mise à jour en conséquence.
Exemple2
(a) avant fusion des cases.
~ 100101101011
Table T
Table B
o
1
2
3
4
5
55

---

(b) après fusion des cases 2 et 4.
o
1
~
rn=IJJ
100110101
1
o 1 2 3
4
Table T
Table B
Cases du fichier
Sur la figure 7 ci-dessus, les cases 2 et 4 du fichier ont fusionné. Les articles
de la çiernière cese ont été transférés dans la eese 4. Cela a entrainé la fusion des
noeuds correspondant de l'arbre digital (ici les noeuds 2 et 4). La table T a rétréci
d'un élément et a été mise à jour en conséquence; la table B a rétréci de 2 bits, les
bits correspondants aux noeuds externes qui fusionnent.
La procédure de fusion des noeuds est récursive; ainsi la fusion de deux noeuds
peut entrainer celle de plusieurs autres noeuds de l'arbre comme l'Illustre bien
l'exemple qui suit:
Considérons la figure 8 ci après
.56

---

(b)
(a)
1
2
Sur cette figure~ des noeuds 'nil' se sont formés en (a) et n'ont pas pu être
fusionnés parce que aucun d'autre eux n'avait de frère.
Si les noeuds 1 et 2 viennent à être fusionnés, ils entraineront la fusion de tous
les noeuds 'nil' qui appartiennent au même sous arbre qu'eux. Nous obtiendrons
alors la structure (b).
2.9 Le problème des noeuds 'nil'
Le problème inévitable sous jacent à notre méthode du hachage ~ est la
formation des noeuds dits 'nll'. Comme nous l'avons vu, un noeud 'nil' est un noeud
externe qui ne pointe pas de case sur le fichier. Il se crée ete deux- manières
différentes; soit pendant "éclatement d'une case: lorsque tous les articles sont
logés dans une même et seule case (paragraphe 2.3~ règle 3); soit pendant les
suppressions d'articles: quand la case devient vide et qu'on ne peut pasfusionner le
noeud externe corresponderrt, (paragraphe 2.6.2). Les noeuds 'ni l'encombrent
inutilement les tables B et T~ mais ne peuvent pas être supprimés. Ils peuvent de ce
fait entrainer une augmentation importante des tailles de ces tables. Ceci
impliquerait d'importantes pertes de places rnémolres, surtout si leur nombre en
proportion est importante par rapport au nombre de cases du fichier. Il faut donc
57

---

trower un procédé qui minimiserait leur formation. Nous proposons une solution
dans le paragraphe suivant.
J. Implémentation
3.1 Proposition de solution pour lesnoeyds 'nil'
Dans le but de réduire I.a formation des noeuds 'nil ', et pour.notre méthode,
nous avons étudié
la configuration binaire des caractères alphabétiques et
numériques. Cette analyse nous révèle que tous les caractères commencent par les
mêmes bits: 01 pour les caractères alphabétiques et 00 pour les caractères
numériques. Ces bits égaux favorisent la création des noeuds 'nil'. Nous nous
sommes donc proposés de les ignorer dans la constttutlon de l'arbre digital et dans
le calcul d'adresse. Cela signifie que nous ne travaillons passur la clé originale mais
sur une clé transformée.
J.2 Déjec:tlon des emplacements 1ibres dans le fichier
Au cours de l'exploitation du fichier, nous avons besoin de savoir le nombre n
d'éléments effectivement présents dans une case. Soit pour les insertions, soit pour
les fusions de cases.
Plusieurs
possibi lités
peuvent-
être
envisagées
pour
consigner
cette
information:
, 0 _ Nous pouvons adjoindre n
ia chaque case du fichier. Mais cette solution
demandera des accès disques supplémentai res pour examiner la fusion des cases; or
la fusion peut s'avérer impossible. Les performances d'accès peuvent être alors
détériorées inutilement, surtout s'II y a beaucoup de suppressions et peu de fusions.
20_
Nous pouvons également consigner n dans une table séparée et adressée
par le numéro de la case correspondante dans le fichier. Cette table sera en
mémoi re centrale pendant l'exploitation du fichier. Chaque nombre n sera noté sur
un octet {puisque les valeurs de b sont inférieures à 255}. Mais cette table va
occuper de la place en mémoire; en outre" elle sera un fichier en plus à gérer.
58

---

3°_La troisième possibilité qui peut être erNisagée est une variante de la
seconde possibilité. Elle consiste à adjoindre n à chaque case de la table T. Chaque
nombre n sera toujours noté sur un octet. Par rapport à la seconde possibilité, le
bénéfice que nous retirons dans cette organisation est qu'il y a une seule table à
gérer. Mais reste toujours la place mémoi re qu'occupera cette table..
Le choix de "une ou l'autre des possibiHtés que nous venons de mentionner est
un .cornpromts espace-temps. Le premier cas est un gain de place mémoire
centrale et le second cas(ou le troisième) constitue une rapidité d'accès.
Nous pensons que pour un
fichier volumineux(la table n occupera une
importante place en mémoire), la première possibilité serait préférable. Par
contre... pour un fichier peu volumineux qui subit beaucoup de suppressions, la
troisième possibil ité est à notre avis le meilleur choix.
3.3 Réalisation d'une aeelication eratigue
Une application pratique basée sur notre méthode, en l'occurence un systéme
de gestion de fichiers(SGF), a été implémentée sur
SM90 UNIX à "INRIA. Les
fonctions principales de notre système sont
les fonctions habituelles d'un
gestionnai re de fichiers.
Notre SGF est composé de deux couches: le noyau(qui constitue la couche la
plus interne), et une couche externe.
3.3.1 Le nwou
.Le noyau de notre système assure les fonctions de création et de destruction
d'un fichier, et de calcul d'adresse; il fournit aussi les caractéristiques d'un fichier.
2.3.2 La couche externe
La couche externe de notre système assure la gestion des articles(insertion,
suppression, modification et consultation). Les requêtes à intervalles sont aussi à la
charge de [a couche externe.
59

---

Chapitre 3 ; EVALUATION DES PERFORMANCES
Ce chapitre est consacré à l'analyse des performances de notre méthode. Ces
performances ont été uniquement étudiées à travers des simulations.
A cette fin, nous avons généré des séries d'Insertions d'une part avec des clés
générées aléatoirement et d'autre part avec des clés triées en ordre ascendant. Le
programme de génération aléatoire des clés est donné en annexe. Les capacités des
cases ont été respectivement b= 10, 20, 50, 100. Pour les différentes valeurs de b
mentionnées -aussi bien pour les insertions aléatoi res que pour les insertions en
ordre ascendant des elés-r , nous avons d'une part tracé les courbes représentant
l'évolution des tables B et T en fonction du nombre d'articles dans le fichier; cela
nous a permis de calculer l'encombrement mémoire de l'arbre digital au fur et à
mesure des insertions et de savoir la taille maximum du fichier pour laquelle la
structure des données peut résider en mémoire centrale. D'autre part, nous avons
étudié le taux de rempl issage.
Tous les dessins et toutes les courbes de ce travail ont été obtenus à l'aide du
microordinateur LISA de APPLE. Le texte a été aussi écrit à l'aide de l'éditeur de
texte Lisa Write d'APPLE.
,. Poyrcentage et influence des noeuds 'nll'
Les résultats du tableau numéro 1 de l'annexe ont été obtenus en tenant compte
de toute la configuration binaire de la clé. Les observations qui se dégagentsont les .
suivantes:
-le nombre de noeuds 'nil' augmente au fur et à mesure que le nombre de cases
du fichier croit. Cette augmentation des noeuds 'nil' est telle qu'à un moment
donné, leur nombre atteint presque le tiers du nombre de cases du fichier; cela
augmente considérablement et inutilement la taille de la structure des données. En
outre, le taux de remplissage moyen est faible, il oscille entre 50 et 55%. Ce
mauvais
taux est dû aux insertions dans les noeuds 'nil'; en effet, quand il y a
insertion d'un article dans un noeud 'nil', on crée une case dans le fichier pour ce
seul article. L'insertion dans plusieurs noeuds 'nil' détériore le taux de remplissage.
60

---

La solution du paragraphe 3.1 du chapitre précédent nous a permis d'obtenir les
résultats des tableaux numéro 2 li 7 de l'annexe. Nous notons d'une manière
générale que:
-
le nombre de noeuds 'nil' diminue quand la capacité des cases augmente.
Dans le cas des insertions aléatoires, ce nombre n'atteint pas 40 pour des fichiers
ayant plus de 7000 cases.
-
dans le cas des insertions ascendantes, le nombre de noeuds 'nil' est
nettement plus élevé que dans le cas des insertions aléatoires. Cela est dû au fait
que dans les insertions ascendantes, les clés qui se présentent sont triées; par
groupes, elles commencent donc par les mêmes digits. De sorte que beaucoup
d'éclatements donnent lieu il la formation d'un ou de plusieurs noeuds 'nil'. Mais le
nombre reste encore très petit par rapport au nombre de cases du fichier. Le
tableau sUivant résume les résultats des simulations concernant la formation des
noeuds 'niJl.
insertions aléatoi res
insertions ascendantes
capacité
10
20
50
100
10
20
50
100
d'une case
nbre cases
2048 2048 2048 2048 2048 2048 2046 2.041
du fichier
nombre de
10
7
5
3
50
39
24
15
noeuds 'nll'
Finalement, ces chiffres sont très insignifiants; cela confirme les prévisions
établies au paragraphe 3 du chapitre précédent. En d'autres termes, l'application de
notre algorithme de sélection des bits conduit effectivement à un nombre
négligeable de noeuds 'nil'. Nous powons donc dire que la taille de la table des
pointeurs (en nombre d'éléments) est pratiquement égale à la taille du fichier (en
nombre de cases).
61

---

2. Taux de remplissage
Les graphes des figures 9.a à 9.b des'pages 97 à 101 montrent les courbes de
taux de rempl issage tracées à parti r des résultats des simulations pour les
dIfférentes valeurs de b.
Nous dégageons les propriétés générales suivantes:
- le taux de remplissage est instable quand le nombre d'articles dans le fichier
est petit. Nous constatons en effet qu'au début, toutes les courbes sont irégulières;
elles se présentent toutes en dents de scie. Mais au fur et à mesure que le nombre
d'articles augmente, nous constatons que les courbes deviennent beaucoup plus
régulières et stables. A partir de là, elles se répètent égales à elles mêmes sur un
intervalle
régul ier:
elles
sont
donc périodiques.
Fagin(79),
Litwin{79)
et
Régnier(83) montrent que la période observée est log2x où x est le nombre
d'articles dans le fichier.
- en ce qui concerne les courbes obtenues à l'aide d'insertions ascendantes, la
partie non stable est beaucoup moins accentuée et moins longue que dans le cas des
courbes obtenues à l'aide d'insertions aléatoires.
-
la valeur moyenne du taux de remplissage est indépendante de la capacité
d'une case. Elle est de 69% pour les insertions aléatoires et de 66,5% pour les
insertions ascendantes.
-
enfIn, nous observons qu'au fur et à mesure que la capacité des cases
augmente, les graphes présentent des courbures plus accentuées.
La légère différence observée entre le taux de rempl issage obtenu par
insertions aléatoi res et le taux de remplissage obtenu par insertrions en ordre
ascendant, s'explique par le fait suivant: dans l'ordre ascendant, beaucoup de clés
ont leurs prem iers caractères égaux; de sorte qu'elles sont logées dans la même
case jusqu'a ce que celle ci déborde et éclate. A cause du tri, l'éclatement est
légèrement non uniforme en faveur de la case qui éclate. Les nouvelles insertions
sont presque toutes dirigées vers la nouvelle case jusqu'à ce qu'elle soit pleine et
éclate à son tour. Les éclatements sont pratiquement faits de manière cyclique.
Ainsi, on crée progressivement des cases remplies chacune à environ 66%.
62

---

3. Encombrement de la fonction de hachage
La fonction-nous l'avons vu- est représentée par les tables B et T. Nous
~ons suivi l'évolution de ces deux tebles ta trevers les séries d'insertions. Tent
qu'elles sont en mémoire centrale, la recherche d'un article se fait en un accès
disque.
Examinons le nombre d'articles pour lequel la structure des données peut
résider en mémoire pendant l'exploitation du fichier. Nous ferons notre analyse
avec les hypothèses suivantes: nous prendrons b- 100 articles et 68% comme
valeur moyenne du taux de remplissage.
Le nombre x d'articles sera calculé avec la formule x == 0,68bN; N étant le
nombre de cases du fichier.
3.1 Table des bits
Les éléments de la table B sont des bits! Les résultats des simulations en
annexe nous revèlent que pour des cases de 100 erttcles, la titille de B n'atteint pas
1k octet pour un fichier de 250000 articles. Nous powons donc dire que 3..5k octets
suffisent. largement à la table 8 pour un fichier d'un mi Il ion d"articles.
3.2 Table des pointeyrs
Nous venons d'établir au paragraphe 1. 1 de ce chapitre que le nombre
d'éléments de la table des pointeurs est égal au nombre de cases du fichier.
Un élément 'de la table T étant un pointeur, deux octets suffisent donc pour le
représente r.
3.3 Autre facteur
Nous avons vu au paragraphe 7 du chapitre précédent que pour une
implémentation réelle, nous avons besoin de savoir le nombre n d'articles que
contient chaque case du fichier. Nous avions vu qu'il y a deux possibilités de
consigner ce nombre. Nous Itnalysons ces deux possibilités.
3.3.1 Cas oû n est en mémoire centrale
63

---

Une case du ficbier est caractérisée par son adresse -qui est fournie par un
élément de T-, et par son contenu n. Nous avons établi que ce nombre n powait
être représenté sur 1 octet. La case du fichier est donc matérialisée en mémoire
centrale par 3 octets(2 pour l'élément de T et 1 pour n).
Avec un buffer de 16k octets, nous avons la repartition suivante:
- 3,,5k octets pour conserver constamment la table B en mémoi re centrale
pendant l'exploitation du fichier;
.;,. Ir reste 12,5k octets pour la table T et le contenu n de chaque case; ce qui
donne: 12..5k octets/3 octets = 4,167k cases du fichier; ~vec les hypothèses ci
dessus nous obtenons: X = 0,68bN = 0,68*100*4,167*1024 = 281662 articles!
Un buffer de 32k octets nous permettra de gérer deux -fois plus d'articles, c'est
à dire 583324 articles, sans détériorer les performances d'accès.
3.3.2 Cas oû n est sur le disque
Dans ce cas, une case est matérialisée en rnérnolre centrale par son adresse qui
sera représentée sur 2 octets. De même que précédemment, nous obtenons(avec un
buffer de 16k octets):
-3,5k pour B,
-12,5k pour la table T. Ce qui donne: 12,5k octets/2 octets= 6,25k cases du
-fichier. Le nombre d'articles est alors de: X - O,68bN -0,68* 100*6,25* 1024 -
435200 articles.
Un tampon de 32k permettra à notre algorithme de gérer deux fois plus
d'articles, c'est à dire 870400 articles.
Il est à noter que sous les mêmes hypothèses, un buffer de 64k octets permet à
l'algorithme original de gérer 760000 articles( Mekouar et Trie hashing : further
properties and performance).
Quand on sait que les microordinateurs professionnels actuels ont des capacités
mémoire de plus d-un méga octets ( 1M pour LISA d-APPLE et 3M pour IBM-AT),
on est en droit de penser que la table des pointeurs peut résider en mémoire
centrale pour un fichier de plus de 1000000 d-articles! Et ce chiffre dépasse
largement la taille des fichiers des applications usuelles. Toutefois, si la taille du
64

---

fichier avoisinne 107 articles, alors la tai Ile de la table des pointeurs peut devenir
prohibitive. Dans ce cas, d'autres représentations sont ~ rechercher.
4. Graphes de la fonction de hachage
Les courbes des figures 10.a à 11.b représentent la fonction de hachage. Iles ont
été tracées à partir des résultats des simulations (avec n en mémoire).
Ces graphes sont tous des droites d'équation
Y = Ax, où x représente le
nombre d'articles dans le fichier et Y
8 ou T.
B et T varient donc de façon linéaire en fonction du nombre d'articles dans le
fichier.
Les pentes de ces droites dim inuent au fur et à mesure que la capacité des
cases croit. Cela implique une diminution de l'encombre.ment de la fonction de
hachage. Pour avoir donc une fonction de hachage peu encombrante qui puisse être
conservée en mémoire centrale pendant l'exploitation du fichier, il faut choisir des
cases assez grandes (b l 100).
Nous avons résumé les résultats des simulations dans le tableau ci dessus :
insertions aléatoi res
insertions ascendantes
capacité
d'une case
10
20
50
100
10
20
50
100
nombre de
2048
2048
2048
2048
2048
cases du fichier
2048
2048
2048
nombre
d'articles
13712 27618
68803 137423 13889 27406
67616 13829~
taille de
514,25 513,50
512,50 524,25 521,50 517,75
B (en octets)
513
522,25
taille de
T (en octets)
4116
4110
4106
4102
4196
4174
4144
4126
tai Ile total
4,52k
4,51k
4,51k
(en k octets)
4,50k
4,60k
.t1.,58k
4,55k
4,54k
65

---

Ainsi
nous
constatons
que
pour
les
cases
assez
grandes
(b= 100),
l'encombrement de la fonction de hachage n'atteint même pas 5k pour un fichier
eentenent plus de 137000 articles! Ces résultats confirment les analyses que nous
venons de mener.
5. PerformQnces d'accès
Dans la méthode que nous venons d'exposer, les collisions sont résolues en
allouant une nouvelle case au fichier et en partageant les articles entre la nowelle
case et l'ancienne case. Il n' y a donc pas de chaines de débordements. L'algorithme
de recherche fournit l'adresse exacte où doit se trouver l'article. Si l'article n'est
pas à cette adresse, alors on conclut qu'il n'est pas dans le fichier. En particulier
dans le cas où l'adresse est 'nil', on conclut sans lire lefichier que l'article n'est pas
dans le fichier; on évite ainsi un accès inutile.
De ces résultats, nous powons établir que tant que l'arbre digital est en
mémoi re centrale, une recherche nécessitera au plus un accès disque. La recherche
avec succès (cas où l'article est dans le fichier) demendere un accès disque. La
recherche sans succès (cas où l'article n'est pas dans le fichier) requera au plus 1
accès disque, puisque les noeuds 'nil' nous évitent d'accéder au fichier.
Une Insertion normale (quand la case existe et qu'II n'y a pas de collision)
demandera 2 accès disques: une lecture de la case en mémoi re centrale et une
écriture de cette case sur le disque. Une insertion avec éclatement nécessitera 3
accès disques: une lecture et deux écritures. Une insertion dans un noeud 'nil'
demandera un seul accès disque: l'écriture de la case sur le disque.
6. Analyse comparative
Ce paragraphe est consacré à la comparaison de notre méthode avec les autres
méthodes d'adressage en général, et en particul ier avec l'algorithme original du
hachage digital. Les critères de comparaison sont le taux de remplissage, le nombre
d'entrée-sorties pour rechercher un article et l'encombrement de la structure des
données.
66

---

6.1. Comparaison avec le hachage digital original
Les deux algorithmes ont les mêmes performances d'accès et d'occupation
mémoire.
La
différence
réside
dans l'encombrement
de l'arbre
digital
:
l'algorithme original utilise deux pointeurs par noeud (noeud interne et noeud
externe) dans sa représentation standard; en plUS Il représente à chaque noeud, la
valeur et le numéro du digit. Il lui faut donc 6 octets pour représenter un noeud. Par
contre dans notre version, un noeud interne est représenté par un bit dans la table
des bits B et un noeud externe .(qui possède un pointeur) est représenté par un bit
dans la table B et un entier dans la table des pointeurs T; l'entier occupe 2 octets.
Notre version est donc beaucoup plus compacte que la version orlglnele. La raison
est que notre version ne représente pas les digits et leur numéro. De ce fait, pour
les mêmes ressources mémoires, notre algorithme permet de gérer beaucoup plus
d'articles. Les analyses des paragraphes 3.3.1 et 3.3.2 de ce chapitre nous le
conf i rm ent.
L' inconvénient de notre algorithme est le temps d'exécution CPU. Ce temps
est plus grand comparativement au temps CPU de la version originale; cela est dû
aux déplacements dans les tables B et T au cours des insertions et des suppressions.
Mais dans de très nombreuses applications, - surtout dans les applications de
gestion -, l'uti 1isateur a plutôt besoin de place mémoi re. Le temps d'exécution
devient un facteur secondai re par rapport à la place mémoi re. A cet égard, notre
version est un bon choix.
6.2. Comparaison avec les autres algorithmes d'adressAge
•
Partant des résultats qui précèdent, nous powons di re que notre méthode est
plus performante que toute autre méthode d'adressage dont les performances sont
inférieures à celles du hachage digital,
en particulier les arbres_B et leurs
variantes qui constttuent les méthodes les plus utilisées actuellement. Il apparait
dans les résultats ci dessus qu'avec les mêmes ressources de mémoire et sous
l'hypothèse d'un seul accès disque, notre méthode peut gérer un fichier deux à trois
fois plus grand que ne le pourrait une méthode d'arbre_B.
Quand les insertions sont aléatoires, notre méthode fournit le même taux de
remplissage que les autres méthodes d'adressage, en particulier les arbres_B. Mais
67

---

les insertions sont faites en ordre ascendant, le taux de remplissage de notre
algorlthme dépasse de plus de 15% celui d'un arbre_B.
En outre dans notre méthode, les réorganisations sont faites au fur et à mesure
des insertions et des suppressions (caractéristique fondamentale du hachage
dynamique). Emin, la recherche d'un article dans un fichier géré par notre méthode
est 3 à 5 fois plus rapide que la recherche d'un article dans un fichier géré par un
arbre
B.
68

---

Chapitre 4: CONCLUSIONS ET ORIENTATIONS FUTURES
1. Domaines d'aplications
Notre méthode peut être util isée dans les applications où l'on doit stocker une
grande quantité d'Informations sur une mémoire secondaire adressable, en vue
d'effectuer des recherches sélectives très fréquentes. De ce fait, notre méthode
trowe place dans les systèmes de gestion des fichiers intégrés (plus communément
appelé bases de données) où elle peut être uti 1isée comme méthode d'accès.
Le hachage binaire peut être aussi conseillé dans la gestion des tables creuses à
grandes dimensions. Le problème dans la gestion de ces tables est qu'II faut
représenter si possible que les éléments significatifs.
2. Conclusions
Ce travail a été consacré à la proposition et à l'étude d'une nouvelle technique
d'adressage par hachage dynamique. Cette technique est une version de la méthode
intitulée hachage digital proposée par L1twin.
Les performances de notre
algorithme permettent d'avoir une structure des données moins encombrante et de
gérer unfichier de taille beaucoup plus grande.
En général, dans les méthodes d'adressage, les bonnes performances limitent le
nombre d' insertions dans le fichier. Cela est dü au fait que l'encombrement de la
fonction de hachage croit avec le nombre d'articles. Cette lim ite dépend donc de la
méthode et de la taille du buffer disponible.
En pratique, notre méthode permet de gérer -sans détériorer les performances
d'accès - un fichier dont la taille dépasse largement les besoins des applications
usuelles. En effet, les analyses des paragraphes précédents ont montré qu'un buffer
de 16k et des cases de 100 articles permettent de gérer un fichier de plus de .
435000 articles avec une performance d'entrée-sortie d'au plus un accès disque.
Il faut noter par ai lieurs que notre méthode est plus faci le à mettre en oewre
que les techniques d'arbres_B. Enfin, comme très peu de mémoire suffit à notre
algorithme, il peut être implementé sur un micro-ordinateur.
69

---

En particulier, notre méthode est beaucoup plus performante que les arbres_B
qui sont les méthodes les plus sowent utilisées actuellement dans l'industrie.
3. Travaux futurs
Une extension de la méthode aux fichiers multidimensionnels devrait être
oussi envisagée. Un fichier multidimensionnel est un fichier où la clé d'un article
est composée de plusieurs attributs. De ce fait, un article peut être accédé de
plusieurs manières (suivant chaque attribut). Dans un fichier multidimensionnel,
un ârticle est un point de l'espace multidimensionnel; chaque axe(dimension} de
l'espace correspond à un attribut de la clé. Les insertions sont faites de manière
cyclique evee chaque attribut: d'abord le premier attribut (suivant le premier
axe), puis le second (suivant le second axe) .. etc. Au cours de chaque cycle, on
insère les "articles dans le fichier suivant un attribut de la clé jusqu'à ce que le
fichier double de cases. Quand tous les attributs de la clé (tous les axes de
l'espace) ont été utilisés" on recommence le processus.
70

---

Annexes
1. Codification Pascal de l'algorithme de recherche d'une adresse
program adresse;
(* calcul d'adresse *)
const
19b i t = 24;
nB = 100;
nT = 5000;
type
bits - O.. 1;
klebite = packed array[O.. lgbit] of bits;
motbite = packed array[O.. lgbit] of bits;
typel • set of 0.. 35;
typeB = array[O.. nB] of type1; (*type de la table des bits*).
var
S : typeS;
T : packed array[1 .. nT] of integer;
indT, indc, indB, lB : integer;
procedure getdown(cpt:integer; var niveau1:integer);
var ens: integer;
begin
ens :- indB div 36;
while nct (indB mod 36 in B[ens]) do
begin
indB : - indB+l;
cpt.
cpt+1;
ens := indB div 36;
71
___.__..__ ...._..... _._ ....1

---

end;
ni veau' : =cpt;
end;
procedure getup{cpt:integer);
var ens,niveau2:integer;
begin
while cpt <> , do
begin
inde : = indB+1;
cpt : = cpt-li
ens :- indB div 36;
if not(indB mod 36 in B[ens]) then
'1
begin
getdown(cpt,nive~u2};
cpt: =niveau2;
end;
end;
end;
procedure jump;
(* Cette procédure saute des s/arbres et positionne *)
(* l'indice indB a la bonne feuille *)
var cpt, niveau: integer;
begin
cpt : = 0;
getdown(cpt,nive~u);
getup (ni veau);
end;
72

---

function casedeT( indT1 : integer) : integer;
(* Cette fonction donne la case de T qui contient *)
(* l'adresse recherchée *)
var
indexe,ens1 : integer;
begin
indexe : = 0;
while indexe (= indB do
begin
ens1 := indexe div 36;
if «indexe+1) mod 36 in B[ens1]) or (indexe-lB)
then indT1 : = indT1 +1;
indexe := indexe+1;
end;
casedeT : = indT1.:
end;
procedure search (bitcle:klebite; var adrT:integer);
var ens, j:integer;
begin
J : = 0;
if bitele[inde] = 1 then jump;
ens := (indB+1) div 36;
if «indB+1) mod 36 in B[ens]) or (indB=lB)
then adrT := casedeT(j)
else
(*on continue la recherche*)
begin
indB :. indB+1;
inde : = indc+1;
search(bitcle,adrT)
73

---

end;
end;
indB : = O·,
inde : = 0;
(* elebit = clé sous forme de .bits *)
search(clebit, indT);
(*T[indT] est l'adresse recherchée*)
end.
74

---

2.Résultats des simulations
2. 1.INSERTIONS ALEATOIRES
2.1.1 Exécution avec tous les bits de chaque caractère
Tableau n·1
.*. débUl des insertions *.*
capacité d'Une case =
10 articles
1----------------------------------------------------------------------.
1 nbre art .Inbre delnbre dei t.remp 1 taille de
j taille de Tlprofondeurl
[du fichierl cases ln. nils[ actuel IB(en oote'h) 1( éléments ) [de l'arbre 1
[--------------------------------------------------------------------_.
11
2
3
55.00%
1. 00
5
4
12
3
2
40.00%
1. 00
5
4
20
4
2
50.00%
1. 25
6
5
29
5
2
58.00%
1.50
7
6
32
fi
2
53.33%
1. 75
8
6
39
7
2
55.71%
2.00
9
6
52
8
2
65. 00%
2.25
10
7
54
9
2
60.00%
2.50
11
7
60
10
2
60.00%
2.75
12
7
61
11
2
55.45%
3.00
13
e
73
12
2
60.83%
3.25
14
8
81
13
2
~2.31~
3.50
15
8
85
14
3
60.71%
4.00
17
8
103
15 1
3
68.67%
4.25
18
8
105
16 1
3
65.62%
4.50
19
e
112
18 1
3
62.22%
5.00
21
8
121
20 1
3
60.50%
5.50
23
B
145
22 1
3
65.91%
6.00
25
e
152
24 1-
5
63.33%
7.00
29
12
75

---

157
26
7
1 60.38% 1
8.00
33
12
1
164
28
7
1 58.57% 1
8.50
35
12
1
174
30
10
1 58.00% 1
0.75
40
12
1
180
32
9
1 56.25% 1
10.00
41
13
1
211
36
19
1 58.61 % 1
13.50
55
13
1
227
40
19
1 56.75% 1
14.50
59
13
1
243
44
27
1 55.23% 1
17.50
71
13
. 1
264
48
27
1 55.00% 1
18.50
75
13
1
274
52
28
1 52.69% 1
19.75
80
13
1
288 1
56
24
151.43\\ 1
19.75
80
13
1
300 1
60
25
50.00% 1
21.00
85
14
1
308 1
64
25
48.12%
22.00
89
14
1
336 1
72
25
46.61%
24.00
91
14
1
380 1
80
30
47.50%
27.25
110
14
1
462 1
ee
36
52.50%
30.75
124
14
513 1
96
33
53.44%
32.00
129
14
589 1
104
37
56.63%
35.00
141
14
659 1
112
36
58.84%
30.75
148
14
732 1 .
120
38
61. 00%
39.25
158
15
761 1
128
37
59.45%
41. 00
165
15
886 1
144
40
61.53%
45.75
184
15
1016
160
39
63.50%
49.50
199
15
1158
176
39
65.80%
53.50
215
15
.
1244
192
38
64.79%
57.25
230
15
1366
208
38
65.67%
61. 25
246
15
1472
224
38
65.71%
65.25
262
16
1545
240
38
64.37%
69.25
278
16
1699
256
39
.65.94%
73.25
294
16
1934
288
31
61.15%
81.00
325
16
2115
320
37
66.09%
80.00
351
16
2299
352
41
65.31%
98.00
393
20
2565
384
52
66.80%
108.75
436
20
2768
416
53
66.54%
117.00
469
20
3049
448
51
68.00%
124.50
499
20
3219
480
61
61.06%
135.00
541
20
76

---

3410
512
67
1 66.60\\ 1
144.50
579
20
3802
576
105
1 66.01\\ 1
170.00
681
20
4131
640
141
1 64.55~ 1
195.00
791
20
4500
704
160
1 63.92\\ 1
215.75
864
20
4873
768
198
1 63.45\\ 1
241.25
966
21
5160
832
233
62.02\\ 1
266.00
1065
21
5462
896
293
60.96\\ 1
297.00
1189
21
5756
060
336
59. 96~ 1
323.75
1296
21
6042
1024
373
59.00\\ 1
349.00
1397
21
6551
1152
429
56.87\\ 1
395.00
1581
21
7061
1280
465
55.16~ 1
436.00
1745
21
7620
1408
530
54.12\\ 1
484.25
1938
21
8163
1536
552
53.14\\ 1
521.75
2088
21
·It
8754
1664
586
52.61 \\ 1
562.25
2250
21
9379
1792
606
52.34\\ 1
599.25
2398
21
0036
1020
613
51. 75\\
633.00
2533
22
10594
2048
629
5t.73\\
669.00
2677
22
12241
2304
679
53.13\\
745.50
2983
22
13934
2560
710
54.43\\
817.25
3270
22
15974
2816
695
56.73\\
877.50
3511
22
18021
3072
730
58.66\\
950.25
1
3802
23
20025
3328
739
60. 17'.\\
1016.50
1
4067
23
1
21945
3584 1 765
61.23%
1087.00
1
4349
23
1
23842
3840 1
770
62.00\\
1152.25
1
4610
23
1
25740
4096 1
768
62.84'.\\
1215.75
1
4864
23
1
29672
4608 1 757
64.39\\
1341.00
1
5365
1
24
1
33371
5120 1 761
65.19\\
1470.00
1
5881
1
24
1
37181
5632 1 758
66.02%
1597.25
1
6390
1
24
1
40662
6144 1 763
66.18\\
1726.50
1
6907
1
24
1
43900
6656 1 765
65.96%
1855.00
1
7421
1
24
1
u*fin des insertions·"
77

---

2. 1.2 Exécution avec saut des deux premiers bits de chaque caractère
Tableau n02
***début des insertions*··
capacité d'une case =
10 articles
,------------------------------------
1 nbre art.lnbre delnbre dei t.remp] taille de 1 taille deTlprofondeurl
Idu fichierl cases ln. nlls] actuel
18(en octets)/(éléments)lde l'arbre 1
1------------------------------------
~ 1
11 1
2 1
0 1 55.00% 1
0.25
1
2
1
1
1
1
ze 1
3 1
0
1 66.67% 1
0.50
1
3
1
2
1
1
28 1
41
0
1 70.00% 1
0.75
1
4
1
2
1
1
29 1
5 1
0 158.00% 1
1.00
1
5
1
3
1
1
32 1
6 1
0 153.33% 1
1.25
1
6
1
3
1
52 1
7 1
0 1 74.29% 1
1.50
1
7
1
4
1
54 1
8 1
0 1 67.50% 1
1.75
1
8
1 4
1
60 1
9 1
0 166.67% 1
2.00
1
9
1
4
1
61 1
10 1
0
61.00%
2.25
10
1 5
1
73 1
11 1
0
66.36%
2.50
11
1
5
1
76 1
12 1
0
63.33%
2.75
12
1
5
1
85 1
13 1
1
65.38%
3.25
14
5
1
98 1
14 1
1
70.00%
3.50
15
5
1
103 1
15 1
1
68.67%
3.75
16
5
1
105 1
16 1
1
65.62%
4.00
17
5
1
1 12 1
1B 1
1
62.22%
4.50
19
5
1
123 1
20 1
1
61.50%
5.00
21
5
1
149 1
22 1
1
67.73%
5.50
23
5
1
173 1
24 1
1
72.06%
6.00
25
6
1
182 1
26 1
1
70.00%
6.50
27
6
1
188 1
28 1
1
67.14%
7.00
29
6
1
192 1
30 1
2
64.00%
7.75
32
6
1
208 1
32 1
2
65.00%
8.25
34
6
1
78

---

251
36 1
2
69.72% 1
9.25
1
38
6
274
40 1
2
68.50% 1
10.25
1
42
7
301
44 1
2
68.41 % 1
11.25
1
46
7
338
48 1
2
70.42% 1
12.25
1
50
7
365
52 1
2·
70.19% 1
13.25
1
54
7
401
56 1
2
71.61 % 1
14.25
1
58
7
413
60 1
2
68.83% 1
15.25
1
62
7
437
64 1
2
68.28% 1
16.25
1
66
7
493
72 1
2
68.47% 1
18.25
1
74
8
532
80 1
3
66.50% 1
20.50
1
83
8
580
88 1
2
65.91 % 1
22.25
1
90
8
647
96 1
2
1 67.40% 1
24.25
1
98
8
1
711
104 1
2
68.37%
26.25
1
106
8
753
1
.112 1
2
67.23%
28.25
1
114
9
1
838
120 1
2
69.83%
30.25
122
1
9
1
898
128 1
2
70.16%
32.25
1
130
9
1
101 9
1
144 1
2
70.76%
36.25
146
9
1
1
1101
160 1
2
68.81 %
40.25
162
9
1
1
1228
176 1
2
69.77%
44.25
178
10
1315
1
192 1
2
68.49%
48.25
194
10
1
1452
208 1
2
69.81 %
52.25
210
10
1
1532
224 1
2
68.39%
56.25
226
10
1
1659
240 1
2
69.12%
60.25
242
10
1
1771
256
2
69.18%
64.25
258
10
1
2003
288
3
69.55%
72.50
291
10
1
2187 1
320
4
68.34%
80.75
324
11
1
2346 1
352
3
66.65 %
88.50
355
1
11
1
2631 1
384
5
68.52%
97.00
389
1
11
1
2842 1
416
5
68.32%
105.00
421
1
11
1
3096 1
448
6
69. 11 %
113.25
454
1
11
1
3266 1
480
5
68.04%
121.00
485
1
1 1
1
3437 1
512
4
67.13%
128.75
516
1
11
1
3886 1
576
3
67.47%
144.50
579
1
11
1
4455 1
640
3
69.61 %
160.50
643
1
12
1
4796 1
704
4
68.12 %
176.75
708
1
12
79

---

1
5233 1
768 1
8
1 68.14% 1
193.75
1
776
1
12
1
1
5658 1
832 1
7 1 68.00% 1
209.50
1
839
1
12
1
1
6144 1
896 1
9 1 68.57% 1
226.00
1
905
1
12
1
1
6557 1
960 1
7
1 68.30% 1
241.50
1
967
1
13
1
1
6920 1 1024
7
/67.58%1
257.50
1
1031
1
13
1
1
7763 1 1152
12 1 67.39% 1
290.75
1
1164
1
13
1
1
8698 1 1280
9 167.95% 1
322.00
1
1289
1
13
1
1
9513 1 1408
12
67.56%
354.75
1
1420
1
13
1
1
10322 1 1536
13
67.20%
387.00
1
1549
13
1
1
11177
1664
14
67.17%
419.25
1
1678
13
1
1
11975
1792
12
66.82%
450.75
1
1804
13
1
1
12788
1920
15
66.60%
483.50
1
1935
14
1
1
13712
2048
10
66.95%
514.25
1
2058
14
1
1
15491
2304
11
67.24%
578.50
1
2315
14
1
1
17298
2560
13
67.57%
643.00
1
2573
14
1
1
19106
2816
20
67.85%
708.75
/
2836
14
1
1
20635
3072
22
67.17%
773.25
1
3094
15
1
1
22351
3328 1
18
67.16%
836.25
1
3346
15
1
1
24321
3584 1
17
67.86%
900.00
1
3601
15
1
1
25967
3840 1
27
67.62%
966.50
1
3867
15
1
1
27666
4096 1
28
67.54%
1030.75
1
4124
15
1
1 31161
4608 1
31
67.62%
1159.50
1
4639
15
1
1
34625
5120 1
25
67.63%
1286.00
1
5145
15
1
1
38364
·5632 1
31
68.12%
1415.s,o
1
5663
15
1
1
41900
6144 1
29
68.20%
1543.00
1
6173
16
1
1
45371
6656 1
28
68.17%
1670.75
1
6684
16
/
1
48705
7168 1
31
67.95%
1799.50
1
7199
16
1
*** fin des insertions u*
le fichier contient 50000 articles
longueur de B = 14788 bits
longueur de T = 7395 éléments
nombre de noeuds ni Is - 33
nombre de cases du fichier = 7362 cases
80

---

***début des insertions***
capacité d'une case =
50 articles
.------------------------------------------------------------------------_.
Inbre art. Inbre delnbre dei t.remp 1 teille de
1 taille de TI profondeur 1
Idu fichierl cases 1n. nilsl actuel IB(en octets) 1( éléments )Ide l'arbrel
1-------------------------------------------------------------------------
51
2 1
0
51.00t.
0.25
2
82
3 1
0
54.67%
0.50
3
2
127
4 1
a
63.50t.
0.75
4
3
137
5
0
54.80%
1. 00
5
3
191
6
0
1 63.57t.
1. 25
6
3
207
7
0
1 59.14%
1. 50
7
3
269
8
0
1 67.25t.
1. 75
8
4
326
9
0
1 72.44t.
2.00
9
4
353
10
0
1 70.60t.
2.25
10
4
354
11
0
1 64.36%
2.50
11
4
387
12
0
1 64.50t.
2.75
12
4
397
13
0
1 61. 08%
3.00
13
4
419
14
1 59.86%
3.50
15
4
532
15
1
1 70.93%
3.75
16
5
559
16
1
1 69.87t.
4.00
17
5
628
18
1
1 69.18t.
4.50
19
5
642
20
1
1 64.20t.
5.00
21
5
660
22
1
1 60. 00t.
S.50
23
5
112
24
1
1 59.33t.
6.00
25
5
775
26
1
1 59.62%
6.50
21
5
1159
28
1
1 82.19%
7.00
29
6
1189
30
1
1 79.27%
7.50
31
6
81

---

1225
32
1
76.56\\
8.00
33
6
1272
36
2
70.67\\
9.25
38
6
1314
40
2
65.70%
10.25
42
6
1359
44
3
61. 77\\
11.50
47
7
1436
48
3
59.83%
12.50
51
7
1828
52
3
70.31\\
13.50
55
7
2097
~6
'3
74.89\\
14.~0
59
7
2222
60
3
74.07%.
15.50
63
7
.
2251
64
3
70.34\\
16.50
67
7
2449
72
3
68.03%.
18.50
75
8
2713
80
3
67.82%
20.50
83
8
2985
88
3
67.84\\
22.50
91
8
3231
96
3
67.31\\
24.50
99
8
3612
104
3
69.46\\
26.50
107
9
3920
112
3
70. 11\\
28.~0
115
9
4169
120
3
69.48%.
30.50
123
9
4265
128
3
66.64%
32.50
131
9
4828
144
3
67.06\\
36.50
147
9
5240
160
3
1 65.50\\
40.50
163
9
5942
176
3
1 67.52\\
44.~0
179
9
6652
192
3
1 69.29\\ 1
48.50
195
9
7388
20e
3
1 71. 04\\ 1
52.50
211
9
7900
224
3
171.12%[
.56.50
227
10
8286
240
·3
1 69. OS%.
60.50
243
10
8532
256
3
1 66.66\\
64.50
259
10
9529
288
3
1 66.17\\
72.50
291
10
10719
320
5
1 66.99\\
81.00
325
10
11817
352
.5
1 67.14\\
89.00
351
10
12925
384
4
1 67.32\\
96.15
388
10
14113
416
3
1 61.85\\
104.50
419
11
15228
448
3
1 61.98\\
112.50
451
11
16430
480
3 '1 68.46\\
120.50
483
11
11125
512
3
1 66.89\\
128.50
515
11
19240
516
3
1 66.81\\
144.50
519
11
21803
640
3
1 68.13%
160.50
643
12
82

---

24632
704
3
1 69.98% 1
176.50
707
12
26668
768
3
1 69.45% 1
192.50
771
12
28552
832
3
1 68.63% 1
208.50
835
12
30254
896
3
1 67.53% 1
224.50
899
12
31934
960
3
1 66.53% 1
240.50
963
12
34159
1024
4
1 66.72% 1
256.75
1028
12
38161
1152
4
1 66.25% 1
288.75
1156
12
4323Q
12BO
4
1 67.56% 1
320.75
1284
~2
47798
1408
4
1 67.89% 1
352.75
1412
13
52379
1536
4
68.20% 1
384.75
1540
13
57005
1664
4
68.52% 1
416.75
1668
13
61351
1792
4
68.47%
448.75
1796
14
65032
1920
4
67.74%
480.75
1924
14
69903
2048
5
67.19%
513.00
2053
14
77589
2304
4
67.35%
576.75
2308
14
86943
2560
4
67.92%
640.75
2564
14
96114
2816
4
68.26%
704. 75
2820
14
104106
3072
4
67.78%
768.75
3076
14
111520
3328
4
67.02\\
832.75
3332
14
119229
3584
4
66.53%
896.75
~588
15
128358
3840
4
66.85\\
960.75
3844
15
137374
4096
4
1 67.08%
1024.75
4100
15
157482
460S
4
1 68.35%
1152.75
4612
15
175452
5120
4
1 68.54%
1280.75
5124
15
193100
5632
5
1 68.57%
1409.00
5637
15
210145
6144
4
1 68.41%
1536.75
6148
15
225103
6656
8
1 67.64\\
1665.75
6664
15
239501
7168
9
1 00.83%
1794.00
7177
15
*** fin des insertions ***
le fichier contient 240000 articles
longUeur de B = 14390 bits
longueUr de T z 7196 éléments
nombre de noeUds nils = 8
nombre de cases duiichier = 71R8 cases
83

---

Tableau n·4
.*.début des insertions •••
capacité d'une case -
100 articles
I-------------~------------------------
1 nbre ert.lnnre delnere dei t.remp 1 taille de
1 taï Ile de T lprotondeur!
ldu fichierl cases ln. nils 1 actuel IB(en octets)1( éléments )Ide l'arbre]
1------------------------------------_·
101
21
0
1 50.50% 1
0.25
1
2
1
1
170
31
0
1 56.67% 1
0.50
1
3
2
1
242
41
0
1 60.50% 1
0.75
1
4
2
1
305
51
0
161.00% 1
1.00
1
5
3
1
350
61
0
1 58:33% 1
1.25
1
6
3
1
373
7 1
0
1 53.29% 1
1.50
1
7
3
1
618
81
0
1 77.25% 1
1.75
1
8
4
1
637
91
0
170.78% 1
2.00
1
9
4
1
654
10
0
65.40%
2.25
1
10
4
1
666
11
0
60.55%
2.50
1
11
4
1
734
12
0
61. 17%
2.75
1
12
4
1
788
13
1
60.62%
3.25
1
14
4
1
843
14
1
60.21 %
3.50
1
15
4
1
1168
15
1
77.87%
3.75
1
16
5
1
1198
16
1
74.87%
4.00
1
17
1
5
1
1305
18
1
72.50%
4.50
1
19
1
5
1
1326
20
1
66.30%
5.00
1
21
1
5
1
1350
22
1
61.36%
5.50
1
23
1
5
1
1:36 1 1 24
1
56.71 %
6.00
1
25
1
5
1
1485 1
26
1
57.12%
6.50
1
27
1
5
1
2373 1
28
2
84.75%
7.25
1
30
1
6
1
2434 1
30
2
81.13%
7.15
1
32
1
6
1
2482 1
32
2
77.56%
8.25
1
34
1
6
1
2593 1· 36
2
72.03%
9.25
1
38
1
7
1
2659 1
40·
2
66.47%
10.25
1
42
1
7
1
84

---

2712
44 1
2 161.64% 1
11.25
46
7
2785
48 1
2 1 58.02% 1
12.25
50
7
3415
52 1
3 1 65.67% 1
13.50
55
7
4140
56 1
3 1 73.93% 1
14.50
59
7
4348
60 1
3
1 72.47% 1
15.50
63
7
4473
641
3 1 69.89% 1
16.50
67
7
4794
72 1
3 1 66.58% 1
18.50
75
7
5300
BO 1
3 1 66.25%
20.50
83
7
5959
88 1
3 167.72% 1
22.50
91
8
6866
96 1
3 171.52%1
24.50
99
8
7326
104
3
70.44%
26.50
107
8
7839
112
3
69.99%
28.50
115
8
8114
120
3
67.62%
30.50
123
9
8467
128
3
66.15 %
32.50
131
9
9099
144
3
63.19%
36.50
147
9
10505
160
3
65.66%
40.50
163
9
11987
176
4
68. 11 %
44.75
180
9
13179
192
3
68.64%
48.50
195
9
14732
208
3
70.83%
52.50
211
9
15673
224
3
69.97%
56.50
227
9
16525
240
3
68.85%
60.50
243
9
17170
256
3
67.07%
64.50
259
9
18927
288
3
65.72%
72.50
291
10
21131
320
4
66.03%
80.75
1
324
10
24582
352
3
69.84%
88.50
1
355
10
1
26870
384
3
69.97%
96.50
1
387
10
1
26870
384
3
69.97%
96.50
1
387
10
1
29818
416
3
71.68%
104.50
1
419
11
1
31325
448
3
69.92%
112.50
1
451
11
1
32705
480
3
68.14%
120.50
1
483
11
1
34139
512
3
66.68%
128.50
1
515
11
1
38164 1 576
3
66.26%
144.50
1
579
11
1
43205 1
640
3
67.51 %
160.50
1
643
12
1
49776 1
704
3 1 70.70%
176.50
1
707
12
1
55184 1
768
3
1 71.85%
192.50
1
771
L 12
1
85

---

58798 1 832 1
3 1 70.67% 1
208.50
1
835
12
1
61340
896 1
3
1 68.46% 1
224.50
1
899
12
1
54937
960 1
3
1- 67.64% 1
240.50
1
963
12
1
68154
1024 1
3 1'66.56% 1 256.50
1
1027
12
1
75147
1152 1
3 1 65.23% 1
288.50
1
1155
12
1
85551
1280 1
3 1 66.84% 1
320.50
1
1283
13
1
96440
1408 1
3 1 68.49% 1
352.50
1
1411
13
1
105554
1536 1
3 168.73% 1 384.50
1
1539
13
1
114694
16°64 1
3 1 68.93% 1
416.50
1
1667
13
1
122011
1792 1
3 1 68.09% 1
448.50
1
1795
13
1
129513
1920 1
3 1 67.45% 1
480.50
1
1923
13
1
137423
2048 1
3 1 67.10% 1
512.50
1
2051
13
1
153485
2304 1
3
1 66.62% 1
576.50
1
2307
13
1
175860
2560 1
3
1 68.70% 1
640.50
1 2563
14
1
195550
2816 1
3 1 69.44% 1 . 704.50
1
2819
14
1
211396
3072 1
3 168.81% 1
768.50
1
3075
14
1
225760
3328 1
3 1 67~84% 1 832.50
1
3331
14
1
239604
3584 1
3 1 66.85% 1
896.50
1 3587
14
1
.. '" fin des insertions **'"
le fichier contient 250000 articles
longueur de B == 7494 bits
longueur de T == 3748 éléments
nombre de noeuds ni 1 -
3
nombre de cases du fichier == 3745 cases
86

---

2.2 INSERTIONS ASCENPANTES
Tableau nOS
*** début des insertions ***
oapacité d'une case =
10 arhcles
1-----------------------------------------------------------------------.
1nbre art. 1nbre de1nbre de1t. rernp 1t ai11e de 1 taille de Tlprofondeurl
IdU fichierl cases ln. nil s 1 act Uel IB(en octets)l( éléments ) Ide l'arbrel
1-------_·_--------------------------------------------------------------
11
2
5
55.00%
1. 50
7
6
12
3
11
40.00%
3,.25
14
13
14
4
10
35.00%
3.25
14
13
24
5
10
48.00%
3.50
15
14
26
fi
9
43.33%
3.50
15
14
31
7
9
52. B6%
3.15
16
14
45
8
9
56.25%
4.00
11
14
46
ri
9
51. 11 %
4.25
18
14
41
10
9
41.00%
4.50
19
14
63
11
9
51.21%
4.15
20
14
11
12
8
64.11%
4.15
20
14
80
13
1
61. 54%
4.15
20
14
90
14
10
64.29%
5.15
24
14
99
15
10·
66.00%
6.00
25
14
100
16
9
62.50%
6.00
25
14
113
18
Q
62.19%
6.50
27
14
127
20
8
63.50% 1
6.75
28
14
142
22
9
64.55% 1
1.50
31
14
156
24
9
65.00% 1
1.15
32
14
175
26
8
67.31% 1
8.25
34
14
186
28
7
166.43% 1
8.50
35
14
191
30
7
163.67% 1
9.00
37
14
213
32
8
166.56% 1
9.15
40
14
87

---

240
36
8
66.67\\ 1
10.75
1
44
14
1
270
40
7
67.50\\ 1
11.50
1
47
14
1
207
44
7
67.50% 1
12.50
1
51
14
1
318
48
7
66.25\\ 1
13.50
55
1
14
1
351
52
7
67.50\\ 1
14.50
1
59
15
1
361
56
7
64.46\\ 1
15.50
1
63
15
1
398
60
7
66. 3~\\ 1
16.50
1
67
15
1
418
64
7
65.31% 1
17.50
1
71
15
1
477
72
6
66.25\\ 1
19.25
78
15
1
531
80
8
66.37\\ 1
21. 75
88
15
584
88
7
66.36\\ 1
23.50
95
15
639
96
7
66.56% 1
25.50
103
15
706
104
8
67.88\\ 1
27.75
112
15
755
112
6
67.41\\ 1
29.25
118
15
806
120
7
67.17% 1
31.50
127
15
864
128
9
67.50\\ 1
34.00
137
15
1000
144
8
69.44% 1
37.75
152
15
1113
160
6
69.56\\ 1
41. 25
166
15
1214
176
7
68.9S\\
45.50
183
15
1325
192
7
69.01%
49.50
199
15
1454
208
6
69.90%
53.25
214
15
1557
224
7
69.51%
57.50
231
15
1678
240
7
69.92\\
61.50
247
15
1701
256
10
6Q.06%
66.25
266
15
2015
288
14
69.97\\
75.25
302
15
2217
320
14
69.28%
83.25
334
15
2469
352
16
70.14\\
91. 75
·1
368
15
2684
384
14
69.90%
99.25
1
398
15
2910
416
14
69.95%
107.25
1
430
15
3103
448
14
69.26%
115.25
1
462
15
3334
480
16
69.46%
123.75
1
496
15
3547
512
14
69.28%
131. 25
1
526
15
3949
576
16
68.56%
147.75
1
592
15
4348
640
17
67.94%
164.00
1
657
16
4781
704
20
67.01~
180.75
1
724
16
88

---

5226
768
18
68.05%
196.25
786
16
5645
832
19
67.85%
212.50
851
16
6070
B06
24
67.85%
220.75
020
16
6537
960
24
68.09%
245.75
984
16
6982
1024
26
68. 18%
262.25
1050
16
7785
1152
30
67.58%
295.25
1182
16
8664
1280
31
67.69%
327.50
1311
16
0552
1408
35
67.84%
360.50
1443
16
10400
1536
38
67.71%
393.25
1574
16
11284
1664
40
67.81%
425.75
1704
16
12175
1792
42
67.94%
458.25
1834
16
13017
1920
41
67.80'.
490.00
1961
10
13889
2048
50
67.82% 1
524.25
2098
16
15608
2304
53
67.74% 1
589.00
2357
16
17305
2560
60
67.60% 1
654.75
2620
10
19059
2816
68
67.68% 1
720.75
2884
16
20780
3072
67
67.64% 1
784.50
3139
16
22570
3328
79
67.82% 1
851.50
3407
16
24242
3584
82
67.64% \\
916.25
3666
16
25908
3840
83
67.62% 1
980.50
3923
10
27679
4096
89
67.58% 1
1046.00
4185
16
31173
4608
103
67.65% 1
1177.50
4711
16
.*.fin des inseztions*.*
•
89

---

T.bleau n-6
*** début des insertions ***
capacité d'une case =
50 articles
I------------------------~---------------~------------
-- ---- -- -- ---- -----
1 nbre art. 1 nbre de I.nbre de 1t. rernp
1 taille de
1 taille
de Tlprofondeurl
Idu fichierl cases 1n. nil s 1actuel IB(en octets) 1 ( éléments )Ide l'arbrel
1------------------------------------------------------------------------
51
2 1
5
51.00\\
1. 50
7
6
52
3 1
0
34.67%
2. 75
12
11
95
4 1
10
47.50\\
3.25
14
13
105
5 1
11
42.00%
3.75
16
13
108
6 1
10
36.00\\
3.75
16
13
111
7
9
31.71%
3.75
16
1
13
161
8 1
10
40.25%
4.25
18
14
162
9
9
36.00%
4.25
18
14
1
217
10 1
9
43.40%
. 4.50
19
14
2SS
11 1
9
52.36%
4.75
20
14
339
12 1
9
56.50%
5.00
21
14
341
13 1
8
52.46%
5.00
21
14
360
14 1
7
51.43%
5.00
21
14
410
15 1
10
54.67%
e. 00
25
14
436
16
9
54.50%
6.00
25
14
1
515
18 1
9
57.22%
6.50
27
14
548
20 1
8
54.80%
6.75
28
14
627
22 1
9
57.00%
7.50
31
14
002
24 1
8
55.11%
1.15
32
14
715
26 1
6
55.00\\
7.75
32
14
783
28 1
7
55.93%
8.50
35
14
872
30 1
7
58.13%
9.00
37
14
905
32 1
6
56.56%
9.25
38
14
1016
36 1
6
56.44\\
10.25
42
14
1203
40 1
8
1 60. 15%
11.75
48
14
1309
44 1
S
1 50.50%
12.75
52
14
90

---

1
1463
48
8
60.96\\
13.75
56
14
1
1
1568
52
7
60.31\\
14.50
59
14
1
1
1721
56
fi
61.46\\
15.25
62
14
1
1
1875
60
7
62.50\\
16.50
67
14
1
1
2064
64
6
64.50\\
17.25
70
14
1
2325
72
5
64.59\\
19.00
77
14
1
2516
80
8
62.90\\
21. 75
88
14
1
2739
88
6
62.25\\
23.25
94
14
3054
96
5
63.62\\
25.00
101
14
3310
104
7
63.65\\
27.50
111
14
3620
112
fi
64.80%
20.25
118
14
3900
120
5
65.00%
31.00
125
14
4103
128
5
64.11%
33.00
133
14
4643
144
5
64.49%.
37.00
149
14
5229
160
5
65.36\\
41. 00
165
14
5736
176
5
65.18\\
45.00
181
14
6167
192
5
64.24\\
49.00
197
14
6797
208
5
65.36%
53.00
213
14
7832
240
7
65.27%
61.50
247
14
8340
256
8
65.16%
65.75
264
15
9318
288
8
64.71%
73.75
296
15
10525
no
11
65. 79\\
82.50
331
15
11586
352
12
65.83%
90.75
364
15
12660
384
14
65". Q4%
00.25
39B
15
13622
416
12
65.49\\
106.75
428
15
14613
448
10
65.24\\
114.25
458
15
15697
480
12
65.40\\
122.75
492
15
10747 .
512
10
05.42\\
130.25
522
15
18821
576
9
65.35\\
146.00
585
15
20967
640
10
65.52\\
162.25
650
15
23266
704
11
66.10%
178.50
715
15
25235
768
10
1 65.72\\
194.25
778
-1
15
27217
832
10
1 65.43\\
210.25
842
1
15
29285
896
15
1 65.37\\
227.50
911
1
15
31348
060
15
1 65.31%
243.50
075
1
15
91

---

33452
1024
19
65. 34~ 1
260.50
1043
15
1
31114
1152
11
65.48% 1
292.00
1169
15
1
41970
1280
15
65.5B% 1
323.50
1295
15
1
46324
1408
15
65.80% 1
355.50
1423
15
1
50696
1536
19
66.01~ 1
388.50
1555
15
1
54822
1664
18
65. 89~ 1
420.25
1682
15
1
.59388
1792·
19
66.28% 1
452.50
1811
15
1
63482
1020
22
66.13'l 1
485.25
1942
15
1
67616
2048
24
66.03% 1
511.75
2072
15
1
16155
2304
23
66.11%1
581. 50
2321
15
1
84729
2560
24
66.19%1
645.75
2594
15
1
93291
2816
26
66.26% 1
710.25
2842
15
1
"'*"'fin des insertions"'*'"
92

---

2721 1
44
5
61.84% 1
12.00
49
13
2980 1
48
5
62.08% 1
13.00
53
13
3267 1
52
5
62. 83~ 1
14.00
57
13
3502 1
56
6
62. 54~ 1
15.25
62
13
3888 1
60
6
64.80% 1
16.25
66
13
4121 1
64
5
64.39% 1
17.00
69
13
4708 l'
72
5
55.39% 1
19.00
77
13
525Q 1
SO
6
65.74% 1
21.25
86
13
5869
88
6
66.69% 1
23.25
94
13
6222
ge,
9
64.81% 1
26.00
105
13
6958
104
9
65. 94~ 1
28.00
113
13
7508
112
9
67.04% 1
30.00
121
13
7980
120
8
66.50% 1
31. 75
128
13
8557
128
7
66.95% 1
33.50
135
13
9479
144
8
65.83t 1
37.75
152
13
10735
160
7
67.09%
41.50
167
13
11852
176
8
67.34%
45.75
184
13
12743
192
9
66.37%
50.00
201
13
13762
208
9
66.16%
54.00
217
13
14994
224
9
66.94%
58.00
233
13
16018
240
9
66.74%
62.00
249
13
17256
25f.
9
67.41%
66.00
265
13
19262
288
11
1 66.88t
74.50
299
13
21558
320
10
1 67.37t
82.25
330
13
23924
352
14
1 67.97t
91.25
366
13
26101
384
12
1 67.97\\
98.75
396
13
28349
416
12
1 68.15t
106.75
428
13
30578
448
14
1 08.25%
115.25
402
13
32575
480
14
1 67.86\\
12-3.25
494
13
34909
512
12
168.18t
130.75
524
13
39291
576
12
1 tl8.21t.
146.75
588
13
43Q15
640
17
1 68.62t
164.00
657
13
47714
704
18
1 67. 78%
180.25
722
13
51982
768
18
1 67.68\\
196.25
786
13
56342
832
10
1 67.72t
212.50
851
13
94

---

.*. début des insertions *.*
capacité d'une case = 100 articles
,--------~--------------------------------------------------------------
1 nbre art. Inbre delnbre delt.remp
1
taille de
Itaille de TI profondeur 1
Idu fichierl cases 1n. nils 1actuel IB(en octets) 1 (éléments) Ide l'arbrel
1-----------------------------------------------------------------------
1
101 1
2
5
50. 50%.
1
1. 50
7
1
6
1
1
104 1
3
10
1 34.67%.
3.00
13
1
12
1
1
105 1
4
9
1 26.25%.
3.00
13
1
12
1
126
1
1
5
8
1 25.20%
3.00
13
12
1
1
162 1
0
a 1 27.00%
3.25
14
12
1
1
173 1
7
8
1 24.11%
3.50
15
13
1
1
211 1
8
7
1 26.37%
3.50
15
13
1
311 1
9
9
1 34.56%
4.25
18
13
1
350 1
10
8
1 35. DO%.
4.25
18
13
1
441 1
11
7
1 40.64%
4.25
18
13
1
~48
12
8
45.67%.
4. 15
20
13
580
13
7
44.62%
4.15
20
13
662
14
6
41.29%
4.15
20
13
163
15
9
50.87%.
5.75
24
13
806
16
8
50.31%
5.15
24
13
815
18
7
48.61%
6.00
25
13
919
20
7
48.95%.
6.50
27
13
1203
22
7
54. 6e~
7.00
29
13
1252
24
6
52. 11%.
7.25
30
13
1442
26
6
55.46%
7.75
32
13
1562
28
5
55.19%
8.00
33
13
1689
30
8
56.30%.
9.25
38
13
1871
32
6
58.41%
9.25
38
13
2099
36
6
58.31%
10.25
42
13
2514
40
5
52.85%.
11.00
45
13
93

---

60671
896
17
167.71\\ 1
229.00
1
913
1
13
64863
960
17
1 67.57\\ 1
245.00
1
971
1
13
69168
1024
17
1 67.55\\ 1
260.75
1
1041
1
13
78148
1152
15
1 67.84\\ 1
293.50
1
1165
' 1
13
86814
1280
15
1 67.82\\ 1
327.25
1
1295
1
13
95087
1408
16
1 67.53\\ 1
359.00
1
1424
1
13
103965
1536
16
1 67.69\\ 1
391. 75
1
1552
1
13
112484
1664
16
1 67.60\\ 1
424.25
1
1680
1
13
120727
1792
15
1 67.37\\ 1
456.25
1807
1
13
129414
1920
15
1 67.40\\ 1
489.00
'"
1
1935
1
13
138297
2049
15
1 67.53\\ 1
522.25
1
2063
1
13
**. fin des insertions .**
le fichier contient 150000 articles
longUeur de B = 4536 bits
longueur de T = 2269 éléments
nombre de cases du fichier = 2226 cases
•
95

---

3.COURB.fS.
96

---

3.1.Taux de remplissage
97

---

Figures 9a
Insertions
aléatoires
b = 10
taux
• 75 . . . - - - - - - - - - - - - - - - - - - - - - - - - - - ,
.70
.60
• 50 L........:.-_ _----J
-.L~---.....l-----"'"""------'
o
10000
20000
30000
.040000
50000
Nbre d1articles
b = 20
Taux
.90 r-----------------------,.,.....-----,
.. 80
.. 70
.60
.. 50 -----.1.----.1.----.1.----"-----.1.----"---.......
.. O·
15000
30000
.. 5000
50000
75000
90000100000
Nbr. dl ar t Lcles
98

---

b = 50
Taux
,90 . . . - - - - - - - - - - - - - - - - - - - - - - - - - - . . . . ,
,80
,70
,60
, 50 L..-_ _........
.......L
.....I...
.......
"""--
......
~ _
o
15000
30000
45000
60000
75000
90000 100000
nbre d'article
b = 100
taux
,90 .........- - - - - - - - - - - - - - - - - - - - - - - - . . . . ,
,80
,70
,60
,50 L..-_ _........
.......L
.....I...
.......
"""--
......._
......
o
15000
30000
45000
60000
75000
90000 100000
Nbre articles
99

---

Fipures
9b
Insertions
ascendantes
b = 10
Taux
,80 r--------------------------,
CiO
1
1-
,50 -
,40 ...
1
1
15000
30000
-40000
nbre articles
b = 20
taux
,gO
,80 -
, 7 0 - A-
{
.60
,50 l-
,40 -
.30
1
r
1
1
1
0
15000
30000
45000
60000
75000 80000
Nbre articles
100

---

b = 50
Taux
.80 , - - - - - - - - - - - - - - - - - - - - - - - - - - - - ,
• 70 1-
-
.60
.50 1-
.40 f-
• 30 1--
1
" - -
!.1..-
1
" - -
1
1 - -_ _
1
.......1 - -
1
. 1 . . - _ - '
o
15000
30000
45000
60000
15000
~OOOO 100000
Nbre articles
b = 100
taux
. 9 0 . . . . - - - - - - - - - - - - - - - - - - - - - - - ï
.84 1-
,74 -
.64 -_
,54
,34 -
1
t
1
1
1
1
15000
30000
45000
60000
15000
90000 100000
Hbre d'articles
101

---

3.2
FONCTION
DE HACHAGE
102

---

3.2.1
Taille de la table des bits
Figures
10 a
Insertions aléatoires
b = 10
lB
(en octets)
2500 r - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - .
2250
2000
1750
1500
1250
1000
750
500
250
01ol:;;.
.L..-
l - -
.L..-_---J
o
150~0
30000
.. 5000
50000
Hbre articles
b = 100
lB
(en octets)
400 r - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ,
250
.
»>:
,
~-
, /
.
......
..l...
__I_
_.J..
___I.
.......
_ _ '
O ~
o
15000
30000
.. 5000
60000
75000
90000 100000
Nbre ~rtiole~
103

---

b = 20
lB (en 'octets)
2500 r - - - - - - - - - - - - - - - - - - - - - - - - - - ,
2250
2000
1750
1500
1250
1000
750
500
250
01.01::;",_ _----""--_ _---1.
.....1-
-&...
- ' -
..1.-_--'
o
15000
"30000
~5000
60000
75000
00000100000
Nb:re dl articles
b = 50
lB (en octets)
750 , - - - - - - - - - - - - - - - - - - - - - - - - - - - - . ,
SOO
250
Ow::;._ _---l'-_ _--L
--'-
....I..
-'--
..I.-_--'
o
15000
30000
~SOOO
60000
7S000
90000 1000a
104

---

Figures
10 b
Insertions ascendantes
b .. 10
lB (en octets)
1600 r__--------------------------,
1500
1250
1000
750
500
25D
DL..ol:::
J..-
. . 1 - - -_ _- - - I
o
15000
30000
40000
nbre articles
b = 20
lB (en octets)
1600 r----------------------------,
1500
1250
1000
750
500
250
O " - - - - - I - - - - - l . . . . - -
l....-
~
I.._.....J
o
15000
30000
45000
60000
75000
80000
Nbre dl articl.e.s
105

---

b = 50
lB (en octets)
800 r----------------------------,
DOO
400
200
_ ___I.
__l_
...l._
L...__ ___.L.
__L__
___'
O~-
o
15000
30000
45000
&0000
15000
90000
1000
..
Nbxe axt::i
b •
100
lB (en octets)
400 r-----------------------------,
250
oa:::;...-_---I
---'-
- J -
......I...
. . . .
' " " " ' - _ - - '
o
15000
30000
45000
&0000
Hbxe articles
106 .

---

3.2.2
Taille de la table des pointeurs T
Figures 11 a
Insertions aléatoires
b = 10
IT (en éléments)
8000 r-----------------------------.
1000
5000
5000
..000
3000
2000
1000
0
0
10000
20000
3-0000
40000
50000
Hbre arti'e1es
b = 20
IT (en éléments)
8000 ......-----------------------~
1000
5000
5000
.f000
3000
2000
1000
o~_ ____l.
__.1.._--....l---.......Jl...-----..L.---...J-----J
o
15000
30000
45000
60000
75000
goooo 100000
Nbre d oartic~es .
J.07

---

b = SO
IT (en éléments)
.. 000 r----------------------------,
3000
2000
1000
Ol-=:;._ _----I
---L
- - ' -
- ' -
...I.-
..I.-_---I
o
1S000
30000
..sooo
60000
75000
90000 10001
nbre d"artic
b = 100
IT (en éléments)
1600 r----------------------------,
1000
OIolC.._ _..-L.
....L..._ _----IL...-_ _.-L-.
..L..-_ _- - - I . _ - - J
o
15000
30000
..sooo
60000
15000
90000 100011
Nbre articles
108

---

Figures 11 b
Insertions
ascendantes
b = 10
IT (en éléments)
SOOO r - - - - - - - - - - - - - - - - - - - - - - - -.....
4000
300{)
2000
1000
15000
30000
-40000
nbre articles
b = 20
lT (en éléments)
5000 ....-----~--------------------,
4000
. /
/
3000
2000
1000
o "-
.L..-
...L..-
..J....
...L..-
...L..---J
o
15000
30000
45000
60000
15000
80000
Nbre d' ari:iolQ~
109

---

b = SO
IT
4000 , . . . . . . - - - - - - - - - - - - - - - - - - - - - - - ,
3000
2000
1000
Dw:::;.,_ _---I
...-.
....&.
-L..
"""___
__'
~
o
1S000
30000
4S000
60000
75000
90000
1000
nbre d 'articl
b • 100
IT (en éléments)
1DOO r----------------------------,
.1000
_ _-L.
...L..._ _
O ~
_ J ~_ _.....L..
..L..__ __ _ ' _ _ - - - J
o
15000
30000
4S000
60000
75000
00000 10000m
"bre d'articles
110

---

Bjbl jographie
BAYER R., McCREIGHT C. 'Organisation and Maintenance of Large Ordred
Indexes'.
ACTA INFORMATICAi(3) 1912.
BAYER et UNTERAUER 'Prefix B trees'. Acm Transactions on Database
systems. Vo 1.2.
BURKHARD, 'Interpolation based on index maintenance'.
BOUSSARD Jean Claude, MAHL Robert 'Programmation Avan.cée. Algorithme
et Structures de données'.
COMER, 'The Ubiquitous B_Tree'. ACM Computer Surveys, vol. 11, n02, June
19. Pages 121-131.
FAGIN, NIEVEAGELT, PIPPPENGEA, STAONG 78 'Extendible h~hing. A f~t
Acces Method for Dynamic Files'. ACM Data basesyst., 4,3 pages
315-344.
FREDKING E.... 'Trie Memory'; C.A.C.M 3 sept. 1960.
ESEN O., OUKSEL M. 85, 1 Oynamic and order preserving data partitionning for
Database Machines'. Sigmod 85.
GUIHO, 'Organisation des mémoires. Influence d'une structure et étude d'une
optimisation'. Thèse de Doctorat d'Etat, Paris VI, 1973.
GUIHO, 'Etude des collisions dans les méthodes de hash-coding, CRAS 274
(Féb. 14, 1912).
HAMILTON, SORENSON and TREMBLAY 'Survey of D.>mamic hashing
techniques'.
IBM 'OS/VS Virtual Storage Access Method (VSAM): Planning guide'.
IBM 'OS/VS2 Virtual Storage Access Method :Logic'.
111

---

KAMBAYASH 1et KOJIMA 84 'Fi le Organlzatlon Sultable for Large capaclty
main memory'. Submitted to VLDB.
KEEHN 'VSAM Data set Design Parameters'. IBM System Journal, n03, 1974
pages 186-212.
KNUTH 73 'The Art of computer programming'. Vo1.3, Addison-Wesley, 1973.
LARSON 78, '~,mamic hashing'. Bit 18, 1978, pages 184-201.
LARSON 80, 'Linear hashing with Partial Expansions'.
L1TWIN 79 'Hachage Virtuel'. These de Doctorat d'Etat, Paris VI, 1979.
L1TWIN 8 1,82,83 'Trie hashing'. ACM SIGMOD 198 1 co~. Proc. 19-29.
LOMET 'Digital B_trees'. Proceeding Very Large Database Conference,
Cannes, Sept 1981.
MEKOUAR 83 'Etude des performances du hachage digital'. Rapport de DEA.
MULTICS, P li t'R\\tAl~,: INRIA.
Iv
CAME
,)
Ci
' :
J;.
Pascal 680
'c
~ i
ens2 February 83 INR lA.
'-
~
Compilateur .A,
L
~
e, Environnement de Programmation SM9D
"é~__
s~ç
INRIA Février~=I11~~\\
REGNIER, Etudes des performances du hachage digital.
Thèse de 3ème cycle. Université Paris 6.
REGNIER, 'Linear Hashing with Groups of Reorganization, an algorithm for
Files without Hlstory'.
2nd Internotlonal Conference on Databases. Jerusalem, June 22nd-24th, 1982.
SCHOLL 81, 'New File Organisation Based on Dynamic hashing', ACM
Transactions on Database Systems,6, 1, pages 194-211.
112

---

RESUME
Le hachage digital est une nowelle technique de gestion des fichiers
dynamiques introduit par W. L1TWIN. Elle requiert au plus un ICC~ disque pour
conclure qu'un article appartient ou non au fichier; et cela pour des fichiers ayant
plus d'un million d'articles. Le taux de remplissage de la mémoire auxiliaire (le
disque) est de l'ordre de 70%. Un 'fichier géré par cette méthode est totalement
ordonné, propriété que n'essurent.pas les autres méthodes de gestion de fichiers.
Nous étudions ici une version de cet algorithme que nous avons appelée
séquentielle binaire à pointeurs séparés. L'analyse des performances montre
que cette version a l'avantage d'avoir les mêmes propriétés que l'algorithme
originëlJ. En outre, elle permet d'obtenir une structure de données beaucoup plus
compacte powant résider cri mémoire centrale même pour des fichiers de très
grande taille. Du fait que cette version se contente de très peu de mémoi re
centrale, elle peut être implémentée sur la quasi totalité des microordinateurs
protesslcnnels actuels.
Ces propriétés font du hachage digital et de sa version séquentielle binaire -
qui est l'objet de notre thèse-, de bons cheix parm i les nombreuses méthodes du
hachage d;,Inamique connues actuellement.
Mots clés
Arbre-S, arbre digital, hachage, hachage dynamique, article, clé,
noeud, noeud "nil", collision, requête à intervalle, table des
bits, index.
ISBN· 2 • 7261 • 0433 • 9

---