2 Gestion des données en

mémoire secondaire
 Données persistantes en mémoire
secondaire
– principalement le disque
 Organisation physique des données
– façon dont les données sont structurées en mémoire
secondaire
 Méthode d'organisation des données
– structure de données particulière utilisée pour
organiser les données en mémoire secondaire

08/02/25 © Robert Godin. Tous droits réservés 1

.
 Critères d'évaluation des méthodes
d'organisation

 Temps d'accès aux données par

rapport à différentes méthodes
d'accès
 Délai d'insertion et de suppression
 Occupation mémoire

08/02/25 © Robert Godin. Tous droits réservés 2

.
 Conception physique
 Choix des méthodes d ’organisation
– organisation sérielle
– organisation séquentielle
– indexage
– hachage
– organisation par grappe
– ...
 Schéma interne de la BD

08/02/25 © Robert Godin. Tous droits réservés 3

.
 2.1 Principales caractéristiques
des disques
 Unité de disque (disk pack ) ou
disque Plateau
T ête de
lecture/écriture
Secteur
Piste

Cylindre

08/02/25 © Robert Godin. Tous droits réservés 4

.
 Capacité de Superbit
 capacitéDisque = nbSurfaces  nbCylindres 
nbSecteursParPiste
Paramètre  tailleSecteur Valeur
Nombre de surfaces (nbSurfaces) 20
Nombre depistes par surface (nbCylindres) 1000
Nombre de secteurs par piste (nbSecteursParPiste) 50
Nombre d'octets de données par secteur (tailleSecteur) 512

 = 20 surfaces  1000 cylindres  50 secteurs par piste

 512 octets
 = 512,000,000 octets  500,000 kilooctets(K)  500
mégaoctets (M)

08/02/25 © Robert Godin. Tous droits réservés 5

.
 Transfert d ’un secteur
 Secteur
– unité d'adressage et de transfert minimal
 Adresse physique de secteur
– numéro de surface (noSurface), numéro de cylindre
(noCylindre), numéro de secteur dans la piste
(noSecteur)
 Adresse relative de secteur (noSecteurRelatif)
– dans l'intervalle [0..n-1]
 Tampon (buffer )
– zone de la mémoire centrale où transitent les données
de la mémoire secondaire

08/02/25 © Robert Godin. Tous droits réservés 6

.
 2.1.1Modèle simple d'estimation du coût
d'une entrée/sortie (transfert) sur disque

 Temps de transfert (entrée/sortie) de n

octets
– TempsESDisque(n) = TempsPosDébut + TempsTrans (n)
 TempsPosDébut = TempsDépBras + TempsRotation (10ms)
– TempsDépBras : 6-25 ms (6ms)

– TempsRotation : 4.18 à 8.35 ms = 60 à 120 tours/sec (4ms)

 TempsTrans(n) = n / TauxTransVrac
– TauxTransVrac = NombreOctetsPiste / TempsRotationComplète
(2M/sec)
– ex: TempsTrans(2K) = 2K / 2M/sec = 1ms
ex: TempsESDisque(2K) = 10ms + 1ms = 11ms

 Minimiser le nombre d'entrées/sorties en mémoire
secondaire

08/02/25 © Robert Godin. Tous droits réservés 7

.
 Importance de la contiguïté
physique
 Ex: transfert de 2000 secteurs de 512 octets (1M)
– Secteurs consécutifs
 TempsESDisque(1M) = 10ms + 500ms = 510ms
– Secteurs dispersés aléatoirement
 TempsESDisque(un secteur) = 10ms + 0.25ms =
10.25ms
 Total = 2000  10.25 = 20500 ms = 20.5 secs

 Effet de grappe (clustering)

– regrouper physiquement selon patrons d ’accès
logiques

08/02/25 © Robert Godin. Tous droits réservés 8

.
 2.1.2 Contrôleur de disque

 Contrôleur de disque (disk controller )

– processeur simple et indépendant de l'unité centrale
de traitement
– DMA (« Direct Memory Access »)
 Interface du contrôleur :
– type de transfert (lecture ou écriture)
– adresse du premier secteur
– nombre de secteurs à transférer
– adresse du tampon
 Standards pour PC
– IDE/ATA, SCSI

08/02/25 © Robert Godin. Tous droits réservés 9

.
 2.1.3 Autres types d'unité de
mémoire secondaire
Tableau comparatif des types de
mémoire
Type d'unité Temps de Taux de Capacité Coût ($/ M) Particularité
positionnement transfert en vrac (M)
(ms) (M/ sec)
Mémoire vive 10-6-10-5 102-103 0-104 10-102 Volatile
Disque 1-10 1-102 10-104 10-1-1 Non amovible
Disque 10-102 1 10-103 1-10
amovible
Disquette 102 10-1 1 10-1
Disque 102 10-1-1 102-103 10-2-10-1 Cédérom non
Optique modifiable
Bande 106 1-10 102-106 10-3-10-2 Accès direct
magnétique prohibitif

08/02/25 © Robert Godin. Tous droits réservés 10

.
 2.2 Fichiers et répertoires
 Système de gestion de fichier (SGF,
file system)
– abstraction des mémoires secondaires sous
forme d'un ensemble de fichiers
 Hiérarchie des répertoires
(directory hierarchy) ou répertoire
– structure d ’arbre
– dossier, catalogue

08/02/25 © Robert Godin. Tous droits réservés 11

.
 Cas de UNIX
 Chemin du fichier (“ file path ”)
– /usr/degas/travaux/fibonacci.cpp
/
Volume racine

bin dev usr

degas monet

travaux

cv.txt

fibonacci fibonacci.cpp

08/02/25 © Robert Godin. Tous droits réservés 12

.
 Descripteur de fichier (file
descriptor )
 Ensemble d ’attributs du fichier
– Nom du fichier
– Type de fichier
– Propriétaire
– Date de création
– Date de dernière modification
– Paramètres de protection
– Taille actuelle
– Taille maximale
– Référence à la table d'allocation des fichiers

08/02/25 © Robert Godin. Tous droits réservés 13

.
 Descripteur de répertoire
 Ensemble d ’attributs du répertoire
– Nom du répertoire
– Type de répertoire
– Propriétaire
– Date de création
– Paramètres de protection
– Taille
– Collection de références aux sous-répertoires
– Collection de références aux fichiers sous ce
répertoire

08/02/25 © Robert Godin. Tous droits réservés 14

.
 Unité de mémoire secondaire
logique /physique
 Partition du disque (“ disk partition
”)
– découper un disque en plusieurs partitions
– unité logique de mémoire secondaire
 Descripteur de disque
– partitions, hiérarchie des répertoires et
fichiers
– maintenu sur disque

08/02/25 © Robert Godin. Tous droits réservés 15

.
 Services de base
 Ouvrir (IN cheminFichier, OUT idInterne,…)
– SGF crée une entrée dans la table des fichiers
ouverts
– idInterne : référence à la table des fichiers ouverts
– mode d ’accès : lecture/écriture, accès
direct/séquentiel, création ou fichier existe déjà ,…
– allocation d ’espace
– exceptions
 Fermer (IN idInterne, …)
– libère l ’entrée de la table des fichiers ouverts
– évacuer tampons

08/02/25 © Robert Godin. Tous droits réservés 16

.
 2.3 Organisation par bloc
 Fichier ~ tableau de blocs (taille variable)
– LireBloc(IN idInterne, IN numéroBloc, OUT
tamponApplication,…)
– ÉcrireBloc(IN#bloc
idInterne, IN numéroBloc, IN
tamponApplication,…)
0

n-1

08/02/25 © Robert Godin. Tous droits réservés 17

.
 Bloc, page ou
enregistrement physique
 Ensemble de bits d'une taille fixe
– habituellement n secteurs (1, 2, 4, 8,…)
– traduction bloc => secteur
 Unité de base de transfert de
données
 Unité minimale d'allocation d'espace

08/02/25 © Robert Godin. Tous droits réservés 18

.
 Allocation des secteurs aux blocs de
Superbit
noBloc noSecteurRelatif noPiste noSurface noSecteur
Paramètre Valeur 0 0-4 0 0 0-4
nbSurfaces 20 1 5-9 0 0 5-9
nbCylindres 1000 2 10-14 0 0 10-14
3 15-19 0 0 15-19
nbSecteursParPiste 50 ... ... ... ... ...
tailleSecteur 512 9 45-49 0 0 45-49
nbSecteursParBloc 5 10 50-54 0 1 0-4
11 55-59 0 1 5-9
... ... ... ... ...
20 100-104 0 2 0-4
21 105-109 0 2 5-9
... ... ... ... ...
190 950-954 0 19 0-4
191 955-959 0 19 5-9
... ... ... ... ...
200 1000-1004 1 0 0-4
 Allocation par cylindre
201 10 pour
05-1009 minimiser
1 0déplacement
5-9
du bras ... ... ... ... ...

08/02/25 © Robert Godin. Tous droits réservés 19

.
 Calcul d ’adresse relative du premier
secteur d ’un bloc
noBloc noSecteurRelatif noPiste noSurface noSecteur
Paramètre Valeur 0 0-4 0 0 0-4
nbSurfaces 20 1 5-9 0 0 5-9
2 10-14 0 0 10-14
nbCylindres 1000 3 15-19 0 0 15-19
nbSecteursParPiste 50 ... ... ... ... ...
9 45-49 0 0 45-49
tailleSecteur 512 10 50-54 0 1 0-4
nbSecteursParBloc 5 11 55-59 0 1 5-9
... ... ... ... ...
20 100-104 0 2 0-4
21 105-109 0 2 5-9
... ... ... ... ...
190 950-954 0 19 0-4
191 955-959 0 19 5-9
... ... ... ... ...
200 1000-1004 1 0 0-4
201 1005-1009 1 0 5-9
 noSecteurRelatif (105) ... ... ... ... ...

– = noBloc (21)  nbSecteursParBloc (5)

08/02/25 © Robert Godin. Tous droits réservés 20

.
 Calcul de l ’adresse physique du
premier secteur du bloc
noBloc noSecteurRelatif noCylindre noSurface noSecteur
Paramètre Valeur 0 0-4 0 0 0-4
1 5-9 0 0 5-9
nbSurfaces 20 2 10-14 0 0 10-14
3 15-19 0 0 15-19
nbCylindres 1000 ... ... ... ... ...
nbSecteursParPiste 50 9
10
45-49
50-54
0
0
0
1
45-49
0-4
tailleSecteur 512 11
...
55-59
...
0
...
1
...
5-9
...
nbSecteursParBloc 5 20 100-104 0 2 0-4
21 105-109 0 2 5-9
... ... ... ... ...
190 950-954 0 19 0-4
191 955-959 0 19 5-9
... ... ... ... ...
200 1000-1004 1 0 0-4
201 1005-1009 1 0 5-9
 noCylindre (0) = noSecteurRelatif (105) ... ... ...
DIV nbSecteursParCylindre (1000) ... ...

 où nbSecteursParCylindre (1000) = nbSecteursParPiste (50)  nbSurfaces

(20)
 noSurface (2) = (noSecteurRelatif (105) MOD nbSecteursParCylindre (1000)) DIV
nbSecteursParPiste (50)
 noSecteur (5) = (noSecteurRelatif (105) MOD nbSecteursParCylindre (1000)) MOD
nbSecteursParPiste (50)

08/02/25 © Robert Godin. Tous droits réservés 21

.
 2.3.1 Allocation d'espace
contigu au fichier
 Allocation en vrac à la création du fichier

ajusté
Mieux

Fichier A Fichier B Fichier C Fichier D

Premier
ajusté

Fichier A Fichier B Fichier C Fichier D

 Croissance de la taille du fichier ???

 Fragmentation externe

08/02/25 © Robert Godin. Tous droits réservés 22

.
 2.3.2 Allocation dynamique
d'espace par granule
 Granule d'allocation d'espace (segment, cluster, extent)
– unité d'allocation d'espace
– ensemble de blocs consécutifs
 Fragmentation du fichier (“file fragmentation ”)

D A B A C B B B C D B

Défragmentation

D D A A B B B B B C C

08/02/25 © Robert Godin. Tous droits réservés 23

.
 Table d'allocation des
fichiers ( “fille allocation
table - FAT ”) T able d'alloc ation
des fi c hiers
Numéro de bloc
Dis que organis é
par bloc

Nom du Numéro du du disque

fichier premier bloc

A 10 10 11 10 Bloc 0 du Fichier A

B 12
11 20 11 Bloc 1 du Fichier A
C 17
12 13 12 Bloc 0 du Fichier B

13 23 13 Bloc 1 du Fichier B

 Ex: granule = 1 bloc

14 14 Bloc libre

15 15 Bloc libre

16 Nil 16 Bloc 5 du Fichier A

 Style DOS 17 10 17 Bloc 0 du Fichier C

18 Nil 18 Bloc 1 du Fichier C

 Allocation d ’espace chaînée

19 19 Bloc libre

20 21 20 Bloc 2 du Fichier A

21 22 21 Bloc 3 du Fichier A

 Chargée en mémoire centrale 22 16 22 Bloc 4 du Fichier A

23 24 23 Bloc 2 du Fichier B

24 Nil 24 Bloc 3 du Fichier B

08/02/25 © Robert Godin. Tous droits réservés 24

.
 Organisations plus
sophistiquées pour la table
d ’allocation
 UNIX
– arborescence de I-node
 Stratégie des frères jumeaux
(“buddy system”)
– granules d'allocation d'espace de taille
2n
– fusion/division de granules voisins
(jumeaux)

08/02/25 © Robert Godin. Tous droits réservés 25

.
 Couches de base
Niveau 3
Opérations sur hiérarchie de
répertoires et fichiers organisés par
blocs

Niveau 2
Opérations sur blocs

Niveau 1
Opérations sur secteurs

08/02/25 © Robert Godin. Tous droits réservés 26

.
 2.3.3Optimisation du déplacement du
bras de lecture/écriture

 Algorithme de l'ascenseur (“SCAN”)

Temps

 Algorithme de balayage circulaire

(“ C-SCAN ”) Temps

08/02/25 © Robert Godin. Tous droits réservés 27

.
 2.3.4 Taille optimale de bloc

 Grande taille =>

– effet de grappe
– données transférées inutilement
– gaspillage d ’espace pour petits fichiers
 Compromis
– 512 octets à 4K pour applications
traditionnelles
– >> pour entrepôt de données,
multimédia

08/02/25 © Robert Godin. Tous droits réservés 28

.
 2.3.5 Antémémoire
(cache memory )
 Mémoire intermédiaire
 Données fréquemment utilisées
 Réduire le temps moyen
 Antémémoire disque (disk cache)
– réalisée en mémoire centrale afin
d'accélérer les entrées/sorties sur un
disque

08/02/25 © Robert Godin. Tous droits réservés 29

.
 Principe de l ’ antémémoire

B loc 0
B loc 1
Tam pon B loc 2
Tam pon
processus #1 systèm e B loc 3
2e 1er
B loc 4 B loc 4 B loc 4
3e B loc 5
Tam pon B loc 6
processus #2
B loc 7
B loc 4
B loc 8
B loc 9

Mémoire primaire Disque

08/02/25 © Robert Godin. Tous droits réservés 30

.
 Antémémoire

B loc 0
B loc 1
B loc 2
noBloc S T ampon
B loc 3
2 0 B loc 4
B loc 4
4 0 B loc 2
B loc 5
5 0 B loc 7
B loc 6
7 0 B loc 5
B loc 7
Répertoire de
l'antémémoire
Antémémoire B loc 8
B loc 9
 Gestionnaire de l'antémémoire disque (“disk cache
Disque
manager ”) Mémoire primaire

08/02/25 © Robert Godin. Tous droits réservés 31

.
 Écriture en antémémoire
Tam pon
processus #1
B loc 2'
B loc 0
B loc 1
B loc 2
noBloc S T ampon
B loc 3
2 0 B loc 4
B loc 4
4 1 B loc 2'
B loc 5
5 0 B loc 7
B loc 6
7 0 B loc 5
B loc 7
Répertoire de
l'antémémoire
Antémémoire B loc 8
B loc 9

Mémoire primaire Disque

08/02/25 © Robert Godin. Tous droits réservés 32

.
 Sélection d ’une victime
 Processus #1: lire Bloc 3 et antémémoire pleine !
 Choix d ’une victime pour remplacement: Bloc 2 ’ qui
est sale (s = 1)
 Évacuation de la victimeTam pon
processus #1

B loc 0
B loc 1
B loc 2'
1 er
noBloc S T ampon
B loc 3
2 0 B loc 4
B loc 4
4 1 B loc 2'
B loc 5
5 0 B loc 7
B loc 6
7 0 B loc 5
B loc 7
Répertoire de
l'antémémoire
Antémémoire B loc 8
B loc 9

Mémoire primaire Disque

08/02/25 © Robert Godin. Tous droits réservés 33

.
 Remplacement de la victime
Tam pon
processus #1
B loc 3
B loc 0
3e B loc 1
B loc 2'
noBloc S T ampon
B loc 3
3 0 B loc 4 2e B loc 4
4 0 B loc 3
B loc 5
5 0 B loc 7
B loc 6
7 0 B loc 5
B loc 7
Répertoire de
l'antémémoire
Antémémoire B loc 8
B loc 9

Mémoire primaire Disque

08/02/25 © Robert Godin. Tous droits réservés 34

.
 Stratégie de remplacement

 Maximiser la probabilité d ’accès en

antémémoire
 Remplacer le tampon le moins récemment
utilisé (Least Recently Used (LRU))
 Remplacer le tampon le moins fréquemment
utilisé (Least Frequently Used (LFU))

08/02/25 © Robert Godin. Tous droits réservés 35

.
 Hiérarchie de mémoire
Vitesse
Coût Capacité
d'accès
Primaire

Secondaire

Tertiaire

 Hierarchical Storage Management

– migration automatique entre niveaux
– contrôlée par paramètres de configuration

08/02/25 © Robert Godin. Tous droits réservés 36

.
 2.4Organisation par
enregistrements
 Enregistrement (record ), champ (field )
TYPE PlantCatalogue = ENREGISTREMENT
noCatalogue : ENTIER;
description : CHAINE[30];
prixUnitaire : REEL;
FIN.
noCatalogue description prixUnitaire
10 Cèdreen boule 10.99
20 Sapin 12.99
40 Epinettebleue 25.99
50 Chêne 22.99
60 Erable argenté 15.99
70 Herbeàpuce 10.99
80 Poirier 26.99
81 Catalpa 25.99
90 Pommier 25.99
95 Génévrier 15.99

08/02/25 © Robert Godin. Tous droits réservés 37

.
 Niveau 4 : enregistrement
N iveau 4
O pérations sur hiérarchie de
répertoires et fichiers organisés par
enregistrements

N iveau 3
O pérations sur hiérarchie de
répertoires et fichiers organisés par
blocs

N iveau 2
O pérations sur blocs

N iveau 1
O pérations sur secteurs

08/02/25 © Robert Godin. Tous droits réservés 38

.
 Méthode et chemin d ’accès

 Méthode d'accès (“ access method

”) ou mode d'accès
– manière d'accéder d'un point de vue
logique
 sériel, séquentiel, sélection par clé, par
intervalle

 Chemin d'accès (“ access path ”)

– chemin dans les structures de données

08/02/25 © Robert Godin. Tous droits réservés 39

.
 Méthode d'accès sériel
 Patron d ’itérateur
PremierEnregistrement (TypeEnregistrement, TamponEnregistrement, …)
TANT QUE pas la fin de la collection

traitement d'un enregistrement

EnregistrementSuivant (TypeEnregistrement, TamponEnregistrement,…)

FIN TANT QUE
 Ordre => séquentiel

08/02/25 © Robert Godin. Tous droits réservés 40

.
 Méthode d'accès par sélection basée sur
un identifiant d'enregistrement

 Identifiant d ’enregistrement (IDE)

– accès rapide
SélectionnerEnregistrement(IDE, TamponEnregistrement)
Entrée : IDE
Sortie : TamponEnregistrement

CréerEnregistrement(IDE, TamponEnregistrement)
Entrée : TamponEnregistrement
IDE sera une entrée ou une sortie selon le cas

ModifierEnregistrement (IDE, TamponEnregistrement)

Entrée : IDE, TamponEnregistrement
SupprimerEnregistrement (IDE)
Entrée : IDE

08/02/25 © Robert Godin. Tous droits réservés 41

.
 Méthode d'accès par sélection basée
sur une clé d'accès
 Clé d'accès (“ access key ”)
– champ ou combinaison de champs utilisés
comme critère de sélection
 Clé simple/composée
 Clé unique (“ unique key ”)
 Sélection par intervalle
 Méthode d ’accès
multidimensionnelle

08/02/25 © Robert Godin. Tous droits réservés 42

.
 2.4.1 Organisation primaire
et secondaire
 Organisation primaire (primary
organization)
– placement des enregistrements
 sériel, séquentiel, index primaire, hachage, grappe, ...

– gestion des IDE

 Organisation secondaire (secondary

organization )
– liste , arbre, index secondaire, etc.
– référence aux IDE

08/02/25 © Robert Godin. Tous droits réservés 43

.
  2.4.2 Fichier homogène
(homogeneous) ou hétérogène
(heterogeneous)
 2.4.3 Niveau 4 : SGF ou SGBD

08/02/25 © Robert Godin. Tous droits réservés 44

.
 2.4.4 Alternatives de
réalisation de l'IDE
 idFichier, NER
 l'adressage relatif
 (e.g. organisation “relative” de NON STOP SQL)
 l'indexage
 (e.g. organisation “key sequenced” sur “SYSKEY” de NON STOP
SQL)
 idFfichier, #bloc, #séquence (e.g. DBKEY DBMS-32
(CODASYL), ROWID ORACLE).
 idFichier, #bloc, #octet (e.g. “entry-sequenced” de NON
STOP SQL)
 idFichier, clé unique (e.g. “key-sequenced” de NON STOP
SQL)
 IDE logique
 (e.g. OID dans les SGBDO)

08/02/25 © Robert Godin. Tous droits réservés 45

.
 2.4.5 Représentation interne
des enregistrements
 Enregistrements => blocs
 Séquence consécutive d ’octets
 Taille fixe ou variable

08/02/25 © Robert Godin. Tous droits réservés 46

.
 2.4.5.1 Enregistrements de
taille fixe
 Chaque champ => nombre fixe
d ’octets
 Remplissage par caractère neutre

noCatalogue description prixUnitaire

ENT IER CHAINE[30] REEL
binaire 32 bits un octet (ASCII 8 bits) par caractère (remplissage avec espaces) point-flottant 64 bits
(4 octets) (30 octets) (8 octets)

T otal : 42 octets

08/02/25 © Robert Godin. Tous droits réservés 47

.
 2.4.5.2 Enregistrements de
taille variable
 Frontières de champs et
d ’enregistrements
 indicateur de taille en entête de chaque
champ (descripteur de champ)
tailleNoCatalogue tailleDescription taillePrixUnitaire
noCatalogue description prixUnitaire

 délimiteur (code réservé)

noCatalogue description prixUnitaire

 index en entête de l'enregistrement

(descripteur d'enregistrement)

noCatalogue description prixUnitaire

08/02/25 © Robert Godin. Tous droits réservés 48
.
 2.5 Allocation sérielle d'espace pour les
enregistrements de taille fixe et
l'adressage relatif
 Allocation d'espace sérielle (serial space allocation)
Num éro
Num éro d'enregistrem ent
– avec/sans chevauchement de bloc de bloc relatif
0
 Facteur de blocage (FB, blocking factor) 1

2
– nombre d'enregistrements par bloc 0
3

4
 Numéro de bloc = NER / FB Espace perdu
5
 Position relative dans le bloc = 6

7
1
– NER MOD FB  taille d'un enregistrement 8

9
 NER = champ ?
10

 IDE = idFichier, NER 11

12
2
 Gros enregistrement : chevauchement 13

14

08/02/25 © Robert Godin. Tous droits réservés 49

.
 Liste des espaces libres
(free list) Bloc
réservé à
Pointeur sur
prem ier
espace libre
l'entête
de fichier

Espace libre 1

Espace libre 4

Espace libre 7

Espace libre 8

10

11

Espace libre 12

13

14

08/02/25 © Robert Godin. Tous droits réservés 50

.
 2.6 Allocation d'espace pour les
enregistrements de taille variable

 Analogue à l ’allocation d ’espace

pour les fichiers
 Granularité plus fine

08/02/25 © Robert Godin. Tous droits réservés 51

.
 2.6.1 Allocation sérielle pour
enregistrements de taille variable
N um éro
de bloc
 Gestion d ’espace libre
– ne pas récupérer 0

– liste libre
 mieux ajusté
 premier ajusté 1

 Fragmentation interne au fichier

 IDE = idFichier, #bloc, #octet2
– enregistrement cloué

08/02/25 © Robert Godin. Tous droits réservés 52

.
 2.6.2 Récupération d'espace et
adressage structuré par bloc
 IDE = idFichier, #bloc, #séquence
(clouage partiel)
Index des positions des
enregistrements
Taille de l'index des
positions

3 Espace libre Enr. #3 Enr. #2 Enr. #1

1 2 3

Suppression de #2

3 Espace libre Enr. #3 Enr. #1

1 2 3

08/02/25 © Robert Godin. Tous droits réservés 53

.
 2.6.3Gestion des débordements
N um éro
de bloc

 Même IDE Bloc virtuel

de taille
variable
0
 Oracle : PCTFREE

Bloc
d'ancrage
1

Bloc de
2 débordement

08/02/25 © Robert Godin. Tous droits réservés 54

.
 Découpage de l ’enregistrement
N um éro
de bloc

2e m orceau
Bloc
d'ancrage
1
1er m orceau

Bloc de
2 débordement

Cas particulier :
adresse de suivi (forwarding address)
08/02/25 © Robert Godin. Tous droits réservés 55
.
 2.6.4 Adressage logique
 IDE découplé de sa position physique
 Souplesse d ’allocation d ’espace
– Ex: OID dans les BD objet M écanism e
ID E de adresse
logique traduction physique
(e.g. index)

08/02/25 © Robert Godin. Tous droits réservés 56

.
 2.6.5 Découpage en morceaux
de taille fixe
 Découper un enregistrement de
taille variable en morceaux de
taille fixe
 Allocation des morceaux par
adressage relatif

08/02/25 © Robert Godin. Tous droits réservés 57

.
 2.6.6Allocation d'espace pour gros
enregistrements de taille variable

 Allocation chevauchante
– blocs consécutifs
– diminuer le nombre de
positionnements
 Réalisation de l ’IDE
– adressage logique
– adresse de suivi

08/02/25 © Robert Godin. Tous droits réservés 58

.
 2.6.7Allocation hybride pour les
enregistrements de taille variable

 Organisations spécialisées selon la

taille des champs
– un mécanisme pour petits champs
– un autre pour les gros champs
 référence externe (e.g. chemin, URL)

08/02/25 © Robert Godin. Tous droits réservés 59

.
 2.7Allocation sérielle par
grappe homogène
 Grappe (cluster)
– ensemble d ’enregistrements regroupés
physiquement
 Clé de la grappe (cluster key)
– critère de regroupement
– ensemble de champs
 Identifiant de grappe (IDG, cluster
identifier)
– IDG = #bloc, valeur de la clé de grappe

08/02/25 © Robert Godin. Tous droits réservés 60

.
 Exemple : insertion avec idMembre = 2

idMembre datePrêt idExemplaire Num éro

2 15/ 08/ 2000 75 de bloc IDG = #bloc, clé de grappe
3 16/ 08/ 2000 200
1 17/ 08/ 2000 100 2 15/08/2000 75 0, 2
4 18/ 08/ 2000 400
2 19/ 08/ 2000 50 3 16/08/2000 200 0, 3
1 20/ 08/ 2000 300 0
3 21/ 08/ 2000 150 1 17/08/2000 100 0, 1

4 18/08/2000 400 0, 4

Num éro
de bloc IDG

3 16/08/2000 200 0, 3 2 15/08/2000 75

0, 2
1 17/08/2000 100 0, 1 2 19/08/2000 50
0
4 18/08/2000 400 0, 4

08/02/25 © Robert Godin. Tous droits réservés 61

.
 Exemple : insertion avec idMembre = 1

Num éro
de bloc IDG

3 16/08/2000 200 0, 3 2 15/08/2000 75

0, 2
1 17/08/2000 100 0, 1 2 19/08/2000 50
0
4 18/08/2000 400 0, 4

Num éro
de bloc IDG

3 16/08/2000 200 0, 3 2 15/08/2000 75

0, 2
1 17/08/2000 100 2 19/08/2000 50
0, 1
0
1 20/08/2000 300

4 18/08/2000 400 0, 4

08/02/25 © Robert Godin. Tous droits réservés 62

.
 Exemple : insertion avec idMembre = 3
Num éro
de bloc IDG

3 16/08/2000 200 0, 3 2 15/08/2000 75

0, 2
1 17/08/2000 100 2 19/08/2000 50
0, 1
0
1 20/08/2000 300

4 18/08/2000 400 0, 4

Num éro
de bloc IDG

1 17/08/2000 100 2 15/08/2000 75

0, 1 0, 2
1 20/08/2000 300 2 19/08/2000 50
0
4 18/08/2000 400 0, 4 3 16/08/2000 200
0, 3
3 21/08/2000 150

08/02/25 © Robert Godin. Tous droits réservés 63

.
 2.7.1 Réservation d'espace
pour les grappes
Num éro
de bloc
 Limiter débordements2
IDG

15/08/2000 75
– ex: SIZE (Cluster Oracle) 0, 2

Num éro 0
3 16/08/2000 200
de bloc IDG = #bloc, clé de grappe 0, 3
2 15/08/2000 75 0, 2

3 16/08/2000 200 0, 3 1 17/08/2000 100

0 1, 1
1 17/08/2000 100 0, 1
1
4 18/08/2000 400 0, 4 4 18/08/2000 400
1, 4

Sans réservation d ’espace Avec réservation d ’espace

08/02/25 © Robert Godin. Tous droits réservés 64
.
 Résultat final
Numéro
de bloc IDG

2 15/08/2000 75
Num éro
de bloc IDG 0, 2
1 17/08/2000 100 2 15/08/2000 75
2 19/08/2000 50
0, 1 0, 2
1 20/08/2000 300 2 19/08/2000 50
0
3 16/08/2000 200
0
4 18/08/2000 400 0, 4 3 16/08/2000 200
0, 3
0, 3
3 21/08/2000 150
3 21/08/2000 150

1 17/08/2000 100
1, 1
Sans réservation d ’espace 1 20/08/2000 300
1
4 18/08/2000 400
4, 1

Avec réservation d ’espace

08/02/25 © Robert Godin. Tous droits réservés 65
.
 2.8 Fichiers séquentiels
 Enregistrements ordonnés (clé de
Num éro
tri) Num éro
de bloc
d'enregistrem ent
relatif
10 Cèdre en boule 10.99 0

 Mise à jour difficile 20

40
Sapin
Epinette bleue
12.99
25.99
1

2
0
50 Chêne 22.99 3

60 Erable argenté 15.99 4

70 Herbe à puce 10.99 5

80 Poirier 26.99 6

81 Catalpa 25.99 7
1
90 Pom m ier 25.00 8

95 G énév rier 15.99 9

08/02/25 © Robert Godin. Tous droits réservés 66

.