Ali walidIFT 15755 (A-02) Index multi-niveaux dynamiques (les B-arbres et les B-arbres +)

Ali walidIFT 15755 (A-02)

Index multi-niveaux dynamiques

(les B-arbres et les B-arbres+)

.


Plan: Index multi-niveaux dynamiques (les B-arbres et les B-arbres+)...

1- Quelques rappels sur la terminologie :

2- Arbres de recherche :

2- 1- Arbres de recherche binaire:

2- 2- Arbres AVL:

2-3- Le système de pagination d'un arbre :

2- 4- Arbre de recherche n-aire ou arbre 2-3-4 :

2- 5- Équilibrage d’un arbre de recherche n-aire:

3-Utilisation d’un B-arbre :

3-1-Historique :

3-2- Les B-arbres :

3-3- Diviser et promouvoir :

3-4- Les algorithmes de gestion d’un B-arbre :

Structure de nœud

Le principe de la recherche :

- Principe

- Exemple

L'insertion, la subdivision et la promotion :



- Principe

- Exemple

Le cas des suppressions

- Principe

- Exemple

Exemple1 : Gestion des B-arbres

Exemple2 : Gestion des B-arbres

Exercice et solution

3-5-Conclusion sur les B-arbres :

4- Utilisation d’un B-arbre+

5- Variante des B-arbres et B-arbres+

6- Les différentes organisations de type indexé

6 – 1 - Organisation séquentielle indexée

6 – 2 - Organisation indexée

6 – 3 – Les index secondaires



7- Un exemple : les fichiers VSAM d’IBM (Virtual Storage Access Method) :

7 – 1 - Présentation :

7 – 2 - Mise à jour d’un fichier VSAM d’organisation séquentielle indexée

A - Le cas des insertions

B- Le cas des suppressions :


Objectif...

Les index multi-niveaux, sont les index les plus performants parmi les types d’index qu’on a vu précédemment.

Le problème: Les opérations d’insertions et de suppressions des enregistrements sont difficiles à implanter à cause de l’aspect statique de l’index.

La structure d’un index multi-niveaux n’est qu’une structure d’arbre.

On veut profiter de la structure d’arbre pour implanter des index dynamiques qui évoluent dynamiquement avec les fichiers de données.

Objectif: Implanter l’index multi-niveaux dans une autre structure (Structure d’arbre)


Critère de classification des arbres...

Il existe plusieurs types de structures d’arbres pouvant être utilisées dans le cadre d’une application données Quelle structure d’arbre va-t-on choisir?

Critères de comparaison des structures d’arbre:

* Les types d’opérations privilégiés

* Le temps de recherche

* La facilité de maintenance

* L’équilibre

* Le nombre de niveaux minimum

* Ordre maximum (i.e. facteur de connexion)


Classification des arbres...

Structure d’arbre

Binaire

(ordre = 2)2 inconvénients majeurs :Temps de recherche élevé

Maintenance difficileNon adapté pour les opérations d’insertion et de

suppressionMécanisme complexe d’équilibrage

Nombre de niveaux minimumlog2 (N) +1

(N = nombre d’enregistrements à représenter)

n-aires

(ordre = n, avec n > 2)Les avantages :

Arbre binaire généraliséHauteur (i.e. nombre de niveaux moindre)

Très bien adapté aux opérations d’insertion et de suppression

Mécanisme d’équilibrage incorporé et efficaceTemps de recherche plus performant que pour les

arbres binaires


Classification des arbres...

Arbres binaires :

Un arbre dont un nœud n’acceptent pas plus que deux nœuds, un nœud fils à droite et un fols à gauche (à part les feuilles). Dans ce type d’arbres on a :

* Arbre binaire (non équilibré).

* L’arbre AVL (Arbre binaire équilibré).

Arbre n-aires :

Un arbre dont chaque nœud peut accepter de 0 à n nœuds. Dans ce type d’arbres on a :

* L’arbre de recherche (arbre non équilibré).

* Arbre équilibré: B-arbre.

* Le B-arbre*

* Le B-Arbre+

Arbres équilibrés


Rappels terminologiques...

Arbre = { nœud } : Un arbre est un ensemble de nœuds.

Pour chaque nœud (excepté la racine) :

Un nœud père

0 à N nœuds fils

Un nœud terminal (ou feuille) est un nœud n’ayant aucun fils

Un nœud non terminal est dit interne

Le niveau d’un nœud donné est supérieur d’une unité à celui de son nœud père => La racine est toujours de niveau 0.

Le sous-arbre d’un nœud est constitué de ce dernier et de tous ses descendants » ou « Le sous-arbre d’un nœud est constitué de ce dernier et du sous-arbre de chacun de ses fils (définition récursive) »


Exemple de structure d’arbre...

.


Implantation de la structure d’arbre...

La technique usuelle d’implantation d’une structure d’arbre est la suivante :

=> Si la structure d’arbre est utilisée dans un contexte de traitement de fichiers (i.e. ce qui est le cas ici) comme structure d’accès: la partie « information » associé à un nœud contiendra le plus souvent une valeur clé (champ d’indexation)

Champs po eurs Chaque noeud est muni d'au t de po eurs qu il possède de fils

Quelquefois, un po eur père est également stocké dans chaque noeud erne« int »

tan int '

int int

Champs « ormation» Une partie ormation est enfin stockée dans chaque noeudinf inf


Les arbres de rechecherche (Larbre de recherche binaire)...

Ce sont des arbres binaires de la forme < k , A1 , A2 > avec la relation

A1 <= k < A2

Tous les nœuds du sous-arbre gauche ont une valeur inférieure ou égale à la sienne et tous les nœuds du sous-arbre droit ont une valeur supérieure à la valeur du nœud lui-même .

La mise à jour de cet arbre doit maintenir sa propriété. Après n’importe quelle opération de mise à jour, l’arbre doit rester un arbre de recherche binaire.


Exemple d’indexation (arbre de recherche binaire)...

Soit la liste triée suivante :

AX CL DE FB FT HN JD KF NR PA RF SD TK WS YJ

Maintenant, transformons cette liste pour constituer un arbre binaire :

KF

AX

CL

DE

FB

HN

FT JD NR

PA

RF

SD

WS

TK YJ


Exemple d’indexation (arbre de recherche binaire): Implantation...

Il est très facile d'implémenter cette méthode. Il suffit de créer un nœud qui contient à sa droite et à sa gauche les champs d'information.

KF

FBSD


Exemple d’indexation (arbre de recherche binaire):Implantation...

On pourrait utiliser une liste chaînée qui contiendrait cette structure. Chaque nœud pourrait être comme un enregistrement de longueur fixe dans lequel on retrouverait deux champs de chaînage et un champs qui contient l'information.

Les champs de chaînage contiennent des pointeurs qui pointent sur le nœud suivant.

On peut également garder de l'information sur le numéro d'enregistrement du nœud ou sa position dans l'arbre.

num. enregistrement

Clef Fils gauche Fils droit

0 FB 10 8

1 JD

2 RF

3 SD 6 13

4 AX

5 YJ

6 PA 11 2

7 FT

8 HN 7 1

9 KF 0 3

10 CL 4 12

11 NR

12 DE

13 WS 14 5

14 TK


Exemple d’indexation (arbre de recherche binaire): Insertion...Les clés n'ont pas besoin d'être ordonner pour que l'ont puisse y faire une recherche binaire ? Car l'ordonnancement est contenu dans le champs chaînés. Donc, la structure logique de l'arbre est contenue dans les champs chaînés.

Cette propriété nous rend la vie plus facile lors d'une insertion d'une nouvelle clef dans l'arbre, car il nous suffit de bien faire le chaînage et le tour est joué. Par exemple, ajoutons une clef LV.


Exemple d’indexation (arbre de recherche binaire): arbre balancé...

La performance de la recherche dans cet arbre est équivalente à une recherche sur un indexe trié, car ce arbre est dans un état balancé.

On entend par état balancé que la longueur du plus petit parcours vers une feuille n'est pas différent du plus grand parcours vers une feuille d'au moins d'un niveau. Si la différence entre ces deux parcours est plus grande de 1, alors on parlera d'un arbre qui n'est pas dans un état balancé.


Exemple d’indexation (arbre de recherche binaire): arbre balancé... Pour illustrer un arbre qui ne serait pas balancé, ajoutons la suite de clefs suivantes dans l'arbre: NP MB TM LA UF ND TS NK

KF

AX

CL

DE

FB

HN

FT JD NR

PA

RF

SD

WS

TK YJ

LV

LA NP

MB

ND

NK

TM

UF

TS


Inconvénient des arbres non balancés...

Avec l'arbre précédent, nous voyons bien que nous sommes dans un état non balancé. C'est l'effet typique que l'ont retrouve, quand on ajoute des clefs sans avoir de méthode de rangement qui nous garantie de conserver la règle de l'état équilibré de l'arbre.

Avec un arbre non balancé, la performance de recherche se trouve grandement amputée. À la longue nous pourrions avoir que des arbres avec une structure dégénérée. C'est-à-dire une liste chaînée.

Donc, pour remédier à ce problème de dégénérescence, il faut trouver une méthode qui nous permettre de garder notre arbre dans un état d'équilibre.


Les arbres AVL (les arbre de recherche binaire balancés)...

La méthode qui nous permettra d'éviter la dégénérescence de notre arbre quand nous lui ajouterons des nouvelles clefs se nomme les arbres AVL, du nom des deux mathématiciens Russe G. M. Adel'son-Vel'skii et E.M. Landis.

Un arbre AVL n'est rien d'autre qu'un arbre dont la hauteur des branches est équilibrée.

Dans un arbre AVL cette limite maximum est une différence de 1. Ce qui revient à dire que l'on veut que notre arbre soit dans l'état d'équilibre en tout temps.

Quelle que fois dans la littérature on retrouve la notation HB(1) (pour hauteur balancé=1)pour désigner les arbres AVL. Parce que les AVL font partis d'une classe d'arbres encore plus générale que l'on appelle HB(k).


Les arbres AVL: Exemple...

On peut implanter les index en utilisant une structure d’arbre AVL.

Arbres AVL

Non AVL

x

x

x


Le système de pagination d’un arbre...

Le système de pagination a pour but de mettre à profit le fait qu'il faut faire un accès disque d'une manière ou d'un autre. Et tant qu'à faire un accès disque, mieux vaut rapatrier le plus possible d'information en mémoire. C'est ce qu'on appelle la lecture d'une page.

La façon de faire est de diviser l'arbre binaire en plusieurs pages. Alors , chaque page représente un bloc d'informations contiguës sur l'espace disque.


Le système de pagination d’un arbre: Avantages...

Un arbre binaire permet une recherche de log 2 (N+1). Avec le concept de la pagination nous pouvons atteindre log k+1 (N+1). (N = le nombre de clefs, k = le nombre de clefs que contient une page) Voici un exemple numérique pour illustrer la rapidité d'exécution :

log2(134 217 727 + 1) = 27 accès

log 511+1 (134 217 727 + 1) = 3 accès (pour une page à 511 clés)

Comme on peut le constater, il y a une grande amélioration. Il est vrai qu'on rapatrie beaucoup plus d'informations que nécessaire mais on économise sur les accès.

Le nombre de pointeurs doit toujours excéder le nombre de clefs de 1. Cette représentation s'appelle une page. Quelques fois, nous l'appellerons le nœud. Le nombre maximum de pointeurs que peut stocker un nœud est appelé l'ordre de l’arbre. En effet, le concept de pagination ne définit rien d'autre qu'un B-arbre.


Les arbres de recherche n-aire...

Peut être utilisé comme index multi-niveaux dynamique pour l’accès à un fichier de données à partir d’une valeur donnée du champ de recherche.

Les index multi-niveaux présentés dans la séance précédente peuvent être perçus comme une variante d’un arbre de recherche.

Chaque nœud de l’index multi-niveaux possède un nombre de pointeurs et

de valeurs de clé égal au facteur de blocage fb de l’index.


Les arbres de recherche n-aire (structure)...

Un arbre de recherche d’ordre p est un arbre où chaque nœud contient :

* au plus p-1 valeurs de clé

* p pointeurs dans l’ordre :

<P1, K1, P2, K2, ........., Pq-1, Kq-1, Pq>

où :

* p <= q

* chaque Pi est un pointeur sur un nœud fils

* chaque Ki est une valeur de clé

Toutes les valeurs de clé sont supposées uniques (i.e. le champ d’indexation est supposé être une clé primaire).


Les arbres de recherche n-aire (structure)...

.


Les arbres de recherche n-aire (contraintes)...

Un arbre de recherche doit vérifier à tout instant les deux contraintes suivantes :

1- Dans chaque nœud :

K1 < K2 < ...... < K q-1

2- Pour toutes les valeurs X d’un sous-arbre pointé par Pi·

Ki-1<X<Ki , pour 1<i<q·

X<Ki , pour i = 1·

Ki-1<X , pour i=q

Exemple d’arbre de recherche d’ordre 3:


Les arbres de recherche n-aire (le principe de recherche)...

Parcourir l’arbre à l’aide des pointeurs jusqu'à atteindre le bloc du fichier de données contenant l’enregistrement recherché => Le guidage par pointeur dans le parcours de l’arbre permet de restreindre la recherche à chaque niveau à un sous-arbre en ignorant ainsi tous les autres nœuds.

=> Pour rechercher une valeur de clé X, il suffit alors de parcourir l’arbre à l’aide des pointeurs Pi en appliquant les contraintes sur l’arbre n-aire de recherche.

=> Ces deux contraintes doivent être vérifiées à tout instant i.e. après chaque insertion d’une nouvelle valeur de clé.


Les arbres de recherche n-aire (Utilisation comme index)...

On peut utiliser ce type d’arbre comme mécanisme d’accès aux enregistrements d’un fichier (organisation séquentielle ou indexée):

* Valeurs contenues dans chaque nœud de l’arbre = valeurs de l’un des champs des enregistrements du fichier. Ce champ est appelé champ de recherche (analogie avec le champ d’indexation dans un index multi-niveaux).

* Chaque valeur dans l’arbre est associée à un pointeur sur un enregistrement ou un bloc du fichier.

* L’arbre de recherche peut être stocké sur disque en assignant chaque nœud à un bloc disque.

* Lorsqu’un nouvel enregistrement est ajouté dans le fichier de données, l’arbre de recherche doit être mis à jour par l’inclusion :

- de la valeur du champ de recherche de l’enregistrement inséré

- d’un pointeur sur cet enregistrement dans le fichier.


Limites des arbres de recherche n-aire...

Comme dans le cas des arbres binaire non AVL, les algorithmes d’insertion ne garantissent généralement pas l’équilibre de l’arbre (i.e. toutes les feuilles au même niveau).

Il est très important de maintenir l’arbre équilibré.

On va ajouter d’autres contraintes pour s’assurer que l’arbre reste balancé à chaque opération de mise à jour. Un arbre n-aire équilibré n’est que le B-arbre.


Les B-arbres: Présentation...

Un B-arbre: Un arbre de recherche sur lequel sont définies des contraintes additionnelles.

Un B-arbre présente l’avantage de résoudre les deux principaux problèmes posés par les arbres de recherche (i.e. 1. Équilibrage après M.A.J., 2. Gaspillage d’espace dû aux suppressions). Mais les algorithmes d’insertion et de suppression sont plus complexes que pour un arbre de recherche !

Dans un B-arbre, le taux de remplissage de chaque nœud est maintenu entre 50 % et 100 %.

Les pointeurs sur des blocs du fichier de données sont présents aussi bien dans les nœuds internes que dans les feuilles (contrairement aux B-arbres+ qu’on va les voir après avoir les B-arbres).

Les insertions et les suppressions deviennent simples à réaliser sauf dans deux cas particuliers :

* Insertion dans un nœud déjà plein

* Suppression dans un nœud entraînant un taux de remplissage de ce dernier inférieur à 50 %.


Les B-arbres: Présentation formelle...

Un B-arbre d’ordre q, utilisé comme structure d’accès (sur un champ clé) à un fichier, peut être défini comme suit :

1. Chaque nœud interne est de la forme :

<P1,<K1,Pr1>, P2,<K2,Pr2>,......,<Kq-1,Prq-1>,Pq>

où

p <= q

chaque Pi est un « pointeur arbre » (i.e. sur ne nœud du B-arbre)

chaque Pr est un « pointeur donnée » (i.e. sur un bloc du fichier de données contenant l’enregistrement de valeur de champ clé Ki).

2. Dans chaque nœud : K1<K2<...<Kq-1

3. Chaque nœud possède, au plus, p pointeurs arbre


Les B-arbres: Présentation formelle...

4. Chaque nœud, exceptés la racine et les feuilles, possède au moins (p/2) pointeurs arbre et la racine possède au moins deux pointeurs arbre (sauf si elle constitue le seul nœud du B-arbre)

5. Pour toutes les valeurs du champ de recherche dans le sous-arbre pointé par Pi

Ki-1<X<Ki, pour 1<i<q

X<Ki, pour i = 1

Ki-1<X, pour i = q

6. Un nœud possédant q pointeurs arbre (avec q <= p) possède q-1 valeurs de clé (donc q-1 pointeurs donnés)

7. Toutes les feuilles sont au même niveau (arbre équilibre) et elles possèdent la même structure que les nœuds internes excepté que leurs pointeurs arbre pointent sur nil.


Les B-arbres: Exemple de noeud et d’un B-arbre...

Un noeud d’un B-arbre a la forme suivante:

Un exemple de B-arbre d’ordre q = 3 (3 pointeurs et 2 clés) est présenté dans la figure en bas:

Les valeurs de recherche sont uniques (on a supposé en effet que le champ de recherche est une clé primaire du fichier de données).


La clé de recherche...

.Champ de recherche

Champ clé Champ non clé

Pri = Pointeur sur un bloc

du fichier de données

Pri = Pointeur sur un bloc

(ou liste chaînée de blocs) de pointeurs sur enregistrements du fichier de données


Diviser et promouvoir...

Le principe d’exploitation d’un B-arbre (cas des insertions) est le suivant :

* Début : nœud racine (qui est aussi une feuille) de niveau 0

* Lorsque le nœud racine contient q-1 valeurs de clé (i.e. il est plein) et qu’une nouvelle valeur doit être insérée, la racine est éclatée en deux nœuds de niveau 1 (diviser). La valeur médiane est conservée dans la racine et toutes les autres valeurs sont réparties sur les deux nœuds nouvellement créés au niveau 1.

En général, lorsqu’un nœud (non racine) est plein et qu’une nouvelle valeur est à insérer dans le nœud, celui-ci est éclaté en deux nœuds au même niveau.

=>La valeur médiane remonte vers le père muni de son pointeur arbre droit sur le nouveau nœud qui vient d’être créé.

=>Si le nœud père est lui-même plein, il est éclaté de la même façon.

=>Les éclatements peuvent ainsi se propager jusqu’à atteindre la racine (promouvoir).

=>Lorsque c’est le cas, un nouveau niveau est créé.


Diviser et promouvoir : Exemple...

Supposons que les valeurs 8, 5, 1, 7, 3, 12, 9, 6, 20 doivent être insérées (dans cet arbre d’arrivée) dans un B-arbre d’ordre q = 3


Diviser et promouvoir : Exemple...

À l’insertion de la valeur 20 la racine va être éclatée ce qui va donner lieu à un nouveau niveau.


Les algorithmes de gestion d’un B-arbre: La structure du noeud...

classe BTPAGE{

short COMPTE_CLE;

/* Le compteur de clefs. Peut être utile: indique quand le nœud est plein. */

char CLE[MAX_CLES];

/* Le vecteur d'information ou clef. Ici nous avons un caractère pour simplifier. */

short FILS[MAX_CLES+1];

/* Le vecteur qui contiendra les fils pointés */

} PAGE;

La structure d’un noeud B-arbre est la suivante:

Un B-arbre est un ensemble de ces noeuds.


Les algorithmes de gestion d’un B-arbre: La recherche...

L'algorithme de recherche dans un B-arbre est de type récursif. Il recherche un nœud et il cherchera dans ce nœud pour trouver la bonne clef.

Il cherchera successivement la clef dans le niveau plus bas jusqu'à ce qu'il trouve la clef ou jusqu'à ce qu'il ne soit plus capable d'aller plus loin (il sera alors rendu dans une feuille de l'arbre).



L’algorithme de recherche est le suivant:

RECHERCHE (RRN, CL, TROUV_RRN, TROUV_POS)

si RRN == NIL alors /* condition d'arrêt de la récursion */

return NON TROUV

sinon

lire page RRN dans PAGE

regarder à travers la PAGE pour trouver CL

mettre POS égale à la position où KEY apparaît ou devrait apparaître.

si CL est trouvé alors /* RRN contient la clef */

TROUV_RRN := RRN

TROUV_POS := POS

return TROUV

sinon /* le FILS suivant fait référence à un niveau plus bas, dans l'arbre */

return (RECHERCHE(PAGE.FILS[POS], CL, TROUV_RRN, TROUV_POS)

finsi

finsi

fin



L’algorithme de recherche est le suivant:

RECHERCHE (RRN, CL, TROUV_RRN, TROUV_POS)

si RRN == NIL alors /* condition d'arrêt de la récursion */

return NON TROUV

sinon

lire page RRN dans PAGE

regarder à travers la PAGE pour trouver CL

mettre POS égale à la position où KEY apparaît ou devrait apparaître.

si CL est trouvé alors /* RRN contient la clef */

TROUV_RRN := RRN

TROUV_POS := POS

return TROUV

sinon /* le FILS suivant fait référence à un niveau plus bas, dans l'arbre */

return (RECHERCHE(PAGE.FILS[POS], CL, TROUV_RRN, TROUV_POS)

finsi

finsi

fin

Appel recursif


Les algorithmes de gestion d’un B-arbre: La recherche (exemple)...

Prenons le B-arbre suivant:

Nous illustrons deux cas :

* Cas 1: Recherche d'une clef qui n'est pas dans l'arbre: Nous cherchons la clef K dans l'arbre.

On aura un appel de la fonction de recherche avec RRN comme argument. La racine a un RRN = 2. Donc, RRN n'est pas nul, nous pouvons poursuivre l'algorithme. L'étape suivante sera de lire le contenu de la racine pour voir si la clef K est dedans (PAGE.CLE[]). K n'y est pas. Comme K va entre D et N, POS = 1. La prochaine étape sera d'appeler la fonction RECHERCHE (), mais cette fois avec un RRN stocké dans la PAGE.FILS[1]. Donc, RRN = 3.

Dans le prochaine appel, la fonction RECHERCHE () lira le contenu du nœud pour trouver si K est là. K n'y est pas. La fonction RECHERCHE () sera rappelée mais cette fois avec PAGE.FILS[2]; mais comme c'est une feuille, la valeur de retour sera nil pour RRN. Donc, ce dernier appel arrêtera la fonction RECHERCHE () immédiatement et retournera NON TROUV. Ce message sera retourner jusqu'au premier appel.


Les algorithmes de gestion d’un B-arbre: La recherche (exemple)...

* Cas 2: Examinons maintenant le cas où l'on chercherait la clef M. Le début est semblable à l'autre cas, sauf que RECHERCHE () ira dans la position 2 du nœud 3. La fonction assignera la valeur 3 et 2 aux variables TROUV_RRN et TROUV_POS respectivement. Ceci nous indique que nous pouvons trouver M dans le nœud 3. Donc, la fonction RECHERCHE () nous retournera TROUV.


Les algorithmes de gestion d’un B-arbre:L’insertion, diviser et promouvoir...

Il y a deux observations que l'on peut faire sur l'insertion, la subdivision et la promotion.

1) L'algorithme commence par chercher à travers l'arbre jusqu'au niveau des feuilles.

2) Ensuite, l'algorithme trouve le point d'insertion au niveau de la feuille. Le travail d'insertion, de subdivision et de promotion s'effectue de bas en haut.

Ces deux observations nous permettront de construire un algorithme récursif qui s'effectuera en trois étapes:

- Une étape de recherche avec la fonction RECHERCHE () qui prend place avant l'appel récursif.

- Ensuite, l'appel récursif lui même, qui recherchera une clef ou l'endroit où insérer une clef.

- Enfin, le travail d'insertion, de subdivision et de promotion, exécuté après l'appel récursif.


Les algorithmes de gestion d’un B-arbre:L’insertion, algorithme...

Insere (RRN_COURANT, CLE, PROMO_FILS_D, PROMO_CLE)

début

si RRN_COURANT = NIL alors /* nous avons dépassé le niveau des feuilles de l'arbre */

PROMO_CLE := CLE

PROMO_ R_ CHILD := NIL

return PROMOTION /* promouvoir la clef originale et NIL */

sinon

lire la page à l'endroit RRN_COURANT

chercher la CLE dans PAGE

POS := la position où CLE apparaît ou devrait apparaître.

si CLE trouvée alors

donner un message d'erreur qui indique que la clef est dupliquée

return ERREUR

RETURN_VALUE := insere(PAGE.FILS[POS], CLE, P_B_RRN, P_B_CLE)

si RETURN_VALUE == NON PROMOTION ou ERREUR alors

return RETURN_VALUE

Appel recursif


Les algorithmes de gestion d’un B-arbre:L’insertion, algorithme... sinon

si il y a de la place dans PAGE pour P_B_CLE alors

insere P_B_CLE et P_B_RRN dans PAGE

return NON PROMOTION

sinon

subdivise(P_B_CLE, P_B_RRN, PAGE, PROMO_CLE, PROMO_FILS_D,

NOUVELLEPAGE)

écrire PAGE dans fichier à la position RRN_COURANT

écrire NOUVELLEPAGE dans le fichier à la position PRN

PROMO_FILS_D

return PROMOTION

/* promotion de PROMO CLE et PROMO_FILS_D */

fin si

fin si

fin si

fin si

fin

Appel recursif


Les algorithmes de gestion d’un B-arbre:L’insertion, algorithme...

La fonction insert (RRN_COURANT, CLE, PROMO_FILS_D, PROMO_CLE) insère une CLE dans le B-arbre.

L'insertion s'effectue à la page (nœud) où il y a le numéro relatif d'un enregistrement RRN_COURANT.

Si ce nœud n'est pas un nœud de type feuille, la fonction s'appelle récursivement jusqu'à trouver une clef dans un nœud ou jusqu'à ce qu'elle atteigne une feuille. Si l'algorithme trouve une clef, il donnera un message d'erreur et quittera et retournera ERREUR.

S'il y a de l'espace pour insérer une CLE dans la PAGE, alors la CLE sera insérée. Autrement, la PAGE sera subdivisée. Quand il y a une subdivision, la valeur de la clef médiane ira dans PROMO_CLE et la valeur relative du numéro d'enregistrement de la nouvelle page construite ira dans PROMO_FILS_D. De cette façon, l'appel récursif pourra s'exécuter de bas en haut. Si une promotion d'une clef doit arriver, insere() l'indiquera en retournant PROMOTION. Sinon, il retournera NON PROMOTION.


Les algorithmes de gestion d’un B-arbre:La division, algorithme...

subdivise (I_CLE, I_RRN, PAGE, PROMO_CLE, PROMO_FILS_D, NOUVELLEPAGE)

début

Copier toutes les clefs et les pointeurs de la PAGE dans l'espace de travail (page de travail) qui

contiennent une clef supplémentaire et un fils.

Insérer I_CLE et I_RRN à la bonne place dans la page de travail.

Allouer et initialiser une nouvelle page dans le fichier B-arbre pouvant contenir NOUVELLEPAGE.

Affecter PROMO_CLE à la valeur de la clef médiane, laquelle sera promue après la subdivision.

Affecter PROMO_FILS_D à RRN de NOUVELLEPAGE.

Copier les clefs et les pointeurs des fils précédents de PROMO_CLE de la page de travail à la PAGE.

Copier les clefs et les pointeurs des fils (suivants) de PROMO_CLE de la page de travail à la

NOUVELLEPAGE

fin


Les algorithmes de gestion d’un B-arbre:La division, algorithme...

La procédure Subdivise (I_CLE, I_RRN, PA GE, PROMO_CLE, PROMO_FILS_D, NOUVELLEPAGE), est une procédure qui insère I_CLE et I_RRN (ceci cause un débordement), crée une nouvelle page appelée NOUVELLEPAGE, distribue les clefs entre la PAGE originale et la NOUVELLEPAGE. Cette procédure détermine également quelle clef et quel RRN seront promus. La clef promue et le RRN seront retournés via les arguments de PROMO_CLE et POMO_FILS_D.

Nous avons besoin maintenant d'une routine qui intégrera les procédures insère() et subdivise(). La procédure driver ouvrira et créera le fichier B-arbre et identifiera ou créera le nœud racine. Cette procédure lira les clefs stockées dans le B-arbre et appellera insère() pour mettre une clef dans le B-arbre. Par la suite, la procédure driver créera une nouvelle racine quand insère() subdivisera le nœud racine courant.


Les algorithmes de gestion d’un B-arbre:Driver, algorithme...La procédure driver

début

si le fichier B-arbre existe, alors

ouvrir le fichier B-arbre

lire dans ROOT l'en-tête de ce fichier où se trouve le RRN de la racine

sinon

créer un fichier B-arbre

placer la première clef dans la racine

mettre le RRN de la page racine du fichier dans ROOT

demander une clef et la stocker dans la variable CLE

tant qu'il y a des CLE

si (insère(ROOT, CLE, PROMO_FILS_D, PROMO_CLE) == PROMOTION) alors

créer une nouvelle racine avec la clef := PROMO_CLE, fils gauche := ROOT,

et fils droit = PROMO_FILS_D

fin si

affecter ROOT de la valeur du RRN du nouveau nœud racine

demander la prochaine clef et la stoker dans CLE


Les algorithmes de gestion d’un B-arbre:Driver, algorithme... fin tantque

écrire le RRN stocké dans ROOT dans l'en-tête du fichier B-arbre

fermer le fichier B-arbre

fin si

fin


Les algorithmes de gestion d’un B-arbre: La suppression... Lorsque la suppression d’une valeur fait descendre le taux de remplissage d’un nœud en-dessous de sa moitié (50 %), il peut être combiné à ses plus proches voisins.

=> Possibilité de propagation jusqu’à la racine

=> Et par conséquent de diminution du nombre de niveaux

L’analyse et la simulation ont montré qu’après avoir réalisé de nombreuses insertions et suppressions successives et aléatoires sur un B-arbre, les nœuds sont approximativement pleins à 69 % lorsque le nombre de valeurs dans l’arbre se stabilise (Ceci est aussi vrai pour les B-arbres+).

Ce résultat est intéressant puisqu’il veut dire que lorsque le nombre de valeurs se stabilise, l’éclatement et la combinaison de nœuds deviennent rares et les insertions et suppressions beaucoup plus efficaces.

De plus, si le nombre de valeurs croît, le B-arbre peut s’étendre sans problème.

=> Les éclatements de nœuds peuvent alors se produire entraînant des insertions un peu plus longues à effectuer.


La gestion des B-arbres: Exemple...

Soit la figure suivante illustre un B-arbre d'ordre 5 avec 3 niveaux :

Chaque page contient 2, 3 ou 4 éléments, sauf la page racine qui, dans cet exemple, n'en contient qu'un seul. Toutes les pages feuilles sont au niveau 3.

Chaque page est de la forme :

p0 k1d1 p1 k2d2 p2 .... pm-1 kmdm pm (1)

avec pi : pointeurs vers des pages di : valeurs des éléments ki : clés des éléments


La gestion des B-arbres: Exemple (Recherche)...

* Recherche : Soit un élément de clé x, que l'on désire rechercher dans un B-arbre. Supposons qu'une page de cet arbre ait été amenée en mémoire. La recherche de x parmi les valeurs des clés ki peut se faire selonles méthodes classiques (séquentielle, binaire, etc . . .). Si l'on ne trouve pas x parmi les clés de la page en mémoire, on se trouve obligatoirement dans un des trois cas suivants :

1. ki < x < ki+1 pour 0< i <m : x est compris entre les clés ki et ki+1,auquel cas on continue la recherche dans la page indiquée par pi

2. km < x : x est plus grande que toutes les clés de la page, auquel cas on continue la recherche dans la page indiquée par pm

3. x < k1 : x est plus petite que toutes les clés de la page, auquel cas on continue la recherche dans la page indiquée par p0.


La gestion des B-arbres: Exemple (Insertion)...

* Insertion : Supposons que nous ayons le B-arbre de la figure suivante :

et que l'on désire insérer la valeur 12. Cette valeur devrait être insérée dans la page B. On va donc déplacer l'élément charnière (20) de la page parente (A) vers la page adjacentes à la page B et possédant une place libre (page C). La place libérée en page A par le déplacement de l'élément charnière va maintenant accueillir l'élément de la page B qui lui est directement inférieur (18). La page B contient alors une place libre qui peut recevoir la nouvelle valeur à insérer (12).



On aboutit enfin à la structure suivante :



L'insertion d'un nouvel élément dans une feuille pleine avec des pages adjacentes pleines également a des conséquences sur la structure globale, dans la mesure où il faut allouer de nouvelles pages.

Considérons le même B-arbre d'ordre 5 de la figure suivante :



On désire insérer l'élément 22 dans ce B-arbre. L'insertion dans la page C (page devant contenir 22) n'est pas possible, car la page est déjà pleine. On effectue alors les opérations suivantes :

1. on prépare de la place en créant une nouvelle page (D) au même niveau que B et C.

2. on répartit les éléments de la manière suivante :

a. l'élément "milieu" soit 30 (dans notre exemple) est déplacé vers la page parente (A), où il joue le rôle de charnière entre la page C et la page D

b. les éléments plus petits que l'élément milieu (22 et 26) sont placés dans la page C

c. les éléments plus grands que l'élément milieu (35 et 40) sont placés dans la page D.



On aboutit ainsi au B-arbre suivant :

Ce mécanisme préserve toutes les propriétés des B-arbres. En particulier, la division d'une page aboutit à la création de 2 pages contenant exactement n éléments. Il est possible que l'insertion de l'élément "milieu" dans la page parente puisse, à son tour, provoquer un dépassement de capacité (si la page parente était pleine) et nécessiter un autre découpage. Le découpage peut ainsi se propager de niveau en niveau et, éventuellement, atteindre la racine elle-même. C'est d'ailleurs la seule façon, pour un B-arbre, d'augmenter de profondeur (nb. de niveaux). Contrairement aux autres structures arborescentes, un B-arbre croît donc à partir des feuilles, vers sa racine.


La gestion des B-arbres: Exemple (Suppression)...

* Suppression: L'élimination d'un élément d'un B-arbre est simple à première vue, mais un peu plus compliquée quant on l'examine en détail. Comme pour les structures d'arbres, deux cas sont à distinguer :

1. l'élément à éliminer est dans une feuille

2. l'élément à éliminer est dans une page intermédiaire. Il faut alors l'échanger avec un des deux éléments immédiatement adjacents (dans l'ordre des clés selon la relation d'ordre définie sur le B-arbre). Ces deux éléments immédiatement adjacents se trouvent forcément dans des feuilles. Une fois l'échange effectué, l'élément à détruire se trouve donc dans une feuille. On retombe donc sur le cas 1) pour son élimination.

Dans les deux cas, la diminution du nombre d'éléments d'une feuille doit s'accompagner d'une vérification :

si le nombre d'éléments est maintenant inférieur à n, alors le critère de B-arbre n'est pas respecté. Il faut donc rétablir l'équilibre en prenant un autre élément ailleurs.



L'élément à emprunter doit être trouvé dans une des deux pages voisines. Si au moins l'une d'entre elles a plus de n éléments, c'est dans celle là que sera effectué le prélèvement.

Si les deux pages voisines n'ont que le minimum autorisé (50 pourcent), il faut alors fusionner l'une d'elles avec la page fautive en amenant dans la page résultante, l'élément de la page parente qui se trouve entre les deux pages à fusionner.

Le prélèvement d'un élément de la page parente peut provoquer, à son tour, une situation nécessitant une fusion. Ce phénomène peut se propager de niveau en niveau, jusqu'à atteindre la racine qui peut, à son tour, voir son nombre d'éléments tomber à 0, auquel cas elle disparaît, ce qui réduit la profondeur du B-arbre d'un niveau.



Première étape : échange avec l'élément directement inférieur. On obtient alors:

puis, suppression de la valeur 20 dans la feuille :



La feuille doit maintenant être combinée avec une feuille adjacentes. On obtient alors :

Cette fois, c'est la page contenant la valeur 14 qui est trop peu remplie. Il faut donc la regrouper avec la page adjacente (de même niveau) en utilisant la valeur charnière (25) qui se trouve dans la page racine. On obtient alors :


B-arbre: Exercices et solutions...

a) Soit le B-arbre d'ordre 2 suivant, dessinez le B-arbre résultant de l'insertion de la valeur 10 .

a) La page racine étant déjà pleine, l'adjonction de la valeur 10 va nécessiter la scission de cette page en deux et la création d'une page au niveau au-dessus contenant l'élément charnière (qui est 10). Le B-arbre résultant est:



b) Soit le B-arbre d'ordre 2 suivant, dessinez le B-arbre résultant de l'insertion de la valeur 21

b) La page dans laquelle devrait venir la nouvelle valeur (21) est déjà pleine. La page de même niveau qui est à sa gauche peut recevoir un élément supplémentaire. L'élément intermédiaire (20) qui se trouve dans le niveau au dessus est donc déplacé dans la page de gauche et la place ainsi libérée peut être occupée par le plus petit élément de la page excédentaire. Le B-arbre résultant est:



c) Avec le même B-arbre de départ qu'au point b, dessinez le B-arbre résultant de la suppression de la valeur 55.

c) En supprimant la valeur 55, la page en question tombe en dessous du nombre minimum d'éléments. La page d'à côté ayant plus que le minimum d'éléments, on peut lui emprunter un élément (42) qui vient remplacer l'élément intermédiaire (50) qui se trouve dans le niveau au dessus. Cet élément intermédiaire (50) vient alors dans la page dans laquelle il manquait un élément. Le B-arbre résultant est:



d) Soit le B-arbre d'ordre 2 suivant, dessinez le B-arbre résultant de l'insertion de la valeur 23

d) La page dans laquelle devrait venir la nouvelle valeur (23) est déjà pleine. Les deux pages voisines de même niveau sont aussi pleines. Il faut donc scinder la page excédentaire en deux, avec comme élément charnière la valeur 23 qui ira dans la page du niveau au-dessus. Les deux pages résultant de la scission seront connectées à l'élément charnière nouvellement rajouté au niveau au-dessus. Le B-arbre résultant est:



e) Avec le même B-arbre de départ qu'au point d, dessinez le B-arbre résultant de l'insertion de la valeur 4.

e) La page dans laquelle devrait venir la nouvelle valeur (4) est déjà pleine. La page voisine de même niveau est aussi pleine. Il faut donc scinder la page excédentaire en deux, avec comme élément charnière la valeur 4 qui ira dans la page du niveau au-dessus. Les deux pages résultant de la scission seront connectées à l'élément charnière nouvellement rajouté au niveau au-dessus. Le B-arbre résultant est:



f) Avec le même B-arbre de départ qu'au point d, dessinez le B-arbre résultant de la suppression de la valeur 15.

f) Pour supprimer la valeur 15, on va d'abord l'échanger avec la valeur qui se trouve le plus à droite du sous-arbre gauche, en l'occurrence la valeur 7. La valeur 7 remplace donc la valeur 15 dans la page racine et doit être supprimée de la feuille dans laquelle elle se trouvait précédemment. Cette page feuille ayant assez d'éléments, la suppression peut se faire sans autre. Le B-arbre résultant est:


Clacul du nombre de blocs et de niveaux d’un B-arbre...

Supposons que le champ de recherche de l’exemple 3 soit un champ clé non ordonné et que l’on construise un B-arbre sur ce champ.

On suppose également que chaque nœud du B-arbre est plein à 69 %.

En moyenne chaque nœud possédera :

p * 0,69 = 25 * 0,69 = 17

17 pointeurs arbre

16 entrées (i.e. valeurs de clé)

16 pointeurs données

Information à chaque niveau : (*) nb. entrées (niveau n) = nb_pointeurs_arbre (niveau n-1_ * 16

Nœuds Entrées Pointeurs arbre

Racine 1 16 17

Niveau 1 17 272(*) 289

Niveau 2 289 4624 4913

Niveau 3 4913 78 608 83 521


Clacul du nombre de blocs et de niveaux d’un B-arbre...

Pour :

- un bloc de 512 octets

- un pointeur bloc de 6 octets

- un champ de recherche de 9 octets

Un B-arbre possédera en moyenne :

- s’il a 2 niveaux : 4624 + 272 + 16 = 4912 entrées

- s’il a 3 niveaux : 78 608 + 4912 = 83 520 entrées

=> Si un nœud est plein, il contiendra :

- 25 pointeurs arbre

- 24 pointeurs donnée

- 24 valeurs de clé

=> Un B-arbre dont tous les nœuds seraient pleins posséderait :

- s’il a 1 niveau : (25 * 24) + 24 = 624 entrées

- s’il a 2 niveaux : (25 * 25 * 24) + 624 = 15 624 entrées

- s’il a 3 niveaux : (25 * 25 * 25 * 24) + 15 624 = 390 624 entrées

=> À éviter lorsque les insertions et les suppressions se produisent de façon aléatoire.


Conclusion sur les B-arbres...

Le nombre maximum de pointeurs que le nœud peut emmagasiner est appelé l'ordre du B-arbre. Donc, si un B-arbre est d’ordre n, un nœud aura par conséquent n-1 clefs (m). Durant la subdivision d'un nœud (page), les descendants devront être réparti de façon la plus équitable. Conséquemment, chaque nœud (sauf la racine et les feuilles) aura au moins n/2 descendants. Donc, le nombre minimum de descendants sera [m/2]. Et le minimum de clefs par page sera [m/2]-1. Les nœuds qui se retrouvent au plus bas de l'arbre se nomment feuilles.

Définition formelle du B-arbre:

Chaque nœud (page) a un maximum de m descendants;

Chaque nœud (sauf la racine et les feuilles) a au moins [m/2] descendants;

La racine a au minimum deux descendants;

Toutes les feuilles sont sur le même niveau;

Un nœud interne avec k descendants contient k-1 clefs;

Une feuille contient au moins [m/2]-1 clefs et au plus m-1 clefs.


Les b*-arbres...

C'est une B-arbre spécialisé dans lequel chaque nœud doit être rempli au moins 2/3.Le B*-arbre est plus performant qu'un B-arbre pour le stockage des clefs.


Les B-arbres+...

La plupart des implantations d’index multi-niveaux dynamiques utilisent une variante du B-arbre, le B-arbre+.

Le B-arbre Plus (B-arbre+) est sensiblement semblable au B-arbre. La distinction se fait au niveau des feuilles. Dans le B-arbre Plus, on a voulu se doter d'une façon d'accéder aux enregistrements d'une façon séquentielle. Pour réaliser cette contrainte, le dernier niveau (feuilles) a été chaîné. C'est-à-dire que toutes les feuilles sont chaînées entre elles.

Dans un B-arbre, chaque valeur du champ de recherche n’apparaît qu’une fois à un certain niveau avec un pointeur donnée. Dans un B-arbre+, les pointeurs donnée ne sont stockés que dans les feuilles de l’arbre, ce qui fait que la structure des feuilles est différente de celles des nœuds internes. Les feuilles possèdent une entrée pour chaque valeur du champ de recherche ainsi qu’un pointeur donné :

* Sur le bloc du fichier de données contenant l’enregistrement correspondant si le champ de recherche constitue une clé, ou

* Sur un bloc de pointeurs d’enregistrements sinon (création d’un niveau d’indirection)


Les B-arbres+...

Les feuilles d’un B-arbre+ sont généralement chaînées pour permettre un accès séquentiel au fichier. Ces feuilles sont similaires au premier niveau d’un index multi-niveaux statique.

Les nœuds internes correspondent aux autres niveaux de l’index. Certaines valeurs du champ de recherche sont répétées dans les nœuds internes de l’arbre pour faciliter la recherche.

Structure d’un nœud interne d’un B-arbre+ d’ordre p

1. Chaque nœud interne est de la forme :

<P1,K1,P2,K2,......,Pq-1,Kq-1,P>

où : q =<p et chaque Pi est un pointeur arbre

2. Dans chaque nœud interne :

K1<K2<......<Kq-1


Les B-arbres+...

3. Pour toutes les valeurs du champ de recherche X dans le sous-arbre pointé par Pi :

Ki-1<X <=Ki , pour 1<i<q

X <=Ki , pour i =1

Ki-1<X , pour i =q

4. Chaque nœud interne possède au plus p pointeurs arbre

5. Chaque nœud (excepté la racine) possède au moins (p/2) pointeurs arbre. La racine possède au moins deux pointeurs arbre (si ce n’est pas une feuille)

6. Un nœud interne de q pointeurs (q <= p) possède q - 1 valeurs de clé


Structure d’une feuille dans un B-arbre+...

1. Chaque feuille est de la forme :

<<K1,Pr1>,<K2,Pr2>....<Kq-1,Prq-1>,Psuivant>

où : q <= p

chaque Pri est un pointeur donnée

Psuivant pointe sur la feuille suivante de l’arbre

2. Dans chaque feuille : K1<K2<....<Kq-1 , q <= p

3. Chaque Pri est un pointeur donnée qui pointe sur le bloc du fichier de données contenant l’enregistrement de clé Ki (ou sur un bloc de pointeurs sur enregistrements)

4. Chaque feuille possède au moins (p/2) valeurs

5. Toutes les feuilles sont au même niveau (arbre équilibré)



.



Remarque :

Les nœuds internes et les feuilles possèdent le même nombre de pointeurs et de valeurs

Mais : pointeurs arbre dans un cas et pointeurs donnée dans l’autre

Un pointeur Pprécédent pourrait également être rajouté à chaque feuille en permettant ainsi un double chaînage.

De ce qui précède, on peut déduire que le nœud interne d’un B-arbre+ peut contenir plus d’entrées que celui du B-arbre.

Pour une même taille de bloc, l’ordre p d’un B-arbre+ sera supérieur à celui d’un B-arbre.

Diminution du nombre de niveaux et donc du temps de recherche


Calcul de l’ordre d’un B-arbre+...

Supposons que :

Le champ de recherche occupe 9 octets

La taille du bloc est de 512 octets (idem exemple 4)

Un pointeur bloc occupe 6 octets

Chaque nœud interne du B-arbre+ peut posséder :

jusqu’à p pointeurs arbre

et p-1 valeurs de clé

Par conséquent, on doit avoir :

(p * 6) + ((p-1) * 9)) 512

soit (15 * p) 521

Valeur max donc p = 34 (pour un B-arbre)



Remarque :

Le calcul serait identique pour une feuille puisque celle-ci contient le même nombre de pointeurs qu’un nœud interne.

Comme pour l’exemple 4, il aurait fallu déduire de la taille du bloc l’espace nécessaire dans chaque nœud pour les informations nécessaires à l’algorithme d’insertion et l’algorithme de suppression.

Supposons que l’on construise un B-arbre+ sur le champ de recherche de cet exemple.

On suppose que le taux de remplissage de chaque nœud est de 69 %.

Chaque nœud possédera alors en moyenne :

34 * 0,69 soit environ 23 pointeurs et donc

22 valeurs de clé (ou entrées)



D’où les informations suivantes à chaque niveau : (si 4 niveaux)

Nœuds Entrées Pointeurs

Racine : 1 22 23

Niveau 1 : 23 506 529

Niveau 2 : 529 11 638 12 167

Feuille : 12 167 267 674 279 841


Recherche d’une clé dans un B-arbre+...

Algorithme RechercheArbreBPlus:

(*n.ki : ième valeur de clé dans le nœud n *)

(*n.Pi : ième arbre dans le nœud n *)

début

n bloc contenant la racine du B-arbre+ ;

Lire bloc n ;

Tant que (n n’est pas une feuille)

faire

q nombre de pointeurs arbre du noeud n ;

si K n.K1 alors

n n.P1 ;

sinon

si K > n.Kq-1 alors

n n.Pq ;

sinon

chercher une entrée i dans le noeud n telle que


Recherche d’une clé dans un B-arbre+...

n.Ki-1 < K n.Ki ;

n n.Pi ;

fin si

fin si

lire bloc n ;

fin faire

Chercher dans le bloc n l’entrée (Ki,Pri) telle que K=Ki ;

Si trouvé alors

Lire le bloc du fichier de données d’adresse Pri et rechercher l’enregistrement

Sinon

« Enregistrement de clé K inexistant dans le fichier »

Fin si

Fin


Variantes des B-arbres et des B-arbre+...

Dans un B-arbre ou dans un B-arbre+, chaque noeud est, à tout instant, plein au moins à moitié.

=> Contrainte « chaque noeud possède au moins (p/2) entrées »

Si on remplace ce taux de remplissage par une valeur de (2/3) l’arbre est appelé B-arbre*.

En général, certains systèmes permettent à l’usager lui-même de choisir un facteur de remplissage compris entre 0,5 et 1,0.

Pour le cas d’un B-arbre+, certains systèmes permettent même à l’usager de choisir deux facteurs de remplissage :

* l’un pour les noeuds internes

* l’autre pour les feuilles.

À la construction de l’index, chaque noeud est rempli conformément au(x) facteur(s) de remplissage spécifié(s).


Un exemple : les fichiers VSAM d’IBM (Virtual Storage Access Method) :

Objectif :

L'objectif est de pallier aux inconvénients majeurs de ISAM.

Dans VSAM, les enregistrements sont rangés dans des intervalles et dans des zones de contrôle où un espace libre est réservé à l'expansion dynamique du fichier.

=> Aucun chaînage des enregistrements

=> Pas de gaspillage d'espace

=> Indépendance du format de stockage vis-à-vis des caractéristiques

physiques des périphériques (plus grande portabilité)



Stockage des données en VSAM

Les enregistrements logiques sont regroupés en blocs de longueur fixe.

Dans VSAM, un bloc = intervalle de contrôle qui contient des " informations de contrôle " permettant de stocker, de maintenir et d'accéder aux enregistrements dans le bloc.

Chaque intervalle de contrôle contient aussi un espace libre réservé à l'expansion dynamique du fichier.



Eli : Enregistrement logique i

CDEi : Champ de description de l'enregistrement i

CDIC : Champ de description de l'intervalle de contrôle

Espace libre : Pour l'expansion dynamique du fichier

CDEi : Identifie les adresses de début et de fin de l'enregistrement logique i dans le bloc

CDIC : Identifie les adresses de début et de fin de l'intervalle de contrôle ainsi que la taille de l'espace libre dans celui-ci

EL1 EL2 EL3 EL4 Espace libre CDE4

CDE3

CDE2

CDE1

CDIC



Taille de l'intervalle de contrôle :

=>Déterminée par le programmeur ou par défaut par VSAM en fonction :

=>de la taille des enregistrements logiques

=>de la taille du buffer (tampon)

=>de la taille désirée pour l'espace libre

=>des caractéristiques physiques du périphérique de stockage secondaire utilisé

Remarques :

1. Si la taille de l'intervalle de contrôle est déterminée par défaut par VSAM, ces informations doivent être spécifiées par le programmeur.

2. La taille est toujours un multiple de 512 octets.



Zone de contrôle (ZC) :

Pourquoi ? Faciliter le stockage et l'accès.

Une ZC est un groupement d'intervalles de contrôle.

La taille des ZC est déterminée par VSAM en fonction du nombre de ZC initialement requis pour stocker un fichier VSAM.

Comme pour les intervalles de contrôle, chaque ZC contient un espace libre pour faciliter l'expansion dynamique du fichier.

=>Lorsque tous les intervalles de contrôle (bloc) ont été remplis suite à des insertions, un nouvel intervalle de contrôle peut être créé dans la ZC grâce à cet espace libre.



Les trois types de fichiers VSAM

Le format spécifique des intervalles et des zones de contrôle dépend du type d'organisation et d'accès définis par l'utilisateur. VSAM en reconnaît trois :

* Les fichiers d'organisation séquentielle

* Les fichiers d'organisation relative

* Les fichiers d'organisation séquentielle indexée (le seul qui sera étudié ici car largement le plus utilisé)

Le seul qui sera étudié ici car largement le plus utilisé



Les fichiers VSAM d'organisation séquentielle indexée:

Enregistrements insérés et stockés dans les intervalles de contrôle dans l'ordre des valeurs de la clé primaire.

=> Création par VSAM d'un index primaire

Structure d'un index primaire VSAM (arbre)

Index

primaire

Fichier

de

données

... etc

ZC : Zone de contrôle

IC : Intervalle de contrôle



Entrée index =<K(i), P(i)> où :

ou

Nœudterminal

K(i) = valeur maximale de clé primaire stockée dans l'intervalle de contrôle i P(i) = pointeur sur l'intervalle de contrôle i

Nœudnon terminal

K(i) = valeur maximale de clé primaire stockée dans le nœud i de niveau inférieur de l'index P(i) = pointeur sur ce nœud



=> Les index primaires VSAM peuvent être des index multi-niveaux

Pour une efficacité optimale, il doit y avoir d'autant plus de niveaux d'index que le nombre de zones de contrôle est élevé.

Adresse d'un intervalle de contrôle :

* Indépendante des caractéristiques physiques des périphériques de stockage (i.e. cylindre, piste, ...).

* Exprimée en fonction de la position relative de l'intervalle de contrôle considéré par rapport à l'adresse de début du fichier.

=> Méthode d'adressage connue sous le nom de RBA (Relative Byte Address).



Index multi-niveaux dynamique VSAM



Mode opératoire pour l’accès indexé à un enregistrement

(index mono-niveau)

Exemple :recherche de l’enregistrement de valeur de clé 327



Mise à jour d'un fichier VSAM d'organisation séquentielle indexée

Le cas des insertions

Éclatement d'un intervalle de contrôle

* Tous les enregistrements logiques à l'intérieur d'un intervalle de contrôle sont maintenus triés suivant les valeurs de clé primaire.

* À chaque ajout d'un nouvel enregistrement un CDE (champ de description enregistrement) correspondant est créé dans l'intervalle de contrôle considéré.

* Si tous les enregistrements logiques sont de même longueur, un seul CDE est nécessaire par intervalle de contrôle.

* Pour conserver l'ordre des valeurs de clé, certains enregistrements peuvent être déplacés lors d'un ajout d'un nouvel enregistrement



Intervalle de contrôle avant insertion

CDIC = Champ de description de l’intervalle de contrôle

Intervalle de contrôle après insertion de l’enregistrement 350

342 344 357 Espace libre

CDE3

CDE2

CDE1

CDIC

342 344 350 357 Espace libre

CDE4

CDE3

CDE2

CDE1

CDIC



* Et lorsque l'intervalle de contrôle est plein (i.e. plus d'espace libre disponible)

=> Éclatement de l'intervalle de contrôle et répartition des enregistrements.

- L'espace nécessaire est pris dans " l'espace libre " de la zone de contrôle à laquelle appartient l'intervalle de contrôle qui vient d'être éclaté.

- VSAM éclate l'intervalle de contrôle qui est plein en deux intervalles dont chacun contient approximativement la moitié du nombre d'enregistrements de l'intervalle initialement plein.

- Mise à jour en conséquence de la feuille de l'index primaire dont l'un des pointeurs pointait sur l'intervalle de contrôle qui a été éclaté.

=> Opération simple puisque l'index contient déjà une entrée (i.e. pointeur) pour le nouvel intervalle de contrôle issu de l'éclatement (cf. figure page 56).

* La figure suivante illustre l'exemple d'un éclatement d'intervalle de contrôle suite à une insertion.



Zone de contrôle avant éclatement

Feuille de l’index qui pointe sur l’intervalle de contrôle avant son éclatement

# 2

# 1 002 005 007 Espace libre CDE CDE CDE

CDIC

015 016 018 020 CDE CDE CDE CDE

CDIC

# 3 009 012 Espace libre CDE CDE

CDIC

# 4 022 025 028 Espace libre CDE CDE CDE

CDIC

# 5 Espace libre CDIC

007 # 1 012 # 3 020 # 2 028 # 4 FFF # 5



Zone de contrôle après l’ajout de l’enregistrement de valeur de clé 019

Feuille de l’index qui pointe sur l’intervalle de contrôle après son éclatement

# 3

# 1 002 005 007 Espace libre CDE CDE CDE CDIC

015 016 018 Espace libre CDE CDE CDE CDIC

009 012 Espace libre CDE CDE CDIC

# 4 022 025 028 Espace libre CDE CDE CDE CDIC


007# 1 012 # 3 018 # 2 020 # 5 028 # 4

# 2

# 5




Le cas des insertions

Éclatement d'une zone de contrôle

*Et lorsqu'une zone de contrôle ne contient plus d'intervalle de contrôle libre ?

=>Éclatement de la zone de contrôle en deux et répartition des intervalles de contrôle.

*Répartition, comment ?

=>VSAM crée une nouvelle zone de contrôle et y transfère approximativement la moitié du nombre d'intervalles de contrôle initialement contenus dans la zone qui a causé l'éclatement.

*Incidence ?

=>Tous les nœuds de l'index affectés par l'éclatement (feuilles et nœuds non terminaux) sont mis à jour.

*La figure suivante illustre l'éclatement d'une zone de contrôle.



Zone de contrôle avant éclatement (remarquer l’absence d’intervalle de contrôle libre !)

Intervalle de contrôle

Éclatement de la zone de contrôle causé par l’ajout de l’enregistrement de valeur de clé 019


015 016 018 020 CDE CDE CDE CDE CDIC



Intervalle de contrôle



Zone de contrôle d’origine

Nouvelle zone de contrôle


009 012 Espace libre CDE CDE CDE CDIC

Espace libre CDE CDE CDIC

Espace libre CDIC




Espace libre CDIC




Le cas de la suppression

Inversion du processus d'ajout

=> Suppression de l'enregistrement ainsi que du champ de description associé (CDE) dans l'intervalle de contrôle considéré (cf. figure ci-dessous).

Intervalle de contrôle avant suppression

Intervalle de contrôle après suppression de l’enregistrement de valeur de clé 022

Incidence ? => Mise à jour de l'index

017 019 022 025 Espace libre CDE4

CDE3

CDE2

CDE1

CDIC

017 019 025 Espace libre CDE3

CDE2

CDE1

CDIC


Merci...

Merci pour votre attention


.

.

Documents

Ali walidIFT 15755 (A-02) Index multi-niveaux dynamiques (les B-arbres et les B-arbres +)