Upload
george
View
46
Download
0
Embed Size (px)
DESCRIPTION
1. Motivation et introduction 5. Les SGBD 2. Concepts des bases de données 3. Modèle relationnel et normalisation 4. Implémentation des structures de données. 4. IMPLEMENTATION DES STRUCTURES DE DONNEES. Version 1 - 10 novembre 2009 Corrections 5/11/2010. - PowerPoint PPT Presentation
Citation preview
azerty Bases de données J-L Hainaut 2009 1I. Concepts des bases de données
4. IMPLEMENTATION DES STRUCTURES DE DONNEES
Support du chapitre 4, Implémentation des structures de données
de l'ouvrage Bases de données, J-L Hainaut, Dunod 2009.
Version 1 - 10 novembre 2009Corrections 5/11/2010
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
azerty Bases de données J-L Hainaut 2009 2
4.1 Introduction
4.2 Les mémoires externes
4.3 Organisation d'un espace de stockage
4.4 Lecture séquentielle d'un fichier
4.5 Les index
4.6 Organisation séquentielle indexée
4.7 Organisation calculée
4.8 Les index secondaires
4.9 Les techniques d'agrégation(clustering)
Contenu
4. IMPLEMENTATION DES STRUCTURES DE DONNEES
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
azerty Bases de données J-L Hainaut 2009 3
4.1 Introduction
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
azerty Bases de données J-L Hainaut 2009 4
4.1 Introduction
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
1. Comment les tables, les lignes et les index sont-ils stockés dans l'ordinateur ?
2. Quel volume occupent une table et un index ?
3. Comment calculer le temps d'accès aux données ?
Trois questions
azerty Bases de données J-L Hainaut 2009 5
4.1 Introduction
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Mémoire centrale : électronique, volatile, très rapide, limitée, coûteuse
Mémoire externe : magnétique / optique / électronique, persistante, lente, grande capacité, peu coûteuse
L'ordinateur est composé (entre autres) :
• d'un processeur
• d'une mémoire centrale (mémoire interne, mémoire RAM)
• de mémoires externes fixes
• de mémoires externes amovibles
azerty Bases de données J-L Hainaut 2009 6
4.1 Introduction
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Mémoire externe magnétique : • disque magnétique• disque magnéto-optique• mémoire à bande magnétique (cartouche)
Mémoire externe optique : • CD• DVD• Blue Ray
Mémoire externe électronique : • mémoire flash (clé USB), • disque électronique (solid-state disk ou SSD)
azerty Bases de données J-L Hainaut 2009 7
4.2 Les mémoires externes
I. Concepts des bases de données
Les données sont stockées dans une mémoire externe, distincte de la mémoire centrale.
Données inactives, backup : bande magnétique, mémoires optiques
Données actives : disque magnétique, disque électronique
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
étude du disque magnétique
azerty Bases de données J-L Hainaut 2009 8
4.2 Les mémoires externes - le disque magnétique
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
bras en positionde lecture/écriture
tête
face supérieuredu premier plateau
axe et moteur (caché) parking
axe des bras
moteur des bras
azerty Bases de données J-L Hainaut 2009 9
4.2 Les mémoires externes - le disque magnétique
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
bras au parking
azerty Bases de données J-L Hainaut 2009 10
4.2 Les mémoires externes - le disque magnétique
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
4 bras dont 2 doubles (et six têtes) trois plateaux et six (sur)faces
azerty Bases de données J-L Hainaut 2009 11
4.2 Les mémoires externes - le disque magnétique
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Exemple de disqueà déplacement radial(NEC D5126, 1985)
azerty Bases de données J-L Hainaut 2009 12
4.2 Les mémoires externes - géométrie du disque magnétique
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Géométrie d'un disque magnétique
• Le support est formé de 1 à 10 plateaux présentant 2 faces.
• Chaque face comprend de 50.000 à 200.000 pistes circulaires et concentriques.
• Chaque piste est décomposée en 200 à 1.000 secteurs.
• Un secteur comprend 512 octets.
• Le support tourne à une vitesse constante de 3.200 à 15.000 rpm.
• Les pistes de même rang constituent un cylindre (virtuel)
Une mémoire à disque magnétique est donc constituée de 50.000 à 200.000 cylindres, formés de 2 à 20 pistes, de 200 à 1.000 secteurs de 512 octets.
azerty Bases de données J-L Hainaut 2009 13
4.2 Les mémoires externes - géométrie du disque magnétique
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
piste 0
piste 7
cylindre 63450secteur 307 de la piste 2 du cylindre 63450
piste 2
secteurs 0
Adresse physique d'un secteur : <c, p, s>
Exemple : secteur <63450, 2, 307>
Adressage LBA (logical block addressing) : les secteurs sont numérotés de 0 à 979.199.999. Conversion LBA <c,p,s> par le contrôleur.
azerty Bases de données J-L Hainaut 2009 14
4.2 Les mémoires externes - géométrie du disque magnétique
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Modèle de disque de référence (500 Go, 3.5”)
• Géométrie : 136.000 cylindres de 8 pistes (ou têtes) de 900 secteurs de 512 octets
• Capacité : 979.200.000 secteurs501.350.400.000 octets467 Go
• Vitesse de rotation : 7.200 rpm ou 120 rps ou 8,33 msec/rév.
Géométrie d'un disque magnétique
azerty Bases de données J-L Hainaut 2009 15
4.2 Les mémoires externes - lecture / écriture sur un disque
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
• Secteur = unité de lecture/écriture trop petite
• Les échanges entre le disque et le SGBD s'effectuent par pages entières
• 1 page = de 2 à 256 secteurs contigus, soit de 1Ko à 128 Ko.
• Les enregistrements (les lignes) sont écrits dans les pages
• Taille typique : 1 page = 8 secteurs = 4 Ko
Les secteurs et les pages
azerty Bases de données J-L Hainaut 2009 16
4.2 Les mémoires externes - lecture / écriture sur un disque
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
page 126
page 127
0
Deux pages consécutives de 8 secteurs
azerty Bases de données J-L Hainaut 2009 17
4.2 Les mémoires externes - lecture / écriture sur un disque
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
pour lire un secteur <c, p, s> :
1. les bras se déplacent sur le cylindre c
2. le bras de position p est connecté
3. attente que le secteur s se présente sous la tête de lecture
4. la tête lit et transfère le contenu du secteur <c, p, s>
Lecture du contenu d'un secteur d'adresse <c, p, s>
temps de la lecture :
• déplacement du bras = (1, 8, 15) msec
• connexion = 0 msec
• délai rotationel de 1/2 révolution = 4,17 msec
• temps de transfert : 8,33 / 900 = 0,00925 msec
temps moyen : 12,18 msec
Ecriture dans un secteur : même temps sauf si relecture de vérification. Dans ce cas, ajouter une rotation, soit 8,33 msec : 20,5 msec.
azerty Bases de données J-L Hainaut 2009 18
4.2 Les mémoires externes - lecture / écriture sur un disque
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
1. les bras se déplacent sur le cylindre c
2. le bras de position p est connecté
3. attente que le secteur s se présente sous la tête de lecture
4. la tête lit et transfère le contenu des 8 secteurs à partir de <c, p, s>
Lecture du contenu d'une page de 4 Ko d'adresse <c, p, s>
• déplacement du bras = (1, 8, 15) msec
• connexion = 0 msec
• 1/2 révolution = 4,17 msec
• transfert : 8,33 / 900 * 8 = 0,074 msec
temps moyen : tla1 = 12,3 msec
on retient !
azerty Bases de données J-L Hainaut 2009 19
4.2 Les mémoires externes - Optimisation
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Lecture d’un enregistrement quelconque : optimisation
Théoriquement :
l’enregistrement est stocké dans une page
la lecture de l’enregistrement réclame la lecture de sa page
le temps de lecture de l'enregistrement est donc de 12,3 msec
la vitesse de lecture est de 1/0,0123 = 81 enregistrements par seconde
c'est INSUFFISANT !
on devrait pouvoir dépasser 1.000 enregistrements par seconde
Deux optimisations simples : le tampon et la lecture anticipée
(troisième technique examinée plus tard : le clustering)
azerty Bases de données J-L Hainaut 2009 20
4.2 Les mémoires externes - Optimisation : le tampon
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Optimisation # 1 : le tampon
Observation de transfert d'une page de 4 Ko
mémoire centrale mémoire centrale : 0,00043 msec
disque mémoire centrale : 12,3 msec
Soit un rapport de 28.600
Conclusion : il serait préférable de conserver les données en mémoire centrale plutôt que sur disque.
Conclusion bien sûr irréaliste, mais pas tant que cela ...
azerty Bases de données J-L Hainaut 2009 21
4.2 Les mémoires externes - Optimisation : le tampon
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Optimisation # 1 : le tampon
Idée : conserver en mémoire centrale des copies des pages les plus utilisées.
Tampon (buffer) ou mémoire cacheEspace en mémoire rapide (en général mémoire centrale) dans lequel sont rangées des données issues de (ou destinées à) une mémoire plus lente (disque).
PrincipeEviter les accès au disque en conservant dans un tampon une quantité importante de données. Avec un peu de chance, les données demandées sont dans le tampon, ce qui évite d’accéder au disque.
StructureLe tampon est constitué d'un tableau de cadres (taille 1 cadre = 1 page) et d'un index n° page n° de cadre.
azerty Bases de données J-L Hainaut 2009 22
4.2 Les mémoires externes - Optimisation : le tampon
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Optimisation # 1 : le tampon
Le programme PA demande la lecture de données qui se trouvent sur le disque.
la donnée réclamée est dans le tamponcoût = 0,00043 msec
PA
tampon disque
la donnée demandée n'est pas dans le tamponcoût supplémentaire de 12,3 msec
azerty Bases de données J-L Hainaut 2009 23
4.2 Les mémoires externes - Optimisation : le tampon
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Optimisation # 1 : le tampon
Principes de la lecture (lecture de l'enregistrement R) :
1. Le SGBD détermine la page P dans laquelle se trouve R
2. Deux cas :2.1 une copie de P se trouve dans le tampon, dans le cadre (emplacement) C :2.2 pas de copie de P dans le tampon :
2.2.1 Le SGBD recherche un cadre libre dans le tampon2.2.2 Deux cas :
2.2.2.1 Un cadre libre C est trouvé2.2.2.2 Tous les cadres sont occupés :
le SGBD recherche le cadre C dont le contenu n'a plus été utilisé (copié, modifié) depuis le plus long temps. Si le contenu de C a été modifié, il est recopié sur le disque. C est alors considéré comme libre (politique LRU simplifiée : least recently used)
2.2.3 La page P est lue sur le disque et une copie est rangée dans le cadre C
3. Le SGBD recherche l'enregistrement R dans le cadre C et en transfère une copie dans la variable du programme :
azerty Bases de données J-L Hainaut 2009 24
4.2 Les mémoires externes - Optimisation : le tampon
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Optimisation # 1 : le tampon
Principes de l'insertion/modification/suppression de l'enregistrement R) :
1. le SGBD détermine la page P dans laquelle se trouve (ou se trouvera) R
2. Deux cas :2.1 une copie de P se trouve dans le tampon, dans le cadre C :2.2 pas de copie de P dans le tampon :
2.2.1 Le SGBD recherche un cadre libre dans le tampon2.2.2 Deux cas :
2.2.2.1 Un cadre libre C est trouvé2.2.2.2 Tous les cadres sont occupés
Le SGBD recherche le cadre C dont le contenu n'a plus été utilisé (copié, modifié) depuis le plus longtemps. Si le contenu de C a été modifié, il est recopié dans la mémoire secondaire.
2.2.3 La page P est lue sur le disque dur et une copie est rangée dans le cadre C
3. Le SGBD effectue la modification dans le contenu du cadre C (mais cette réécriture peut être retardée).
azerty Bases de données J-L Hainaut 2009 25
4.2 Les mémoires externes - Optimisation : lecture anticipée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Optimisation # 2 : la lecture anticipée
Idée : lire d'avance les pages qui seront probablement demandées.
Observationla lecture de pages consécutives est très fréquente (lecture séquentielle).
PrincipeLorsque la lecture d'une page est demandée, le SGBD lit et copie dans le tampon certaines des pages suivantes (par exemple celles de la piste courante).
JustificationLa lecture de pages consécutives est très rapide : temps de transfert uniquement et pas de positionnement du bras ni de délai rotationnel.
azerty Bases de données J-L Hainaut 2009 26
4.2 Les mémoires externes - Optimisation
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Optimisation : un exemple
Exemple : lecture d'une page
1. Pages de 4 Ko, enregistrements de 200 octets, piste de 450 Ko.
2. Une page contient 20 enregistrements; la piste contient une séquence de 112 pages.
3. Le programme client effectue une lecture séquentielle des enregistrements
Premier scénario : pas de lecture anticipée, chaque page fait l'objet d'une lecture aléatoire.Temps de lecture des 112 pages : 112 x 12,3 = 1.377,6 msec
Second scénario : le SGBD effectue une lecture anticipée des pages de la piste.
Temps de lecture de la 1re page : 12,3 msec
Temps de lecture des 111 pages suivantes : 111/112 x 8,33 = 8,26 msec
Temps de lecture des 112 pages : 20,56 msec.
Temps de lecture d'une page avec anticipation d'une piste : tls1 = 20,56 / 112 = 0,184 msec
on retient !
facteur d'amélioration
de 67 !
azerty Bases de données J-L Hainaut 2009 27
4.2 Les mémoires externes - Optimisation
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Modèle de disque de référence (500 Go)
• Géométrie : 136.000 cylindres de 8 pistes (ou têtes) de 900 secteurs de 512 octets
• Capacité : 979.200.000 secteurs501.350.400.000 octets467 Go
• Vitesse de rotation : 7.200 rpm ou 120 rps ou 8,33 msec/rév.
• Déplacement du bras : seek1 = 1 msec, seekavg = 8 msec, seekmax = 15 msec
• Lecture d'une page aléatoire (4 Ko) : tla1 = 12,3 msec
• Transfert d’une page (4 Ko) : ttr = 0,074 msec
• Lecture d’une page (4 Ko) avec anticipation d’une piste : tls1 = 0,184 msec
• Gain de la lecture avec anticipation d’une piste : as = tla1 / tls1 = 67
Géométrie d'un disque magnétique (suite et fin)
on met un marque-page
azerty Bases de données J-L Hainaut 2009 28
4.2 Les mémoires externes - Optimisation
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
0 49849
début
0 19999
début
Remarque : le temps de lecture séquentielle ne dépend pas de l'adresse initiale [*]
Exemple : lecture de 100 pages contiguës
Optimisation : un exemple
[*] tant qu'on reste dans le même cylindre
azerty Bases de données J-L Hainaut 2009 29
4.2 Les mémoires externes - Mémoire flash
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Complément : la mémoire flash
1. Mémoire électronique (EEPROM, technologie NAND) non volatile. La rétention des données ne nécessite pas d'énergie (comme le DM et contrairement à la MC). Disponible de 32 MB à 256 GB (en 2009).
2. Utilisée comme mémoire externe (clé USB, cartes mémoire) ou interne (mémoire BIOS, disque dur électronique ou SSD [de 60 GB à 1 TB mais 4.000 $ en 2010])
3. Deux technologies : SLC (single level cell, ou 1 bit par cellule) et MLC (multiple level cell, ou 2+ bits par cellule).
4. SLC : plus rapide (de 3 à 4 X), plus robuste à l'usure (10 X) mais plus coûteuse (3 X) et plus faible densité (3 X); surtout utilisée dans les SSD rapides
MLC : plus lente, usure rapide, faible coût; forte densité; surtout utilisées dans les clés USB, cartes mémoire multimédia, SSD standard;
azerty Bases de données J-L Hainaut 2009 30
4.2 Les mémoires externes
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Complément : la mémoire flash
1. Comportement externe similaire à celui du disque magnétique ...
2. ... mais fonctionnement interne complexe, très différent.
3. La mémoire MLS est décomposée en blocs (typiquement 128 Ko), eux-mêmes décomposés en pages (typiquement 4 Ko).
4. Au départ, chaque bloc est vierge = tous ses bits sont à 1.
5. L'écriture d'une page consiste à mettre à 0 certains bits de la page encore vierge dans un bloc. Ecriture séquentielle des pages dans un bloc.
6. Lorsque toutes les pages d'un bloc ont été écrites, ce bloc n'est plus modifiable. Pour pouvoir y écrire à nouveau, il faut effacer le bloc pour y mettre tous les bits à 1. Opération coûteuse : temps important et usure de la mémoire (maximum 10.000 à 100.000 effacements d'un même bloc)
7. Pour retarder la dégradation irréparable : wear-leveling. Le firmware de la mémoire répartit les écritures dans tous les blocs de la mémoire.
azerty Bases de données J-L Hainaut 2009 31
4.2 Les mémoires externes
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Complément : la mémoire flash
8. Une page modifiée est recopiée à un autre emplacement que son adresse d'origine (devenue read-only + wear-leveling).
9. Temps (MLS) : lecture d'une page : 0,025 msec
écriture d'une page : 0,800 msec
effacement d'un bloc : 1,500 msec
azerty Bases de données J-L Hainaut 2009 32I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
4.3 Les espaces de stockage
azerty Bases de données J-L Hainaut 2009 33I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Espace de stockage : conteneur dans lequel les lignes d'une table peuvent être enregistrée.
• Pour le lecteur fatigué : concept analogue à celui de fichier• Occupe généralement une portion d'un disque magnétique• Constitué d'une suite de Np pages numérotées de 0 à Np-1
• En principe, ces pages sont consécutives sur le disque• ... mais, si cette suite est trop longue, elle peut être fragmentée en
plusieurs sous-suites stockées à différents endroits du disque• Peut s'étendre sur plusieurs disques
. . .
210 Np-1Np-2Np-3
4.3 Les espaces de stockage
azerty Bases de données J-L Hainaut 2009 34
4.3 Les espaces de stockage
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Comment ranger des enregistrements dans une page ?
aaaaaaaaa bbbbb cccccccccccccc ddddddddd
aaaaaaaaa bbbbb cccccccccccccc ddddddddd
... 5 4 3 2 1 0
aaaaaaaaabbbbb ccccccccccccccddddddddd
On retient 3 techniques (il y en a d'autres) :
1. rangement séquentiel
2. pages segmentées en cellules (slots) de taille fixe
3. rangement dynamique avec indirection
azerty Bases de données J-L Hainaut 2009 35
4.3 Les espaces de stockage
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Comment gérer l'évolution de la taille des enregistrements ?
Deux techniques de base préservant l'adresse initiale des enregistrements :
1. indirection
2. fragmentation
Comment choisir la page d'un enregistrement ?
1. Au hasard (là où il y a de la place) : rangement en vrac
2. De manière à le retrouver rapidement via la valeur d'un champ : selon un index primaire (voir plus loin)
3. A proximité d'un enregistrement logiquement lié : clustering
azerty Bases de données J-L Hainaut 2009 36
4.3 Les espaces de stockage
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Adresse d'un enregistrement
Chaque enregistrement possède une adresse dans son espace de stockage.
Selon la technique de stockage :• rang de l'enregistrement• rang de son segment• n° de page + n° de segment dans la page• n° de page + n° de pointeur dans la page
azerty Bases de données J-L Hainaut 2009 37
4.3 Les espaces de stockage
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Adresse d'un enregistrement
Une adresse est stable si sa valeur ne change pas durant la vie de l'enregistrement
Stabilisation des adresses : par table de correspondance n° adresse réelle.• l'adresse pratique est le n°• en cas de déplacement d'un enregistrement, on remplace l'adresse réelle
dans la table de correspondance.
Dans une table relationnelle, chaque ligne est identifiée par un numéro : le rowid.= adresse stable
azerty Bases de données J-L Hainaut 2009 38I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.4 Lecture séquentielle d'un fichier
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
azerty Bases de données J-L Hainaut 2009 39I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
Petit rappel utile
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Modèle de disque de référence (500 Go)
• Géométrie : 136.000 cylindres de 8 pistes (ou têtes) de 900 secteurs de 512 octets
• Capacité : 979.200.000 secteurs501.350.400.000 octets467 Go
• Vitesse de rotation : 7.200 rpm ou 120 rps ou 8,33 msec/rév.
• Déplacement du bras : seek1 = 1 msec, seekavg = 8 msec, seekmax = 15 msec
• Lecture d'une page aléatoire (4 Ko) : tla1 = 12,3 msec
• Transfert d’une page (4 Ko) : ttr = 0,074 msec
• Lecture d’une page (4 Ko) avec anticipation d’une piste : tls1 = 0,184 msec
• Gain de la lecture avec anticipation d’une piste : as = tla1 / tls1 = 67
azerty Bases de données J-L Hainaut 2009 40I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
La lecture d'une séquence de pages consécutives dans un fichier est une opération extrêmement fréquente. Quel est le temps de cette lecture ?
Problème préliminaire : lecture d'une courte séquence de q pages [*].
1. lecture de la première page : tla1
2. lecture des q-1 pages suivantes : (q - 1) x ttr
lecture des q pages : tlsq = tla1 + (q - 1) x ttr
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Exemple : lecture d'une séquence de 200 pages de 4 Ko [*].
tlsq = tla1 + (q - 1) x ttr = 12,3 + 199 x 0,074 = 27,03 msec
si chaque page contient 10 enregistrements, la vitesse de lecture est de 10 x 200 / 0,02703 = 73.992 enreg./sec.
[*] dans le même cylindre
4.4 Lecture séquentielle d'un fichier
azerty Bases de données J-L Hainaut 2009 41
4.4 Lecture séquentielle d'un fichier
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Lecture séquentielle d'un fichier de Np pages.
Concept préliminaire : disque dédié ou partagé
• Disque dédié : seul le processus lecteur utilise le disque et il y lit exclusivement le fichier
• Disque partagé : plusieurs processus utilisent le disque en même temps et/ou le processus lecteur exécute en même temps d'autres lectures/écritures sur ce disque
Conséquence
• Disque dédié : après une lecture, le bras conserve sa position
• Disque partagé : après une lecture, le bras est déplacé et occupe pour la lecture suivante une position aléatoire
azerty Bases de données J-L Hainaut 2009 42
4.4 Lecture séquentielle d'un fichier
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Lecture séquentielle d'un fichier de Np pages.
On distingue 3 situations :
A. Disque dédié, fichier non fragmenté (cas le plus favorable)
B. Disque partagé, lecture anticipée (cas normal)
C. Disque partagé, pas de lecture anticipée (cas le plus défavorable)
azerty Bases de données J-L Hainaut 2009 43
4.4 Lecture séquentielle d'un fichier
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
A. Lecture séquentielle d'un fichier de Np pages.Disque dédié (cas le plus favorable)
Caractéristiques :
1. Seul le processus lecteur utilise le disque
2. La séquence des pages du fichier est d'un seul tenant (pas de fragmentation)
3. Les pages d'un cylindre sont lues sans interruption
4. Les seules ruptures sont les sauts au cylindre suivant
5. Lecture anticipée inutile
= lecture en streaming
azerty Bases de données J-L Hainaut 2009 44
4.4 Lecture séquentielle d'un fichier
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
A. Lecture séquentielle d'un fichier de Np pages.
1. cas simplifié : le fichier réside dans un seul cylindre
tlsf1 = tla1 + (Np - 1) x ttr
2. cas général : le fichier occupe plusieurs cylindres
il faut compter le temps de déplacement du bras aux cylindres suivants (seek1)
Nombre de cylindres suivants : ncyl = Np x Lp/ Lcyl + 0,5
Temps de lecture du fichier : tlsf1 = tla1 + (Np - 1) x ttr + ncyl x seek1
Np = nombre de pages Lp = taille d'une page Lcyl = taille d'un cylindre
3. Calcul simplifié : on néglige tla1 et seek1 devant le temps du transfert
tlsf1 Np x ttrà vérifier !
Disque dédié (cas le plus favorable)
azerty Bases de données J-L Hainaut 2009 45
4.4 Lecture séquentielle d'un fichier
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
B. Lecture séquentielle d'un fichier de Np pages.Disque partagé, lecture anticipée (cas normal)
Caractéristiques :
1. Plusieurs processus utilisent le disque
2. Conséquence : entre deux lectures (avec anticipation) le bras se déplace de manière aléatoire
3. La lecture du fichier apparaît comme une série de lectures de courtes séquences de pages consécutives
azerty Bases de données J-L Hainaut 2009 46
4.4 Lecture séquentielle d'un fichier
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
B. Lecture séquentielle d'un fichier de Np pages.Disque partagé, lecture anticipée (cas normal)
Lecture du fichier avec anticipation d'une piste :
tlsf2 = Np x tls1
azerty Bases de données J-L Hainaut 2009 47
4.4 Lecture séquentielle d'un fichier
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
C. Lecture séquentielle d'un fichier de Np pages.Disque partagé, pas de lecture anticipée (cas le plus défavorable)
Caractéristiques :
1. Plusieurs processus utilisent le disque
2. Le processus lit une page à la fois sans anticipation
3. La lecture du fichier apparaît comme une série de lectures de pages d'adresses aléatoires
azerty Bases de données J-L Hainaut 2009 48
4.4 Lecture séquentielle d'un fichier
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
C. Lecture séquentielle d'un fichier de Np pages.Disque partagé, pas de lecture anticipée (cas le plus défavorable)
Lecture du fichier sans lecture anticipée :
tlsf3 = Np x tla1
azerty Bases de données J-L Hainaut 2009 49
4.4 Lecture séquentielle d'un fichier
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Lecture séquentielle d'un fichier de Np pages.
Exemple : Np = 250.000 pages
B. Disque partagé avec lecture anticipée d'une piste :
tlsf2 = Np x tls1 = 46 sec
A. Disque dédié : Calcul standard : tlsf1 = tla1 + (Np - 1) x ttr + ncyl x seek1 = 18,8 secCalcul simplifié : tlsf1 Np x ttr = 18,5 sec
C. Disque partagé sans lecture anticipée :
tlsf3 = Np x tla1 = 3.075 secutilité des
optimisations !
azerty Bases de données J-L Hainaut 2009 50
4.4 Lecture séquentielle d'un fichier
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Le phénomène de fragmentation
En principe, un fichier occupe une suite de pages contiguës sur le disque.
Dans certaines circonstances, il n'est pas possible d'allouer au fichier un espace d'un seul tenant :
• pas assez d'espace libre contigu sur le disque au moment de la création du fichier stockage en plusieurs fragments
• le fichier s'est progressivement étendu il a fallu lui ajouter des pages
En toute généralité, le fichier occupe sur le support de 1 à nfrag fragments (= suites de pages contiguës).
azerty Bases de données J-L Hainaut 2009 51
4.4 Lecture séquentielle d'un fichier
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Le phénomène de fragmentation
. . .
210 502 503 504 505 1286 1287 12891288 Np-1Np-2
séquentiel ( tls1)
1 fragment
. . .
210 Np-1Np-2502 503
. . .
505504 1286 1287
. . .
12891288
séquentiel ( tls1)
séquentiel ( tls1)
séquentiel ( tls1)
aléatoire ( tla1)
aléatoire ( tla1)
3 fragments
azerty Bases de données J-L Hainaut 2009 52
4.4 Lecture séquentielle d'un fichier
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Le phénomène de fragmentation.
Le fichier est formé de Np pages réparties en nfrag fragments.
• Temps de lecture du fichier (disque dédié) :
tlsf4 tlsf1 + (nfrag - 1) x tla1
• Temps de lecture du fichier (disque partagé avec lecture anticipée d'une piste) :
tlsf4 tlsf2 + (nfrag - 1) x tla1
azerty Bases de données J-L Hainaut 2009 53
4.4 Lecture séquentielle d'un fichier
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Le phénomène de fragmentation
Exemple 1 : fichier de 250.000 pages décomposé de 50 fragments (de 50.000 pages ou 200 Mo en moyenne)
tlsf4 tlsf1 + nfrag x tla1 = 18,8 + 49 x 0,0123 = 19,4 sec. (+ 3%)
tlsf4 tlsf2 + nfrag x tla1 = 46 + 49 x 0,0123 = 46,6 sec. (+ 1,3%)
Exemple 2 : fichier de 25.000 pages décomposé de 50 fragments (de 500 pages ou 2 Mo en moyenne)
tlsf4 tlsf1 + nfrag x tla1 = 1,9 + 49 x 0,0123 = 2,5 sec..(+ 32%)
tlsf4 tlsf2 + nfrag x tla1 = 4,6 + 49 x 0,0123 = 5,2 sec. (+ 13%).
Exemple 3 : fichier de 2.500 pages décomposé de 50 fragments (de 50 pages ou 200 Ko en moyenne)
tlsf4 tlsf1 + nfrag x tla1 = 0,2 + 49 x 0,0123 = 0,8 sec..(+ 300%)
tlsf4 tlsf2 + nfrag x tla1 = 0,5 + 49 x 0,0123 = 1,1 sec. (+ 120%).
azerty Bases de données J-L Hainaut 2009 54
4.4 Lecture séquentielle d'un fichier
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Le phénomène de fragmentation
Quelques conclusions rapides• la dégradation du temps de lecture est sensible pour des fragments de
petite taille (prépondérence de tla1 sur ttr ou tls1).• la dégradation du temps de lecture est sensible les petits fichiers très
fragmentés.• la dégradation du temps de lecture est négligeable les fichiers de grande
taille peu fragmentés.
Défragmentation : opération visant à diminuer le nombre de fragments des fichiers sur le support.Utilitaires de défragmentation ou plus simplement
• déplacement des fichiers du support A vers le support B• supression des fichiers sur le support A• déplacement des fichiers du support B vers le support A
Variante : déplacements via un utilitaire d’image de disque ou de partition (Ghost, Acronis, etc.)
azerty Bases de données J-L Hainaut 2009 55I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.5 Les index
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
azerty Bases de données J-L Hainaut 2009 56I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
Index structure technique associée à un fichier (table par exemple) qui permet un accès sélectif et rapide aux enregistrements (ou lignes) de ce fichier qui possèdent des valeurs déterminées de certains champs. Ces champs constituent la clé de l'index.
En SQL, l'extraction et la modification de données ne nécessitent pas la connaissance des index.
On peut associer un nombre quelconque d'index à un fichier (table).
Un index est dit identifiant si un identifiant a été déclaré sur la clé de cet index.
4.5 Les index
azerty Bases de données J-L Hainaut 2009 57I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
4.5 Les index
Les index améliorent les performances de certaines opérations sur les données mais induisent des coûts de stockage et/ou de gestion.
La requête select NOM, LOCALITE from CLIENT where NCLI = ’C400’ • s'exécutera en 15 sec sans index sur NCLI
• et en 25 msec avec un index sur NCLI (600 fois plus rapidement !).
Mais, pas de miracle : tout avantage a un coût ! Ici, coût de gestion de l'index.
La modification de lignes de la table CLIENT implique des opérations de modification de l'index sur NCLI.
azerty Bases de données J-L Hainaut 2009 58I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
4.5 Les index
Formellement, un index défini sur une colonne K de la table T matérialise une fonction f qui renvoie pour chaque valeur k de K un ensemble A d'adresses de lignes dans T.
A = f(k)
Si la colonne K est identifiante, A contient au plus une adresse.
Les différentes technologies d'index se distinguent par la manière dont la fonction f est implémentée.
azerty Bases de données J-L Hainaut 2009 59I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
4.5 Les index
Deux classes d'index
1. les index primaires
2. les index secondaires
azerty Bases de données J-L Hainaut 2009 60I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
4.5 Les index
Index primaire
1. le plus souvent identifiant
2. un seul index primaire par fichier
3. la structure du fichier dépend fortement de la présence d'un index primaire
4. difficile d'ajouter et de supprimer un index primaire au vol
5. faible volume, très bonne performances
Index secondaire
1. identifiant ou non identifiant
2. de 0 à N index secondaires par fichier
3. la structure du fichier est indépendante de la présence d'un index secondaire
4. facile d'ajouter et de supprimer un index secondaire au vol
5. volume plus important, moins bonnes performances
6. Certains SGBD n'offrent que des index secondaires
azerty Bases de données J-L Hainaut 2009 61I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.1 Introduction 4.5 Les index4.2 Les mémoires externes 4.6 Organisation séquent. indexée4.3 Espace de stockage 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier . . .
4.5 Les index
Principales technologies des index primaires
1. organisation séquentielle indexée
2. organisation calculée
azerty Bases de données J-L Hainaut 2009 62I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
4.6 Organisation séquentielle indexée
azerty Bases de données J-L Hainaut 2009 63I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Un fichier séquentiel indexé de clé K est constitué• d'un fichier de base séquentiel ordonné sur le(s) champ(s) K• d'un index sur K
fichier de baseordonné sur K
index sur K
4.6 Organisation séquentielle indexée
azerty Bases de données J-L Hainaut 2009 64I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Considérant l'expression A = f(k), la fonction f est implémentée sous la forme d'une table de correspondance fournissant une adresse (celle d'une page) pour chaque valeur de K.
4.6 Organisation séquentielle indexée
azerty Bases de données J-L Hainaut 2009 65I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
L'organisation séquentielle indexée d'un fichier permet
1. la lecture séquentielle ordonnée des enregistrements du fichier de base
2. la lecture séquentielle ordonnée des valeurs de K (via l'index)
3. l'accès rapide à l'enregistrement possédant une valeur de clé K = k
4. l'insertion rapide d'un enregistrement de clé K
5. la modification rapide de la valeur de K d'un enregistrement
6. la suppression rapide d'un enregistrement
4.6 Organisation séquentielle indexée
à démontrer !
Cette organisation s'inspire de structure d'arbre dite B-tree (balanced tree)
azerty Bases de données J-L Hainaut 2009 66I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Hypothèses simplificatrices
1. La clé K est un identifiant du fichier
2. Le fichier contient des enregistrements d'un seul type
3. Les enregistrements sont de taille fixe
4. La taille des enregistrements est inférieure à la moitié de celle des pages
5. Un enregistrement est entièrement compris dans une page
4.6 Organisation séquentielle indexée
azerty Bases de données J-L Hainaut 2009 67
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
B062 GOFFIN Namur B2
B112 HANSENNE Poitiers C1
B332 MONTI Genève B2
B512 GILLET Namur B1
C003 AVRON Poitiers B1
B512 GILLET Namur B2
C003 AVRON Poitiers C1
C123 MERCIER Genève B2
C123 MERCIER Namur C1
C400 FERARD Poitiers B2
D063 MERCIER Toulouse
F010 TOUSSAINT Poitiers C1
F011 PONCELET Poitiers B2
F400 JACOB Bruxelles C2
K111 VANBIST Lille B1
K729 NEUMAN Toulouse
N227 MARTIN Bruxelles C1
P650 ANTOINE Poitiers B2
B332 C003 D063 F400
G110 H736
H991
F375 BERNIER Paris C1
G110 STEVEN London B2
L422 FRANK Namur C1
M562 MERCIER Toulouse C2
M345 NOEL Liège B1
S127 VANDERKA Namur C1
S712 GUILLAUME Paris B1
. . .
I452 J079
J823 K729 M345 P650
S712
F400 H991 J079 P650
S712
P650 S712
fichier de base
index
H109 DUPUIS Lausanne C2
H736 ARNOULD Paris B1
Observations
1. les enregistrements de chaque page de base sont ordonnés selon K
2. une page de base est caractérisée par sa plus grande valeur de K.
3. les pages de base sont ordonnées selon K
4. l'index comprend n niveaux (n 1)
10. certaines pages ne sont pas pleines
7. chaque entrée du niveau n de l'index comprend 1 valeur ki de K et 1 pointeur vers la page de base dont la plus grande valeur de K = ki
8. chaque entrée du niveau m (m < n) de l'index comprend 1 valeur ki de K et 1 pointeur vers la page d'index de niveau m+1 dont la plus grande valeur de K = ki
9. le 1er niveau de l'index comprend 1 page
5. chaque page d'index comprend des entrées d'index
6. chaque niveau d'index jouit des propriétés 1 à 3
11. la position d'un enregistrement est fonction de sa valeur de K
azerty Bases de données J-L Hainaut 2009 68
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
G110 H736 H991 F400
H991 J079 P650
P650 S712
H109 DUPUIS Lausanne C2
H736 ARNOULD Paris B1
niveau 1 niveau 2 niveau 3 page de base
Accès par clé (K = 'H109')
K = 'H109'
H109 P650 H109 H991 H109 H736 H109 se trouve dans cette pageou nulle part ailleurs
Observation 1 : la recherche par clé nécessite la lecture de n+1 pages, quel que soit l'enregistrement.
Observation 2 : si la recherche échoue, tout n'est pas perdu : elle indique la page dans laquelle l'enregistrement aurait dû se trouver.
azerty Bases de données J-L Hainaut 2009 69
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
i := 1; p := p1
i := i + 1
I := 1re entrée de la page [p] tel que I.K k
R:= 1er enreg. de la page [p] tel que R.K k
i = n ?
oui
non
non
oui
R.K = k ?
l'enregistrement recherché est absent du fichier
R est l'enregistrement recherché
p := I.ptr
Accès par clé (K = k)
azerty Bases de données J-L Hainaut 2009 70
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Les trois modes d'accès aux enregistrements
select * from CLIENTwhere NCLI = 'C400'
select * from CLIENTwhere NCLI >= 'C400'order by NCLI
select * from CLIENTorder by NCLI
ponctuel selon K intervalle selon K séquentiel selon K
azerty Bases de données J-L Hainaut 2009 71
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Insertion d'un enregistrement (K = k)
Procédure
1. On recherche la page [p] dans laquelle l'enregistrement devrait être stocké.
2. Si la page [p] n'est pas pleine, on y insère l'enregistrement.
3. Si la page [p] est pleine, on procède à son éclatement :
3.1 on insère devant [p] une page vide (logiquement, pas physiquement)
3.2 on répartit la charge de [p] entre ces deux pages
3.3 on insère l'enregistrement dans l'une de ces deux pages
3.4 on insère une entrée relative à la nouvelle page dans le niveau n de l'index
Observations1. le taux d'occupation de chaque page reste 0,52. les pages logiquement consécutives ne le sont plus nécessairement
physiquement3. l'insertion d'une entrée d'index obéit à la même procédure
azerty Bases de données J-L Hainaut 2009 72
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Suppression d'un enregistrement
Procédure 1. On recherche la page [p] de l'enregistrement. 2. On efface l'enregistrement de la page [p].3. Si le taux d'occupation de la page [p] est < 0,5 :
3.1 on rééquilibre le contenu de [p] avec celui de la page précédente3.2 si le taux d'occupation des 2 pages est 0,5, on corrige l'entrée de
niveau n relative à la 1re page3.2 si le taux d'occupation d'une des pages est < 0,5
3.3.1 on transfère le contenu de la page précédente vers [p]3.3.2 on supprime la page précédente3.3.3 on supprime son entrée dans le niveau n de l'index
Observations1. le taux d'occupation de chaque page reste 0,52. on produit des pages vides réutilisables lors de l'insertion d'enregistrements3. la suppression d'une entrée d'index obéit à la même procédure
azerty Bases de données J-L Hainaut 2009 73
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Modification de la valeur de K (k1 k2) d'un enregistrement
Procédure 1. On supprime l'enregistrement K = k1. 2. On crée un enregistrement K = k2 de même contenu.
azerty Bases de données J-L Hainaut 2009 74
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Volume d'un fichier séquentiel indexé
Les données
1. Nombre d'enregistrements : Nr
2. Taille des enregistrements : Lr
3. Taille de la clé K : Lk
4. Taille d'une entrée d'index (Lk + taille pointeur de page) : Li
5. Taux moyen d'occupation des pages de base : B
6. Taux moyen d'occupation des pages d'index : I
Les grandeurs calculées
1. Taille du fichier (en pages) : Np
2. Taille du fichier de base : Npb
3. Taille de l'index : Npi
4. Nombre de niveaux d'index : n
5. Nombre d'entrée d'index au niveau m : Ni(m)
6. Nombre de pages d'index au niveau m : Npi(m)
azerty Bases de données J-L Hainaut 2009 75
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Volume d'un fichier séquentiel indexé
On a bien sûr : Np = Npb + Npi
Fichier de base : calcul de Npb
Capacité d'une page de base Mrpp = Lp / LrContenu moyen d'une page de base Nrpp = b x Mrpp
Nombre de pages de base Npb = Nr / Nrpp
pages vides ignorées
azerty Bases de données J-L Hainaut 2009 76
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Volume d'un fichier séquentiel indexé
Index : calcul de Npi
On a : Npi = m n Npi(m)
Capacité d'une page d'index Mipp = Lp / Li Contenu moyen d'une page de base Nipp = i x Mipp
Taille du niveau nNombre d'entrée de l'index Ni(n) = Npb
Nombre de pages Npi(n) = Ni(n) / Nipp
Taille d'un niveau m < nNombre d'entrée de l'index Ni(m) = Npi(m+1)
Nombre de pages Npi(m) = Ni(m) / Nipp
On atteint le niveau m = 1 lorsque Npi(m) = 1
On en déduit le nombre de niveaux n
azerty Bases de données J-L Hainaut 2009 77
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Volume d'un fichier séquentiel indexé
Index : calculs simplifiés
Evaluation de n (base quelconque) n = log(Npb) / log(Nipp)
Evaluation de Npi
En général Npi(n) >> m < n Npi(m)
Donc Npi Npi(n) = Npb / Nipp
azerty Bases de données J-L Hainaut 2009 78
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Volume d'un fichier séquentiel indexé
Pour les concepteurs pressés et pas trop regardants :
1. Taille du fichier de base Npb = Nr / b x Lp / Lr
2. Taille de l'index Npi = Npi(n) = Npb / (i x Lp / Li)
3. Nbre de niveaux d'index n = log(Npb) / log(b x Lp / Li ) Eviter d'étudier ces formules par coeur !
azerty Bases de données J-L Hainaut 2009 79
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Evaluation des taux d'occupation
Comment évolue b ? 1. En fonction du nombre d'opérations depuis la création du fichier 2. Dépend du taux d'insertions %Add [0-100] dans les opérations (100 = insertions
seulement) 3. Dépend de la taille des pages (Mrpp) [en nombre d'enregistrements]4. Dépend du taux d'occupation 0 [0-1] à la création du fichier5. Ne dépend pas de la taille du fichier (Np)
Comment évaluer b ? 1. Analytiquement (processus stochastiques) : complexe 2. Par simulation : plus simple, intuitif mais réclame un peu de programmation
Le comportement de i est identique à celui de b.
azerty Bases de données J-L Hainaut 2009 80
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Evaluation des taux d'occupationlire : Mrpp !
tauxd'occupation en %
Nbre totald'opérations
Nbre d'opérations en pourcentage du nombre initial d'enregistrements
azerty Bases de données J-L Hainaut 2009 81
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Evaluation des taux d'occupation
50
55
60
65
70
75
80
85
90
95
100
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
Simulation fichier de baseNp = 1.000Mrpp = 10
0 = 80%
%Add = 100Nop = 8.000
azerty Bases de données J-L Hainaut 2009 82
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Evaluation des taux d'occupation
50
55
60
65
70
75
80
85
90
95
100
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
Simulation indexNp = 1.000Mrpp = 85
0 = 80%
%Add = 100Nop = 68.000
azerty Bases de données J-L Hainaut 2009 83
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Temps d'accès à un fichier séquentiel indexé
Trois opérations 1. Lecture séquentielle 2. Lecture ponctuelle par l'index3. Lecture par intervalle de K par l'index
Hypothèses réalistes 1. Disque partagé 2. Lecture anticipée d'une piste
azerty Bases de données J-L Hainaut 2009 84
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Temps d'accès à un fichier séquentiel indexé
1. Lecture séquentielle selon K
Analyse 1. Lecture des pages du fichier de base inappropriée, car ruptures de séquence
dues à l'éclatement des pages (séquence physique séquence logique)2. On accède aux pages de base à partir de l'index (tout ou dernier niveau avec
chaînage), qui est ordonné selon K 3. Temps de lecture = temps de parcours de l'index (ou dernier niveau) + temps
d'accès aux pages de base4 Mais, temps de parcours de l'index en général négligeable
azerty Bases de données J-L Hainaut 2009 85
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Temps d'accès à un fichier séquentiel indexé
1. Lecture séquentielle selon K
Calcul sans rupture de séquenceOn a déterminé : tlsf = tlsf2 = Npb x tls1
Calcul avec ruptures de séquence
Soit r la proportion de pages en rupture de séquence
On a : tlsf = (1 - r) x Npb x tls1 + r x Npb x tla1
Exemple
Npb = 250.000; r = 0,2;
Sans rupture : tlsf = 46 secAvec ruptures : tlsf = 652 sec
azerty Bases de données J-L Hainaut 2009 86
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Temps d'accès à un fichier séquentiel indexé
2. Lecture ponctuelle selon K
Analyse 1. Examen naïf : on accède à 1 page pour chaque niveau d'index + 1 page de
base2. En pratique, on charge les premiers niveaux d'index dans le tampon pour éviter
les accès au disque
azerty Bases de données J-L Hainaut 2009 87
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Temps d'accès à un fichier séquentiel indexé
2. Lecture ponctuelle selon K
Calcul naïf : tlk1 = tla1 x (n + 1)
Calcul pratiqueSi on maintient les m premiers niveaux d'index dans le tampon : tlk1 = tla1 x (n-m+1)
Le nombre de pages du tampon dédiées au processus est de j m Npi(j) + 1
ExempleNpb = 250.000; n = 3; Npi(1) = 1; Npi(2) = 46; Npi(3) = 3.361; Tampon de 1 page: tlk1 = 12,3 X 4, soit 49,2 msecTampon de 1 + 1 = 2 pages : tlk1 = 12,3 X 3, soit 36,9 msecTampon de 1 + 46 + 1 = 48 pages : tlk1 = 12,3 X 2, soit 24,6 msecTampon de 1 + 46 + 3.361 + 1 = 3.409 pages : tlk1 = 12,3 X 1, soit 12,3 msec
+ 1 page pourtout le reste
les performancesont un coût
azerty Bases de données J-L Hainaut 2009 88
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Temps d'accès à un fichier séquentiel indexé
3. Lecture par intervalle [k1,k2] selon K
Analyse 1. Intervalle : NCLI >= 'K111'; NCLI between 'K000' and 'K999'; NCLI like 'K%'2. L'index est utilisé en deux temps :
2.1 accès par l'index NCLI = k1 (ou, plus généralement 1er enregistrement qui satisfait la condition NCLI >= k1)
2.2 lecture séquentielle selon l'index tant que K <= k2
azerty Bases de données J-L Hainaut 2009 89
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Temps d'accès à un fichier séquentiel indexé
Nombre d'enregistrements et de pages dans l'intervalle• Probabilité qu'un enregistrement tombe dans l'intervalle : pik
• Nombre d'enregistrements dans l'intervalle : nrik = pik x Nr
• Ces enregistrements occupent : npik = nrik / Nrpp + 0,5 + 1 pages consécutives
Calcul du temps de lecture• séquence courte : tlik = tla1 + (npik - 1) x ttr
• séquence plus longue (lecture anticipée) : tlik = npik x tls1
• séquence plus longue avec ruptures : voir texte
3. Lecture par intervalle [k1-k2] selon K
corriger !
azerty Bases de données J-L Hainaut 2009 90
4.6 Organisation séquentielle indexée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Compléments
1. Adaptation aisée au cas où K n'est pas un identifiant (mais rarement appliqué)
2. Le fichier de base est instable : l'adresse d'un enregistrement peut évoluer au cours du temps
3. Application intéressante aux fichiers comportant des enregistrements de plusieurs types.
4. Phénomène de dégradation des performances4.1 nombre croissant de ruptures de séquences dues à l'éclatement des pages4.2 baisse du taux d'occupation (à Nr constant, Np et n augmentent)4.3 heureusement : dégradation progressive (graceful degradation)
5. Nécessité de réorganiser le fichier en temps utile. Processus très simple et très rapide (linéaire en Nr):
5.1 lire séquentiellement le fichier courant5.2 ranger séquentiellement ces enregistrements dans le nouveau fichier, avec un
taux d'occupation initial favorable (p. ex. 0 = 0,8)5.3 en parallèle, construction des différents niveaux d'index, avec un taux
d'occupation initial favorable.
azerty Bases de données J-L Hainaut 2009 91I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.7 Organisation calculée
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
azerty Bases de données J-L Hainaut 2009 92I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
Deuxième technique de base d'implémentation d'un index primaire
L'adresse d'un enregistrement est obtenue par une fonction de calcul
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
4.7 Organisation calculée
azerty Bases de données J-L Hainaut 2009 93I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
4.7 Organisation calculée
Considérant l'expression A = f(k), la fonction f est implémentée sous la forme d'une procédure de calcul fournissant une adresse (celle d'une page) pour chaque valeur de K.
f k
calculé
conversion k pcalculée
séquentielindexé
conversion k pmémorisée
k page p
azerty Bases de données J-L Hainaut 2009 94I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
4.7 Organisation calculée
L'organisation calculée d'un fichier permet
1. la lecture séquentielle non ordonnée des enregistrements du fichier de base
2. l'accès rapide à l'enregistrement possédant une valeur de clé K = k
4. l'insertion rapide d'un enregistrement de clé K
5. la modification rapide de la valeur de K d'un enregistrement
6. la suppression rapide d'un enregistrement
à démontrer !
Cette organisation ne permet pas l'accès séquentiel ordonné
azerty Bases de données J-L Hainaut 2009 95I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
4.7 Organisation calculée
Hypothèses simplificatrices
1. La clé K est un identifiant du fichier
2. Le fichier contient des enregistrements d'un seul type
3. Les enregistrements sont de taille fixe
4. Un enregistrement est entièrement compris dans une page
Ces contraintes sont aisées à lever
azerty Bases de données J-L Hainaut 2009 96I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
4.7 Organisation calculée
Nature de la fonction f ?
K : identifiantp : adresse de la page de l'enregistrementMrpp : capacité d'une page
Cas 1K = {0, 1, 2, 3, ..., 99998, 99999}p = K / Mrpp
Cas 2K = {1, 3, 5, 7, ..., 99997, 99999}p = ((K - 1)/2) / Mrpp
Cas 3K = {1, 3, 4, 87, 162, 163, 164, 290, 1035, ..., 99991}p = ?
Cas 4K = {'Anselme', 'Bernard', 'Catherine', 'Eve', ..., 'Xavier'}p = ?
azerty Bases de données J-L Hainaut 2009 97I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
4.7 Organisation calculée
Nature de la fonction f ?
La fonction f doit convertir un ensemble de valeurs quelconques en une suite d'entiers naturels également répartis dans l'espace des adresses
En pratique, une telle fonction n'existe pas en toute généralité
La fonction f doit convertir un ensemble de valeurs quelconques en une suite d'entiers naturels raisonnablement bien répartis dans l'espace des adresses
Les pages du fichier seront donc inégalement occupées : • certaines pages resteront peu, voire pas occupées• certaines pages déborderont.
azerty Bases de données J-L Hainaut 2009 98I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
Deux problèmes à résoudre :
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
4.7 Organisation calculée
1. Choix de la fonction f de calcul d'adresse
2. Gestion des débordements
azerty Bases de données J-L Hainaut 2009 99I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
La fonction de calcul d'adresse
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
4.7 Organisation calculée
f(k) = f3(f2(f1k)))
f1 : numérisation - transforme k en nombre n1
f2 : hachage - transforme n1 en n2 de répartition régulière
f3 : cadrage - transforme n2 en p, ajusté à Np
Objectif : répartir au mieux les valeurs de K dans l'espace des adresses.
azerty Bases de données J-L Hainaut 2009 100I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
La fonction de calcul d'adresse
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
4.7 Organisation calculée
Où ranger l’enregistrement d’identifiant "Charles" dans un fichier de 5.000 pages ?
• numérisation f1Codes ASCII des caractères de "Charles" = chaîne de 56 bits :
01000011 01101000 01100001 01110010 01101100 01100101 01110011
XOR entre les 32 premiers bits et les 24 suivants étendus à 32 bits par des 0
On obtient le nombre 0010 1111 0000 1101 0001 0010 0111 0010 = 789385842
On a donc f1("Charles") = 789385842.
• hachage f2Technique du pliage : f2(789385842) = 78938 + 02485 = 81423.
• cadrage f3Ajustement à un espace de [0- 4999] pages : f3(81423) = 81423 mod 5000 = 1423.
On a donc :f("Charles") = 1423
L’enregistrement sera rangé dans la page d ’adresse p = 1 423.
azerty Bases de données J-L Hainaut 2009 101I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
4.7 Organisation calculée
Gestion des débordements
Que faire d'un enregistrement dont l'adresse p désigne une page pleine ?
Réponse : on le stocke dans une page dont l'adresse p' est dérivable de p. Il devient un squatter.
Exemple : on le stocke dans la page la plus proche de p qui possède assez d'espace pour accueillir l'enregistrement.
Problème : comment retrouver p' à partir de p ?
On distingue donc : l’adresse de base pl’adresse de stockage p’
azerty Bases de données J-L Hainaut 2009 102
4.7 Organisation calculée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
C
A
B
D
page 85page 84page 83page 82
F
E
Gestion des débordements
Technique par chaînage en zone primaire
(la page 82 contient un squatter)
1. insertion de A (p = 82) dans la page 82
2. insertion de B (p = 82) dans la page 82
(la page 82 accueille un squatter)
3. insertion de C (p = 82) dans la page 82
(la page 83 est pleine)
4. insertion de D (p = 82) dans la page 84
(la page 84 est pleine)
5. insertion de E (p = 82) dans la page 84
6. insertion de F (p = 82) dans la page 84
(1 enreg. est supprimé de la page 83)
Historique de l'insertion d'une séquence d'enregistrements de même valeur de p
• présence de squatters
• chaînes longues
• bloquage brutal à 100%
• bonne occupation de l’espace
azerty Bases de données J-L Hainaut 2009 103
4.7 Organisation calculée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Gestion des débordements
Technique alternative
zone primaire
C
AB
page 82DE
J
HI
page 83K
N
LM
page 84OP
Y
WX
page 85Z0
FG
page 1471
S
QR
page 1472TU
page 1473
V
page 1474
zone de débordement
• pas de squatters
• chaînes courtes
• pas de bloquage (graceful degradation)
• moins bonne occupation de l’espace
azerty Bases de données J-L Hainaut 2009 104
4.7 Organisation calculée
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
1,00
1,05
1,10
1,15
1,20
1,25
1,30
1,35
1,40
1,45
1,50
50 55 60 65 70 75 80 85 90 95 100
Mrpp = 5
Mrpp = 10
Mrpp = 20
Mrpp = 30
Mrpp = 40
Performances d'un fichier calculé (chaînage en zone primaire)
azerty Bases de données J-L Hainaut 2009 105
4.7 Organisation calculée - Comparaison des techniques primaires
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
disponibilité très répandu
séquentiel indexé
plus rare
calculé
occupation espace disque moyen moyen à excellent
occupation mémoire centrale plusieurs milliers de pages 1 page
stabilité adresses faible très bonne
accès par clé : temps moyen assez bon très bon
accès par clé : constance
tps d'accès par clé selon Npb
accès ordonné
accès par intervalle
dégradation
extensibilité
reconstruction
tps constant
logarithmique
oui
oui
progressive
oui
rapide
tps très variable [*]
moyenne constante
non
non
brutale ou progressive
selon la technique
lente
[*] sauf techniques spéciales
azerty Bases de données J-L Hainaut 2009 106I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.8 Les index secondaires
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
azerty Bases de données J-L Hainaut 2009 107I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
Index primaire
1. le plus souvent identifiant
2. un seul index primaire par fichier
3. la structure du fichier dépend fortement de la présence d'un index primaire
4. difficile d'ajouter et de supprimer un index primaire au vol
5. faible volume, très bonne performances
Index secondaire
1. identifiant ou non identifiant
2. de 0 à N index secondaires par fichier
3. la structure du fichier est indépendante de la présence d'un index secondaire
4. facile d'ajouter et de supprimer un index secondaire au vol
5. volume plus important, moins bonnes performances
6. Certains SGBD n'offrent que des index secondaires
Rappel
4.8 Les index secondaires
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
azerty Bases de données J-L Hainaut 2009 108I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Index (dans un livre)
Bbase de données active 167base de données temporelles 153, 170between 67
Ccardinalité d’attribut 182cardinalité d’un role 187catalogue 147, 169cellules 280Chen 29, 205chimpanzé 364circuit de dépendances 312, 392classe d’objets 201classe fonctionnelle 184, 185, 242, 245clé étrangère 34, 44, 77, 81, 156close 145coalescing 155COBOL 18, 143Codd 27codomaine 351colonne 32, 35, 44
les termes de la lettre B
le terme clé étrangère
numéros des pagesqui contiennent ce terme
Rappel
4.8 Les index secondaires
azerty Bases de données J-L Hainaut 2009 109I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
BruxellesGenève
LilleNamur
ParisPoitiers
Toulouse
11031201 06 14 151602 07 09 04 05 08 10 13
01020304050607080910111213141516
les valeurs de LOCALITE,triées par ordre alphabétique
numéros des lignes dontLOCALITE = 'Toulouse'
Index sur la colonne LOCALITE
chaque ligne possède un numéro unique;l'accès à une ligne de numéro donné est très rapide
Index (dans une base de données) Rappel
4.8 Les index secondaires
azerty Bases de données J-L Hainaut 2009 110
4.8 Les index secondaires
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Index (LOCALITE)
Bruxelles
Genève
Lille
Paris
Toulouse
Poitiers
Namur
Fichier de base
B062 ... NamurGoffin B2 ...
S712 ... ParisGuillaume B1 ...
B112 ... PoitiersHansenne C1 ...
B332 ... GenèveMonti B2 ...
B512 ... ToulouseGillet B1 ...
C003 ... ToulouseAvron B1 ...
C123 ... NamurMercier C1 ...
C400 ... PoitiersFérard B2 ...
D063 ... ToulouseMercier A1 ...
F010 ... PoitiersToussaint C1 ...
F011 ... PoitiersPoncelet B2 ...
F400 ... BruxellesJacob C2 ...
K111 ... LilleVanbist B1 ...
K729 ... ToulouseNeuman B3 ...
L422 ... NamurFrank C1 ...
S127 ... C1 NamurVanderka ...
Index du dictionnaire des valeurs (séq. indexé ou calculé)
Dictionnaire des valeurs
données de base
Accès aux enregistrements (liste de pointeurs)
Structure d'un index secondaire (non identifiant)
Nv entrées
azerty Bases de données J-L Hainaut 2009 111
4.8 Les index secondaires
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
peut remplacerun index primaire
Index (NCLI) Fichier de base
B062 ... NamurGoffin B2 ...
S712 ... ParisGuillaume B1 ...
B112 ... PoitiersHansenne C1 ...
B332 ... GenèveMonti B2 ...
B512 ... ToulouseGillet B1 ...
C003 ... ToulouseAvron B1 ...
C123 ... NamurMercier C1 ...
C400 ... PoitiersFérard B2 ...
D063 ... ToulouseMercier A1 ...
F010 ... PoitiersToussaint C1 ...
F011 ... PoitiersPoncelet B2 ...
F400 ... BruxellesJacob C2 ...
K111 ... LilleVanbist B1 ...
K729 ... ToulouseNeuman B3 ...
L422 ... NamurFrank C1 ...
S127 ... C1 NamurVanderka ...
B062
S712
B112
B332
B512
C003
C123
C400
D063
F010
F011
F400
K111
K729
L422
S127
Structure d'un index secondaire (identifiant)
azerty Bases de données J-L Hainaut 2009 112
4.8 Les index secondaires
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Index (LOCALITE)
Bruxelles
Genève
Lille
Paris
Toulouse
Poitiers
Namur
Index (NCLI) Fichier de base
B062 ... NamurGoffin B2 ...
S712 ... ParisGuillaume B1 ...
B112 ... PoitiersHansenne C1 ...
B332 ... GenèveMonti B2 ...
B512 ... ToulouseGillet B1 ...
C003 ... ToulouseAvron B1 ...
C123 ... NamurMercier C1 ...
C400 ... PoitiersFérard B2 ...
D063 ... ToulouseMercier A1 ...
F010 ... PoitiersToussaint C1 ...
F011 ... PoitiersPoncelet B2 ...
F400 ... BruxellesJacob C2 ...
K111 ... LilleVanbist B1 ...
K729 ... ToulouseNeuman B3 ...
L422 ... NamurFrank C1 ...
S127 ... C1 NamurVanderka ...
B062
S712
B112
B332
B512
C003
C123
C400
D063
F010
F011
F400
K111
K729
L422
S127
Un fichier peut posséder plusieurs index secondaires
azerty Bases de données J-L Hainaut 2009 113
4.8 Les index secondaires
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Représentation pratique des listes de pointeurs
Toulouse
Toulouse
Toulouse
Toulouse
Toulouse
Toulouse
Toulouse
Toulouse
Toulouse
Toulouse
une entrée théorique Toulouse
Toulouse
Toulouse
Toulouse
ner entrées réelles
azerty Bases de données J-L Hainaut 2009 114
4.8 Les index secondaires
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Performances d'un index secondaire
Un index secondaire est constitué de :
• un dictionnaire de valeurs; pour chacune des Nv entrées théoriques, ner entrées réelles :
• une valeur de K de longueur Lk
• une sous-liste de R' pointeurs
• un index primaire pour l'accès au dictionnaire de valeurs (séquentiel indexé ou calculé)
• le volume de l'index
• le temps d'accès aux enregistrements selon le critère "where K = k"
• le temps d'accès aux enregistrements selon le critère "where K between k1 and k2"
On dispose donc de tous les éléments pour calculer :
azerty Bases de données J-L Hainaut 2009 115I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
4.9 Les techniques d'agrégation
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
azerty Bases de données J-L Hainaut 2009 116
4.9 Les techniques d'agrégation
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Proximité logique proximité physique
Proximité logique :
• enregistrements d'un fichier lus successivement
• enregistrements lus dans un certain ordre
• enregistrements couplés par des associations
Proximité physique :
• enregistrements dans la même page
• enregistrements dans des pages successives
Objectif : minimiser le nombre d'accès physiques
azerty Bases de données J-L Hainaut 2009 117
4.9 Les techniques d'agrégation
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Proximité logique proximité physique
enregistrements d'un fichier lus successivement
select NCLI, NOM, LOCALITE from CLIENT;
enregistrements rangés séquentiellement dans l'espace;chaque page est lue une seule fois
azerty Bases de données J-L Hainaut 2009 118
4.9 Les techniques d'agrégation
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Proximité logique proximité physique
enregistrements lus dans un certain ordre
select NCLI, NOM, LOCALITE from CLIENT order by NCLI;
les enregistrements sont rangés dans l'espace par valeurs croissante de NCLI;chaque page est lue une seule fois
azerty Bases de données J-L Hainaut 2009 119
4.9 Les techniques d'agrégation
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Proximité logique proximité physique
enregistrements couplés par des associations
select M.NCOM, DATECOM, QCOM, NPRO from COMMANDE M, DETAIL D where M.NCOM = D.NCOM;
les enregistrements COMMANDE et DETAIL de mêmes valeurs de NCOM sont rangés dans la (les) même(s) page(s);plusieurs enregistrements utiles dans une même page;
azerty Bases de données J-L Hainaut 2009 120
4.9 Les techniques d'agrégation
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Deux techniques très répandues :
• le clustering index (p. ex. DB2, SQL Server)
• le cluster (p. ex. Oracle)
azerty Bases de données J-L Hainaut 2009 121
4.9 Les techniques d'agrégation
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Le clustering index
• index secondaire sur une K;• table de base a priori en vrac MAIS :
(tant qu'à faire) on cherche à ranger les lignes selon les valeurs croissantes de K;
• lors du chargement initial, on laisse de l'espace libre dans chaque page;• les insertions se font autant que possible de manière à respecter l'ordre
selon K;• après un certain temps, l'ordre est de moins en moins respecté;• nécessite une réorganisation de temps en temps;
azerty Bases de données J-L Hainaut 2009 122
4.9 Les techniques d'agrégation
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Le clustering index
• au début, performances aussi favorables que le séquentiel indexé (lecture d'une page pour Nrpp lignes);
• au cours du temps, les performances se dégradent et se rapprochent de celles d'une table en vrac (lecture d'une page pour chaque ligne);
• un seul clustering index par table• exclut tout index primaire
favorise les requêtes incluant :• order by K• group by K• K between k1 and k2• K >= k1• K like 'MAC%';
azerty Bases de données J-L Hainaut 2009 123
4.9 Les techniques d'agrégation
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
Le cluster
Index (NCOM)
30179 C400 22/12/2008 30179 CS262 0060 30179 PA60 0020
30182 S127 23/12/2008 30182 PA60 0030
30178 K111 22/12/2008 30178 CS464 0025
30184 C400 23/12/2008 30184 CS464 0120 30184 PA45 0020
30185 F011 02/01/2009 30185 CS464 0260 30185 PA60 0015 30185 PS222 0600
30177
30178
30179
30182
30184
30185
30186
30187
Fichier de base : clusters <COMMANDE(NCOM), DETAIL(NCOM)>
• basé sur une colonne (ou des colonnes) K commune(s) à une ou plusieurs tables;
• les lignes de même valeur de K sont rangées dans la même page; si nécessaire dans des pages successives
• on associe un index à chaque cluster
azerty Bases de données J-L Hainaut 2009 124
4.9 Les techniques d'agrégation
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
. . . 4.7 Organisation calculée4.4 Lecture séquentielle d'un fichier 4.8 Index secondaires4.5 Les index 4.9 Techniques d'agrégation4.6 Organisation séquent. indexée
• un seul cluster par table• exclut tout index primaire
favorise les requêtes incluant :• des jointures• des sous-requêtes• group by K• K = k1
et, si l'index du cluster est en séquentiel indexé :• K between k1 and k2• K >= k1• K like 'MAC%';
Le cluster
azerty Bases de données J-L Hainaut 2009 125
Fin du chapitre 4
Chapitre suivant :
Chap. 5 : Les systèmes de gestion de bases de données
I. Concepts des bases de données
1. Motivation et introduction 5. Les SGBD2. Concepts des bases de données3. Modèle relationnel et normalisation4. Implémentation des structures de données
azerty Bases de données J-L Hainaut 2009 126