CHAPITRE 2

Plan 1 INTRODUCTION2 RAPPELS SUR LES METHODES CLASSIQUES DE STOCKAGE2.1 Le Fichier comme un  « tas de données »2.2 Le hachage ou adressage associatif2.3 Fichiers indexés3 INDEX EN B-ARBRE3.1 Définitions3.2 Algorithme d’insertion3.3 Algorithme de suppression4 HACHAGE VIRTUEL4.1 Introduction4.2 hachage virtuel HV1

IntroductionNous nous intéressons dans ce chapitre à la couche du SGBD qui accède

à la BD, c’est-à-dire au système de stockage appelé la mémoire relationnelle.

Cette couche présente quatre fonctions principales :

1.Présenter une vision relationnelle des fichiers qui constituent la BD. Nous rappelons qu’un fichier est un ensemble d’enregistrements composés eux-mêmes de champs. En première approximation, une relation peut être vue comme un fichier, et chaque tuple correspond à un enregistrement.

2.Gérer la mémoire centrale (MC) : les relations sont découpées et stockées par page de taille fixe en mémoire secondaire (MS), lesquelles sont amenées en MC à la demande, grâce à des mécanismes de mémoire virtuelle. L’espace de stockage en MS est logiquement divisé en segments. Un segment est un espace virtuel de stockage qui se compose physiquement de plusieurs pages. Nous rappelons que la page est l’unité de transfert entre MC et MS. Un fichier est stocké dans un seul segment et peut s’étendre donc, sur plusieurs pages.

3.Gérer les différentes relations de la BD, c’est-à-dire les relations de base, les index appelés encore relations inverses, les vues, les différentes relations catalogues permettant de les décrire.

Usager 1 Usager nProg. en PL/1 ou Cobol

Langage SQL

RDS : Relationnel Data System•Gestion de catalogues•Optimisation de requêtes•Mécanismes d’autorisation•Contraintes d’intégrité

DBSS : Data Base Storage System•Gestion espace physique•Gestion des index•Gestion des transactions•Accès concurrents•Reprise après pannes

BD

Méta Base(Description relations de base et relations systèmes

4. Etablir des méthodes d’accès : nous distinguons les méthodes classiques (les méthodes indexées, le hachage etc.) et des méthodes plus particulières à savoir le hachage virtuel et les arbres balancés B-arbres.

Les opérations que nous pouvons effectuer sur le fichier sont :•Insérer un enregistrement•Supprimer un enregistrement•Modifier un enregistrement.

rappels sur les méthodes classiques de stockage

1.Le fichier comme un « tas de données »

Dans cette technique, les enregistrements sont placés à la queue leu leu dans des pages successives. Un enregistrement n’est pas à cheval sur deux pages. Le seul accès aux données dans le cas de la recherche d’un enregistrement est un balayage séquentiel des tuples. Cette opération est donc très coûteuse.

L’insertion d’un nouvel enregistrement s’effectue dans la dernière page. Si cette dernière est saturée, alors une nouvelle page est allouée et l’enregistrement est inséré.

La suppression est assurée logiquement grâce à un indicateur de suppression. Cette organisation est généralement implémentée par défaut dans les SGBD.

2. LE HACHAGE OU ADRESSAGE ASSOCIATIF

Principe : disposer d’une fonction de hachage h(c ) qui permet de calculer un numéro de bloc ou paquet, contenant un ensemble de pages, à partir d’une clé. La recherche de l’enregistrement s’effectue ensuite séquentiellement dans le bloc.

•.

H(c)

P4 P5

P6 P7 P8

Table des blocs

P1 P2 P3Exemple de fichier

12...

n

Explication : La table des blocs va contenir n+1 pointeurs vers n+1 blocs. Chaque pointeur est l’adresse de la première page du bloc. Un bloc peut contenir une à plusieurs pages chaînées entre elles.

La fonction de hachage permet de retrouver à partir de la clé le numéro du bloc qui va contenir l’enregistrement.

Remarque : la table des blocs peut être résidente en MC si elle est petite. Dans le cas contraire (définie sur plusieurs pages), il faudra la ramener de la MS par partie (par page) en appliquant la fonction de hachage.

Algorithme de recherche entrée : valeur de clé c•Calcul h ( c ) : numéro de bloc•Consultation de la table des blocs : récupération de la première page du bloc•Recherche dans cette page l’enregistrement ayant pour clé c.Algorithme de modification :•rechercher l’enregistrement à l’aide de l’algorithme précédent•réaliser la modificationAlgorithme d’insertion :•rechercher si le nouvel enregistrement n’existe pas.•Si non : si le bloc n’est pas saturé alors insérer le nouvel enregistrement, sinon, allouer une nouvelle page, insérer le nouvel enregistrement et chaîner la nouvelle page aux autres. *Le bloc est saturé signifie qu’il va y avoir débordement. C’est la gestion des débordements qui va dégrader les performances dans les techniques de hachage.Algorithme de suppression :•rechercher l’enregistrement à supprimer et•soit libérer la place qu’occupait cet enregistrement en mettant à jour le chaînage,•soit mettre un indicateur de suppression dans l’en-tête de l’enregistrement à supprimer.

3. Fichiers indexés

Principe : un fichier index contient un ensemble de couples (c,p) où c est la clé du premier enregistrement de la page p.

Index dense : il contient toutes les clés du fichierIndex non dense : on crée des enregistrements index pour certains

enregistrements du fichier : dans ce cas le fichier est trié et divisé en blocs. A chaque bloc lui est associée une entrée dans l’index.

(c,p) = < plus grande clé du bloc, adresse relative du bloc>

ExempleSoit le fichier suivant :

Adresses de blocs

Index non dense

18101213

202130

Bloc1

Bloc2

@1@2@3@4@5@6@7@8

Index dense

Clés

1 8 10 12 13 20 21 30 @1 @2 @3 @4 @5 @6 @7 @8

12 30

@01 @02

1.Algorithme de recherche : •accès à l’index,•recherche dans l’index de la clé d’enregistrement désiré,•récupération dans l’index de l’adresse relative de l’enregistrement ( si index dense), ou de l’adresse relative du bloc qui le contient (si index non dense),•Conversion de l’adresse relative en adresse réelle,•Accès à l’enregistrement ou au bloc,•Transfert de l’enregistrement dans la zone du programme utilisateur.

2. Algorithme d’insertion :•accès à l’index,détermination de l’emplacement de la page qui doit contenir l’enregistrement, puis détermination de la place de l’enregistrement dans la page.•Si la place existe (page non saturée), alors insérer l’enregistrement en déplaçant les autres si nécessaire.•Si la page est pleine, il existe différentes stratégies, entre autres, aller à la page suivante ou allouer une nouvelle page, tout en mettant à jour l’index.

3. Algorithme de suppression :•appliquer l’algorithme de recherche pour trouver l’enregistrement,•soit supprimer réellement l’enregistrement en mettant à jour l’index,•soit faire une suppression logique.•Cas particuliers : si l’enregistrement à supprimer est le premier de l’index, alors une modification de l’index est nécessaire. Lorsqu’une page devient complètement vide, il faut la rendre au système et mettre à jour l’index.

4. Algorithme de modification :•appliquer l’algorithme de recherche pour trouver l’enregistrement à modifier,•réaliser la modification.•Cas particulier : si la modification porte sur la clé, alors la traiter comme une suppression, suivie d’une insertion.

Un index étant lui-même un fichier, il n’y a aucune raison, si celui-ci est volumineux, de définir un autre niveau d’index et ainsi de suite : nous obtenons alors un index hiérarchisé à plusieurs niveaux ( exemple la méthode séquentielle indexée ISAM dans laquelle il pouvait y avoir deux ou trois niveaux d’index : index de cylindres, index de pistes, et éventuellement index maitre ).

4. Index en b-Arbre

Les fichiers séquentiels indexés ont pour désavantage de diminuer leurs performances lorsque leur taille grandit. Souvent dans de telles organisations la réorganisation était nécessaire de manière assez fréquente (pour récupérer les places libérées, pour allouer de nouvelles places etc…). Une technique efficace dans le cas de nouvelle insertion ou suppression existe et est largement appliquée dans le cas des BD, il s'agit des index en B-arbre ou encore appelé arbre balancé qui sont des cas particuliers d’index hiérarchisé à plusieurs niveaux.

Un B-arbre est un arbre équilibré dans lequel les chemins qui conduisent de la racine à une feuille quelconque sont tous de même longueur.

Définition : Soient d et p des nombres entiers positifs : un B-arbre d’ordre d (nombre de

descendants directs d’un nœud interne) et de profondeur p est défini comme une arborescence ayant les propriétés suivantes :

•Chaque nœud a au plus d fils, c’est-à-dire d pointeurs.•Chaque nœud excepté la racine et les feuilles a au moins [d/2] fils (plus petit

entier non inférieur à d/2, ou encore l’arrondi supérieur de d/2).•La racine a au moins 2 fils.•Toutes les feuilles apparaissent au même niveau : (p),•Un nœud ayant k fils (k<= d) c’est-à-dire k pointeurs, contient k-1 clés.•Les données (tuples) sont rangées dans les feuilles ou nœuds terminaux. Les

nœuds non terminaux ne contiennent que des clés et des pointeurs vers d’autres nœuds de l’arborescence.

Ainsi un B-arbre a deux composantes :Un B-index constitué par l’ensemble des nœuds non feuilles appelé le B+ arbre Une relation de base représentée par les feuilles de l’arborescence.

Les types d’accès fournis par un B-index

Nous pouvons avoir deux types d’index :

Index principal : l’ordre physique coïncide avec l’ordre logique. Il est construit au chargement initial de la relation et est défini sur une clé.

Index secondaire : ordre physique est différent de l’ordre logique dans la plupart des cas et peut être défini sur des attributs non clés

Exemple :

Fichier

IndexP1

1114 2212

1100 2018 2100 2300

1001 1010 --

1100 1112 ---- 2018 2019 ---

2100 2200 - 2300 2308 2360

2212 2220 ---

P2 P3 P4

P5 P7 P9

P6 P8 P10

P11

D = 3P = 3

1114 2006 2007

*Par souci de clarté, seul le champ clé est représenté dans les pages du fichier (pages P5 à P11).

Algorithme de recherche : soit la recherche d’un tuple de clé c•lire la racine et rechercher quelle valeur de clé recouvre la valeur c.•lire la valeur de pointeur associé.•Aller à la page pointée par le pointeur sélectionné.•Rechercher quelle valeur de clé recouvre c, lire la valeur de pointeur

associé et aller à la page pointée.• Répéter l’opération précédente jusqu’à trouver la page feuille contenant la

clé. Exemple : le chemin d’accès nécessaire à la recherche du tuple de clé

2200 est le suivant :P1 : 1114<2200<2212 : aller à la page P3 ;P3 : 2200>2100 : aller à la page P9 ;P9 : recherche séquentielle du tuple de clé 2200.

Algorithme d’insertion : soit à insérer un tuple de clé crechercher la page feuille du B-arbre qui doit contenir ce tuple en appliquant l’algorithme de recherche : soit Pi cette page ; deux possibilités.1. Si Pi est non saturée alors insertion dans l’ordre des clés.2. Sinon il faut allouer une nouvelle page P’. On répartit les tuples de Pi avec le nouveau tuple en deux groupes équilibrés qui seront stockés respectivement sur Pi et P’.

Soit P0 la page qui pointait sur Pi ; deux possibilités :1. Soit P0 est non saturée, c’est-à-dire qu’elle n’a pas les d-1 clés alors insertion d’un pointeur pour P’ avec la valeur minimum de clé de P’.2. Sinon, il faut allouer une nouvelle page pour l’index tout en contrôlant le pointage du niveau antécédent. Dans le cas où plusieurs ancêtres de P0 sont pleins alors l’insertion aura pour effet de modifier l’arbre sur plusieurs niveaux et ainsi être dans la possibilité de modifier la racine qui deviendra un nœud intermédiaire, et qui sera remplacée par une nouvelle racine avec 2 fils. La profondeur de l’arbre sera alors modifiée. On parle alors d’insertion avec éclatement de nœuds et propagation de l’éclatement jusqu’à la racine.

Exemple : • Insérer le tuple de clé 2000• Rechercher la page qui doit contenir le tuple de clé 2000 : soit P7• P7 est saturée : allocation d’une nouvelle page P12 : • Répartition des clés : 1114 et 2000 dans P7, 2006 et 2007 dans P12.• Insertion dans P3 de la clé 2006 et un pointeur sur la nouvelle page P12, mais P3 est saturée (elle a le maximum de fils).• Allocation d’une nouvelle page P13 : Pointeurs P7 et P12 dans P3, Pointeurs P8 et P9 dans P13.• Insérer dans P1 une nouvelle clé 2018 et un pointeur pour P13, mais P1 est saturée.• Allocation d’une nouvelle page P14 : pointeurs P2 et P3 dans P1, pointeurs P13 et P4 dans P14.• Créer une nouvelle racine P15 contenant la clé 2018 pointant sur P1 et P14.

Le B-arbre initial devient :

P4

1114

1100 2006 2300

1001 1010 ---

1100 1112 ----

1114 2000

2018 2019 ---

2100 2200 - 2300 2308 2360

2212 2220 ---

D = 3P = 4

2018

P15

2212

2006 2007

2100

P13

P5 P7 P9 P11

P6 P12P8

P10

P2 P3

P1 P14

Algorithme de suppression : soit à supprimer le tuple de clé c•appliquer l’algorithme de recherche de la clé c : soit Pi la page qui contient c•Si Pi a un nombre d’enregistrement >= [d/2] après suppression alors réaliser la suppression. Il faut cependant vérifier que la clé du tuple supprimé ne se retrouve pas comme clé dans l’index du B-arbre (vérifier tous les niveaux de l’index). Dans ce cas, il faut alors remonter dans la hiérarchie afin de remplacer cette clé par la clé du tuple suivant. •Sinon (c’est-à-dire que Pi a moins de [d/2] fils après suppression) :•On examine la page Pj immédiatement à gauche ou à droite de Pi et ayant le même père. •Si Pj a plus de [d/2] enregistrements, on redistribue les enregistrements de Pi et Pj de manière équilibrée tout en conservant l’ordre. On répercute la modification sur les ancêtres de Pi puisque les clés sont modifiées.•Sinon on réalise une suppression avec fusion. On regroupe Pi et Pj en un seul bloc et on modifie les ancêtres de Pi. Cette fusion peut être récursive.Exemple : Soit à supprimer dans le B-arbre précédent le tuple de clé 2018La procédure de recherche nous donne le chemin d’accès : P15, P14, P13, P8.La suppression du tuple de clé 2018 implique deux situations :• Le tuple de clé 2018 est le premier enregistrement de la page P8. Il faut propager vers le haut de l’arbre que maintenant la plus petite valeur de la clé dans P8 est 2019. •Par ailleurs, lorsque 2018 est supprimé de P8, cette page ne respecte plus les caractéristiques du B-arbre (>= [d/2]). P8 n’a pas de frère à gauche mais il a un frère droit P9 qui contient 2 tuples. On fusionne alors P8 et P9. Mais P13 n’a plus qu’un seul fils, ce qui implique la fusion de P13 avec son frère P4. Alors P14 n’aura plus qu’un seul fils, donc la fusion se propage à P14 et son frère P1. La racine P15 se retrouve avec un seul fils (P14 et P1 fusionnés), elle est supprimée.Nous obtenons le B-arbre suivant :

P10

1114 2019

1100 2006 2212 2300

1001 1010 ---

1100 1112 ---

1114 2000

2006 2007 ---

2019 2100 2200 2300 2308 2360

2212 2220 ----P6 P12

D = 3P = 3

P5 P7 P8 et P9 P11

P2 P3 P4 et P13

P1 et P14

IntroductionNous avons vu en étudiant les fichiers aléatoires, que la méthode de hachage

était performante tant que le fichier n’évoluait pas. La détérioration des performances d’accès est due à l’accumulation des débordements. Souvent la prévision des débordements impliquait des taux d’occupation de fichier assez faible. L’idée du hachage virtuel est de prévoir une solution dans le cas d’insertion lorsque le taux d’occupation du fichier est voisin de 1.

1.Hachage virtuel1 : HV1La méthode de hachage virtuel 1 est appliquée à des fichiers ayant des taux de

remplissage tout à fait usuel (voisin de 1), lorsque de nouvelles insertions posent problème. La solution consiste lorsqu’il y a débordement à modifier la fonction de hachage initiale.

Principe : il consiste à éclater le paquet saturé en deux paquets grâce à la nouvelle fonction de hachage, et à répartir les enregistrements.

La fonction de hachage sur laquelle a été développé le principe de HV1 est la division.

Soit la fonction initiale de hashcoding H0 , soit c une clé et N le nombre de paquets.

H0 : c m [0, N[ R(c,N) = reste de la division de c par N

8003900180070014600

La nouvelle fonction de hachage à utiliser est :

229013460112016011701

52753245325335353

30999451995499341992090

m [0, 2N[ H1 : c R(c, 2N)Exemple : Fichier à l’état initial : N=100 : H0 (c) = R(c,100)

0 1 53 99

Insertion de 23750 : H0 (23753) = 53 : débordement du paquet 53, alors application de la nouvelle fonction de hashcoding H1 .H1 (23753) = R(23753,200) = 153, donc éclatement du paquet 53 en deux paquets 53 et 153.

22901

34601

1201

601

1701

2453

253

53

30999

45199

5499

34199

2090

0 1 53 99

800

3900

1800

700

1460

23753

52753

353

153 199

Fichier = 200 paquets

Ainsi, un nouvel enregistrement r aura soit la même adresse, soit une nouvelle adresse H0(c)+N ou encore H1 (c) = m est telle que H0 (c ) = m-N.

Mathématiquement il a été prouvé que lorsqu’on utilise une pareille fonction de hachage alors :

•Si y enregistrements partagent la même adresse m avec H0, alors en moyenne y/2 changeraient d’adresse en appliquant H1.

•Soit b le nombre maximal d’enregistrements du paquet, alors si y est voisin de b , il est très peu probable que H1 attribue m ou m+N à plus de b enregistrements.

Ces implications nous permettent d’affirmer que la recherche d’un enregistrement se fera au maximum en 2 accès : (paquet m et paquet m+N).

Règles de fonctionnement de HV1•Le fichier est crée avec H = H0•H est inchangé jusqu’à ce qu’une collision se produise et que le taux de

remplissage dépasse l’usuel.•Dès la première collision, alors les actions suivantes sont exécutées :•La mémoire est allouée pour les paquets N, N+1, …, 2N-1•Une table de bits B(0 , N-1) est crée avec B(n) = 0 quelque soit n.•Si m0 est l’adresse de la collision, alors B(m0) =1•H’ = H1(c) si H0(c) = m0H’ = H0(c) sinon•Chaque enregistrement de clé c tel que H0(c) = m0 est réinséré à l’adresse H1(c)

soit m0+N.

0 1 53 99 CONCLUSIONUne série de tests utilisant HV1 a aboutit à la conclusion suivante :Un fichier HV1 peut subir un grand nombre d’insertions sans altérer les performances.En général, un enregistrement sur deux est trouvé en un accès.Au pire un enregistrement est trouvé en deux accès en moyenne ( la table de bits est résidente en MC).

0 0 1 0 0