Gestion de Fichiers

Hachage Extensible

2

Plan du cours d’aujourd’hui Le concept de hachage extensible Transformation des tries en tables Insertions Division de buckets pour accomoder un

débordement

3

Motivation Les arbres B sont des structures de fichiers efficaces par

rapport au nombre de seeks nécessaires pour trouver un enregistrement. De plus, ce sont des structures dynamiques qui s’adaptent très bien aux fichiers dans lesquels de nouvelles données sont ajoutées ou effacées fréquement.

Le hachage, néanmoins, est plus efficace que les arbres B pour des fichiers statiques. En d’autres termes ce sont des structures efficaces mais pas dynamiques.

Est-il possible de créer des structures de fichier basées sur le hachage qui soient aussi dynamiques? OUI !

4

Concept de hachage extensible: les tries

Le hachage extensible est du hachage qui maintient une excellente performance dans des fichiers qui permettent des insertions et effacements.

L’idée principale est de combiner le hachage avec une structure d’arbre appelée un “trie” (prononcer comme “try”) et de comprimer ce trie en une table de référence.

Un trie est un arbre digitale semblable aux arbres digitaux vus dans la méthode d’encodage de de Lempel-Ziv.

5

Concept de hachage extensible: les tries

Un trie est un arbre de recherche dont le facteur de branchement correspond au nombre d’éléments qu’il y a dans l’alphabet en usage. Ce facteur de branchement est appelé la base (“radix”) du trie.

Des exemples dans les transparents qui suivent concretiseront ce concept de trie.

Une capacité importante du trie est que l’on utilise souvent qu’une portion de la clé pour la recherche: une portion plus grande n’est utilisée que si de l’information supplémentaire est nécessaire pour parachever la recherche. Cette capacité dite “use-more-as-we-need-more” est fondamentale pour le hachage extensible.

6

Exemple d’un trie: lettres de l’alphabet

a

b

b

d

n

l

r

d e

r

able

abrahms

adams

anderson

andrews

baird

Un trie avec un radix de 26

7

Exemple d’un trie: nombres décimaux

1

1

3

5

6

3

7

5

26

3

8

1136

1153

1629

3182 7263

7268

7521

Un trie avec un radix de 10

8

Tranformation du trie en table Qu’est ce que le trie a en commun avec le

hachage? On peut utiliser un trie de radix 2 (avec les

valeurs 0 et 1). Les buckets du hachage representent les feuilles de ce trie.

La recherche s’effectuera bit par bit en utilisant la capacité “use-more-as-we-need-more”.

Les clés sont placés dans des buckets. Les clés ayant une adresse de hachage avec un préfixe identique partageront le même bucket.

L’accès aux buckets se fait en utilisant un préfixe de l’adresse de hachage.

9

Tranformation du trie en table Dans l’exemple ci-bas, on suppose que h(clé(A)) = 01, h(clé(B)) = 10, h(clé(C)) = 11 Comme il n’y a pas d’autre enreg. qui a 0 comme

préfixe, nous pouvons utiliser 0 comme adresse au lieu de 01.

1

0

0

1

A

B

C

10

Tranformation du trie en table Problème: 1. Si on représente le trie par un arbre, le nombre de comparaisons augmente plus on decend vers les feuilles de l’arbre. 2. Pire encore, si le trie est trop grand pour tenir en mémoire, on retrouve les problèmes de stockage d’arbres sur disque. L’utilisation du hachage

devient dans ce cas prohibitif. Solution: applatir le trie et le représenter en un

tableau d’enregistrements contigus.

11

Tranformation du trie en table: algorithme

Première étape: étendre le trie à un arbre binaire complet (i.e. don’t les feuilles sont toutes au même niveau).

Deuxième étape: applatir le trie et le représenter en un tableau d’enregistrements contigus.

12

Algorithme: exemple

0

0

1

1

1

0

Un trie complet qui étend celui du transparent de la page 9

A

B

C

13

Algorithme: exemple (suite)

Un tableau correspondant au trie complet du transparent de la page 12.

A

B

C

00

01

1011

14

Recherche d’une clé Calculer l’adresse de hachage de la clé

Vérifier le nombre i de bits utilisés dans la table de hachage (dans l’exemple du transparent 13, c’est 2)

Prendre les i derniers bits de l’adresse de hachage

Utiliser ces i derniers bits comme index de recherche dans la table de hachage pour dénicher le bucket où se trouverait la clé recherchée

15

En quoi cette méthode de hachage est-elle extensible?

Il est important de voir en quoi la méthode de hachage extensible est dynamique et en quoi la table de hachage (“directory”) est extensible.

Deux méchanismes essentielles constituent son dynamisme et son extensibilité: 1. Les insertions peuvent entrainer une division de buckets en deux pour accomoder un surplus d’enregistrements. 2. Les effacements peuvent entrainer des combinaisons de buckets pour accomoder un déficit d’enregistrements.

16

Division de buckets pour accomoder un débordement

L’idée de la solution au problème de débordement est d’augmenter l’espace d’adresses en réponse à un débordement, au lieu de créer de longues séquences d’enregistrements débordants comme c’est le cas avec la méthode des débordements progressifs vue.

2 cas sont possibles: Cas simple: le trie était sous-utilisé et un bucket peut

être divisé en deux nouveaux buckets et les enregistrements sont redistribués selon leurs addresses.

Cas plus complexe: on peut étendre notre préfixe de n a n+1 bits, doublant ainsi le nombre de buckets présents dans notre structure.

17

Débordement: cas simple

A

D

B

C

00

01

11

Table après que l’insertion de D ait causé le débordement du bucket A:

10

18

Débordement: cas complexe

Ce cas est illustré par la Figure 12.6. Supposez que le bucket B déborde aprè ys avoir

inserer D. Nous sommes obligés d ’utiliser une adresse de 3 bits pour diviser les enregistrements dont l’adresse de hachage tombe sur B.

Nous obtenons ainsi 100 comme adresse de B et 101 comme adresse de D. Ceci résulte en un nouveau trie (Fig. 12.6 (a)) qui doit être complété (Fig. 12.6 (b)) avant d ’être enfin transformé en table (Fig. 12.6 (c)).