--- /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>Stockage</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="bd01.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 2 : Stockage</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>Où stocker les données ?</h1>
+ <p>Hierarchie mémoire : </p>
+ <table style="width:100%">
+ <tr><td style="width:20%">Type</td>
+ <td style="width:20%">Accès</td>
+ <td style="width:20%">Taille max</td>
+ <td style="width:20%">Coût</td>
+ <td style="width:20%">durée de vie</td></tr>
+ <tr>
+ <td>Registre</td> <td> <tt><</tt> 1ns</td>
+ <td>128 bits</td>
+ <td>Très cher</td>
+ <td>alimenté</td>
+ </tr>
+
+ <tr>
+ <td>Cache L1/2/3</td> <td> ~ 10 ns</td>
+ <td>1ko ~ 1Mo</td>
+ <td>Très cher</td>
+ <td>alimenté</td>
+ </tr>
+ <tr>
+ <td>RAM</td> <td> ~ 50 ns</td>
+ <td>10 Go </td>
+ <td>Cher</td>
+ <td>alimenté</td>
+ </tr>
+ <tr>
+ <td>Disque SSD </td> <td> ~ 0.1ms</td>
+ <td>1 To </td>
+ <td>- Cher</td>
+ <td>Écritures limitées</td>
+ </tr>
+ <tr>
+ <td>Disque dur </td> <td> ~ 5ms</td>
+ <td>10 To </td>
+ <td>Peu cher</td>
+ <td>Fragiles</td>
+ </tr>
+
+ <tr>
+ <td>Bandes</td> <td> 10 s</td>
+ <td>1 Po/Eo </td>
+ <td>Donné</td>
+ <td>Bonne</td>
+ </tr>
+ </table>
+
+ <ul><li>RAM : mémoire primaire</li>
+ <li>Disques : mémoire secondaire</li>
+ <li>Bandes magnétiques/Disques optiques : mémoire tertiaire</li>
+ </ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Quels types de mémoire pour une BD ?</h1>
+ <p>On attend en général d'une BD:</p>
+ <ul><li>Stockage d'un nombre important de données</li>
+ <li>Interrogation rapide (et si possible, mise à jour rapide
+ aussi)</li>
+ <li>Resistance aux pannes, aux corruptions</li>
+ <li>…</li>
+ </ul>
+ <p>Celà implique l'utilisation de mémoire primaire (comme toutes
+ les applications) <em>et secondaire</em></p>
+ <p>Pas <em>d'adressage direct du disque</em> par le processeur, nécessité de
+ « monter » les données en RAM</p>
+ <p>Goulet d'étranglement : facteur 10 000 (SSD) ~ 100 000 (HDD) entre
+ mémoire et disques</p>
+ <p><s>Priorité des SGBD</s> (ce qu'on présente dans ce cours) :
+ limiter <em>les accès disque</em></p>
+ </div>
+ <h1>Aspects bas-niveau</h1>
+ <div class="sws-slide">
+ <h1>Caractéristiques physiques de disques</h1>
+ <p>Disques rotatifs:</p>
+ <div>
+ <img src="hdd.svg" style="margin-left:10%;width:50%;" alt="hdd"/>
+ </div>
+ <ul style="background:white"><li>Chaque plateau a deux faces</li>
+ <li>Un plateau est composé de pistes concentriques</li>
+ <li>Les pistes sont décomposées en secteurs</li>
+ <li>Une tête de lecture/écriture travaille secteur par
+ secteur</li>
+ <li>Un secteur fait plusieurs octets (typiquement 512)</li>
+ <li>Un <i>cylindre</i> est l'ensemble des pistes situées à la
+ même positions sur tous les plateaux</li>
+ </ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Temps d'accès à un disque</h1>
+ <p>Accès à un secteur arbitraire :</p>
+ <ul>
+ <li>Positionner la tête sur la bonne piste (recherche)</li>
+ <li>Attendre que le bon secteur soit sous la tête
+ (rotation)</li>
+ <li>Parcourir le secteur et renvoyer les données en mémoire
+ (transfert)</li>
+ </ul>
+ <p>Tout cela constitue la <em>latence</em> du disque</p>
+ <p>Une fois qu'on a payé le temps de latence, lire le secteur
+ suivant ne demande que le temps de transfert</p>
+ <p>On va donc essayer d'organiser les données de manière éviter
+ les déplacements arbitraires</p>
+ </div>
+ <div class="sws-slide">
+ <h1>Unité de transfert</h1>
+ <p>On appelle <em>page</em> (ou <em>bloc</em>) la quantité de
+ mémoire que le disque dur transfert de manière atomique en
+ mémoire. En pratique 512o ~ 4ko (dépendant des disques).
+ </p>
+ <p>On doit lire/écrire <s>au moins une page</s> même si on ne
+ désir lire/écrire qu'un octet</p>
+ <p>Exemple : on souhaite stocker 5 chaines de caractères de 200o
+ chacunes sur le disque</p>
+ <ul><li>Si placés sur blocs différents (arbitraires) : 5 pages
+ montées en mémoire, <tt>5 * temps de latence</tt></li>
+ <li>Si placés sur deux blocs consécutifs : <tt>temps de
+ latence + temps de transfert</tt> (on gagne un facteur presque 5)
+ </li></ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Stratégies de placement</h1>
+ <p>On peut placer en priorité les données « reliées » (qu'on
+ veut utiliser en même temps):</p>
+ <ol>
+ <li>Dans le même bloc (T.A. à la deuxième donnée:
+ 0)</li>
+ <li>Sur deux blocs contigus (T.A. à la deuxième donnée:
+ T. transfert)</li>
+ <li>Bloc à la même position sur un autre plateau (T.A. à la
+ deuxième donnée: T. transfert)</li>
+ <li>Sur la même piste (T.A. à la deuxième donnée:
+ T. rotation)</li>
+ <li>Sur des pistes proches</li>
+ </ol>
+ </div>
+ <div class="sws-slide">
+ <h1>Mise en place de la stratégies de placement</h1>
+ <p>Pour mettre en place les stratégies de placement il faut
+ connaître:</p>
+ <ul><li>La liste des blocs libres et occupés</li>
+ <li>La liste des blocs occupés par un « fichier » (i.e. qui
+ stocke des informations reliées à la même donnée logique)</li>
+ </ul>
+ <p>On ne travaille pas page à page : on alloue
+ un <em>buffer</em> de pages</p>
+ <p ><table class="withborder" style="margin-left:20%;">
+ <tr><td style="width:10pt;">
+ P1 </td><td style="width:10pt">P132 </td><td style="width:10pt">
+ P10 </td><td style="width:10pt">P99 </td></tr>
+ <tr><td style="width:10pt">
+ P2 </td><td style="width:10pt"> P1000 </td><td style="width:10pt"> P507 </td><td style="width:10pt">
+ </td></tr>
+ <tr><td style="width:10pt"> </td><td style="width:10pt"> </td><td style="width:10pt"> </td><td style="width:10pt">
+ </td></tr>
+ </table><br/>
+ On maintient pour chaque page : un <em>compteur
+ d'utilisation</em> et un <em>dirty-bit</em> qui indique si la
+ page a été modifiée (on doit donc l'écrire sur le disque à un
+ moment donné).<br/>
+ Lorsque le buffer est plein, il faut supprimer des pages (et
+ en monter d'autres en mémoire) suivant une stratégie:
+ LRU, MRU, Random, FIFO, LIFO, …
+ </p>
+ </div>
+ <div class="sws-slide">
+ <h1>Qui gère les accès disques bas-niveau, le buffer, … ?</h1>
+ <p>
+ <ul>
+ <li class="sws-pause">Dans le temps, le SGBD
+ directement </li>
+ <li class="sws-pause">De nos jours, le système
+ d'exploitation via ses systèmes de fichiers et gestion de la
+ mémoire virtuelle (<i>swap</i> ou fichier d'echange)</li>
+ </ul>
+ </p>
+ <p>Les systèmes d'exploitation ont <i>énormément</i> progressé
+ (les SGBD ne pouvaient pas reposer sur quelque chose d'aussi
+ primitif que FAT ou NTFS, mais les systèmes de fichier modernes
+ sont plus performant que le traitement natif du disque fais par
+ les SGBD, en particulier pour les SSD).<br/>
+ Pour prédire le bon comportement d'un SGBD il faut connaître
+ non seulement ce dernier, <s>mais aussi</s>, de manière
+ détaillée, les caractéristiques de l'OS et du système de
+ fichier.
+ </p>
+ </div>
+ <div class="sws-slide">
+ <h1>Un mot sur les SSD</h1>
+ <p><i>Solid State Disk</i> : « disque » dur composé entièrement
+ de mémoire flash. Avantages:</p>
+ <ul style="sws-pause">
+ <li>Pas de temps de recherche et de rotation, uniquement temps
+ de transfert. Accès arbitraires aussi rapides que les
+ séquentiels</li>
+ <li>Consomation électrique moindre, poid moindre, pas de
+ pièce mobile (resistance aux chocs)</li>
+ </ul>
+ <ul><li>Couteux</li>
+ <li>Écriture <s>très</s> complexe (écrire dans une cellule
+ impose de l'effacer avant, nombre de cycle d'effaçage limité,
+ etc)
+ </li>
+ <li>Nécessite une coopération à tous les niveaux, seul le
+ système d'exploitation peut bien le gérer (bibliothèque
+ système, gestion de la mémoire virtuelle, système de fichier,
+ pilote du disque et <i>firmware</i>).</li>
+ </ul>
+ </div>
+ <h1>Stockage pour les SGBD</h1>
+ <div class="sws-slide">
+ <h1>Utilisation du disque par les SGBD</h1>
+ <ul>
+ <li>n-uplet (ou ligne) : enregistrement, séquence contiguë
+ d'octets </li>
+ <li>table = ensemble de lignes = fichier </li>
+ <li>base = ensemble de tables = ensemble de fichiers</li>
+ </ul>
+ <p>Opérations de base sur les enregistrements</p>
+ <ul><li>recherche d'un enregistrement (<tt>SELECT</tt>)</li>
+ <li>ajout d'un enregistrement à une table
+ (<tt>INSERT</tt>)</li>
+ <li>mise à jour d'un enregistrement (<tt>UPDATE</tt>)</li>
+ <li>suppression d'un enregistrement (<tt>DELETE</tt>)</li>
+ </ul>
+ <p>Les fichiers (i.e. les tables) sont <em>paginées</em>
+ (découpées en pages)</p>
+ </div>
+ <div class="sws-slide">
+ <h1>Représentation des enregistrements fixes</h1>
+ <ul><li>Nombre fixe d'attributs (schéma de la table)
+ </li>
+ <li>Champs de taille fixe
+ (<tt>VARCHAR[50]</tt>, <tt>INTEGER</tt> (32 bits), …)
+ </li>
+ </ul>
+ <p>
+ <table style="margin-left:20pt;" class="withborder">
+ <tr><td>C<sub>1</sub></td> <td>C<sub>2</sub></td> <td>C<sub>3</sub></td> <td>C<sub>4</sub></td> <td>C<sub>5</sub></td></tr>
+ </table>
+ <table >
+ <tr><td>B</td><td> L<sub>1</sub></td> <td> L<sub>2</sub></td> <td> L<sub>3</sub></td> <td> L<sub>4</sub></td> <td> L<sub>5</sub></td></tr>
+ </table> <br/>
+Pour accéder au i<sup>ème</sup> champ d'un enregistrement en
+ connaissant l'addresse de base <tt>B</tt>, on ajout à <tt>B</tt>
+ les longueurs des champs 0, 1, …, i-1.<br/>
+ adresse de C<sub>4</sub> = B + L<sub>1</sub> + L<sub>2</sub> + L<sub>3</sub><br/>
+ </p>
+ </div>
+
+ <div class="sws-slide">
+ <h1>Représentation des enregistrements variables</h1>
+ <ul><li>Nombre fixe d'attributs (schéma de la table)
+ </li>
+ <li>Champs de taille variables (<i>blobs</i> de texte)
+ </li>
+ </ul>
+ <p>
+ <table style="margin-left:20pt;" class="withborder">
+ <tr><td>C<sub>1</sub></td> <td>$</td><td>C<sub>2</sub></td> <td>$</td> <td>C<sub>3</sub></td> <td>$</td><td>C<sub>4</sub></td><td>$</td> <td>C<sub>5</sub></td></tr>
+ </table>
+ On utilise un séparateur spécial entre les champs (scan linéaire
+ pour arriver au i<sup>ème</sup> champ.<br/>
+ <table style="margin-left:20pt;" class="withborder">
+ <tr><td>L<sub>1</sub></td> <td>L<sub>2</sub></td> <td>L<sub>3</sub></td> <td>L<sub>4</sub></td> <td>L<sub>5</sub></td><td>C<sub>1</sub></td> <td>C<sub>2</sub></td> <td>C<sub>3</sub></td> <td>C<sub>4</sub></td> <td>C<sub>5</sub></td></tr>
+ </table>
+ On stocke les longueurs dans l'enregistrement
+ </p>
+ </div>
+ <div class="sws-slide">
+ <h1>Méta-données</h1>
+ <p>Chaque enregistrement possède un en-tête stockant des données
+ auxiliaires</p>
+ <ul><li>taille totale de l'enregistrement (avec entête)</li>
+ <li>pointeur vers le schéma de la table (pour déterminer les
+ tailles des champs)</li>
+ <li>date de dernière mise à jour</li>
+ <li>information de gestion des valeurs nulles:
+ <ul class="sws-pause">
+ <li>Stockage d'une valeur spéciale (pas toujours
+ possible)</li>
+ <li>Stockage d'un bitmap (masque) : 26<sub>10</sub> =
+ 11010<sub>2</sub> : valeur nulle dans les champ 0 et 2</li>
+ </ul>
+ </li>
+ </ul>
+ </div>
+ <div class="sws-slide">
+ <h1>Stockage des enregistrements dans une page </h1>
+ <p>Chaque enregistrement à une adresse (<i>rid</i> : record id)
+ constituée de l'adresse de la page et de la position de
+ l'enregistrement au sein de la page</p>
+ <p>Lors d'une insertion, on doit trouver un emplacement libre
+ dans la page</p>
+ <p>Lors d'une suppression, on doit « effacer » un emplacement
+ occupé et éventuellement compacter la page</p>
+ </div>
+ <div class="sws-slide">
+ <h1>Stockage compact vs non compact (taille fixe)</h1>
+ <p>
+ <img style="width:40%" src="page_comp.svg"/>
+ <img style="margin-left:10%;width:40%" src="page_ncomp.svg"/>
+ </p>
+ </div>
+ <div class="sws-slide">
+ <h1>Stockage compact (taille variable)</h1>
+ <p>
+ <img style="margin-left:10%;width:70%" src="page_var.svg"/>
+ </p>
+ </div>
+ </body>
+</html>
projects / hacks / simpleWebSlides.git / blobdiff