1 <?xml version="1.0" encoding="utf-8" ?>
2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
3 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"
5 <!ENTITY in "<small style='font-size:small'>∈</small>">
6 <!ENTITY notin "<small style='font-size:small'>∉</small>">
10 <html xmlns="http://www.w3.org/1999/xhtml" >
12 <title>Indexation</title>
14 <meta http-equiv="Content-Type"
15 content="text/html; charset=utf-8" />
16 <meta name="copyright"
17 content="Copyright © 2013 Kim Nguyễn" />
20 <script src="../jquery-2.0.3.min.js" type="text/javascript" ></script>
21 <script src="../libs/raphael-min.js" type="text/javascript" ></script>
22 <!-- Load the library -->
23 <script src="../simpleWebSlides.js" type="text/javascript" ></script>
25 <link rel="stylesheet" href="../simpleWebSlides.css" type="text/css" media="all" />
26 <!-- Load a custom Theme, the class-element marks this style-sheet
27 a "theme" that can be swtiched dynamicaly -->
28 <link class="sws-theme" rel="stylesheet" title="U-Psud style" href="../themes/uPsud.css" type="text/css" />
30 <!-- Customize some templates and initialize -->
32 <script type="text/javascript">
33 SWS.Config['sws-slide-change'] = SWS.Effects.slideChangeFadeOutIn;
34 SWS.Config['sws-object-deactivate'] = SWS.Effects.objectDeactivateFadeOut;
35 SWS.Config['sws-object-activate'] = SWS.Effects.objectActivateFadeIn;
37 //Ensures that we load SWS at the very end, after MathJax has
40 $(window).load(SWS.Presentation.init);
44 <a href="bd02.xhtml" class="sws-previous"/>
45 <div class="sws-slide sws-cover sws-option-nofooter">
46 <h1>Bases de données</h1>
47 <h3>Polytech Paris-Sud</h3>
48 <h3>Apprentis 4<sup>ème</sup> année</h3>
49 <h1>Cours 3 : Indexation</h1>
50 <a href="mailto:kn@lri.fr">kn@lri.fr</a><br/>
51 <a href="http://www.lri.fr/~kn/">http://www.lri.fr/~kn</a>
55 <div class="sws-slide">
56 <h1>Le fichier comme abstraction du support physique</h1>
57 <p>Le système et la couche physique exposent plusieurs notions
60 <li>Secteurs, pistes, plateau, …</li>
62 <li><i>Buffer</i> de lecture/écriture</li>
65 <p>On souhaite proposer des <em>structures de données</em> et
66 <em>des algorithmes génériques</em> permettant d'implanter un
67 moteur d'exécution de requêtes (SQL).
69 <p>On abstrait les concepts bas niveau par la notion
70 de <em>fichier</em>. Un fichier un ensemble
71 d'<em>enregistrements</em>. Un enrigstrement contient des données
72 structurées en champs. En pratique, les fichiers sont <em>paginés</em></p>
74 <div class="sws-slide">
75 <h1>Opérations sur les fichiers</h1>
76 <p>La couche physique propose plusieurs opérations sur les
79 <li>Création/suppression de fichier</li>
80 <li>Insertion/supression d'enregistrement</li>
81 <li>Accès au i<sup>ème</sup> enregistrement du fichier</li>
82 <li>Accès au i<sup>ème</sup> champ d'un enregistrement</li>
84 <p>(cf. cours 2 pour les différentes manières d'implanter ces
86 Une table est généralement représenté par un <em>fichier</em>
87 (au sens collection d'enregistrements)</p>
89 <div class="sws-slide">
90 <h1>Fichier simple</h1>
91 <p>La structure la plus simple pour un fichier est la structure
92 en <em>tas</em> (à ne pas confondre avec la structure de donnée
93 du même nom). La couche physique du SGBD connait la liste des pages d'un
94 fichier ainsi que l'espace libre sur chaque page, les
95 enregistrements sont ajoutés ou supprimé dans les pages que le
96 SGBD considère comme meilleures (du point de vue des E/S) sans
97 considération sur les données.
99 <p>Rechercher un enregistrement particulier, en fonction d'un
100 critère sur son contenu (ex: <tt>id='5'</tt>) nécessite un
101 <em>parcours séquentiel du fichier</em> (scan)</p>
103 <h1>Types d'indexes</h1>
104 <div class="sws-slide">
106 <p>Un index est un <em>fichier
107 auxiliaire</em>, <em>structuré</em> qui va rendre plus efficace
108 l'accès à certaines données, en fonction d'une <em>clé d'index</em>.
110 <p>Un enregistrement d'un index s'appelle une <em>entrée</em>
111 d'index. L'entrée associée à la clé <i>k</i> est
112 notée <i>k*</i> et contient suffisament d'information pour
113 retrouver le ou les enregistrements (de la table indexée)
114 associés à <i>k</i>. On distingue trois types d'indexes:
116 <ul><li><em>Index de type I</em> : <i>k*</i> représente directement un
117 enregistrement de la table originale (la table indexée).
119 <li><em>Index de type II</em> : une entrée est un
120 couple <tt><k,rid></tt> où <tt>k</tt> est la clé
121 et <tt>rid</tt> est un pointeur vers l'enregistrement ayant
123 <li><em> Index de type III</em> : un
124 couple <tt><k,rid-list></tt> où <tt>k</tt> est la clé
125 et <tt>rid-list</tt> est une liste de pointeurs vers les enregistrements ayant
129 <div class="sws-slide">
130 <h1>Indexes groupants</h1>
131 <p>Un index est dit <em>groupant</em> si ses entrées sont triées
132 dans le même ordre que les enregistrement du fichier indexé. Il
133 est dit non-groupant dans le cas contraire</p>
134 <p>Les enregistrements de la table initiale ne
135 sont <s>jamais dupliqués</s>. On ne garde donc jamais un indexe
136 de type I en plus de la table initiale (on supprime cette
140 <div class="sws-slide">
141 <h1>Indexes denses</h1>
142 <p>Un index <em>dense</em> s'il contient une clé par
143 enregistrement et non dense sinon</p>
144 <p>Si une table possède un index <s>non-dense</s>, alors le
145 fichier de cette table est <em>toujours</em> trié selon la clé
146 d'index (sinon l'index ne sert à rien).</p>
148 <div class="sws-slide">
149 <h1>Autres propriétés</h1>
150 <p>Un index pour lequel la clé d'index contient <em>la clé
151 primaire</em> de la relation est appelé un
152 index <em>primaire</em>. Les autres indexes sont appelés
153 indexes <em>secondaires</em>
155 <p>Deux entrées d'index possédant la même clé sont
156 des <em>doublons</em>. Un index primaire ne contient pas de
162 <h1>Structures de données pour les indexes</h1>
163 <div class="sws-slide">
164 <h1>Différentes structures pour différents usages</h1>
165 <p>Outre le fichier <em>tas</em> un index peut avoir les
166 représentations internes suivantes:
168 <ul><li>Hash-index : l'index est organisé comme une table de
170 <li>Tree-index : l'index est organisé comme un arbre de
173 <li>Fichier trié : le fichier est trié selon une clé
174 particulière (i.e. l'ordre des enregistrements sur le disque
175 coïncide avec l'ordre de la clé d'index)
178 <p>On illustre sur une relation ayant le schéma <tt>Emp(Nom, Age, Salaire)</tt></p>
180 <div class="sws-slide">
181 <h1>Hash index (informel)</h1>
182 <p>Un hash index repose sur une <em>fonction de hash</em> <tt>h</tt>
184 <code class="centerbox">
187 où <tt>k</tt> est la clé d'index et <tt>@page</tt> est
188 l'adresse (sur le disque) de la page où se trouve
189 l'enregistrement associé à <tt>k</tt>
191 <p class="centerbox"><img class="sws-pause" style="width:80%" src="hash_index_simple.svg"/></p>
192 <p style="background:white" >Remarque: index de type I</p>
194 <div class="sws-slide">
195 <h1>Arbre B+ (informel)</h1>
196 <p>Arbre «n-aire» de recherche (avec n grand, généralement
198 <p class="centerbox"><img class="sws-pause" style="width:90%" src="btree_index_simple.svg"/></p>
199 <p style="background:white" >Remarque: index de type II, non groupant</p>
201 <div class="sws-slide">
202 <h1>Fichier trié</h1>
203 <p class="centerbox"><img class="sws-pause" style="width:90%" src="sorted_file_simple.svg"/></p>
204 <p style="background:white" >Remarque: index de type II, non groupant</p>
206 <div class="sws-slide">
207 <h1>Cas d'utilisation</h1>
209 <li>Hash-index : condition d'égalité (<tt>age=28 OR
211 <li>Arbre B+ : condition d'intervale (<tt>sal > 1000 AND sal
212 < 3000</tt>), condition de préfixe (<tt>nom LIKE
214 <li>Fichier trié : idem (plus compact mais
215 insertion/suppression plus difficile)</li>
218 <div class="sws-slide">
219 <h1>Coût des opérations 1/2</h1>
220 <p>On pose: <tt>B</tt> : nombre de pages de données <br/>
221 <tt>R</tt> : nombre d'enregistrements par page<br/>
222 <tt>D</tt> : temps moyen de transfert d'une page<br/>
223 On suppose des indexes de type I
227 <li>Parcours <tt>B * D</tt></li>
228 <li>Recherche <ul><li> 0 réponse <tt>B * D</tt></li>
229 <li> 1 réponse <tt>0.5 * B * D</tt> (en moyenne)</li>
230 <li> n réponses <tt>B * D</tt></li>
235 <div class="sws-slide">
236 <h1>Coût des opérations 2/2</h1>
239 <li>Recherche sur autre que clé de tri: <tt>B * D</tt></li>
240 <li>Recherche sur clé de tri : <tt>D*log<sub>2</sub>B + D*(#réponses/R)</tt></li>
244 <li>Recherche sur autre que clé de tri, ou recherche autre qu'égalité: <tt>B * D</tt></li>
245 <li>Recherche (egalité) sur clé de tri : <tt>D*2 + D*(#réponses/R)</tt></li>
249 <li>Recherche sur autre que clé de tri : <tt>D * log<sub>F</sub>B + B*D</tt></li>
250 <li>Recherche sur clé de tri : <tt>D*log<sub>F</sub>B + (#réponses/R)*D</tt></li>
253 <div class="sws-slide">
254 <h1>Clé composée</h1>
255 <p>Une clé d'index peut être composée de <em>plusieurs champs</em> de la
256 relation originale. <br/>
257 Si une clé est composée de <tt>(c<sub>1</sub>, …,
258 c<sub>n</sub>)</tt>, on peut l'utiliser pour toute requête
259 dont la valeur dépend de <em>tous</em> les <tt>i <= k</tt>,
260 pour <tt>k <=n</tt>.
262 <p>Supposons une clé composée sur <tt>(age,salaire)</tt>. On
263 peut l'utiliser pour <tt>age > 30</tt> ou pour <tt>age >30
264 AND salaire <4000</tt> mais pas pour <tt>salaire
265 <4000</tt> ou <tt>age >30 OR salaire <4000</tt>
269 <h1>Hash-index extensible</h1>
270 <div class="sws-slide">
271 <h1>Tables de hash classique (rappel)</h1>
272 <p>Table de hash classique = tableau de taille <tt>N</tt> contenant des listes
273 chaînées de valeurs (<i>bucket</i>). On calcule <tt>h(k) mod
274 N</tt> pour voir dans quel <i>bucket</i> insérer la nouvelle
275 valeur. Si un <i>bucket</i> devient trop grand, on double la
276 taille du tableau et on redistribue tous les contenus
279 <p>La redistribution est trop couteuse ici : on doit
280 scanner/écrire tout l'index. On souhaite ne toucher que le
281 tableau et le <i>bucket</i> trop grand, et pas les autres.
284 <div class="sws-slide">
285 <h1>Hash-index avec répertoire</h1>
286 <p>On n'utilise pas un simple tableau mais un tableau contenant
287 un masque binaire. On garde aussi un compteur de profondeur
288 globale et un compteur de profondeur local, pour
291 <p class="centerbox"><img style="width:60%" src="hash_index_01.svg"/></p>
293 <div class="sws-slide">
294 <h1>Insertion de 20</h1>
295 <p>On sépare le <i>bucket</i> plein en deux (100 vs 000)</p>
296 <p class="centerbox"><img style="width:50%" src="hash_index_02.svg"/></p>
298 <div class="sws-slide">
299 <h1>Insertion de 20</h1>
300 <p>On double la taille du répertoire et on augmente les
301 compteurs globaux et locaux</p>
302 <p class="centerbox"><img style="width:50%" src="hash_index_03.svg"/></p>
304 <div class="sws-slide">
305 <h1>Insertion de 20</h1>
306 <p>Le pointeur de 100 va vers le nouveau <i>bucket</i> les
307 autres vont vers les anciens</p>
308 <p class="centerbox"><img style="width:50%" src="hash_index_04.svg"/></p>
311 <div class="sws-slide">
313 <p>Un <em>Arbre B+</em> est un arbre «n-aire» dont les nœuds
314 peuvent contenir entre M et 2M valeurs (sauf la racine, qui a
315 entre 1 et 2M valeurs).</p>
316 <p>Les noeuds internes contiennent des valeurs et des pointeurs
318 <p>Les feuilles contiennent les valeurs finales, un pointeur
319 vers les données indexées et sont chaînées entre-elles </p>
320 <p>Exemple sur un noeud <em>d'ordre</em> 4 (i.e. entre 2 et 4
321 valeurs, 5 pointeurs vers les fils).</p>
322 <p>Arbre vide: <img src="btree_index_00.svg"/></p>
323 <p class="sws-pause">Insertion 4,19,22,39 <img src="btree_index_01.svg"/> (noeud plein)</p>
325 <div class="sws-slide">
326 <h1>Arbre B+ partage des feuilles</h1>
327 <p class="sws-pause">Insertion
328 25 <img style="vertical-align:middle" src="btree_index_02.svg"/><br/>
329 (partage du noeud, insertion
330 de 25, report de la plus petite valeur dans le parent, chaînage
332 <p class="sws-pause">Insertion
333 90 <img style="vertical-align:middle" src="btree_index_03.svg"/></p>
334 <p class="sws-pause">Insertion
335 95 <img style="vertical-align:middle" src="btree_index_04.svg"/>
338 <div class="sws-slide">
339 <h1>Arbre B+ partage des noeuds internes</h1>
340 <p class="centerbox sws-pause">
341 <img style="vertical-align:middle"
342 src="btree_index_05.svg"/></p>
343 <p> insertion de 54</p>
344 <p class="centerbox sws-pause">
345 <img style="vertical-align:middle"
346 src="btree_index_06.svg"/></p>
347 <p>Partage en 2 et insertion de la valeur mediane dans un
349 <p class="centerbox sws-pause">
350 <img style="vertical-align:middle"
351 src="btree_index_07.svg"/></p>
353 <div class="sws-slide">
354 <h1>Arbre B+ suppression</h1>
355 <p class="centerbox sws-pause">
356 <img style="vertical-align:middle"
357 src="btree_index_05.svg"/></p>
358 <p> suppression 95 (simple)</p>
359 <p class="centerbox sws-pause">
360 <img style="vertical-align:middle"
361 src="btree_index_08.svg"/></p>
362 <p> suppression 71 (utilisation des voisins) </p>
363 <p class="centerbox sws-pause">
364 <img style="vertical-align:middle"
365 src="btree_index_09.svg"/></p>
367 <div class="sws-slide">
368 <h1>Arbre B+ suppression (suite)</h1>
369 <p class="centerbox sws-pause">
370 <img style="vertical-align:middle"
371 src="btree_index_09.svg"/></p>
372 <p> suppression 19 (fusion des voisins, suppression de l'entrée
374 <p class="centerbox sws-pause">
375 <img style="vertical-align:middle"
376 src="btree_index_10.svg"/></p>
378 <div class="sws-slide">