Cours et exercices SGBD relationnels pour débutant
Cours de bases de données – Aspects système
Table des matières
1 Introduction 3
2 Dispositifs de stockage 5
2.1 S1 : Supports de stockage ……. . . . 5
2.1.1 Mémoires …. . 6
2.1.2 Performances des mémoires …. . . . 7
2.1.3 Disques …. . . 8
2.1.4 Un mot sur les Solid State Drives …. . 10
2.1.5 Quiz ……. 11
2.1.6 Exercices …. . 11
2.2 S2 : Gestion des mémoires ……. . . . 12
2.2.1 Les lectures …. 12
2.2.2 Les mises à jour …. 14
2.2.3 Le principe de localité ……. 16
2.2.4 Quiz ……. 19
2.2.5 Exercices …. . 19
3 Fichiers séquentiels 21
3.1 S1 : Enregistrements, blocs et fichiers …. . . . 21
3.1.1 Enregistrements …. 21
3.1.2 Blocs …. . . . 24
3.1.3 Fichiers …. . . 27
3.1.4 Exercices …. . 29
3.2 S2 : Oracle ……. . 29
4 Indexation : l’arbre B 31
4.1 S1 : Indexation de fichiers ……. . . . 32
4.1.1 Structure et contenu des index …. . . 32
4.1.2 Comment chercher avec un index …. . 33
4.1.3 Index non-dense …. 34
4.1.4 Index dense …. 36
4.1.5 Index multi-niveaux ……. . . 37
4.1.6 Quiz ……. 39
4.2 S2 : L’arbre-B …. . ……. . 40
4.2.1 Structure de l’arbe B ……. . 40
4.2.2 Construction de l’arbre B ……. . 42
4.2.3 Recherches avec un arbre-B …. . . . 46
4.2.4 Création d’un arbre B ……. . 47
4.2.5 Propriétés de l’arbre B …. . 48
4.2.6 Quiz …. 48
5 Opérateurs et algorithmes 51
5.1 S1 : Introduction à l’optimisation et à l’évaluation ……. . 51
5.1.1 Quiz …. 52
5.2 S2 : Modèle d’exécution : les itérateurs …. 53
5.2.1 Matérialisation et pipelinage …. . 53
5.2.2 Opérateurs bloquants …. . . 55
5.2.3 Itérateurs ……. . 56
5.2.4 Quiz …. 57
5.3 S3 : les opérateurs de base ……. 58
5.3.1 Parcours séquentiel …… 58
5.3.2 Parcours d’index ……. 58
5.3.3 Accès par adresse ……. 59
5.3.4 Opérateurs de sélection et de projection …… 60
5.3.5 Exécution de requêtes mono-tables ……. . . 61
5.3.6 Quiz …. 63
5.4 S4 : Le tri externe ……. . 64
5.4.1 Phase de tri ……. 65
5.4.2 Phase de fusion ……. . 65
5.4.3 Coût du tri-fusion ……. 67
5.4.4 L’opérateur de tri-fusion …. 68
5.4.5 Quiz …. 69
5.5 S5 : Algorithmes de jointure …… 69
5.5.1 Jointure avec un index …. . 70
5.5.2 Jointure avec deux index …. 72
5.5.3 Jointure par boucles imbriquées … 72
5.5.4 Jointure par tri-fusion …. . . 75
5.5.5 Jointure par hachage …. . . 77
5.5.6 Quiz …. 79
6 Evaluation et optimisation 81
6.1 S1 : traitement de la requête …… 81
6.1.1 Décomposition en bloc …. . 81
6.1.2 Traduction et réécriture …. . 84
6.2 S2 : optimisation de la requête …. . . 85
6.2.1 La réécriture ……. 85
6.2.2 Plans d’exécution ……. 86
6.2.3 Arbres en profondeur à gauche …. 90
6.2.4 Quiz …. 92
6.3 S3 : illustration avec ORACLE …. . 92
6.3.1 Paramètres et statistiques …. 92
6.3.2 Plans d’exécution ORACLE …. . 93
7 Transactions 99
7.1 S1 : Transactions ……. . . 100
7.1.1 Notions de base ……. . 100
7.1.2 Exécutions concurrentes …. 102
7.1.3 Propriétés ACID des transactions …104
7.1.4 Un exemple de concurrence sous ORACLE ……. 106
7.2 S2 : effets indésirables des transactions concurrentes ……. 108
7.2.1 Défauts de sérialisabilité …. 108
7.2.2 Défauts de recouvrabilité …. 112
ii
7.2.3 Exercices ……. . 114
7.3 S3 : choisir un niveau d’isolation …. 114
7.3.1 Les modes d’isolation SQL …115
7.3.2 Verrouillage explicite …. . . 116
7.3.3 Le mode read committed …. 118
7.3.4 Le mode repeatable read …118
7.3.5 Le mode serializable …120
7.3.6 Exercices ……. . 122
8 Contrôle de concurrence 123
8.1 S1 : Les mécanismes ……. 123
8.1.1 Versionnement ……. . 123
8.1.2 Verrouillage ……. 124
8.1.3 Exercices ……. . 126
8.2 S2 : les algorithmes ……. 126
8.2.1 Contrôle par verrouillage à deux phases ……127
8.2.2 Contrôle de concurrence multi-versions ……129
8.2.3 Exercices ……. . 130
9 Reprise sur panne 131
9.1 S1 : mécanismes fondamentaux …. . 131
9.1.1 Pannes et mémoires ……132
9.1.2 Le journal des transactions …133
9.2 S2 : Algorithmes de reprise sur panne …. . 134
9.2.1 La notion de checkpoint …. 134
9.2.2 Avec mises à jour différées …135
9.2.3 Avec mise à jour immédiate …. . 135
9.2.4 Journaux et sauvegardes …. . ……. . 136
9.2.5 Quiz …. 137
10 Indices and tables 141
Cours de bases de données – Aspects système, Version 1.1
Contents : Le document que vous commencez à lire fait partie de l’ensemble des supports d’apprentissage proposés sur le site . Il fait partie du cours consacré aux bases de données relationnelles, divisé en deux parties :
— La version en ligne du support “Modèles et langages” est accessible à , la version imprimable (PDF) est disponible à .
— La version en ligne du support “Aspects système” est accessible à , la version imprimable (PDF) est disponible à .
Deux autres cours, aux contenus proches, sont également disponibles :
— Un cours sur les bases de données documentaires et distribuées à .
— Un cours sur les applications avec bases de données à Reportez-vous à pour plus d’explications.
Important : Ce cours de Philippe Rigaux est mis à disposition selon les termes de la licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International. Cf.
Tout le matériel proposé ici sert de support au cours “Aspects systèmes des bases de données” proposé par le département d’informatique du Cnam. Le code du cours est NFP107 (voir le site ?
rubrique220 pour des informations pratiques). Il est donné en
— Cours présentiel (second semestre, mercredi soir)
— Cours à distance (premier semestre, avec supports audiovisuels)
CHAPITRE1 Introduction
Supports complémentaires :
— Diapositives : (à venir)
— Vidéo de présentation (à venir)
Les Systèmes de Gestion de Bases de Données (SGBD) sont des logiciels complexes qui offrent un ensemble complet et cohérent d’outil de gestion de données : un langage de manipulation et d’interrogation (SQL par exemple), un gestionnaire de stockage sur disque, un gestionnaire de concurrence d’accès, des interfaces de programmation et d’administration, etc.
Les systèmes présentés ici sont les SGBD Relationnels, simplement appelés systèmes relationnels. Il s’agit de la classe la plus répandue des SGBD, avec des représentants bien connus comme Oracle, MySQL, SQL Server, etc. Tous ces systèmes s’appuient sur un modèle de données normalisé, dit relationnel, caractérisé notamment par le langage SQL.
Les documents proposés ici proposent d’aller ”sous le capot” de ces systèmes pour étudier comment ils fonctionnent et réussissent le tour de force de proposer des accès sécurisés à des centaines d’utilisateurs en parallèle, tout en obtenant des temps de réponses impressionnants même pour des bases très volumineuses. Le contenu correspond typiquement à un cours universitaire de deuxième cycle en informatique. Il couvre les connaissances indispensables à tout informaticien de niveau ingénieur.
Le cours est découpé en chapitres, couvrant un sujet bien déterminé, et en sessions. Nous essayons de structurer les sessions pour qu’elles demandent environ 2 heures de travail personnel (bien sûr, cela dépend également de vous).
Pour assimiler une session vous pouvez combiner les ressources suivantes :
— La lecture du support en ligne : celui que vous avez sous les yeux, également disponible en PDF ou en ePub.
— Le suivi du cours, en vidéo ou en présentiel.
— Le test des exemples de code fournis dans chaque session.
— La réalisation des exercices proposés en fin de session.
— Dans la plupart des chapitres, des Quiz sur des questions de cours; si vous ne savez pas répondre à une question du Quiz :, relisez le chapitre et approfondissez.
La réalisation des exercices est essentielle pour vérifier que vous maîtrisez le contenu.
Vous devez maîtriser le contenu des sessions dans l’ordre où elles sont proposées. Commencez par lire le support, jusqu’à ce que les principes vous paraissent clairs. Reproduisez les exemples de code : tous les exemples donnés sont testés et doivent donc fonctionner. Le cas échéant, cherchez à résoudre les problèmes par vous-mêmes : c’est le meilleur moyen de comprendre. Finissez enfin par les exercices. Les solutions sont dévoilées au fur et à mesure de l’avancement du cours, mais si vous ne savez pas faire un exercice, c’est sans doute que le cours est mal assimilé et il est plus profitable d’approfondir en relisant à nouveau que de simplement copier une solution.
Enfin, vous êtes totalement encouragé(e) à explorer par vous-mêmes de nouvelles pistes (certaines sont proposées dans les exercices).
Chapitre 1. Introduction
2 Dispositifs de stockage
Une base de données est constituée, matériellement, d’un ou plusieurs fichiers volumineux stockés sur un support non volatile. Le support le plus couramment employé est le disque magnétique (“disque dur”) qui présente un bon compromis en termes de capacité de stockage, de prix et de performance. Un concurrent sérieux est le Solid State Drive, dont les performances sont très supérieures, et le coût est en baisse constante, ce qui le rend de plus en plus concurrentiel.
- les disques magnétiques constituent le principal périphérique de type mémoire; ils offrent une grande capacité de stockage tout en gardant des accès en lecture et en écriture relativement efficaces;
- les Solid State Drive ou SSD sont une alternative récente aux disques magnétiques; leurs peformances sont supérieures, mais leur coût élevé;
- enfin les CD ou les bandes magnétiques sont des supports très économiques mais leur lenteur les destine plutôt aux sauvegardes à long terme.
Fig. 2.1 – Hiérarchie des mémoires
La mémoire vive (que nous appellerons mémoire principale) et les disques (ou mémoire secondaire) sont les principaux niveaux à considérer pour des applications de bases de données. Une base de données doit être stockée sur disque, pour les raisons de taille et de persistance déjà évoquées, mais les données doivent impérativement être placées en mémoire vive pour être traitées. Dans l’hypothèse (réaliste) où seule une fraction de la base peut résider en mémoire centrale, un SGBD doit donc en permanence effectuer des transferts entre mémoire principale et mémoire secondaire pour satisfaire les requêtes des utilisateurs. Le coût de ces transferts intervient de manière prépondérante dans les performances du système.
Vocabulaire : Mais qu’est-ce qu’une “donnée”?
Le terme de donnée désigne le codage d’une information applicative. Dans le contexte de ce cours, “donnée” sera toujours synonyme de nuplet (ligne dans une table). On parlera parfois d’enregistrement quand la perspective “stockage” est privilégiée.
Dans d’autres contextes, une donnée peut être un document, un flux d’octets, etc. Du point de vue de l’application, et de l’information qu’elle manipule, une “donnée” est l’unité de lecture et d’écriture.
La technologie évoluant rapidement, il est délicat de donner des valeurs précises pour la taille des différentes mémoires. Un ordinateur est typiquement équipé de quelques Gigaoctets de mémoire vive (typiquement 4 ou 8 Go pour un ordinateur personnel, plusieurs dizaines de Go pour un serveur de données). La taille d’un disque magnétique est de l’ordre du Téraoctet, soit un rapport de 1 à 1 000 avec les données en mémoire centrale. Les SSD ont des tailles comparables à celles des disques magnétiques (pour un coût supérieur).
2.1.2 Performances des mémoires
Comment mesurer les performances d’une mémoire? Nous retiendrons deux critères essentiels :
— Temps d’accès : connaissant l’adresse d’une donnée, quel est le temps nécessaire pour aller à l’emplacement mémoire indiqué par cette adresse et obtenir l’information? On parle de lecture par clé ou encore d’accès direct pour cette opération;
— Débit : quel est le volume de données lues par unité de temps dans le meilleur des cas?
Le premier critère est important quand on effectue des accès dits aléatoires. Ce terme indique que deux accès successifs s’effectuent à des adresses indépendantes l’une de l’autre, qui peuvent donc être très éloignées. Le second critère est important pour les accès dits séquentiels dans lesquels on lit une collection d’information, dans un ordre donné. Ces deux notions sont essentielles.
Notion : accès direct/accès séquentiel
Retenez les notions suivantes :
— Accès direct : étant donné une adresse dans la mémoire (et principalement sur un disque), on accède à la donnée stockée à cette adresse.
— Accès séquentiel : on parcours la mémoire (et principalement un disque) dans un certain ordre pour lire les données au fur et à mesure.
Les performances des deux types d’accès sont extrêmement variables selon le type de support mémoire. Le temps d’un accès direct en mémoire vive est par exemple de l’ordre de 10 nanosecondes (10?8 sec.), de 0,1 millisecondes pour un SSD, et de l’ordre de 10 millisecondes (10?2 sec.) pour un disque. Cela représente un ratio approximatif de 1 000 000 (1 million!) entre les performances respectives de la mémoire centrale et du disque magnétique! Il est clair dans ces conditions que le système doit tout faire pour limiter les accès au disque.
Le tableau suivant résumé les ordres de grandeur des temps d’acès pour les différentes mémoires.
Tableau 2.1 – Performance des divers types de mémoire
Type mémoire | Taille | Temps d’accès aléatoire | Temps d’accès séquentiel |
Mémoire cache (Static RAM) | Quelques Mo | ? 10?8 (10 nanosec.) | Plusieurs dizaines de Gos par seconde |
Mémoire principale (Dynamic RAM) | Quelques Go | ? 10?8 ? 10?7 (10-100 nanosec.) | Quelques Go par seconde |
Disque magnétique | Quelques Tos | ? 10?2 (10 millisec.) | Env. 100 Mo par seconde. |
SSD | Quelques Tos | ? 10?4 (0,1 millisec.) | Jusqu’à quelques Gos par seconde. |
2.1. S1 : Supports de stockage
2.1.3 Disques
Les disques sont les composants les plus lents, et pourtant ils sont indispensables pour la gestion d’une base de données. Il est donc très utile de comprendre comment ils fonctionnent. Nous parlons essentiellement des disques magnétiques, avec un bref aperçu des SSD (dont l’importance est sûrement amenée à croître rapidement).
Dispositif
Un disque magnétique est une surface circulaire magnétisée capable d’enregistrer des informations numériques. La surface magnétisée peut être située d’un seul côté (“simple face”) ou des deux côtés (“double face”) du disque.
Les disques sont divisés en secteurs, un secteur constituant la plus petite surface d’adressage. En d’autres termes, on sait lire ou écrire des zones débutant sur un secteur et couvrant un nombre entier de secteurs (1 au minimum : le secteur est l’unité de lecture sur le disque). La taille d’un secteur est le plus souvent de 512 octets.
La plus petite information stockée sur un disque est un bit qui peut valoir 0 ou 1. Les bits sont groupés par 8 pour former des octets, les octets groupés par 64 pour former des secteurs, et une suite de secteurs forme un cercle ou piste sur la surface du disque.
Un disque est entraîné dans un mouvement de rotation régulier par un axe. Une tête de lecture (deux si le disque est double-face) vient se positionner sur une des pistes du disque et y lit ou écrit les données. Le nombre minimal d’octets lus par une tête de lecture est physiquement défini par la taille d’un secteur (en général 512 octets). Cela étant le système d’exploitation peut choisir, au moment de l’initialisation du disque, de fixer une unité d’entrée/sortie supérieure à la taille d’un secteur, et multiple de cette dernière. On obtient des blocs, dont la taille est typiquement 512 octets (un secteur), 1 024 octets (deux secteurs) ou 4 096 octets (huit secteurs).
Chaque piste est donc divisée en blocs (ou pages) qui constituent l’unité d’échange entre le disque et la mémoire principale.
Fig. 2.2 – Fonctionnement d’un disque magnétique.
Toute lecture ou toute écriture sur les disques s’effectue par blocs. Même si la lecture ne concerne qu’une donnée occupant 4 octets, tout le bloc contenant ces 4 octets sera transmis en mémoire centrale. Cette caractéristique est fondamentale pour l’organisation des données sur le disque. Un des objectifs du SGBD est de faire en sorte que, quand il est nécessaire de lire un bloc de 4 096 octets pour accéder à un entier de 4 octets, les 4 092 octets constituant le reste du bloc ont de grandes chances d’être utiles à court terme et se trouveront donc déjà chargée en mémoire centrale quand le système en aura besoin. C’est un premier exemple du principe de localité que nous discutons plus loin.
Notion : bloc
Retenez la notion de bloc, zone mémoire contigue stockée sur disque, lue ou écrite solidairement. Le bloc est l’unité d’entrée/sortie entre la mémoire secondaire et la mémoire principale.
La tête de lecture n’est pas entraînée dans le mouvement de rotation. Elle se déplace dans un plan fixe qui lui permet de se rapprocher ou de s’éloigner de l’axe de rotation des disques, et d’accéder à l’une des pistes. Pour limiter le coût de l’ensemble de ce dispositif et augmenter la capacité de stockage, les disques sont empilés et partagent le même axe de rotation (voir Fig. 2.2). Il y a autant de têtes de lectures que de disques (deux fois plus si les disques sont à double face) et toutes les têtes sont positionnées solidairement dans leur plan de déplacement. À tout moment, les pistes accessibles par les têtes sont donc les mêmes pour tous les disques de la pile, ce qui constitue une contrainte dont il faut savoir tenir compte quand on cherche à optimiser le placement des données.
L’ensemble des pistes accessibles à un moment donné constitue le cylindre. La notion de cylindre correspond donc à toutes les données disponibles sans avoir besoin de déplacer les têtes de lecture.
Enfin le dernier élément du dispositif est le contrôleur qui sert d’interface avec le système d’exploitation. Le contrôleur reçoit du système des demandes de lecture ou d’écriture, et les transforme en mouvements appropriés des têtes de lectures, comme expliqué ci-dessous.
Entrées/sorties sur un disque
Un disque est une mémoire à accès dit semi-direct. Contrairement à une bande magnétique par exemple, il est possible d’accéder à une information située n’importe où sur le disque sans avoir à parcourir séquentiellement tout le support. Mais contrairement à la mémoire principale, avant d’accéder à une adresse, il faut attendre un temps variable lié au mécanisme de rotation du disque.
L’accès est fondé sur une adresse donnée à chaque bloc au moment de l’initialisation du disque par le système d’exploitation. Cette adresse est composée des trois éléments suivants :
- le numéro du disque dans la pile ou le numéro de la surface si les disques sont à double-face;
- le numéro de la piste;
- le numéro du bloc sur la piste.
La lecture d’un bloc, étant donné son adresse, se décompose en trois étapes :
- positionnement de la tête de lecture sur la piste contenant le bloc;
- rotation du disque pour attendre que le bloc passe sous la tête de lecture (rappelons que les têtes sont fixes, c’est le disque qui tourne);
- transfert du bloc.
La durée d’une opération de lecture est donc la somme des temps consacrés à chacune des trois opérations, ces temps étant désignés respectivement par les termes délai de positionnement, délai de latence et temps de transfert. Le temps de transfert est négligeable pour un bloc, mais peu devenir important quand des milliers de blocs doivent être lus. Le mécanisme d’écriture est à peu près semblable à la lecture, mais peu prendre un peu plus de temps si le contrôleur vérifie que l’écriture s’est faite correctement.
La latence de lecture fait du disque une mémoire à accès semi-direct, comme mentionné précédemment. C’est aussi cette latence qui rend le disque lent comparé aux autres mémoires, surtout si un déplacement des têtes de lecture est nécessaire. Une conséquence très importante est qu’il est de très loin préférable de lire sur un disque en accès séquentiel que par une séquence d’accès aléatoires (cf. exercices).
Spécifications d’un disque
Le Tableau 2.2 donne les spécifications d’un disque, telles qu’on peut les trouver sur le site de n’importe quel constructeur. Les chiffres donnent un ordre de grandeur pour les performances d’un disque, étant bien entendu que les disques
2.1. S1 : Supports de stockage
destinés aux serveurs sont beaucoup plus performants que ceux destinés aux ordinateurs personnels. Le modèle donné en exemple appartient au mileu de gamme.
Le disque comprend 5 335 031 400 secteurs de 512 octets chacun, la multiplication des deux chiffres donnant bien la capacité totale de 2,7 To. Les secteurs étant répartis sur 3 disques double-face, il y a donc 5 335 031 400 / 6 = 889 171 900 secteurs par surface.
Le nombre de secteurs par piste n’est pas constant, car les pistes situées près de l’axe sont bien entendu beaucoup plus petites que celles situées près du bord du disque. On ne peut, à partir des spécifications, que calculer le nombre moyen de secteurs par piste, qui est égal à 889 171 900/15300 = 58115. On peut donc estimer qu’une piste stocke en moyenne 58115 × 512 = 29 Mégaoctets. Ce chiffre donne le nombre d’octets qui peuvent être lus en séquentiel, sans délai de latence ni délai de positionnement.
Tableau 2.2 – Spécification d’un disque
Caractéristique | Performance |
Capacité | 2,7 To |
Taux de transfert | 100 Mo/s |
Cache | 3 Mo |
Nbre de disques | 3 |
Nbre de têtes | 6 |
Nombre de cylindres | 15 300 |
Vitesse de rotation | 10 000 rpm (rotations par minute) |
Délai de latence | En moyenne 3 ms |
Temps de positionnement moyen | 5,2 ms |
Déplacement de piste à piste | 0,6 ms |
Les temps donnés pour le temps de latence et le délai de rotation ne sont que des moyennes. Dans le meilleur des cas, les têtes sont positionnées sur la bonne piste, et le bloc à lire est celui qui arrive sous la tête de lecture. Le bloc peut alors être lu directement, avec un délai réduit au temps de transfert.
Ce temps de transfert peut être considéré comme négligeable dans le cas d’un bloc unique, comme le montre le raisonnement qui suit, basé sur les performances du Tableau 2.2. Le disque effectue 10 000 rotations par minute, ce qui correspond à 166,66 rotations par seconde, soit une rotation toutes les 0,006 secondes (6 ms). C’est le temps requis pour lire une piste entièrement. Cela donne également le temps moyen de latence de 3 ms.
Pour lire un bloc sur une piste, il faudrait tenir compte du nombre exact de secteurs, qui varie en fonction de la position exacte. En prenant comme valeur moyenne 303 secteurs par piste, et une taille de bloc égale à 4 096 soit huit secteurs, on obtient le temps de transfert moyen pour un bloc :
Le temps de transfert ne devient significatif que quand on lit plusieurs blocs consécutivement. Notez quand même que les valeurs obtenues restent beaucoup plus élevées que les temps d’accès en mémoire principale qui s’évaluent en nanosecondes.
Dans une situation moyenne, la tête n’est pas sur la bonne piste, et une fois la tête positionnée (temps moyen 5.2 ms), il faut attendre une rotation partielle pour obtenir le bloc (temps moyen 3 ms). Le temps de lecture est alors en moyenne de 8.2 ms, si on ignore le temps de transfert.
Il y a deux raisons principales à l’utilisation de fichiers. Tout d’abord il est courant d’avoir affaire à des bases de données dont la taille dépasse de loin celle de la mémoire principale. Ensuite – et c’est la justification principale du recours aux fichiers, même pour des bases de petite taille – une base de données doit survivre à l’arrêt de l’ordinateur qui l’héberge, que cet arrêt soit normal ou dû à un incident matériel.
Important : Une donnée qui n’est pas sur un support persistant est potentiellement perdue en cas de panne.
L’accès à des données stockées sur un support persistant, par contraste avec les applications qui manipulent des données en mémoire centrale, est une des caractéristiques essentielles d’un SGBD. Elle implique notamment des problèmes potentiels de performance puisque le temps de lecture d’une information sur un disque est considérablement plus élevé qu’un accès en mémoire principale. L’organisation des données sur un disque, les structures d’indexation et les algorithmes de recherche utilisés constituent donc des aspects essentiels des SGBD du point de vue des performances.
Une bonne partie du présent cours est, de fait, consacrée à des méthodes, techniques et structures de données dont le but principal est de limiter le nombre et la taille de données lues sur le support persistant.
Un bon système se doit d’utiliser au mieux les techniques disponibles afin de minimiser les temps d’accès. Dans ce chapitre nous décrivons les techniques de stockage de données et le transfert de ces dernières entre les différents niveaux de mémoire d’un ordinateur. La première partie est consacrée aux dispositifs de stockage. Nous détaillons successivement les différents types de mémoire utilisées, en insistant particulièrement sur le fonctionnement des disques magnétiques. Nous abordons en seconde partie les principales techniques de gestion de la mémoire utilisées par un SGBD.
2.1 S1 : Supports de stockage
Supports complémentaires :
— Diapositives: supports de stockage
— Vidéo sur les dispositifs de stockage
Un système informatique offre plusieurs mécanismes de stockage de l’information, ou mémoires. Ces mémoires se différencient par leur prix, leur rapidité, le mode d’accès aux données (séquentiel ou par adresse) et enfin leur durabilité.
— Les mémoires volatiles perdent leur contenu quand le système est interrompu, soit par un arrêt volontaire, soit à cause d’une panne.
— Les mémoires persistantes comme les disques magnétiques, les SSD, les CD ou les bandes magnétiques, préservent leur contenu même en l’absence d’alimentation électrique.
2.1.1 Mémoires
D’une manière générale, plus une mémoire est rapide, plus elle est chère et – conséquence directe – plus sa capacité est réduite. Les différentes mémoires utilisées par un ordinateur constituent donc une hiérarchie (Fig. 2.1), allant de la mémoire la plus petite mais la plus efficace à la mémoire la plus volumineuse mais la plus lente.
- la mémoire cache est une mémoire intermédiaire permettant au processeur d’accéder très rapidement aux données à traiter;
- la mémoire vive, ou mémoire principale stocke les données et les processus constituant l’espace de travail de la machine; toute information (donnée ou programme) doit être en mémoire principale pour pouvoir être traitée par un processeur;