Chapitre 3 : Les structures d’index (PDF)

Chapitre 3 Les structures d’index (Le séquentiel-indexé) Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 1  Plan du chapitre 1) Généralités Définitions , Clé de recherche , U...

Chapitre 3 Les structures d’index (Le séquentiel-indexé) Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 1  Plan du chapitre 1) Généralités Définitions , Clé de recherche , Utilisation 2) Accès mono-clé Index en MC, Index en MS, Index multi-niveaux 2) Accès multi-clés Index indépendants, Index inversées, Bitmaps Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 2  Généralités La recherche d’un enregistrement dans une structure de fichier séquentielle est généralement coûteuse → recherche séquentielle → recherche dichotomique dans un fichier (très) volumineux On appelle ‘clé de recherche’ (Search Key) l’attribut (ou groupe d’attributs) utilisé pour rechercher les enregistrements : Fichier de mesures météorologiques < ville , date, température > Exemples de recherche : → trouver le (ou les) enregistrement(s) tel que ville = ‘DJELFA’ résultat : ‘DJELFA’ , ‘2015-06-23’ , 21 ‘DJELFA’ , ‘2013-10-04’ , 15 ’DJELFA’ , ‘2015-06-22’ , 20 ‘DJELFA’ , ‘2020-07-16’ , 29... → trouver le (ou les) enregistrement(s) tel que ville < ‘MZZZ’ ET ville > ‘ME’ résultat : ‘MSILA’ , ‘2011-04-23’ , 22 ‘MEDEA , ‘2019-02-04’ , 11 ‘MEFTAH , ‘2016-08-25’ , 32 ‘MILA’ , ‘2011-04-23’ , 14 ‘MOSTAGANEM’ , ‘2020-03-08’ , 19... Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 3  Généralités Un index est une structure de données (en MC et/ou en MS) permettant de rendre la recherche d’enregistrements plus rapide. Souvent un index est une table en MC, ordonnée, contenant entre autre, des couples : < val_clé , adr_enreg > F MC MS c5.. clé | adr …... c1 , a1 … Index c2 , a2 c1… Fichier de données c3 , a3... Structure quelconque c4 , a4 c5 , a5 … … c2... Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 4 Exemple : rechercher l’enregistrement ayant comme valeur d’attribut A1 = 54 → recherche dichotomique de 54 dans la table index en MC : résultat adr = → LireDir( F, 4, buf ) et récupérer l’enregistrement buf.tab[ 2 ] MC A1 A2 A3 A4... MS 1 1. 72 , bbb , 245 ,... 2. 20 , ppp , 127 ,... 3. 77 , ccc , 432 ,... A1 | adr 10 , 2 1. 30 , eee , 870 ,... 15 , 2. 32 , aaa , 452 ,... Index 18 , 3. 10 , ddd , 120 ,... Fichier de données 20 , sur A1 30 , 3 1. 15 , aaa , 763 ,... 31 , 2. 45 , aaa , 129 ,... 32 , 3. 68 , ggg , 132 ,... 45 , 50 , 4 1. 90 , bbb , 902 ,... 54 , 64 , 2. 54 , aaa , 539 ,... 68 , 3. 64 , ccc , 131 ,... 70 , 72 , 5 1. 50 , nnn , 243 ,... 77 , 2. 31 , ggg , 122 ,... 83 , 3. 18 , eee , 108 ,... 90 , 99 , 6 1. 70 , eee , 320 ,... 2. 99 , ggg , 777 ,... 3. 83 , ppp , 184 ,... Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 5  Utilisation des index en MC Recherche d’enregistrement Rechercher dans l’index en MC, ensuite accéder aux fichier de données Requête exacte (clé = valeur) → recherche dichotomique de la valeur cherchée Requête à intervalle (clé Î [a,b]) → recherche dichotomique de ‘a’ + les suivants en séquentiel jusqu’à ‘b’ Insertion / Suppression d’enregistrements insertions/suppressions d’enreg dans le fichier de données et éventuellement m-a-j de l’index en MC Création d’un index - quand le fichier de données est encore vide → créer en MC une table d’index vide - à partir d’un fichier de données déjà existant → remplir en MC une table d’index en parcourant le fichier de données Sauvegarde d’un index en MS → sauvegarder le contenu de la table d’index dans un (nouveau) fichier index Chargement d’un index depuis la MS → charger le contenu du fichier index dans la table d’index en MC Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 6  Utilisation des index en MC Table d'index en MC Clé Adr c (i,j) c (i,j) i' j' c' | xxx c' (i', j') c' (i', j') i j c | yyy Fichier index (de sauvegarde) en MS Fichier de données en MS Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 7 La clé peut être à valeurs uniques ou non (valeurs multiples) Exemple d’un index sur un attribut clé à valeurs multiples : MC F MS … c2...... c5... clé | adr ……... …... c1 , a1 Index c2 , a2 , a6 , a8 Fichier de c3 , a3 données c4 , a4 … c5 , a5 , a7 … c2... c5… … c2... Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 8 Différentes représentations des tables d’index à valeurs multiples adr 1) Une entrée par valeur de clé a7 clé adr clé clé | adr ……... ou ou a1 a1 c1 , a1 c1 c1 a2 c2 , a2 , a6 , a8 c2 a2 a6 a8 c2 c3 , a3 c3 c3 a3 c4 , a4......... c5 , a5 , a7 c5 a5 a7 c5 a8 a4 a5 clé | adr 2) Plusieurs entrées par valeur de clé a6 c1 , a1 c2 , a2 c2 , a6 c2 , a8 c3 , a3 c4 , a4 c5 , a5 c5 , a7 Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 9 Le fichier de données peut être ordonné selon la clé ou non … F … 1) Si le fichier de données est ordonné (selon l’attribut clé) … ⇒ Index non dense (Clustered Index) … ne contient pas toutes les valeurs de l’attribut clé … c1.. … … MC … MS … clé | adr … c2.. c1 , a1 … Index c2 , a2 … non dense c3 , a3 … c4 , a4 … c5 , a5 … c3.. Fichier de … données … ordonné … … Dans cet exemple, chaque entré dans la table … d’index, contient la plus grande clé d’un groupe de c4... 2 blocs consécutifs … … … … … Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI c5... 10 Le fichier de données peut être ordonné selon la clé ou non 2) Si le fichier de données n’est pas ordonné (selon l’attribut clé) ⇒ Index dense (non Clustered Index) contient toutes les valeurs de l’attribut clé F c23… c03… MC c75… MS c39… clé | adr c01… c08... c01 ,... c02 ,... c15… Index c04… c03 ,... c12… dense c04 ,... c06… c05 ,... c62… … c44... Fichier de … c99… données c75 ,... c68… Non ordonné c87 , … c07... c99 ,... c26… c05… c09... c74… c25… c40... c38… c02… c87... Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 11 Exemple : Insertion dans TOF avec index dense et clés à valeurs uniques Type Tbloc = Struct tab : tableau[ b ] de typeEnreg ; NB : entier Fin Tcouple = Struct clé : typeqlq ; numBlc , depl : entier Fin Var F : FICHIER de Tbloc BUFFER buf ENTETE ( entier ) Index : tableau [ MaxIndex ] de Tcouple NbE : entier // nombre d’éléments dans la table index ( == nombre d’enreg dans le fichier F) Ins( e:TypeEnreg ) Rech( e.cle , trouv , k ) // Recherche (dichotomique) dans la table index SI ( Non trouv ) // insertion à la fin du fichier de données... OUVRIR( F, « donnees.dat » , ‘A’ ) i ← Entete( F , 1 ) // n° du dernier bloc de F LireDir( F , i , buf ) SI ( buf.NB < b ) buf.NB++ ; j ← buf.NB ; buf.tab[ j ] ← e EcrireDir( F , i , buf ) SINON i++ ; j ← 1 ; buf.NB ← 1 ; buf.tab[ j ] ← e Aff_entete( F, 1, i ) ; EcrireDir( F , i , buf ) FSI FERMER( F ) // insertion dans la table d’index... NbE++ ; m ← NbE TQ ( m > k ) Index[ m ] ← Index[ m-1 ] ; m-- FTQ Index[ k ] ← < e.c , i , j > // clé, numBlc, depl FSI Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 12 Même exemple mais clés à valeurs non uniques Type Tcouple = Struct clé : typeqlq ; tete : ptr(maillon) Fin maillon = struct val : struct (numblc , depl : entier) ; adr : ptr(maillon) Fin Var Index : tableau [ MaxIndex ] de Tcouple Ins( e:TypeEnreg ) // insertion à la fin du fichier de données... OUVRIR( F, « donnees.dat » , ‘A’ ) i ← Entete( F , 1 ) // n° du dernier bloc de F LireDir( F , i , buf ) SI ( buf.NB < b ) buf.NB++ ; j ← buf.NB ; buf.tab[ j ] ← e EcrireDir( F , i , buf ) SINON i++ ; j ← 1 ; buf.NB ← 1 ; buf.tab[ j ] ← e Aff_entete( F, 1, i ) ; EcrireDir( F , i , buf ) FSI FERMER( F ) // insertion dans la table d’index … Rech( e.cle , trouv , k ) SI ( trouv ) // rajouter un maillon la liste index[k].tete Allouer( p ) ; Affval( p , < i , j > ) ; Affadr( p , Index[ k ].tete ) ; Index[ k ].tete = p SINON // insérer une nouvelle entrée dans l’index à la pos k NbE++ ; m ← NbE ; Allouer(p) ; Affval(p, < i , j >) ; Affadr(p,nil) TQ ( m > k ) Index[ m ] ← Index[ m-1 ] ; m-- FTQ Index[ k ] ← < e.c , p > // clé=e.c , tete=p FSI Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 13  Exemple : Index pour Fichier TOF avec zone de débordement c1... c2... c3... c4... c4... c6... c5... c5... c7... c3 c8... c6... c8 c10 c9... c14 c10... c17 c11... c13... c12... c14... Table d'index non dense en MC c15... c16... c17... Fichier de données Fichier de données zone primaire zone de débordement Type Tbloc = struct tab : tableau[ b ] de Tenreg NB : entier Lien : entier Fin Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 14  Exemple : Index pour Fichier LOF (pas de décalages inter-blocs et pas de zone de débordement) c1... c2... c3... c4... c3 c6... c8... c8 c10 c12 c17 c9... c10... Table d'index non dense en MC c11... c12... Fichier de données c15... c16... c17... Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 15  Exemple : Fichier LOF / Insertion L’insertion de c5 provoque l’éclatement du bloc i : c1... - Ajouter un nouveau bloc → i’ c2... - Partager le contenu de i en 2 moitiés c3... - M-a-j de l’index i c4... c5... c3 c6... c8... c8 c10 c12 c17 c9... c10... Table d'index non dense en MC c11... c12... c15... c16... Fichier de données c17... Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 16  Exemple : Fichier LOF / Insertion L’insertion de c5 provoque l’éclatement du bloc i : c1... - Ajouter un nouveau bloc → i’ c2... - Partager le contenu de i en 2 moitiés c3... - M-a-j de l’index en insérant une nouvelle entrée pour le bloc i’ i c4... c3 c5... i’ c5 c6... c8 c8… c10 c12 c17 c9... c10... Table d'index non dense en MC c11... c12... c15... c16... Fichier de données c17... Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 17  Index en MC sous forme de BST...... c2 c3…............... c1 c2… … …... c3......... c1…... Index = arbre de recherche binaire en MC Fichier de données Type Tnoeud = struct clé : typeqlq numBlc , depl : entier fg , fd : ptr(Tnoeud) Fin Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 18  Index de grande taille Si le fichier de données est volumineux (en nombre d’enregistrements) la taille de l’index peut devenir trop grande pour résider en MC. Une solution consiste à maintenir l’index en MS sous forme de fichier TOF (ou TOVC) ⇒ Le fichier index devient un fichier de travail (il n’y a plus de table en MC) Index en MS Fichier de données sous forme de quelconque en MS fichier ordonné avec des blocs contigus Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 19  Index Multiniveaux Table index 2 en MC Clé Adr Sauvegarde index2 Fichier index 1 en MS Chargement index2 Fichier de données en MS Fichier index 2 en MS (de sauvegarde) Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 20  Accès Multiclés Lorsque plusieurs attributs A1, A2, … An sont souvent utilisés comme conditions de recherche, il peut être intéressant de maintenir plusieurs index : IndA1, IndA2 … IndAn (un sur chaque attribut clé) Les requêtes multiclés peuvent ainsi bénéficier du parcours de plusieurs index pour retrouver les enregistrements résultats → c’est l’accès multiclés Si le fichier est ordonné selon l’un des attributs clés, l’index associé (non dense) sera appelé index primaire (Primary Index). Les autres index (forcément denses) seront considérés comme index secondaires (Secondary Indices). A1 A2 A3 A4... A3 adr A1 adr 10 , bbb , 245 ,... IndxA1 1 108 , 30 , 20 , ppp , 127 ,... IndxA3 non dense 30 , ccc , 432 ,... 120 , 40 , (dense) 122 , 48 , 2 30 , eee , 870 ,... 127 , 54 , 30 , aaa , 452 ,... 129 , 65 , 99 , 40 , ddd , 120 ,... Fichier de 131 , 132 , 3 45 , aaa , 763 ,... données 184 , IndxA2 (dense) 45 , aaa , 129 ,... ordonné sur A1 243 , A2 adr... 48 , ggg , 132 ,... 245 , 4 50 , bbb , 902 ,... aaa , , , , 320 , 54 , aaa , 539 ,... bbb , , 432 , 54 , ccc , 131 ,... ccc , , 452 , ddd , 54 , nnn , 243 ,... 539 , 5 eee , , , 61 , ggg , 122 ,... 763 , ggg , , , 65 , eee , 108 ,... 777 , nnn , 870 , 6 ppp , , 70 , eee , 320 ,... 902 , 83 , ggg , 777 ,... Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 99 , ppp , 184 ,... 21 Une variante est souvent utilisée, lorsque l’index primaire est basée sur une clé primaire (à valeurs uniques) en se basant sur les index inversés : L’idée est que les index secondaires utilisent à la place des adresses, des valeurs de clés primaires. Donc l’accès par une valeur de clé secondaire, commence au niveau de l’index secondaire associé, puis passe par l’index primaire (pour récupérer les adresses des enreg) et se termine par l’accès au fichier de données. A3 A1 IndxA3 A1 A2 A3 A4... 108 , 65 120 , 40 (dense) IndxA1 1 10 , bbb , 245 ,... 122 , 61 non dense 20 , ppp , 127 ,... 127 , 20 A1 adr 30 , ccc , 432 ,... 129 , 45 131 , 54 30 , 2 32 , eee , 870 ,... 132 , 48 40 , 35 , aaa , 452 ,... 184 , 99 48 , 40 , ddd , 120 ,... Fichier de 243 , 55 54 , 65 , 3 44 , aaa , 763 ,... données 245 , 10 99 , 45 , aaa , 129 ,... ordonné sur A1 320 , 70 48 , ggg , 132 ,... 432 , 30 452 , 35 4 50 , bbb , 902 ,... 539 , 51 51 , aaa , 539 ,... 763 , 44 54 , ccc , 131 ,... 777 , 83 A2 A1... 870 , 32 55 , nnn , 243 ,... aaa , 51 , 45 , 35 , 44 5 902 , 50 61 , ggg , 122 ,... bbb , 50 , 10 IndxA2 65 , eee , 108 ,... ccc , 30 , 54 (dense) ddd , 40 6 70 , eee , 320 ,... eee , 32 , 65 , 70 83 , ggg , 777 ,... ggg , 48 , 61 , 70 99 , ppp , 184 ,... nnn , 55 ppp , 99 , 20 Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 22 Etapes d’une requête multi-clés avec la méthode des index inversés « trouver tous les enregistrements dont la valeur de X = vx ET la valeur de Y = vy ET... » avec X, Y,... des ‘clés secondaires’ (Pour chaque clé secondaire, il y a donc un index secondaire) : 1- En utilisant l'index secondaire X, trouver la liste Lx de clés primaires associées à la valeur vx. (Refaire la même action pour chaque clé secondaire mentionnée dans la requête…) 2- Faire l'intersection des listes de clés primaires Lx, Ly,... pour trouver les clés primaires associées avec chaque valeur de clé secondaire mentionnée dans la requête. 3- Utiliser l'index primaire pour retrouver les enregistrements du fichier de données (en triant d’abord la séquence des numéros de blocs avant d’effectuer les transferts physiques). Dans la figure de l’exemple précédent, si on cherche tous les enregistrements tel que A2 = ‘eee’ et A3 = 870, L’algorithme de la requête multiclés procédera comme suit : a- Recherche de ‘eee’ dans l’index IndA2 → résultat : LA2 = [ 32 , 65 , 70 ] b- Recherche de 870 dans l’index IndA3 → résultat : LA3 = [ 32 ] c- Intersection de LA2 et LA3 → résultat : Lfinale : [ 32 ] d- Recherche de 32 dans IndA1 → résultat : bloc_N° e- LireDir( F , 2 , buf) et récupérer, l’enreg « 32 , bbb , 870 , … » Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 23 Insertion d’un enregistrement < c , vx , vy , … > 1- Rechercher c dans l'index primaire → ip : l’indice où doit être insérée cette clé (recherche dichotomique). 2- Insérer l'enregistrement dans le fichier de données → adr : l’adresse où l’enreg a été inséré 3- Insérer dans l’index primaire, à la position ip l’entrée < c , adr > s’il s’agit d’un index dense ou alors, éventuellement, mettre à jour l’entrée qui se trouve à l’indice ip s’il s’agit d’un index non dense. 4- Rechercher la valeur vx dans l'index secondaire X, si vx existe, rajouter c à la liste pointée par vx si vx n'existe pas, insérer vx dans l’index de secondaire X. → dans ce cas la nouvelle entrée vx, pointera une liste formé par une seule clé primaire (c). Refaire l'étape 4) pour chaque clé secondaire restante (vy,...). Suppression d’un enregistrement < c , vx , vy , … > Pour supprimer logiquement un enregistrement de clé primaire c, il suffit de positionner un bit (ou caractère) d'effacement au niveau du fichier de données ou de la table d'index primaire, pour l'entrée c. Pour supprimer physiquement un enregistrement de clé primaire c, il faut d’abord supprimer physiquement l’enregistrement dans le fichier de données, ensuite il faut mettre à jour la table d’index primaire soit en supprimant l’entrée relative à c (cas d’un index dense) ou alors modifier la clé et/ou l’adresse du représentant du groupe auquel appartient l’enregistrement supprimé (cas d’un index non dense). Dans les deux types de suppression (logique ou physique), il n’est pas nécessaire de mettre à jour les index secondaires. Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 24  Index Bitmap Un index bitmap sur un attribut A (formé par m différentes valeurs : v1, v2, … vm) est composé de m chaînes binaires, de N bits chacune (IndA_v1, IndA_v2... IndA_vm) : Chaque chaîne IndA_vj est associée à la valeur vj de l’attribut A Si ( IndA_vj[ k ] = 1 ), alors dans l’enregistrement n°k, l’attribut A vaut vj Si ( IndA_vj[ k ] = 0 ), alors dans l’enregistrement n°k, l’attribut A est différent de vj Index_A = n° enregistrement (le fichier contient N enregistrements) 1 2 3 4 5 6 7 8 … i … …... N |---|---|---|---|---|---|---|---|-----|---|-----|---|---|---| IndA_v1 : | 1 | 0| 0 | 0| 1 | 1| 0 | 1| …. | 0| … | 1| 1 | 0| (N bits) → la chaîne de bits associée à v1 |---|---|---|---|---|---|---|---|-----|---|-----|---|---|---| IndA_v2 : | 0 | 1| 0 | 0| 0 | 0| 0 | 0| …. | 1| … | 0| 0 | 0| (N bits) → la chaîne de bits associée à v2 |---|---|---|---|---|---|---|---|-----|---|-----|---|---|---| … … … … … …... |---|---|---|---|---|---|---|---|-----|---|-----|---|---|---| IndA_vm : | 0 | 0| 1 | 1| 0 | 0| 1 | 0| …. | 0| … | 0| 0 |1 | (N bits) → la chaîne de bits associée à vm |---|---|---|---|---|---|---|---|-----|---|-----|---|---|---| Exemples : A = v2 dans l’enregistrement n°2 et l’enregistrement n°i du fichier de donnée A = v1 dans les enregistrements n° 1, 5, 6, 8, … N-2 et N-1... Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 25 Les index bitmaps peuvent être utiles pour les attributs à faible cardinalité (ex < 20 valeurs distinctes). Les différentes chaînes de bits peuvent être chargées en MC indépendamment les unes des autres. Ils sont utilisés principalement pour les requêtes multiclés sur des attributs à faible cardinalité Exemple : « trouver les enregistrements tel que A = v2 et B = w4 » Index_A = n° enr (cardinalité de A = 3 valeurs : v1,v2,v3) 1 234 5678… i … …N |--|--|--|--|--|--|--|--|----|--|----|--|--|--| IndA_v1 : 1 0 0 0 0 1 0 1 …. 0 … 1 1 0 IndA_v2 : 0 0 0 0 1 0 1 0 …. 1 … 0 0 0 IndA_v3 : 0 0 1 1 0 0 0 0 …. 0 … 0 0 1 Index_B = n° enr (cardinalité de B = 4 valeurs : w1,w2,w3,w4) 1 234 5 678… i … …N |--|--|--|--|--|--|--|--|----|--|----|--|--|--| IndB_w1 : 0 0 1 0 0 0 0 1 …. 0 … 1 0 0 IndB_w2 : 0 1 0 0 0 1 0 0 …. 0 … 0 0 1 IndB_w3 : 0 0 0 1 1 0 0 0 …. 0 … 0 1 0 IndB_w4 : 1 0 0 0 0 0 1 0 …. 1 … 0 0 0 Le résultat de la requête est donné par l’opération binaire : ( IndA_v2 AND IndB_w4 ) → Les enregistrements n° 7 et n° i Pr Hidouci W.K. (http://hidouci.esi.dz) / SFSD / ESI 26