Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Techniques d’indexation Implémentation du modèle relationnel ~ LIF10: Fondement

Techniques d’indexation Implémentation du modèle relationnel ~ LIF10: Fondements des bases de données relationnelles Une vision conceptuelle des données : • Algèbre relationnel, SQL, etc. Les tables et leurs enregistrements sont stockés physiquement !! • Les enregistrements ont une adresse (physique, logique). • Mais les requêtes SQL référencent des valeurs d’attributs, pas des adresses. SELECT * FROM R WHERE A=12; SELECT * FROM E WHERE N>10; COMMENT RETROUVER (EFFICACEMENT) LES ENREGISTREMENTS QUI ONT UNE CERTAINE VALEUR SUR UN ATTRIBUT DONNÉ ? Métaphore de l’aiguille • Les données : le foin ! • Le résultat de la requête : l’aiguille ! • Comment trouver très rapidement l’aiguille ? • Comment éviter de parcourir l’intégralité des données quand ce n’est pas nécessaire ? Comment éviter de tout parcourir ? • Sélection • Jointure naturelle • Agrégation SELECT * FROM Etudiant WHERE note<10; SELECT * FROM Etudiant NATURAL JOINT Cours; SELECT Max(note) FROM Etudiant ORDER BY note; SELECT * FROM Etudiant NATURAL JOINT Cours; ou plus généralement SELECT * FROM TABLE1, TABLE2 WHERE TABLE1.X = TABLE2.Y; Approche naïve : Parcourir les deux tables avec une double boucle Coût : |T1|x|T2| Les index pour optimiser les réponses aux requêtes! • Un index sur un fichier : • Une structure de données «disk-based» • Améliore la sélection des clés de recherche (search key) de l’index • Un index peut porter sur la valeur d’un ou plusieurs attributs de la relation. • ☂: Search key ≠ key : un ou plusieurs attributs pour lesquels on veut rechercher efficacement (pas forcément unique) Exemple [wikipedia] • un index sur ( N° sécu ) • Exemple de requête utilisant l'index : Contribuable ayant N° sécu = 123456 • un index sur ( Annee_naissance, Revenu ) • Exemple de requête utilisant l'index : Contribuables nés avant 1980, avec un Revenu entre 20 000 et 30 000 • Exemple de requête utilisant l'index : Revenu maximal selon l'année de naissance N° sécu // N° de sécurité sociale. Annee_naissance // Année de naissance du contribuable Revenu // Revenu Frais Reel // montant des frais réels Concepts • Les structures de stockage consistent en plusieurs fichiers : • «Data files» : stockent les enregistrements d’une relation • Search key • «Index file» : Association valeur_search_key avec les enregistrements qui supportent la valeur de la clé de recherche. • «Sequential files» (fichiers séquentiels): enregistrements triés par rapport à leur clé primaire Questions sur les index • Quel type de requêtes supportent-ils? • sélection de la forme x <op> val • Egalité : (op est =) • Mais aussi (=<, <, >=, >, etc.) • Des requêtes plus complexes : • «ranking queries» : 10 restaurants les plus près de Nautibus; • Expressions régulières (génome, etc.) Index sur des fichiers séquentiels •Rappel : Search key ≠ primary key •Index primaire : (sur le champ séquencé) •l’index sur l’attribut qui détermine le séquençage de la table •Index secondaire : •Index sur n’importe quel autre attibut •Index dense : toutes les clés de recherche présentes •Index «creux» (sparse index) •Index «multi-niveaux» Fichier séquentiel 20 10 40 30 60 50 80 70 100 90 Les tuples sont ordonnés par rapport à leur clé primaire Bloc Fichier Sequent. 20 10 40 30 60 50 80 70 100 90 Index creux 10 30 50 70 90 110 130 150 170 190 210 230 Généralement, une seule clé par bloc de données Trouver l’entrée avec la plus grande valeur inférieure ou égale à la valeur recherchée Fichier séquent. 20 10 40 30 60 50 80 70 100 90 Index creux double niveau 10 30 50 70 90 110 130 150 170 190 210 230 10 90 170 250 330 410 490 570 Traite l’index comme un fichier et construit un index dessus. • 2 niveau sont généralement suffisants • + de 3 rares Pas forcément contigûité des deux fichiers ... Pas forcément contigûité des deux fichiers ... Opération de m.a.j • Insertion • Suppression • Quid de ces opérations par rapport aux types d’index ? Suppression dans index creux 20 10 40 30 60 50 80 70 10 30 50 70 90 110 130 150 Suppression dans index creux –supprimer l’enregistrement 40 20 10 40 30 60 50 80 70 10 30 50 70 90 110 130 150 Si l’entrée supprimée n’apparait pas dans l’index, ne rien faire. Suppression dans index creux 20 10 40 30 60 50 80 70 10 30 50 70 90 110 130 150 –supprimer l’enregistrement 30 40 40 Si l’entrée supprimée apparaît dans l’index alors remplacer avec la clé de recherche suivante Suppression dans index creux (tjs +) 20 10 40 30 60 50 80 70 10 30 50 70 90 110 130 150 – supprimer 30 et 40 50 70 Si la clé suivante a sa propre entrée dans l’index alors supprimer l’entrée Suppression dans index dense 20 10 40 30 60 50 80 70 10 20 30 40 50 60 70 80 Suppression dans index dense 20 10 40 30 60 50 80 70 10 20 30 40 50 60 70 80 – supprimer l’enregistrement 30 40 40 La suppression dans un index primaire dense se fait de la même façon que dans un fichier seq. Insertion dans index creux 20 10 30 50 40 60 10 30 40 60 Insertion dans index creux 20 10 30 50 40 60 10 30 40 60 - insérer l’enregistrement 34 34 • On a de la chance ... mais ce n’est pas toujours le cas Insertion dans index creux 20 10 30 50 40 60 10 30 40 60 – insérer 15 15 20 30 20 Il faut tout réorganiser des variantes : insérer un nouveau bloc m.a.j index 10 20 30 40 50 60 70 80 90 39 31 35 36 32 38 34 33 overflow area (pas séquentielle) Insertion ++ Index (séquentiel) continu espace libre Index basiques Avantages : Algorithmes très simples L’index est un fichier séquentiel facile pour effectuer des passes dessus Inconvénients : Insertions coûteuses, et/ou la notion de séquence est perdue à cause des overflows (blocs de dépassement) des réorganisations sont nécessaires Index basé sur les B(+)-Arbres Rappel ABR : • Niveau recherche : • Généralisation des arbres binaires de recherche. B-Arbres • Chaque noeud correspond à un bloc • Les B-arbres sont équilibrés (toutes les feuilles à la même profondeur). • Garantie d’accès efficaces • B-arbres garantissent une occupation minimale • n : nombre maximum de clés dans le noeud, le nombre minimum étant n/2. • Exception : la racine peut contenir une unique clé • m+1 pointeurs associés (m est le nombre de clés contenues) B-arbre + •Les noeuds feuilles contiennent les enregistrements et sont chainés. •Les noeuds non-feuilles contiennent les entrées de l’index et dirigent les recherches: P0 K 1 P 1 K 2 P 2 K m P m entrée index Non-feuilles Pages Pages Feuilles X<K1 X<K1 K1=<X<K2 K1=<X<K2 B-Arbres • Format des noeuds : (p1,k1, . . ., pn,kn,pn+1) pi: pointeur, ki: clé de recherche • Un noeud avec m pointeurs a m enfants sous arbres correspondants. • n+1 ème entrée a seulement 1 pointeur. Au niveau des feuilles ces pointeurs identifient le noeud suivant (liste chaînée). • propriété : i-ème sous-arbre contient des enregistrement avec une clé de recherche k <ki, i+1-ème sous-arbre contient des entrées avec une clé k >= ki. Exemple (1) Root n = 3 100 120 150 180 30 3 5 11 30 35 100 101 110 120 130 150 156 179 180 200 Exemple (2) to keys to keys to keys to keys < 57 57≤ k<81 81≤k<95 ≥95 57 81 95 Noeud non-feuille Exemple(3) From non-leaf node to next leaf in sequence 57 81 95 To record with key 57 To record with key 81 To record with key 85 Leaf node B-Arbre : espace mémoire 120 150 180 30 3 5 11 30 35 compte même si vide n = 3 Non- feuilles Feuilles Noeud saturé Noeud min. Nombre de pointeurs/clés pour un B-arbre Non-feuilles (non-racine) n+1 n ⎡(n+1)/2 ⎤ ⎡(n+1)/2⎤- 1 feuilles (non-racine) n+1 n Racine n+1 n 1 1 Max Max Min Min ptrs clés ptrs→data clés ⎣(n+1)/2⎦ ⎣(n+1)/2⎦ Utilisation mémoire • Recherche avec la clé k; On commence par la racine • A un noeud donné, trouver la “plus proche clé” ki et suivre à gauche (pi) ou droite (pi+1) le pointeur en fonction de la comparaison entre k et ki. • Continuer jusqu’à atteindre une feuille. • Exploration d’un seul chemin de la racine vers la feuille. • La hauteur du B-arbre est où N est le nombre d’enregistrements indexés. •  compléxité de la recherche Requêtes Exemple (4) : recherche • Trouver 28*? 29*? All > 15* and < 30* • Insertion / suppression : Trouver l’entrée dans une feuille, puis la changer. Besoin d’ajuster les parents dans certains cas. •Et répercussion dans les noeuds supérieurs de l’arbre 2* 3* Root 17 30 14* 16* 33* 34* 38* 39* 13 5 7* 5* 8* 22* 24* 27 27* 29* Entrées <17 Entrées >=17 uploads/Sante/ expose 42 .pdf