bd/bd03.xhtml

   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"
   4 [
   5           <!ENTITY in  "<small style='font-size:small'>∈</small>">
   6           <!ENTITY notin  "<small style='font-size:small'>∉</small>">
   7           <!ENTITY mapsto  "↦">
   8 ]
   9           >
  10 <html xmlns="http://www.w3.org/1999/xhtml" >
  11   <head>
  12     <title>Indexation</title>
  13
  14     <meta http-equiv="Content-Type"
  15           content="text/html; charset=utf-8" />
  16     <meta name="copyright"
  17           content="Copyright &#169; 2013 Kim Nguyễn" />
  18
  19     <!-- Load jQuery -->
  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>
  24
  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" />
  29
  30     <!-- Customize some templates and initialize -->
  31
  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;
  36
  37       //Ensures that we load SWS at the very end, after MathJax has
  38       //been initialized
  39
  40       $(window).load(SWS.Presentation.init);
  41     </script>
  42   </head>
  43   <body>
  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>
  52     </div>
  53
  54     <h1>Introduction</h1>
  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
  58       de bas niveau:</p>
  59       <ul>
  60         <li>Secteurs, pistes, plateau, …</li>
  61         <li>Pages/blocs</li>
  62         <li><i>Buffer</i> de lecture/écriture</li>
  63       </ul>
  64
  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).
  68       </p>
  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>
  73     </div>
  74     <div class="sws-slide">
  75       <h1>Opérations sur les fichiers</h1>
  76       <p>La couche physique propose plusieurs opérations sur les
  77       fichiers </p>
  78       <ul>
  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>
  83       </ul>
  84       <p>(cf. cours 2 pour les différentes manières d'implanter ces
  85       opérations).<br/>
  86       Une table est généralement représenté par un <em>fichier</em>
  87       (au sens collection d'enregistrements)</p>
  88     </div>
  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.
  98       </p>
  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>
 102     </div>
 103     <h1>Types d'indexes</h1>
 104     <div class="sws-slide">
 105       <h1>Index</h1>
 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>.
 109       </p>
 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:
 115       </p>
 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).
 118         </li>
 119         <li><em>Index de type II</em> : une entrée est un
 120         couple <tt>&lt;k,rid&gt;</tt> où <tt>k</tt> est la clé
 121         et <tt>rid</tt> est un pointeur vers l'enregistrement ayant
 122         cette clé</li>
 123         <li><em> Index de type III</em> :  un
 124         couple <tt>&lt;k,rid-list&gt;</tt> où <tt>k</tt> est la clé
 125         et <tt>rid-list</tt> est une liste de pointeurs vers les enregistrements ayant
 126           cette clé</li>
 127         </ul>
 128     </div>
 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
 137         dernière)
 138       </p>
 139     </div>
 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>
 147     </div>
 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>
 154       </p>
 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
 157         doublon.
 158       </p>
 159     </div>
 160
 161
 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:
 167       </p>
 168       <ul><li>Hash-index : l'index est organisé comme une table de
 169       hashage</li>
 170         <li>Tree-index : l'index est organisé comme un arbre de
 171         recherche
 172         </li>
 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)
 176         </li>
 177       </ul>
 178       <p>On illustre sur une relation ayant le schéma <tt>Emp(Nom, Age, Salaire)</tt></p>
 179     </div>
 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>
 183       telle que:
 184         <code class="centerbox">
 185 h(k) = @page
 186 </code>
 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>
 190       </p>
 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>
 193     </div>
 194     <div class="sws-slide">
 195       <h1>Arbre B+ (informel)</h1>
 196       <p>Arbre «n-aire» de recherche (avec n grand, généralement
 197       100)</p>
 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>
 200     </div>
 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>
 205     </div>
 206     <div class="sws-slide">
 207       <h1>Cas d'utilisation</h1>
 208       <ul>
 209         <li>Hash-index : condition d'égalité (<tt>age=28 OR
 210         age=46</tt>)</li>
 211         <li>Arbre B+ : condition d'intervale (<tt>sal &gt; 1000 AND sal
 212         &lt; 3000</tt>), condition de préfixe (<tt>nom LIKE
 213         'Jo%'</tt>) </li>
 214         <li>Fichier trié : idem (plus compact mais
 215         insertion/suppression plus difficile)</li>
 216       </ul>
 217     </div>
 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
 224       </p>
 225       <p>Fichier tas</p>
 226       <ul>
 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>
 231           </ul>
 232         </li>
 233       </ul>
 234     </div>
 235     <div class="sws-slide">
 236       <h1>Coût des opérations 2/2</h1>
 237       <p>Fichier trié</p>
 238       <ul>
 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 + (#réponses/R)</tt></li>
 241       </ul>
 242       <p>Hash index</p>
 243       <ul>
 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>2 + (#réponses/R)</tt></li>
 246       </ul>
 247       <p>Arbre B+</p>
 248       <ul>
 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)</tt></li>
 251       </ul>
 252     </div>
 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 &lt;= k</tt>,
 260         pour <tt>k &lt;=n</tt>.
 261       </p>
 262       <p>Supposons une clé composée sur <tt>(age,salaire)</tt>. On
 263       peut l'utiliser pour <tt>age &gt; 30</tt> ou pour <tt>age &gt;30
 264       AND salaire &lt;4000</tt> mais pas pour <tt>salaire
 265       &lt;4000</tt> ou <tt>age &gt;30 OR salaire &lt;4000</tt>
 266       </p>
 267
 268     </div>
 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
 277         des <i>bucket</i>.
 278       </p>
 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.
 282       </p>
 283     </div>
 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
 289         chaque <i>bucket</i>
 290       </p>
 291       <p class="centerbox"><img style="width:60%" src="hash_index_01.svg"/></p>
 292     </div>
 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>
 297     </div>
 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>
 303     </div>
 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>
 309     </div>
 310     <h1>Arbre B+</h1>
 311     <div class="sws-slide">
 312       <h1>Arbre B+</h1>
 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
 317       vers les fils.</p>
 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>
 324     </div>
 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
 331         des feuilles) </p>
 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"/>
 336       </p>
 337     </div>
 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
 348       nouveau parent</p>
 349       <p class="centerbox sws-pause">
 350         <img style="vertical-align:middle"
 351         src="btree_index_07.svg"/></p>
 352     </div>
 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>
 366     </div>
 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
 373       dans le parent)</p>
 374       <p class="centerbox sws-pause">
 375         <img style="vertical-align:middle"
 376         src="btree_index_10.svg"/></p>
 377     </div>
 378     <div class="sws-slide">
 379
 380     </div>
 381   </body>
 382 </html>