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). Une
165 page fait <em>au moins un secteur</em>. De plus, une page ne
166 peut pas déborder sur <em>plus d'une piste</em>.
168 <p>On doit lire/écrire <s>au moins une page</s> même si on ne
169 veut lire/écrire qu'un octet</p>
170 <p>Exemple : on souhaite stocker 5 chaines de caractères de 200o
171 chacunes sur le disque</p>
172 <ul><li>Si placés sur blocs différents (arbitraires) : 5 pages
173 montées en mémoire, <tt>5 * temps de latence</tt></li>
174 <li>Si placés sur deux blocs consécutifs : <tt>temps de
175 latence + temps de transfert</tt> (on gagne un facteur 5)
178 <div class="sws-slide">
179 <h1>Stratégies de placement</h1>
180 <p>On peut placer en priorité les données « reliées » (qu'on
181 veut utiliser en même temps):</p>
183 <li>Dans le même bloc (T.A. à la deuxième donnée:
185 <li>Sur deux blocs contigus (T.A. à la deuxième donnée:
187 <li>Bloc à la même position sur un autre plateau (T.A. à la
188 deuxième donnée: T. transfert)</li>
189 <li>Sur la même piste (T.A. à la deuxième donnée:
191 <li>Sur des pistes proches</li>
194 <div class="sws-slide">
195 <h1>Mise en place de la stratégies de placement</h1>
196 <p>Pour mettre en place les stratégies de placement il faut
198 <ul><li>La liste des blocs libres et occupés</li>
199 <li>La liste des blocs occupés par un « fichier » (i.e. qui
200 stocke des informations reliées à la même donnée logique)</li>
202 <p>On ne travaille pas page à page : on alloue
203 un <em>buffer</em> de pages</p>
204 <p ><table class="withborder" style="margin-left:20%;">
205 <tr><td style="width:10pt;">
206 P1 </td><td style="width:10pt">P132 </td><td style="width:10pt">
207 P10 </td><td style="width:10pt">P99 </td></tr>
208 <tr><td style="width:10pt">
209 P2 </td><td style="width:10pt"> P1000 </td><td style="width:10pt"> P507 </td><td style="width:10pt">
211 <tr><td style="width:10pt"> </td><td style="width:10pt"> </td><td style="width:10pt"> </td><td style="width:10pt">
214 On maintient pour chaque page : un <em>compteur
215 d'utilisation</em> et un <em>dirty-bit</em> qui indique si la
216 page a été modifiée (on doit donc l'écrire sur le disque à un
218 Lorsque le buffer est plein, il faut supprimer des pages (et
219 en monter d'autres en mémoire) suivant une stratégie:
220 LRU, MRU, Random, FIFO, LIFO, …
223 <div class="sws-slide">
224 <h1>Qui gère les accès disques bas-niveau, le buffer, … ?</h1>
227 <li class="sws-pause">Dans le temps, le SGBD
229 <li class="sws-pause">De nos jours, le système
230 d'exploitation via ses systèmes de fichiers et gestion de la
231 mémoire virtuelle (<i>swap</i> ou fichier d'echange)</li>
234 <p>Les systèmes d'exploitation ont <i>énormément</i> progressé
235 (les SGBD ne pouvaient pas reposer sur quelque chose d'aussi
236 primitif que FAT ou NTFS, mais les systèmes de fichier modernes
237 sont plus performant que le traitement natif du disque fais par
238 les SGBD, en particulier pour les SSD).<br/>
239 Pour prédire le bon comportement d'un SGBD il faut connaître
240 non seulement ce dernier, <s>mais aussi</s>, de manière
241 détaillée, les caractéristiques de l'OS et du système de
245 <div class="sws-slide">
246 <h1>Un mot sur les SSD</h1>
247 <p><i>Solid State Disk</i> : « disque » dur composé entièrement
248 de mémoire flash. Avantages:</p>
249 <ul style="sws-pause">
250 <li>Pas de temps de recherche et de rotation, uniquement temps
251 de transfert. Accès arbitraires aussi rapides que les
253 <li>Consomation électrique moindre, poid moindre, pas de
254 pièce mobile (resistance aux chocs)</li>
257 <li>Écriture <s>très</s> complexe (écrire dans une cellule
258 impose de l'effacer avant, nombre de cycle d'effaçage limité,
261 <li>Nécessite une coopération à tous les niveaux, seul le
262 système d'exploitation peut bien le gérer (bibliothèque
263 système, gestion de la mémoire virtuelle, système de fichier,
264 pilote du disque et <i>firmware</i>).</li>
267 <h1>Stockage pour les SGBD</h1>
268 <div class="sws-slide">
269 <h1>Utilisation du disque par les SGBD</h1>
271 <li>n-uplet (ou ligne) : enregistrement, séquence contiguë
273 <li>table = ensemble de lignes = fichier </li>
274 <li>base = ensemble de tables = ensemble de fichiers</li>
276 <p>Opérations de base sur les enregistrements</p>
277 <ul><li>recherche d'un enregistrement (<tt>SELECT</tt>)</li>
278 <li>ajout d'un enregistrement à une table
279 (<tt>INSERT</tt>)</li>
280 <li>mise à jour d'un enregistrement (<tt>UPDATE</tt>)</li>
281 <li>suppression d'un enregistrement (<tt>DELETE</tt>)</li>
283 <p>Les fichiers (i.e. les tables) sont <em>paginées</em>
284 (découpées en pages)</p>
286 <div class="sws-slide">
287 <h1>Représentation des enregistrements fixes</h1>
288 <ul><li>Nombre fixe d'attributs (schéma de la table)
290 <li>Champs de taille fixe
291 (<tt>VARCHAR[50]</tt>, <tt>INTEGER</tt> (32 bits), …)
295 <table style="margin-left:20pt;" class="withborder">
296 <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>
299 <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>
301 Pour accéder au i<sup>ème</sup> champ d'un enregistrement en
302 connaissant l'addresse de base <tt>B</tt>, on ajout à <tt>B</tt>
303 les longueurs des champs 0, 1, …, i-1.<br/>
304 adresse de C<sub>4</sub> = B + L<sub>1</sub> + L<sub>2</sub> + L<sub>3</sub><br/>
308 <div class="sws-slide">
309 <h1>Représentation des enregistrements variables</h1>
310 <ul><li>Nombre fixe d'attributs (schéma de la table)
312 <li>Champs de taille variables (<i>blobs</i> de texte)
316 <table style="margin-left:20pt;" class="withborder">
317 <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>
319 On utilise un séparateur spécial entre les champs (scan linéaire
320 pour arriver au i<sup>ème</sup> champ.<br/>
321 <table style="margin-left:20pt;" class="withborder">
322 <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>
324 On stocke les longueurs dans l'enregistrement
327 <div class="sws-slide">
328 <h1>Méta-données</h1>
329 <p>Chaque enregistrement possède un en-tête stockant des données
331 <ul><li>taille totale de l'enregistrement (avec entête)</li>
332 <li>pointeur vers le schéma de la table (pour déterminer les
333 tailles des champs)</li>
334 <li>date de dernière mise à jour</li>
335 <li>information de gestion des valeurs nulles:
336 <ul class="sws-pause">
337 <li>Stockage d'une valeur spéciale (pas toujours
339 <li>Stockage d'un bitmap (masque) : 26<sub>10</sub> =
340 11010<sub>2</sub> : valeur nulle dans les champ 0 et 2</li>
345 <div class="sws-slide">
346 <h1>Stockage des enregistrements dans une page </h1>
347 <p>Chaque enregistrement à une adresse (<i>rid</i> : record id)
348 constituée de l'adresse de la page et de la position de
349 l'enregistrement au sein de la page</p>
350 <p>Lors d'une insertion, on doit trouver un emplacement libre
352 <p>Lors d'une suppression, on doit « effacer » un emplacement
353 occupé et éventuellement compacter la page</p>
355 <div class="sws-slide">
356 <h1>Stockage compact vs non compact (taille fixe)</h1>
358 <img style="width:40%" src="page_comp.svg"/>
359 <img style="margin-left:10%;width:40%" src="page_ncomp.svg"/>
362 <div class="sws-slide">
363 <h1>Stockage compact (taille variable)</h1>
365 <img style="margin-left:10%;width:70%" src="page_var.svg"/>