Les fichiers indexés

(Les B-arbres)

Indexation

Buts:– Stocker de grands fichiers– Implémenter efficacement l’ajout et la

suppression d’éléments.– Permettre la recherche par différents types de

clefs.– Permettre la recherche par intervalle de clefs.

Définitions(1)

Fichier séquentiel: Ordonne les enregistrements de façon chronologique (le premier enregistrement inséré apparaît en premier)– Recherche séquentielle

Fichier indexé: Le fichier est organisé de façon à optimiser les recherches. Des pointeurs indiquent l’emplacement réel des enregistrements.– Peut être organisé sous forme de liste triée, d’arbre,

ou autres.

Définitions(2)

Clef primaire: Un identificateur unique associé à chaque enregistrement.

Clef secondaire: Une clef alternative de recherche. Plusieurs enregistrements peuvent posséder une clef secondaire commune.

Indexation linéaireLe fichier est indexé comme une simple

séquence ordonnée d’éléments de la forme (K,P) où K est la clef primaire et P est un pointeur vers l’enregistrement.

Index linéaire

Enregistrements

Indexation linéaire (2)

Si l’index est trop grand pour être contenu en mémoire, un second niveau d’index peut être utilisé.

Second niveau d’index en mémoire

Index sur disque

Indexation par arbre (1)

L’indexation linéaire n’est pas efficace pour effectuer les opérations d’insertion et de suppression.

L’indexation par arbre peut efficacement supporter toutes les opérations désirées.– Insertion/suppression– Recherche par clefs multiples– Recherche par intervalle de clefs

Indexation par arbre (2)

Afin de minimiser le nombre d’accès disque:– Plusieurs noeuds appartiennent au même bloc– L’arbre doit être balancé.– Chaque chemin doit toucher au plus petit

nombre de blocs possibles.

Arbres 2-3 (1)

Un arbre 2-3 possède les propriéteés suivantes:

1. Un noeud contient 1 ou 2 clefs2. Chaque noeud interne a

1. 2 enfants (s’il contient deux clefs) ou 2. 3 enfants (s’il contient 2 clefs).

3. Toutes les feuilles sont au même niveau dans l’arbre (qui est donc balancé).

La recherche dans un arbre 2-3 ressemble à celle dans un arbre binaire de recherche.

Arbre 2-3 (2)

Contrairement à un arbre binaire de recherche, un arbre 2-3 peut être modifié de façon efficace.

Insérer 14 (1)

Insérer 55

Ajouter 19 (1)

Ajouter 19 (2)

Enlever une valeur

3 cas à considérer:

• feuille contenant 2 éléments

• feuille contenant 1 élément

• nœud interne

B-arbres (1)

Un B-arbre est une généralisation d’un arbre 2-3.

Le B-arbre est maintenant la méthode standard d’organisation de fichiers pour les applications demandant des insertions, suppressions et recherches par intervalle de clefs.

B-arbres (2)

1. Les B-arbres sont toujours balancés2. Les B-arbres conservent les clefs

contenant des valeurs similaires dans un même bloc de façon à minimiser le nombre d’accès disque.

3. Les B-arbres garantissent que tous les noeuds seront remplis à au moins un certain pourcentage de leur capacité. Cela optimise l’espace disque utilisé ainsi que le nombre d’accès disque.

Définition

Un B-arbre d’ordre m possède les propriétés suivantes:

– La racine est soit une feuille ou possède au moins 2 enfants.

– Chaque noeud, excepté la racine et les feuilles, a entre m/2 et m enfants.

– Toutes les feuilles sont au même niveau dans l’arbre.

La taille d’un noeud dans un B-arbre est choisit de façon à correspondre à la taille d’un bloc sur le disque.

– Un noeud peut avoir des centaines d’enfants.

Recherche dans un B-arbre

Généralisation d’une recherche dans un arbre 2-3.

Effectuer une recherche binaire dans l’arbre. Si la clef est trouvée, retourner l’enregistrement. Sinon, retourner une valeur indiquant que la clef n’est pas dans l’arbre.

Insertion

Généralisation de l’insertion dans un arbre 2-3

• Trouver la feuille qui devrait contenir l’élément.• S’il y a de l’espace, insérer l’élément.• Sinon, diviser la feuille en deux• La clef du milieu est promue au parent

B+-arbres

La forme de B-arbre habituellement implémentée.

Les noeuds internes ne contiennent que les clefs afin de guider la recherche.

Les feuilles contiennent les enregistrements ou les pointeurs vers les enregistrements.

Une feuille peut contenir plus ou moins d’information que les noeuds internes.

Les nœuds d’un même niveau sont chaînés.

Exemple

InsertionOn insère 50

Plusieurs autres insertions

On insère 30

Enlever 18

Enlever 12

Enlever 33

Analyse (1)

Les noeuds internes d’un B+-arbres sont toujours au moins à moitier pleins.

Le coût de l’insertion et de la suppression d’un noeud est dans (log n).

– La base du log correspond au nombre moyen d’enfants des nœuds de l’arbre.

– Une base de données typique utilise un nombre moyen d’enfants très grand (plus de 100).