--- /dev/null
+<?xml version="1.0" encoding="utf-8" ?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
+ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"
+[
+ <!ENTITY in "<small style='font-size:small'>∈</small>">
+ <!ENTITY notin "<small style='font-size:small'>∉</small>">
+ <!ENTITY mapsto "↦">
+]
+ >
+<html xmlns="http://www.w3.org/1999/xhtml" >
+ <head>
+ <title>Indexation</title>
+
+ <meta http-equiv="Content-Type"
+ content="text/html; charset=utf-8" />
+ <meta name="copyright"
+ content="Copyright © 2013 Kim Nguyễn" />
+
+ <!-- Load jQuery -->
+ <script src="../jquery-2.0.3.min.js" type="text/javascript" ></script>
+ <script src="../libs/raphael-min.js" type="text/javascript" ></script>
+ <!-- Load the library -->
+ <script src="../simpleWebSlides.js" type="text/javascript" ></script>
+
+ <link rel="stylesheet" href="../simpleWebSlides.css" type="text/css" media="all" />
+ <!-- Load a custom Theme, the class-element marks this style-sheet
+ a "theme" that can be swtiched dynamicaly -->
+ <link class="sws-theme" rel="stylesheet" title="U-Psud style" href="../themes/uPsud.css" type="text/css" />
+
+ <!-- Customize some templates and initialize -->
+
+ <script type="text/javascript">
+ SWS.Config['sws-slide-change'] = SWS.Effects.slideChangeFadeOutIn;
+ SWS.Config['sws-object-deactivate'] = SWS.Effects.objectDeactivateFadeOut;
+ SWS.Config['sws-object-activate'] = SWS.Effects.objectActivateFadeIn;
+
+ //Ensures that we load SWS at the very end, after MathJax has
+ //been initialized
+
+ $(window).load(SWS.Presentation.init);
+ </script>
+ </head>
+ <body>
+ <a href="bd02.xhtml" class="sws-previous"/>
+ <div class="sws-slide sws-cover sws-option-nofooter">
+ <h1>Bases de données</h1>
+ <h3>Polytech Paris-Sud</h3>
+ <h3>Apprentis 4<sup>ème</sup> année</h3>
+ <h1>Cours 3 : Indexation</h1>
+ <a href="mailto:kn@lri.fr">kn@lri.fr</a><br/>
+ <a href="http://www.lri.fr/~kn/">http://www.lri.fr/~kn</a>
+ </div>
+
+ <h1>Introduction</h1>
+ <div class="sws-slide">
+ <h1>Le fichier comme abstraction du support physique</h1>
+ <p>Le système et la couche physique exposent plusieurs notions
+ de bas niveau:</p>
+ <ul>
+ <li>Secteurs, pistes, plateau, …</li>
+ <li>Pages/blocs</li>
+ <li><i>Buffer</i> de lecture/écriture</li>
+ </ul>
+
+ <p>On souhaite proposer des <em>structures de données</em> et
+ <em>des algorithmes génériques</em> permettant d'implanter un
+ moteur d'exécution de requêtes (SQL).
+ </p>
+ <p>On abstrait les concepts bas niveau par la notion
+ de <em>fichier</em>. Un fichier un ensemble
+ d'<em>enregistrements</em>. Un enrigstrement contient des données
+ structurées en champs. En pratique, les fichiers sont <em>paginés</em></p>
+ </div>
+ <div class="sws-slide">
+ <h1>Opérations sur les fichiers</h1>
+ <p>La couche physique propose plusieurs opérations sur les
+ fichiers </p>
+ <ul>
+ <li>Création/suppression de fichier</li>
+ <li>Insertion/supression d'enregistrement</li>
+ <li>Accès au i<sup>ème</sup> enregistrement du fichier</li>
+ <li>Accès au i<sup>ème</sup> champ d'un enregistrement</li>
+ </ul>
+ <p>(cf. cours 2 pour les différentes manières d'implanter ces
+ opérations).<br/>
+ Une table est généralement représenté par un <em>fichier</em>
+ (au sens collection d'enregistrements)</p>
+ </div>
+ <div class="sws-slide">
+ <h1>Fichier simple</h1>
+ <p>La structure la plus simple pour un fichier est la structure
+ en <em>tas</em> (à 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.
+ </p>
+ <p>Rechercher un enregistrement particulier, en fonction d'un
+ critère sur son contenu (ex: <tt>id='5'</tt>) nécessite un
+ <em>parcours séquentiel du fichier</em> (scan)</p>
+ </div>
+ <h1>Types d'indexes</h1>
+ <div class="sws-slide">
+ <h1>Index</h1>
+ <p>Un index est un <em>fichier
+ auxiliaire</em>, <em>structuré</em> qui va rendre plus efficace
+ l'accès à certaines données, en fonction d'une <em>clé d'index</em>.
+ </p>
+ <p>Un enregistrement d'un index s'appelle une <em>entrée</em>
+ d'index. L'entrée associée à la clé <i>k</i> est
+ notée <i>k*</i> et contient suffisament d'information pour
+ retrouver le ou les enregistrements (de la table indexée)
+ associés à <i>k</i>. On distingue trois types d'indexes:
+ </p>
+ <ul><li><em>Index de type I</em> : <i>k*</i> représente directement un
+ enregistrement de la table originale (la table indexée).
+ </li>
+ <li><em>Index de type II</em> : une entrée est un
+ couple <tt><k,rid></tt> où <tt>k</tt> est la clé
+ et <tt>rid</tt> est un pointeur vers l'enregistrement ayant
+ cette clé</li>
+ <li><em> Index de type III</em> : un
+ couple <tt><k,rid-list></tt> où <tt>k</tt> est la clé
+ et <tt>rid-list</tt> est une liste de pointeurs vers les enregistrements ayant
+ cette clé</li>
+ </ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Indexes groupants</h1>
+ <p>Un index est dit <em>groupant</em> 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</p>
+ <p>Les enregistrements de la table initiale ne
+ sont <s>jamais dupliqués</s>. On ne garde donc jamais un indexe
+ de type I en plus de la table initiale (on supprime cette
+ dernière)
+ </p>
+ </div>
+ <div class="sws-slide">
+ <h1>Indexes denses</h1>
+ <p>Un index <em>dense</em> s'il contient une clé par
+ enregistrement et non dense sinon</p>
+ <p>Si une table possède un index <s>non-dense</s>, alors le
+ fichier de cette table est <em>toujours</em> trié selon la clé
+ d'index (sinon l'index ne sert à rien).</p>
+ </div>
+ <div class="sws-slide">
+ <h1>Autres propriétés</h1>
+ <p>Un index pour lequel la clé d'index contient <em>la clé
+ primaire</em> de la relation est appelé un
+ index <em>primaire</em>. Les autres indexes sont appelés
+ indexes <em>secondaires</em>
+ </p>
+ <p>Deux entrées d'index possédant la même clé sont
+ des <em>doublons</em>. Un index primaire ne contient pas de
+ doublon.
+ </p>
+ </div>
+
+
+ <h1>Structures de données pour les indexes</h1>
+ <div class="sws-slide">
+ <h1>Différentes structures pour différents usages</h1>
+ <p>Outre le fichier <em>tas</em> un index peut avoir les
+ représentations internes suivantes:
+ </p>
+ <ul><li>Hash-index : l'index est organisé comme une table de
+ hashage</li>
+ <li>Tree-index : l'index est organisé comme un arbre de
+ recherche
+ </li>
+ <li>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)
+ </li>
+ </ul>
+ <p>On illustre sur une relation ayant le schéma <tt>Emp(Nom, Age, Salaire)</tt></p>
+ </div>
+ <div class="sws-slide">
+ <h1>Hash index (informel)</h1>
+ <p>Un hash index repose sur une <em>fonction de hash</em> <tt>h</tt>
+ telle que:
+ <code class="centerbox">
+h(k) = @page
+</code>
+ où <tt>k</tt> est la clé d'index et <tt>@page</tt> est
+ l'adresse (sur le disque) de la page où se trouve
+ l'enregistrement associé à <tt>k</tt>
+ </p>
+ <p class="centerbox"><img class="sws-pause" style="width:80%" src="hash_index_simple.svg"/></p>
+ <p style="background:white" >Remarque: index de type I</p>
+ </div>
+ <div class="sws-slide">
+ <h1>Arbre B+ (informel)</h1>
+ <p>Arbre «n-aire» de recherche (avec n grand, généralement
+ 100)</p>
+ <p class="centerbox"><img class="sws-pause" style="width:90%" src="btree_index_simple.svg"/></p>
+ <p style="background:white" >Remarque: index de type II, non groupant</p>
+ </div>
+ <div class="sws-slide">
+ <h1>Fichier trié</h1>
+ <p class="centerbox"><img class="sws-pause" style="width:90%" src="sorted_file_simple.svg"/></p>
+ <p style="background:white" >Remarque: index de type II, non groupant</p>
+ </div>
+ <div class="sws-slide">
+ <h1>Cas d'utilisation</h1>
+ <ul>
+ <li>Hash-index : condition d'égalité (<tt>age=28 OR
+ age=46</tt>)</li>
+ <li>Arbre B+ : condition d'intervale (<tt>sal > 1000 AND sal
+ < 3000</tt>), condition de préfixe (<tt>nom LIKE
+ 'Jo%'</tt>) </li>
+ <li>Fichier trié : idem (plus compact mais
+ insertion/suppression plus difficile)</li>
+ </ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Coût des opérations 1/2</h1>
+ <p>On pose: <tt>B</tt> : nombre de pages de données <br/>
+ <tt>R</tt> : nombre d'enregistrements par page<br/>
+ <tt>D</tt> : temps moyen de transfert d'une page<br/>
+ On suppose des indexes de type I
+ </p>
+ <p>Fichier tas</p>
+ <ul>
+ <li>Parcours <tt>B * D</tt></li>
+ <li>Recherche <ul><li> 0 réponse <tt>B * D</tt></li>
+ <li> 1 réponse <tt>0.5 * B * D</tt> (en moyenne)</li>
+ <li> n réponses <tt>B * D</tt></li>
+ </ul>
+ </li>
+ </ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Coût des opérations 2/2</h1>
+ <p>Fichier trié</p>
+ <ul>
+ <li>Recherche sur autre que clé de tri: <tt>B * D</tt></li>
+ <li>Recherche sur clé de tri : <tt>D*log<sub>2</sub>B + (#réponses/R)</tt></li>
+ </ul>
+ <p>Hash index</p>
+ <ul>
+ <li>Recherche sur autre que clé de tri, ou recherche autre qu'égalité: <tt>B * D</tt></li>
+ <li>Recherche (egalité) sur clé de tri : <tt>2 + (#réponses/R)</tt></li>
+ </ul>
+ <p>Arbre B+</p>
+ <ul>
+ <li>Recherche sur autre que clé de tri : <tt>D * log<sub>F</sub>B + B*D</tt></li>
+ <li>Recherche sur clé de tri : <tt>D*log<sub>F</sub>B + (#réponses/R)</tt></li>
+ </ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Clé composée</h1>
+ <p>Une clé d'index peut être composée de <em>plusieurs champs</em> de la
+ relation originale. <br/>
+ Si une clé est composée de <tt>(c<sub>1</sub>, …,
+ c<sub>n</sub>)</tt>, on peut l'utiliser pour toute requête
+ dont la valeur dépend de <em>tous</em> les <tt>i <= k</tt>,
+ pour <tt>k <=n</tt>.
+ </p>
+ <p>Supposons une clé composée sur <tt>(age,salaire)</tt>. On
+ peut l'utiliser pour <tt>age > 30</tt> ou pour <tt>age >30
+ AND salaire <4000</tt> mais pas pour <tt>salaire
+ <4000</tt> ou <tt>age >30 OR salaire <4000</tt>
+ </p>
+
+ </div>
+ <h1>Hash-index extensible</h1>
+ <div class="sws-slide">
+ <h1>Tables de hash classique (rappel)</h1>
+ <p>Table de hash classique = tableau de taille <tt>N</tt> contenant des listes
+ chaînées de valeurs (<i>bucket</i>). On calcule <tt>h(k) mod
+ N</tt> pour voir dans quel <i>bucket</i> insérer la nouvelle
+ valeur. Si un <i>bucket</i> devient trop grand, on double la
+ taille du tableau et on redistribue tous les contenus
+ des <i>bucket</i>.
+ </p>
+ <p>La redistribution est trop couteuse ici : on doit
+ scanner/écrire tout l'index. On souhaite ne toucher que le
+ tableau et le <i>bucket</i> trop grand, et pas les autres.
+ </p>
+ </div>
+ <div class="sws-slide">
+ <h1>Hash-index avec répertoire</h1>
+ <p>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 <i>bucket</i>
+ </p>
+ <p class="centerbox"><img style="width:60%" src="hash_index_01.svg"/></p>
+ </div>
+ <div class="sws-slide">
+ <h1>Insertion de 20</h1>
+ <p>On sépare le <i>bucket</i> plein en deux (100 vs 000)</p>
+ <p class="centerbox"><img style="width:50%" src="hash_index_02.svg"/></p>
+ </div>
+ <div class="sws-slide">
+ <h1>Insertion de 20</h1>
+ <p>On double la taille du répertoire et on augmente les
+ compteurs globaux et locaux</p>
+ <p class="centerbox"><img style="width:50%" src="hash_index_03.svg"/></p>
+ </div>
+ <div class="sws-slide">
+ <h1>Insertion de 20</h1>
+ <p>Le pointeur de 100 va vers le nouveau <i>bucket</i> les
+ autres vont vers les anciens</p>
+ <p class="centerbox"><img style="width:50%" src="hash_index_04.svg"/></p>
+ </div>
+ <h1>Arbre B+</h1>
+ <div class="sws-slide">
+ <h1>Arbre B+</h1>
+ <p>Un <em>Arbre B+</em> 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).</p>
+ <p>Les noeuds internes contiennent des valeurs et des pointeurs
+ vers les fils.</p>
+ <p>Les feuilles contiennent les valeurs finales, un pointeur
+ vers les données indexées et sont chaînées entre-elles </p>
+ <p>Exemple sur un noeud <em>d'ordre</em> 4 (i.e. entre 2 et 4
+ valeurs, 5 pointeurs vers les fils).</p>
+ <p>Arbre vide: <img src="btree_index_00.svg"/></p>
+ <p class="sws-pause">Insertion 4,19,22,39 <img src="btree_index_01.svg"/> (noeud plein)</p>
+ </div>
+ <div class="sws-slide">
+ <h1>Arbre B+ partage des feuilles</h1>
+ <p class="sws-pause">Insertion
+ 25 <img style="vertical-align:middle" src="btree_index_02.svg"/><br/>
+ (partage du noeud, insertion
+ de 25, report de la plus petite valeur dans le parent, chaînage
+ des feuilles) </p>
+ <p class="sws-pause">Insertion
+ 90 <img style="vertical-align:middle" src="btree_index_03.svg"/></p>
+ <p class="sws-pause">Insertion
+ 95 <img style="vertical-align:middle" src="btree_index_04.svg"/>
+ </p>
+ </div>
+ <div class="sws-slide">
+ <h1>Arbre B+ partage des noeuds internes</h1>
+ <p class="centerbox sws-pause">
+ <img style="vertical-align:middle"
+ src="btree_index_05.svg"/></p>
+ <p> insertion de 54</p>
+ <p class="centerbox sws-pause">
+ <img style="vertical-align:middle"
+ src="btree_index_06.svg"/></p>
+ <p>Partage en 2 et insertion de la valeur mediane dans un
+ nouveau parent</p>
+ <p class="centerbox sws-pause">
+ <img style="vertical-align:middle"
+ src="btree_index_07.svg"/></p>
+ </div>
+ <div class="sws-slide">
+ <h1>Arbre B+ suppression</h1>
+ <p class="centerbox sws-pause">
+ <img style="vertical-align:middle"
+ src="btree_index_05.svg"/></p>
+ <p> suppression 95 (simple)</p>
+ <p class="centerbox sws-pause">
+ <img style="vertical-align:middle"
+ src="btree_index_08.svg"/></p>
+ <p> suppression 71 (utilisation des voisins) </p>
+ <p class="centerbox sws-pause">
+ <img style="vertical-align:middle"
+ src="btree_index_09.svg"/></p>
+ </div>
+ <div class="sws-slide">
+ <h1>Arbre B+ suppression (suite)</h1>
+ <p class="centerbox sws-pause">
+ <img style="vertical-align:middle"
+ src="btree_index_09.svg"/></p>
+ <p> suppression 19 (fusion des voisins, suppression de l'entrée
+ dans le parent)</p>
+ <p class="centerbox sws-pause">
+ <img style="vertical-align:middle"
+ src="btree_index_10.svg"/></p>
+ </div>
+ <div class="sws-slide">
+
+ </div>
+ </body>
+</html>
projects / hacks / simpleWebSlides.git / commitdiff