From: Kim Nguyễn Date: Wed, 5 Feb 2014 06:00:04 +0000 (+0100) Subject: Ajout cours 3. X-Git-Url: http://git.nguyen.vg/gitweb/?p=hacks%2FsimpleWebSlides.git;a=commitdiff_plain;h=b1739fd451abe174305848faa1062edc87e48d1c Ajout cours 3. --- 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:

+ + +

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

+ +

(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: +

+ +
+
+

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: +

+ +

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

+ +
+
+

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

+ +
+
+

Coût des opérations 2/2

+

Fichier trié

+ +

Hash index

+ +

Arbre B+

+ +
+
+

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 (c1, …, + cn), 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. +

+
+
+

Hash-index avec répertoire

+

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 +

+

+
+
+

Insertion de 20

+

On sépare le bucket plein en deux (100 vs 000)

+

+
+
+

Insertion de 20

+

On double la taille du répertoire et on augmente les + compteurs globaux et locaux

+

+
+
+

Insertion de 20

+

Le pointeur de 100 va vers le nouveau bucket les + autres vont vers les anciens

+

+
+

Arbre B+

+
+

Arbre B+

+

Un Arbre B+ est un arbre «n-aire» dont les nœuds + peuvent contenir entre M et 2M valeurs (sauf la racine, qui a + entre 1 et 2M valeurs).

+

Les noeuds internes contiennent des valeurs et des pointeurs + vers les fils.

+

Les feuilles contiennent les valeurs finales, un pointeur + vers les données indexées et sont chaînées entre-elles

+

Exemple sur un noeud d'ordre 4 (i.e. entre 2 et 4 + valeurs, 5 pointeurs vers les fils).

+

Arbre vide:

+

Insertion 4,19,22,39 (noeud plein)

+
+
+

Arbre B+ partage des feuilles

+

Insertion + 25
+ (partage du noeud, insertion + de 25, report de la plus petite valeur dans le parent, chaînage + des feuilles)

+

Insertion + 90

+

Insertion + 95 +

+
+
+

Arbre B+ partage des noeuds internes

+

+

+

insertion de 54

+

+

+

Partage en 2 et insertion de la valeur mediane dans un + nouveau parent

+

+

+
+
+

Arbre B+ suppression

+

+

+

suppression 95 (simple)

+

+

+

suppression 71 (utilisation des voisins)

+

+

+
+
+

Arbre B+ suppression (suite)

+

+

+

suppression 19 (fusion des voisins, suppression de l'entrée + dans le parent)

+

+

+
+
+ +
+ + diff --git a/bd/pdf/bd03.pdf b/bd/pdf/bd03.pdf new file mode 100644 index 0000000..694d423 Binary files /dev/null and b/bd/pdf/bd03.pdf differ diff --git a/bd/pdf/bd03_print.pdf b/bd/pdf/bd03_print.pdf new file mode 100644 index 0000000..3b75f27 Binary files /dev/null and b/bd/pdf/bd03_print.pdf differ