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>Stockage</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="bd01.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 2 : Stockage</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>Où stocker les données ?</h1>
57 <p>Hierarchie mémoire : </p>
58 <table style="width:100%">
59 <tr><td style="width:20%">Type</td>
60 <td style="width:20%">Accès</td>
61 <td style="width:20%">Taille max</td>
62 <td style="width:20%">Coût</td>
63 <td style="width:20%">durée de vie</td></tr>
65 <td>Registre</td> <td> <tt><</tt> 1ns</td>
72 <td>Cache L1/2/3</td> <td> ~ 10 ns</td>
78 <td>RAM</td> <td> ~ 50 ns</td>
84 <td>Disque SSD </td> <td> ~ 0.1ms</td>
87 <td>Écritures limitées</td>
90 <td>Disque dur </td> <td> ~ 5ms</td>
97 <td>Bandes</td> <td> 10 s</td>
104 <ul><li>RAM : mémoire primaire</li>
105 <li>Disques : mémoire secondaire</li>
106 <li>Bandes magnétiques/Disques optiques : mémoire tertiaire</li>
109 <div class="sws-slide">
110 <h1>Quels types de mémoire pour une BD ?</h1>
111 <p>On attend en général d'une BD:</p>
112 <ul><li>Stockage d'un nombre important de données</li>
113 <li>Interrogation rapide (et si possible, mise à jour rapide
115 <li>Resistance aux pannes, aux corruptions</li>
118 <p>Celà implique l'utilisation de mémoire primaire (comme toutes
119 les applications) <em>et secondaire</em></p>
120 <p>Pas <em>d'adressage direct du disque</em> par le processeur, nécessité de
121 « monter » les données en RAM</p>
122 <p>Goulet d'étranglement : facteur 10 000 (SSD) ~ 100 000 (HDD) entre
123 mémoire et disques</p>
124 <p><s>Priorité des SGBD</s> (ce qu'on présente dans ce cours) :
125 limiter <em>les accès disque</em></p>
127 <h1>Aspects bas-niveau</h1>
128 <div class="sws-slide">
129 <h1>Caractéristiques physiques de disques</h1>
130 <p>Disques rotatifs:</p>
132 <img src="hdd.svg" style="margin-left:10%;width:50%;" alt="hdd"/>
134 <ul style="background:white"><li>Chaque plateau a deux faces</li>
135 <li>Un plateau est composé de pistes concentriques</li>
136 <li>Les pistes sont décomposées en secteurs</li>
137 <li>Une tête de lecture/écriture travaille secteur par
139 <li>Un secteur fait plusieurs octets (typiquement 512)</li>
140 <li>Un <i>cylindre</i> est l'ensemble des pistes situées à la
141 même positions sur tous les plateaux</li>
144 <div class="sws-slide">
145 <h1>Temps d'accès à un disque</h1>
146 <p>Accès à un secteur arbitraire :</p>
148 <li>Positionner la tête sur la bonne piste (recherche)</li>
149 <li>Attendre que le bon secteur soit sous la tête
151 <li>Parcourir le secteur et renvoyer les données en mémoire
154 <p>Tout cela constitue la <em>latence</em> du disque</p>
155 <p>Une fois qu'on a payé le temps de latence, lire le secteur
156 suivant ne demande que le temps de transfert</p>
157 <p>On va donc essayer d'organiser les données de manière éviter
158 les déplacements arbitraires</p>
160 <div class="sws-slide">
161 <h1>Unité de transfert</h1>
162 <p>On appelle <em>page</em> (ou <em>bloc</em>) la quantité de
163 mémoire que le disque dur transfert de manière atomique en
164 mémoire. En pratique 512o ~ 4ko (dépendant des disques).
166 <p>On doit lire/écrire <s>au moins une page</s> même si on ne
167 désir lire/écrire qu'un octet</p>
168 <p>Exemple : on souhaite stocker 5 chaines de caractères de 200o
169 chacunes sur le disque</p>
170 <ul><li>Si placés sur blocs différents (arbitraires) : 5 pages
171 montées en mémoire, <tt>5 * temps de latence</tt></li>
172 <li>Si placés sur deux blocs consécutifs : <tt>temps de
173 latence + temps de transfert</tt> (on gagne un facteur presque 5)
176 <div class="sws-slide">
177 <h1>Stratégies de placement</h1>
178 <p>On peut placer en priorité les données « reliées » (qu'on
179 veut utiliser en même temps):</p>
181 <li>Dans le même bloc (T.A. à la deuxième donnée:
183 <li>Sur deux blocs contigus (T.A. à la deuxième donnée:
185 <li>Bloc à la même position sur un autre plateau (T.A. à la
186 deuxième donnée: T. transfert)</li>
187 <li>Sur la même piste (T.A. à la deuxième donnée:
189 <li>Sur des pistes proches</li>
192 <div class="sws-slide">
193 <h1>Mise en place de la stratégies de placement</h1>
194 <p>Pour mettre en place les stratégies de placement il faut
196 <ul><li>La liste des blocs libres et occupés</li>
197 <li>La liste des blocs occupés par un « fichier » (i.e. qui
198 stocke des informations reliées à la même donnée logique)</li>
200 <p>On ne travaille pas page à page : on alloue
201 un <em>buffer</em> de pages</p>
202 <p ><table class="withborder" style="margin-left:20%;">
203 <tr><td style="width:10pt;">
204 P1 </td><td style="width:10pt">P132 </td><td style="width:10pt">
205 P10 </td><td style="width:10pt">P99 </td></tr>
206 <tr><td style="width:10pt">
207 P2 </td><td style="width:10pt"> P1000 </td><td style="width:10pt"> P507 </td><td style="width:10pt">
209 <tr><td style="width:10pt"> </td><td style="width:10pt"> </td><td style="width:10pt"> </td><td style="width:10pt">
212 On maintient pour chaque page : un <em>compteur
213 d'utilisation</em> et un <em>dirty-bit</em> qui indique si la
214 page a été modifiée (on doit donc l'écrire sur le disque à un
216 Lorsque le buffer est plein, il faut supprimer des pages (et
217 en monter d'autres en mémoire) suivant une stratégie:
218 LRU, MRU, Random, FIFO, LIFO, …
221 <div class="sws-slide">
222 <h1>Qui gère les accès disques bas-niveau, le buffer, … ?</h1>
225 <li class="sws-pause">Dans le temps, le SGBD
227 <li class="sws-pause">De nos jours, le système
228 d'exploitation via ses systèmes de fichiers et gestion de la
229 mémoire virtuelle (<i>swap</i> ou fichier d'echange)</li>
232 <p>Les systèmes d'exploitation ont <i>énormément</i> progressé
233 (les SGBD ne pouvaient pas reposer sur quelque chose d'aussi
234 primitif que FAT ou NTFS, mais les systèmes de fichier modernes
235 sont plus performant que le traitement natif du disque fais par
236 les SGBD, en particulier pour les SSD).<br/>
237 Pour prédire le bon comportement d'un SGBD il faut connaître
238 non seulement ce dernier, <s>mais aussi</s>, de manière
239 détaillée, les caractéristiques de l'OS et du système de
243 <div class="sws-slide">
244 <h1>Un mot sur les SSD</h1>
245 <p><i>Solid State Disk</i> : « disque » dur composé entièrement
246 de mémoire flash. Avantages:</p>
247 <ul style="sws-pause">
248 <li>Pas de temps de recherche et de rotation, uniquement temps
249 de transfert. Accès arbitraires aussi rapides que les
251 <li>Consomation électrique moindre, poid moindre, pas de
252 pièce mobile (resistance aux chocs)</li>
255 <li>Écriture <s>très</s> complexe (écrire dans une cellule
256 impose de l'effacer avant, nombre de cycle d'effaçage limité,
259 <li>Nécessite une coopération à tous les niveaux, seul le
260 système d'exploitation peut bien le gérer (bibliothèque
261 système, gestion de la mémoire virtuelle, système de fichier,
262 pilote du disque et <i>firmware</i>).</li>
265 <h1>Stockage pour les SGBD</h1>
266 <div class="sws-slide">
267 <h1>Utilisation du disque par les SGBD</h1>
269 <li>n-uplet (ou ligne) : enregistrement, séquence contiguë
271 <li>table = ensemble de lignes = fichier </li>
272 <li>base = ensemble de tables = ensemble de fichiers</li>
274 <p>Opérations de base sur les enregistrements</p>
275 <ul><li>recherche d'un enregistrement (<tt>SELECT</tt>)</li>
276 <li>ajout d'un enregistrement à une table
277 (<tt>INSERT</tt>)</li>
278 <li>mise à jour d'un enregistrement (<tt>UPDATE</tt>)</li>
279 <li>suppression d'un enregistrement (<tt>DELETE</tt>)</li>
281 <p>Les fichiers (i.e. les tables) sont <em>paginées</em>
282 (découpées en pages)</p>
284 <div class="sws-slide">
285 <h1>Représentation des enregistrements fixes</h1>
286 <ul><li>Nombre fixe d'attributs (schéma de la table)
288 <li>Champs de taille fixe
289 (<tt>VARCHAR[50]</tt>, <tt>INTEGER</tt> (32 bits), …)
293 <table style="margin-left:20pt;" class="withborder">
294 <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>
297 <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>
299 Pour accéder au i<sup>ème</sup> champ d'un enregistrement en
300 connaissant l'addresse de base <tt>B</tt>, on ajout à <tt>B</tt>
301 les longueurs des champs 0, 1, …, i-1.<br/>
302 adresse de C<sub>4</sub> = B + L<sub>1</sub> + L<sub>2</sub> + L<sub>3</sub><br/>
306 <div class="sws-slide">
307 <h1>Représentation des enregistrements variables</h1>
308 <ul><li>Nombre fixe d'attributs (schéma de la table)
310 <li>Champs de taille variables (<i>blobs</i> de texte)
314 <table style="margin-left:20pt;" class="withborder">
315 <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>
317 On utilise un séparateur spécial entre les champs (scan linéaire
318 pour arriver au i<sup>ème</sup> champ.<br/>
319 <table style="margin-left:20pt;" class="withborder">
320 <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>
322 On stocke les longueurs dans l'enregistrement
325 <div class="sws-slide">
326 <h1>Méta-données</h1>
327 <p>Chaque enregistrement possède un en-tête stockant des données
329 <ul><li>taille totale de l'enregistrement (avec entête)</li>
330 <li>pointeur vers le schéma de la table (pour déterminer les
331 tailles des champs)</li>
332 <li>date de dernière mise à jour</li>
333 <li>information de gestion des valeurs nulles:
334 <ul class="sws-pause">
335 <li>Stockage d'une valeur spéciale (pas toujours
337 <li>Stockage d'un bitmap (masque) : 26<sub>10</sub> =
338 11010<sub>2</sub> : valeur nulle dans les champ 0 et 2</li>
343 <div class="sws-slide">
344 <h1>Stockage des enregistrements dans une page </h1>
345 <p>Chaque enregistrement à une adresse (<i>rid</i> : record id)
346 constituée de l'adresse de la page et de la position de
347 l'enregistrement au sein de la page</p>
348 <p>Lors d'une insertion, on doit trouver un emplacement libre
350 <p>Lors d'une suppression, on doit « effacer » un emplacement
351 occupé et éventuellement compacter la page</p>
353 <div class="sws-slide">
354 <h1>Stockage compact vs non compact (taille fixe)</h1>
356 <img style="width:40%" src="page_comp.svg"/>
357 <img style="margin-left:10%;width:40%" src="page_ncomp.svg"/>
360 <div class="sws-slide">
361 <h1>Stockage compact (taille variable)</h1>
363 <img style="margin-left:10%;width:70%" src="page_var.svg"/>