From b1739fd451abe174305848faa1062edc87e48d1c Mon Sep 17 00:00:00 2001 From: =?utf8?q?Kim=20Nguy=E1=BB=85n?= Date: Wed, 5 Feb 2014 07:00:04 +0100 Subject: [PATCH] Ajout cours 3. --- bd/bd03.xhtml | 382 ++++++++++++++++++++++++++++++++++++++++++ bd/pdf/bd03.pdf | Bin 0 -> 370730 bytes bd/pdf/bd03_print.pdf | Bin 0 -> 351741 bytes 3 files changed, 382 insertions(+) create mode 100644 bd/bd03.xhtml create mode 100644 bd/pdf/bd03.pdf create mode 100644 bd/pdf/bd03_print.pdf diff --git a/bd/bd03.xhtml b/bd/bd03.xhtml new file mode 100644 index 0000000..f021920 --- /dev/null +++ b/bd/bd03.xhtml @@ -0,0 +1,382 @@ + +â"> + â"> + +] + > + + + Indexation + + + + + + + + + + + + + + + + + + + + +

Bases de donnÃ©es

Polytech Paris-Sud

Apprentis 4^Ã¨me annÃ©e

Cours 3 : Indexation

+ kn@lri.fr
+ http://www.lri.fr/~kn +

+ +

Introduction

Le fichier comme abstraction du support physique

Le systÃ¨me et la couche physique exposent plusieurs notions + de bas niveau:

Secteurs, pistes, plateau, â¦
Pages/blocs
Buffer de lecture/Ã©criture

+ +

On souhaite proposer des structures de donnÃ©es et + des algorithmes gÃ©nÃ©riques permettant d'implanter un + moteur d'exÃ©cution de requÃªtes (SQL). +

On abstrait les concepts bas niveau par la notion + de fichier. Un fichier un ensemble + d'enregistrements. Un enrigstrement contient des donnÃ©es + structurÃ©es en champs. En pratique, les fichiers sont paginÃ©s

OpÃ©rations sur les fichiers

La couche physique propose plusieurs opÃ©rations sur les + fichiers

CrÃ©ation/suppression de fichier
Insertion/supression d'enregistrement
AccÃ¨s au i^Ã¨me enregistrement du fichier
AccÃ¨s au i^Ã¨me champ d'un enregistrement

(cf. cours 2 pour les diffÃ©rentes maniÃ¨res d'implanter ces + opÃ©rations).
+ Une table est gÃ©nÃ©ralement reprÃ©sentÃ© par un fichier + (au sens collection d'enregistrements)

Fichier simple

La structure la plus simple pour un fichier est la structure + en tas (Ã ne pas confondre avec la structure de donnÃ©e + du mÃªme nom). La couche physique du SGBD connait la liste des pages d'un + fichier ainsi que l'espace libre sur chaque page, les + enregistrements sont ajoutÃ©s ou supprimÃ© dans les pages que le + SGBD considÃ¨re comme meilleures (du point de vue des E/S) sans + considÃ©ration sur les donnÃ©es. +

Rechercher un enregistrement particulier, en fonction d'un + critÃ¨re sur son contenu (ex: id='5') nÃ©cessite un + parcours sÃ©quentiel du fichier (scan)

Types d'indexes

Index

Un index est un fichier + auxiliaire, structurÃ© qui va rendre plus efficace + l'accÃ¨s Ã certaines donnÃ©es, en fonction d'une clÃ© d'index. +

Un enregistrement d'un index s'appelle une entrÃ©e + d'index. L'entrÃ©e associÃ©e Ã la clÃ© k est + notÃ©e k* et contient suffisament d'information pour + retrouver le ou les enregistrements (de la table indexÃ©e) + associÃ©s Ã k. On distingue trois types d'indexes: +

Index de type I : k* reprÃ©sente directement un + enregistrement de la table originale (la table indexÃ©e). +
Index de type II : une entrÃ©e est un + couple <k,rid> oÃ¹ k est la clÃ© + et rid est un pointeur vers l'enregistrement ayant + cette clÃ©
Index de type III : un + couple <k,rid-list> oÃ¹ k est la clÃ© + et rid-list est une liste de pointeurs vers les enregistrements ayant + cette clÃ©

Indexes groupants

Un index est dit groupant si ses entrÃ©es sont triÃ©es + dans le mÃªme ordre que les enregistrement du fichier indexÃ©. Il + est dit non-groupant dans le cas contraire

Les enregistrements de la table initiale ne + sont ~~jamais dupliquÃ©s~~. On ne garde donc jamais un indexe + de type I en plus de la table initiale (on supprime cette + derniÃ¨re) +

Indexes denses

Un index dense s'il contient une clÃ© par + enregistrement et non dense sinon

Si une table possÃ¨de un index ~~non-dense~~, alors le + fichier de cette table est toujours triÃ© selon la clÃ© + d'index (sinon l'index ne sert Ã rien).

Autres propriÃ©tÃ©s

Un index pour lequel la clÃ© d'index contient la clÃ© + primaire de la relation est appelÃ© un + index primaire. Les autres indexes sont appelÃ©s + indexes secondaires +

Deux entrÃ©es d'index possÃ©dant la mÃªme clÃ© sont + des doublons. Un index primaire ne contient pas de + doublon. +

+ + +

Structures de donnÃ©es pour les indexes

DiffÃ©rentes structures pour diffÃ©rents usages

Outre le fichier tas un index peut avoir les + reprÃ©sentations internes suivantes: +

Hash-index : l'index est organisÃ© comme une table de + hashage
Tree-index : l'index est organisÃ© comme un arbre de + recherche +
Fichier triÃ© : le fichier est triÃ© selon une clÃ© + particuliÃ¨re (i.e. l'ordre des enregistrements sur le disque + coÃ¯ncide avec l'ordre de la clÃ© d'index) +

On illustre sur une relation ayant le schÃ©ma Emp(Nom, Age, Salaire)

Hash index (informel)

Un hash index repose sur une fonction de hash h + telle que: + +h(k) = @page + + oÃ¹ k est la clÃ© d'index et @page est + l'adresse (sur le disque) de la page oÃ¹ se trouve + l'enregistrement associÃ© Ã k +

Remarque: index de type I

Arbre B+ (informel)

Arbre Â«n-aireÂ» de recherche (avec n grand, gÃ©nÃ©ralement + 100)

Remarque: index de type II, non groupant

Fichier triÃ©

Remarque: index de type II, non groupant

Cas d'utilisation

Hash-index : condition d'Ã©galitÃ© (age=28 OR + age=46)
Arbre B+ : condition d'intervale (sal > 1000 AND sal + < 3000), condition de prÃ©fixe (nom LIKE + 'Jo%')
Fichier triÃ© : idem (plus compact mais + insertion/suppression plus difficile)

CoÃ»t des opÃ©rations 1/2

On pose: B : nombre de pages de donnÃ©es
+ R : nombre d'enregistrements par page
+ D : temps moyen de transfert d'une page
+ On suppose des indexes de type I +

Fichier tas

Parcours B * D
Recherche
- 0 rÃ©ponse B * D
- 1 rÃ©ponse 0.5 * B * D (en moyenne)
- n rÃ©ponses B * D
+

CoÃ»t des opÃ©rations 2/2

Fichier triÃ©

Recherche sur autre que clÃ© de tri: B * D
Recherche sur clÃ© de tri : D*log₂B + (#rÃ©ponses/R)

Hash index

Recherche sur autre que clÃ© de tri, ou recherche autre qu'Ã©galitÃ©: B * D
Recherche (egalitÃ©) sur clÃ© de tri : 2 + (#rÃ©ponses/R)

Arbre B+

Recherche sur autre que clÃ© de tri : D * log_FB + B*D
Recherche sur clÃ© de tri : D*log_FB + (#rÃ©ponses/R)

ClÃ© composÃ©e

Une clÃ© d'index peut Ãªtre composÃ©e de plusieurs champs de la + relation originale.
+ Si une clÃ© est composÃ©e de (c₁, â¦, + c_n), on peut l'utiliser pour toute requÃªte + dont la valeur dÃ©pend de tous les i <= k, + pour k <=n. +

Supposons une clÃ© composÃ©e sur (age,salaire). On + peut l'utiliser pour age > 30 ou pour age >30 + AND salaire <4000 mais pas pour salaire + <4000 ou age >30 OR salaire <4000 +

+ +

Hash-index extensible

Tables de hash classique (rappel)

Table de hash classique = tableau de taille N contenant des listes + chaÃ®nÃ©es de valeurs (bucket). On calcule h(k) mod + N pour voir dans quel bucket insÃ©rer la nouvelle + valeur. Si un bucket devient trop grand, on double la + taille du tableau et on redistribue tous les contenus + des bucket. +

La redistribution est trop couteuse ici : on doit + scanner/Ã©crire tout l'index. On souhaite ne toucher que le + tableau et le bucket trop grand, et pas les autres. +

On n'utilise pas un simple tableau mais un tableau contenant + un masque binaire. On garde aussi un compteur de profondeur + globale et un compteur de profondeur local, pour + chaque bucket +