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

2e partie

Version 4 - Septembre 2022

Support du chapitre 4, Implémentation des structures de données

de l'ouvrage Bases de données, J-L Hainaut, Dunod 2022.

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 1
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

Contenu

4.1 Introduction
4.2 Les mémoires externes
4.3 Organisation d'un espace de stockage
4.4 Traitement séquentiel 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)
4.10 Un exemple : SQL Server de Microsoft

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 2
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.5 Les index

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 3
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.5 Les index

Index structure technique associée à un fichier (une 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.

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 4
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

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 de gestion.

La requête select NOM, LOCALITE from CLIENT where NCLI = ’C400’

• s'exécutera en 15 s sans index sur NCLI
• et en 0.025 s avec un index sur NCLI (600 fois plus rapidement !).

Mais, pas de miracle : tout avantage a un coût ! Ici, le volume et le 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
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 5
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.5 Les index

Un index convertit une valeur de la clé en l'ensemble des adresses des

enregistrements qui possèdent cette valeur.
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 : table de conversion ou calcul.

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 6
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.5 Les index

Deux classes d'index

1. les index primaires
2. les index secondaires

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 7
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

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 bonnes 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
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 8
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.5 Les index

Principales technologies des index primaires

1. organisation séquentielle indexée
2. organisation calculée

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 9
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 10
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Principes

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

index sur K fichier de base

ordonné sur K

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 11
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Principes

L’index matérialise une fonction f qui transforme une valeur k de la clé K en

une adresse A.
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.

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 12
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Principes

à démontrer !
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 tel que K = k
4. l'accès rapide aux enregistrements tel que K  [k1, k2]
5. l'insertion rapide d'un enregistrement de clé K
6. la modification rapide de la valeur de K d'un enregistrement
7. la suppression rapide d'un enregistrement

Cette organisation s'inspire d’une structure d'arbre dite B-tree (balanced

tree)

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 13
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Principes

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

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 14
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Principes

fichier de base

B062 GOFFIN Namur B2

Observations
B112 HANSENNE Poitiers C1
B332 MONTI Genève B2 1. les enregistrements de chaque page de
B512 GILLET Namur B1
base sont ordonnés selon K
C003 AVRON Poitiers B1
2. une page de base est caractérisée par sa
C123
B512 MERCIER
GILLET Namur
Namur C1
B2
plus grande valeur de K.
C400
C003 FERARD
AVRON Poitiers
Poitiers B2
C1
D063
C123 MERCIER Toulouse
Genève B2
3. les pages de base sont ordonnées selon K
index B332  F010 TOUSSAINT Poitiers C1 4. l'index comprend n niveaux (n  1)
C003  F011 PONCELET Poitiers B2

D063
F400 
F400 JACOB Bruxelles C2
5. chaque page d'index comprend des

F375 BERNIER Paris C1 entrées d'index
G110 G110 STEVEN London B2

F400 
H736
H991 
6. chaque niveau d'index jouit des propriétés
H991 
H109 DUPUIS Lausanne C2 1à3
H736 ARNOULD Paris B1
P650  J079  I452 
S712  P650  J079  7. chaque entrée du niveau n de l'index
S712 
... comprend 1 valeur ki de K et 1 pointeur
vers la page de base dont la plus grande
J823 
K111 VANBIST Lille B1
valeur de K = ki
K729 
K729 NEUMAN Toulouse
M345  8. chaque entrée du niveau m (m < n) de

P650
L422 FRANK Namur C1
l'index comprend 1 valeur ki de K et 1
S712 
M162 MERCIER Toulouse C2 pointeur vers la page d'index de niveau
M345 NOEL Liège B1 m+1 dont la plus grande valeur de K = ki
N227 MARTIN Bruxelles C1
P650 ANTOINE Poitiers B2 9. le 1er niveau de l'index comprend 1 page
10. certaines pages ne sont pas pleines
S127 VANDERKA Namur C1
S712 GUILLAUME Paris B1
11. la position d'un enregistrement est fonction
de sa valeur de K

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 15
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Accès par clé

Accès par clé (K = 'H109')

H109  P650 H109  H991 H109  H736 H109 se trouve dans cette page
ou nulle part ailleurs

G110 
H736 
F400  H991 
H109 DUPUIS Lausanne C2
H991 
H736 ARNOULD Paris B1
K = 'H109' P650  J079 
S712  P650 

niveau 1 niveau 2 niveau 3 page de base

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
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 16
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Accès par clé

Accès par clé (K = k)

oui
k  Kmax ?
non

i := 1; p := p1

R:= 1er enreg. de la

I := 1re entrée de la page [p] tel que R.K  k
page [p] tel que I.K  k
non oui
R.K = k ?
p := [Link]

oui l'enregistrement recherché R est l'enregistrement

i=n?
est absent du fichier recherché
non

i := i + 1

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 17
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Modes d'accès

Les trois modes d'accès aux enregistrements

ponctuel selon K intervalle selon K séquentiel selon K

select * select * select *

from CLIENT from CLIENT from CLIENT
where NCLI = 'C400' where NCLI like 'C%' order by NCLI

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 18
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Modifications

Insertion d'un enregistrement

1. On identifie la page d'insertion

2. On tente d'y insérer l'enregistrement :
cas 1 : la page contient de l'espace libre
cas 2 : la page ne contient pas d'espace libre

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 19
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Modifications

Insertion d'un enregistrement (K = H555)

G110 
- H555 est absent
H736 
- la page n'est pas pleine
F400  H991 
H991 
K = 'H555' P650  J079  H109 DUPUIS Lausanne C2
S712  P650  H736 ARNOULD Paris B1


G110 
H555 est inséré dans la page
H736 
F400  H991 
H991 
P650  J079  H109 DUPUIS Lausanne C2
S712  P650  H555 MARTINEZ Madrid
H736 ARNOULD Paris B1

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 20
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Modifications

Insertion d'un enregistrement (K = C805)

B332 
- C805 est absent
C003 
- la page est pleine
F400  D063 
H991 
K = 'C805' P650  J079  C123 MERCIER Namur C1
S712  P650  C400 FERARD Poitiers B2
D063 MERCIER Toulouse


B332  - la page est dédoublée
C003  nouvelle page
F400  C400  C123 MERCIER Namur C1
H991  D063  C400 FERARD Poitiers B2  0,5
P650  J079 
S712  P650  C805 SMITH Londres B1
D063 MERCIER Toulouse  0,5
ancienne page

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 21
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Modifications

Insertion d'un enregistrement

La nouvelle page est-elle juste devant la page pleine ?

Sauf miracle, non !

Où a-t-on trouvé cette page ?

- parmi les pages libres réservées à la fin du fichier
- parmi les pages préalablement libérées suite à la suppression d'enregistrements.

En règle générale, la nouvelle page est physiquement plus ou moins éloignée

de sa page soeur.

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 22
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Modifications

Séquence physique et séquence logique

0 1 99 100 101 102 103 99.997 99.998 99.999 séquence physique

des pages dans le fichier
... ...
0 1 99 100 101 102 103

séquence logique
de lecture

Insertion dans la page 101, qui devient 101 (localisée en 99.997) + 102 (localisée en
101):
0 1 99 100 101 102 103 99.997 99.998 99.999 séquence physique

... ...
0 1 99 100 102 103 104 101

séquence logique

Les pages se suivent logiquement mais ne se suivent plus physiquement = ruptures

physiques.

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 23
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Modifications

Comment reconstituer la séquence logique ?

Trois techniques
1. Les pages de bases sont chaînées via l'ajout d'un pointeur référençant la page de
base suivante. Le parcours de cette chaîne livre les pages de base dans bon ordre.
2. Les pages du dernier niveau d'index sont chaînées via l'ajout d'un pointeur
référençant la page d'index suivante (VSAM d'IBM). L'utilisation des pointeurs de
ces pages parcourues selon cette chaîne livre les pages de base dans bon ordre.
3. L'accès aux pages de base s'effectue via le parcours de l'index (visite des noeuds
en profondeur d'abord).

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 24
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Modifications

Synthèse: insertion d'un enregistrement (K = k)

Procédure
1. On recherche la page [p] dans laquelle l'enregistrement K = k 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 [p'] (logiquement, pas physiquement)
3.2 on répartit la charge de [p] entre les pages [p'] et [p]
3.3 on insère l'enregistrement dans l'une de ces deux pages
3.4 on insère une entrée relative à la page [p'] dans le niveau n de l'index

Observations
1. le taux d'occupation de chaque page reste  0,5 (sauf, éventuellement la
dernière)
2. les pages logiquement consécutives ne le sont plus nécessairement
physiquement
3. l'insertion d'une entrée d'index obéit à la même procédure

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 25
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Modifications

Remarque: insertion en fin de fichier

Scénario :
les enregistrements sont insérés par valeurs croissantes de la clé K (insertion
ordonnée)

Dans ce cas, la gestion des pages pleines peut être différente de la procédure
décrite plus haut.

Exemple :
Lors d'une insertion ordonnée, lorsque qu'une page (la dernière du fichier de
base) est pleine, une page suivante lui est associée, qui contiendra les
enregistrements suivants.
Le taux d'occupation n'est plus de 50% mais peut être plus élevé : 90% ou
même 100% (cf. Oracle, malgré l'appellation maladroite 90-10 split)

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 26
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Modifications

Suppression d'un enregistrement

1. On identifie la page de l'enregistrement à supprimer

2. On l'efface de sa page
3. On réorganise la page si nécessaire :
cas 1 : la page garde un taux d'occupation  0,5
cas 2 : le taux d'occupation de la page tombe sous 0,5
cas 2.1 : redistribution des enregistrements avec une page
voisine
cas 2.2 : fusion de la page avec une page voisine

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 27
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Modifications

Suppression d'un enregistrement (K = 'C400')

B332 
C003 
F400  D063 
H991 
K = 'C400' P650  J079  C123 MERCIER Namur C1
S712  P650  C400 FERARD Poitiers B2  0,5
D063 MERCIER Toulouse

 suppression

B332 
C003 
F400  D063 
H991 
P650  J079  C123 MERCIER Namur C1
S712  P650  D063 MERCIER Toulouse  0,5

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 28
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Modifications

Suppression d'un enregistrement (K = 'B512')

B332 
B062 GOFFIN Namur B2
C003 
F400  D063  B110 HANSENNE Poitiers C1  0,5
 B332 MONTI Genève B1
H991  F400
K = 'B512' P650  J079  B512 GILLET Namur B1
S712  P650  C003 AVRON Poitiers B1 < 0,5

 suppression puis répartition

B110 
B062 GOFFIN Namur B2
C003 
F400  D063  B110 HANSENNE Poitiers C1  0,5
H991  F400 
P650  J079  B332 MONTI Genève B1
S712  P650  C003 AVRON Poitiers B1  0,5

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 29
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Modifications

Suppression d'un enregistrement (K = 'H109')

G110 
F375 BERNIER Paris C1
H736 
F400  H991  G110 STEVEN London B2  0,5
H991 
K = 'H109' P650  J079  H109 DUPUIS Lausanne C2
S712  P650  H736 ARNOULD Paris B1 < 0,5

 suppression puis fusion

 0,5
H736 
F400  H991  libre
H991 
P650  J079  F375 BERNIER Paris C1
S712  P650  G110 STEVEN London B2  0,5
H736 ARNOULD Paris B1

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 30
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Modifications

Synthèse: 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édente [p']
3.2 si le taux d'occupation des 2 pages est  0,5, on corrige l'entrée d'index
de niveau n relative à la 1re page
3.2 si le taux d'occupation d'une des deux pages est < 0,5, on les fusionne
3.3.1 on transfère le contenu de la page [p'] vers [p]
3.3.2 on abandonne la page [p'], qui devient libre
3.3.3 on supprime l'entrée de [p'] dans le niveau n de l'index
Observations
1. le taux d'occupation de chaque page reste  0,5
2. on produit des pages vides réutilisables lors de l'insertion d'enregistrements
3. la suppression d'une entrée d'index obéit à la même procédure

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 31
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Modifications

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.

Modification d'un champ extérieur à K : simple remplacement dans la page.

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 32
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances

Caractéristiques et performances

1. Calcul des volumes

2. Calcul des temps de lecture
3. Calcul des temps de modification
4. Estimation des taux

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 33
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (volumes)

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) : N p
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 : N i(m)
6. Nombre de pages d'index au niveau m : N pi(m)

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 34
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (volumes)

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 / Lr
Contenu moyen d'une page de base Nrpp = b x Mrpp
Nombre de pages de base Npb = Nr / Nrpp

pages vides ignorées

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 35
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (volumes)

Volume d'un fichier séquentiel indexé

Index : calcul détaillé 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 n
Nombre d'entrée de l'index Ni(n) = Npb
Nombre de pages Npi(n) = Ni(n) / Nipp
Taille d'un niveau m < n
Nombre 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
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 36
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (volumes)

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
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 37
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (volumes)

Volume d'un fichier séquentiel indexé

Pour les concepteurs pressés et pas trop regardants :

On connait Nr, Lr, Li, b, i, Lp

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)
Eviter de mémoriser
3. Nbre de niveaux d'index n = log(Npb) / log(i x Lp / Li ) ces formules !

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 38
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (temps de lecture)

Temps de lecture d'un fichier séquentiel indexé

Trois opérations
1. Lecture séquentielle
2. Lecture par index d'un enregistrement
3. Lecture par index des enregistrements d'un intervalle de K

Hypothèses réalistes
1. Disque partagé
2. Lecture anticipée d'une piste

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 39
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (temps de lecture)

Temps de lecture d'un fichier séquentiel indexé

1. Lecture séquentielle selon K

Préliminaire : coût du phénomène de ruptures

n° physique  0 1 99 100 101 102 103 99.997 99.998 99.999

... ...
n° séq. logique  0 1 99 100 101 102 103

0,184 0,184 0,184 0,184 0,184

éclatement de la page 101 en 101 (nouvelle) et 102 (ancienne 101)

0 1 99 100 101 102 103 99.997 99.998 99.999

... ...
0 1 99 100 102 103 104 101

0,184 0,184 0,184

0,184
0,184 Pourquoi = 0,184 ?

12,3

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 40
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (temps de lecture)

Temps de lecture d'un fichier séquentiel indexé

1. Lecture séquentielle selon K

Analyse
1. Lecture des pages du fichier de base selon leur séquence physique ne marche
pas, car ruptures de séquence (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 base
4 Mais, temps de parcours de l'index en général négligeable

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 41
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (temps de lecture)

Temps de lecture d'un fichier séquentiel indexé

1. Lecture séquentielle selon K

Calcul sans rupture de séquence

On 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 s
Avec ruptures : tlsf = 652 s

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 42
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (temps de lecture)

Temps de lecture d'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
base
2. En pratique, on charge les premiers niveaux d'index dans le tampon pour éviter
les accès au disque

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 43
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (temps de lecture)

Temps de lecture d'un fichier séquentiel indexé

2. Lecture ponctuelle selon K

Calcul naïf : tlk1 = tla1 x (n + 1)

+ 1 page pour
tout le reste
Calcul pratique
Si 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

Exemple
Npb = 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 ms
Tampon de 1 + 1 = 2 pages : tlk1 = 12,3 X 3, soit 36,9 ms
Tampon de 1 + 46 + 1 = 48 pages : tlk1 = 12,3 X 2, soit 24,6 ms
Tampon de 1 + 46 + 3.361 + 1 = 3 409 pages : tlk1 = 12,3 X 1, soit 12,3 ms
les performances
ont un coût

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 44
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (temps de lecture)

Temps de lecture d'un fichier séquentiel indexé

3. Lecture par intervalle [k1, k2] selon K

Analyse
1. Intervalle : NCLI >= 'K111';
NCLI >= 'K000' and NCLI <= 'K999';
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
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 45
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (temps de lecture)

Temps de lecture d'un fichier séquentiel indexé

3. Lecture par intervalle [k1, k2] selon K

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 - 1)/ 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

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 46
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (temps de modification)

Temps de modification des données

1. Insertion d'un enregistrement

Soit split la proportion des insertions qui ont provoqué un éclatement

tins = tl1k + (1 + 3 x split) x tla1

• lire page vide
• recopier nouvelle page
• maj de l'index

• recopier page courante

• accès à la page de base

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 47
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (temps de modification)

Temps de modification des données

2. Suppression d'un enregistrement

Soit bal la proportion des suppressions qui ont provoqué un rééquilibrage

Soit merge la proportion des suppressions qui ont provoqué une fusion

tdel = (1 + 3 x bal + 3 x merge) x tla1

• lire page voisine
• libérer page vide
• maj de l'index

• lire page voisine

• recopier page voisine
• maj de l'index

• recopier page
courante

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 48
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (temps de modification)

Temps de modification des données

3. Modifier un enregistrement

= une suppression + une insertion

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 49
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation des taux d'occupation

Les calculs dépendent de 6 taux :

• b et i (mais phénomène identique = )
• r
• split
• bal
• merge

Comment les évaluer ?

1. Analytiquement (processus stochastiques) : complexe
2. Par simulation : plus simple, intuitif mais réclame un peu de programmation

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 50
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation des taux d'occupation

Paramètres d'une simulation

1. Nombre initial de pages : Np0
2. Taille des pages : Mrpp [en nombre d'enregistrements]
3. Taux d'occupation initial 0 (ou nombre initial d'enregistrements par page Nrpp0 =
0 x Mrpp )
4. Proportion d'insertions ins parmi des opérations insert-delete (ou %ins de 0 à
100); 100% = insertions seulement; 0% = suppressions seulement
5. Nombre d'opérations de la simulation Nop
6. Nombre d'exécutions Nsim (sous la forme de nombre de pas Npas et nombre
d'opérations par pas Nopp)

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 51
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation des taux d'occupation

Simulateur
• tableau d'entiers PAGE(Npmax); PAGE(I) = nbre d'enregistrements de la page I
• on initialise les Np0 premières pages selon Nrpp0
• on choisit une opération au hasard selon %ins
• on choisit un enregistrement R au hasard (il se trouve dans la page P)
• on simule l'opération sur R en modifiant PAGE(P) et ses voisines selon
l'opération choisie
• à la fin de chaque pas, on mémorise les statistiques
• à la fin des Nsim exécutions, on calcule les moyennes des statistiques et on
les sort dans un fichier de résultats

Simulateur : [Link]

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 52
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation des taux d'occupation

Résultats d'une simulation (moyenne des Nsim exécutions)

1. Step : numéro du pas courant (de 0 à Npas)
2. Nop : nombre d'opérations exécutées
3. Nins : nombre d'insertions exécutées
4. Ndel : nombre de suppressions exécutées
5. Np : nombre actuel de pages
6. Nr : nombre actuel d'enregistrements
7. tocc : taux d'occupation actuel
8. Nsplit : nombre d'insertions avec éclatement
9. Nbal : nombre de suppressions avec rééquilibrage
10. Nmerge : nombre de suppressions avec fusion
11. Nerror : nombre d'erreurs (doit être 0)

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 53
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation des taux d'occupation

Fichier de paramètres pour 3 simulations

'Simulations pour %ins = 70, 80, 90

'Np0, Mrpp, Nrpp0, TauxIns, NbrePas, NbreOpPas, NbreSimul
step Np Nr tocc Nsplit Nbal Nmerge
5000, 40, 28, 70, 200, 2000, 5
5000, 40, 28, 80, 200, 2000, 5
5000, 40, 28, 90, 200, 2000, 5

simulation 1

résultats demandés

' commentaires

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 54
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation des taux d'occupation

Résultats de la simulation 1

Start time = 01/12/2011 [Link]

End time = 01/12/2011 [Link]

STEP Np Nr tocc Nsplit Nbal Nmerge

0 5000 140000 0,7 0 0 0
1 5000 140794 0,70397 0 0 0
2 5000 141608 0,7080137 0,2 0 0
3 5000 142430 0,7121235 0,2 0 0
4 5000 143239 0,7161673 0,2 0 0
5 5000 144017 0,7200552 0,2 0 0
6 5000 144834 0,724112 0,4 0 0
7 5001 145673 0,7282786 0,6 0,2 0
...
197 10571 297375 0,7033097 5929,6 3340,2 359
198 10597 298191 0,7034819 5957,4 3356,8 360,4
199 10629 298985 0,7032048 5990,6 3373,8 361,2
200 10656 299797 0,7033539 6019,6 3388,6 363,6

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 55
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation de 

Comment évolue  ?
1. En fonction du nombre d'opérations nop depuis la création du fichier. Durée de la
simulation : nop = Nop.
2. En fonction de la taille des pages Mrpp [en nombre d'enregistrements]
3. En fonction du taux d'occupation 0 à la création du fichier (Nr0 = x )
4. En fonction du % d'insertions %ins [0-100] dans les opérations insert-delete (100
= insertions seulement; 0 = suppressions seulement)
5. Ne dépend pas de la taille du fichier (Np) mais de nop / Nr0

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 56
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation de 

0,90
%ins=50
0,85 %ins=60
%ins=70
0,80 %ins=80
%ins=90
%ins=100
0,75

0,70

1 pas = 1,25 x Nr0 / 100

0,65

0,60

0,55

0,50 pas
0

10

20

30

40

50

60

70

80

90

100

110

120

130

140

150

160

170

180

190

200
Np0 = 5 000; Mrpp = 40; 0 = 0,8; %ins = 50-100; Nop = 400 000

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 57
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation de  - les résultats sont-ils extrapolables ?

oui : [k x Np0, Mrpp, Nrpp0, %ins, k x Nop] = [Np0, Mrpp, Nrpp0, %ins, Nop]

[ Np0 = 1 000 000; Mrpp = 40; 0 = 0,8; %ins = 90; Nop = 100 000 000]
=
[Np0 = 5 000; Mrpp = 40; 0 = 0,8; %ins = 90; Nop = 500 000]

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 58
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation de  - Comportement asymptotique

Que devient  lorsqu'on laisse fonctionner le fichier pendant très longtemps ?

Il tend vers une constante  = q

0,90
%ins=50
0,85 %ins=60
%ins=70
0,80 %ins=80
%ins=90
%ins=100
0,75

0,70
1 pas = 5 x Nr0 / 100
0,65

0,60

0,55

0,50 pas
0

10

20

30

40

50

60

70

80

90

100

110

120

130

140

150

160

170

180

190

200
Np0 = 5 000; Mrpp = 40; 0 = 0,8; %ins = 50-100; Nop = 1 600 000

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 59
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation de  - Comportement asymptotique

La valeur asymptotique  = q dépend de %ins et Mrpp
q = f(%ins, Mrpp)
q
0,72

0,71

0,70

0,69

0,68
Mrpp=10
0,67 Mrpp=20
Mrpp=30
0,66 Mrpp=40
Mrpp=50
0,65 Mrpp=60
Mrpp=70
0,64 Mrpp=80
Mrpp=90
0,63
Mrpp=100

0,62 %ins
50 55 60 65 70 75 80 85 90 95 100

coût : 700h de calcul

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 60
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation de  - Les abaques opérationnels

La valeur asymptotique est un concept théorique : on ne laisse jamais un fichier

fonctionner aussi longtemps sans réorganisation (r > 0,5 !!!).
Seule la période de prime jeunesse (A, B, C) est utile. Simulations courtes.

1,00
A B C D A' B' C'
0,95

0,90

0,85

0,80

0,75

0,70

0,65

0,60

0,55

0,50 pas
0
10
20
30
40
50
60
70
80
90
100
110
120
130
140
150
160
170
180
190
200
[Mrpp=40; 0 = 0,8; %ins = 90%]
azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 61
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation de  - Les abaques opérationnels

Abaques opérationnels : nous renseignent sur la période utile des fichiers.

• Obtenus à partir d'une série de simulations.
• Plus faciles à utiliser que des tableaux de chiffres
• Permettent des interpolations

Trois familles :
• selon Mrpp
• selon %ins
• selon 0

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 62
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation de  - Les abaques opérationnels

Abaques selon Mrpp

0,80
0,79
0,78
0,77
0,76
0,75
0,74
0,73
0,72
0,71
0,70 1 pas = Nr0 / 100
0,69
0,68
0,67 Mrpp=10
0,66 Mrpp=20
Mrpp=30
0,65 Mrpp=40
0,64 Mrpp=50
Mrpp=60
0,63
Mrpp=70
0,62 Mrpp=80
Mrpp=90
0,61
Mrpp=100
0,60 pas
100

110

120

130

140

150

160

170

180

190

200
10

20

30

40

50

60

70

80

90
0

 = f(%ins=55; 0=0,7; Mrpp=(10-100); pas)

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 63
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation de  - Les abaques opérationnels

Abaques selon %ins

0,85
%ins=50
%ins=51
%ins=52
%ins=53

0,80 %ins=54
0,799
%ins=55
%ins=60
%ins=70
%ins=80
0,75 %ins=90
%ins=100 1 pas = Nr0 / 100

0,70

0,65 pas
10

20

30

40

50

60

70

80

90
0

100

110

120

130

140

150

160

170

180

190

200
22
 = f(%ins=50-100; 0=0,7; Mrpp=20; pas)

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 64
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation de  - Les abaques opérationnels

Abaques selon 0

1,00
0=0,6
0=0,7
0,95
0=0,8
0=0,9
0,90
0=1

0,85

0,80

0,75
1 pas = Nr0 / 100

0,70

0,65

0,60

0,55 pas
100

110

120

130

140

150

160

170

180

190

200
10

20

30

40

50

60

70

80

90
0

 = f(%ins=55; 0=0,6-1; Mrpp=20; pas)

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 65
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation de , r, split , bal, merge

100

90 r
split
80 bal
merge
70

60

50

40
1 pas = Nr0 / 100
30

20

10

0
100

110

120

130

140

150

160

170

180

190

200
10

20

30

40

50

60

70

80

90
0

[Np0 = 11 250; Mrpp = 20; %ins = 90; 0 = 0,8; Nop = 360 000]

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 66
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (taux)

Evaluation de r, split , bal, merge

15
split
14
bal
13
merge
12
11
10
9
8
7
6
1 pas = Nr0 / 100
5
4
3
2
1
0
100

110

120

130

140

150

160

170

180

190

200
0

10

20

30

40

50

60

70

80

90

[Np0 = 11 250; Mrpp = 20; %ins = 90; 0 = 0,8; Nop = 360 000]

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 67
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (application)

Application : évolution d'un fichier de base

Nbre initial de pages Np0 1 000 000 Tps lecture page suivante (prefetch) tls1 0,000184
Taille des pages Mrpp 20 Tps lecture aléatoire 1 page. tla1 0,0123
Taux de chargement initial t0 0,8 Tps lecture page suivante (rupture) tlsr 0,0123
% des insertions %ins 0,9 Tps accès page de base av. insert tl1k (insert) 0,0246
Nbre d'opérations par jour op/jour 40 000 Tps accès page de base av. delete tl1k (delete) 0,0246
Nbre de pas Npas 200
Nop = 2 x Nr0 facteur Nop 2

Nbre initial d'enr. par page Nrpp0 16

Nbre initial d'enr. Nr0 16 000 000
Nbre total d'opérations Nop 32 000 000
Nbre d'opérations par pas op/pas 160 000
Nbre d'insertions par pas insert/pas 144 000
Nbre de suppressions par pas delete/pas 16 000
Nbre de nouveaux enreg. par pas nrec/pas 128 000
Nbre de jours par pas jour/pas 4

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 68
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (application)

Application : évolution d'un fichier de base

Np0 1.000.000 Nrpp0 16 tls1 0,000184

Mrpp 20 Nr0 16.000.000 tla1 0,0123
t0 0,8 Nop 32.000.000 tlsr 0,0123
%ins 0,9 op/pas 160.000 tl1k (insert) 0,0246
op/jour 40.000 insert/pas 144.000 tl1k (delete) 0,0246
Npas 200 delete/pas 16.000
facteur Nop 2 nrec/pas 128.000
jour/pas 4
t 0,8 0,8311 0,8472 0,8351 0,8015 0,7618 0,7251
pr 0 0,0012 0,0197 0,0681 0,1367 0,207 0,2698
tsplit 0 0,0016 0,0139 0,0338 0,0549 0,0724 0,0854
tbal 0 0 0,0033 0,0085 0,017 0,027 0,0376
tmerge 0 0 0,0001 0,0002 0,0006 0,0013 0,0017

Nbre de jours Jours 0 20 40 60 80 100 120

N° du pas Pas 0 5 10 15 20 25 30
Nbre d'enreg. Nr 16.000.000 16.640.000 17.280.000 17.920.000 18.560.000 19.200.000 19.840.000
Nbre d'enr. par page Nrpp 16 16,622 16,9 16,7 16,0 15,2 14,5
Nbre de pages Np 1.000.000 1.001.083 1.019.831 1.072.926 1.157.830 1.260.174 1.368.088
Tps de lecture séquentielle tlsf 184 199 431 1.083 2.131 3.392 4.724
Vitesse de lecture (enreg./s) vls 86.957 83.721 40.087 16.551 8.711 5.660 4.200
Tps d'une insertion tins 0,0369 0,0370 0,0374 0,0381 0,0389 0,0396 0,0401
Tps d'une suppression tdel 0,0369 0,0369 0,0370 0,0372 0,0375 0,0379 0,0384

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 69
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (application)

Application : évolution d'un fichier de base

Quand réorganiser ?

Jours 0 20 40 60 80 100 120

Pas 0 5 10 15 20 25 30 Tps lecture page
Nr 16.000.000 16.640.000 17.280.000 17.920.000 18.560.000 19.200.000 19.840.000 suivante (rupture)
Nrpp 16 16,622 16,9 16,7 16,0 15,2 14,5
Np 1.000.000 1.001.083 1.019.831 1.072.926 1.157.830 1.260.174 1.368.088
tlsf 184 199 431 1.083 2.131 3.392 4.724 tlsr = 12,3 ms
vls 86.957 83.721 40.087 16.551 8.711 5.660 4.200
tins 0,0369 0,0370 0,0374 0,0381 0,0389 0,0396 0,0401
tdel 0,0369 0,0369 0,0370 0,0372 0,0375 0,0379 0,0384

Jours 0 20 40 60 80 100 120

Pas 0 5 10 15 20 25 30
Nr 16.000.000 16.640.000 17.280.000 17.920.000 18.560.000 19.200.000 19.840.000
Nrpp 16 16,622 16,9 16,7 16,0 15,2 14,5
Np 1.000.000 1.001.083 1.019.831 1.072.926 1.157.830 1.260.174 1.368.088
tlsf 184 189 264 476 817 1.227 1.660 tlsr = 4,0 ms
vls 86.957 88.143 65.377 37.628 22.717 15.644 11.950
tins 0,0369 0,0370 0,0374 0,0381 0,0389 0,0396 0,0401
tdel 0,0369 0,0369 0,0370 0,0372 0,0375 0,0379 0,0384

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 70
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (application)

Application : calcul volume et tps de lecture fichier SI

Hardware Physical parameters

Tps déplacement bras unitaire Seek(avg) 8 ms Taille d'une page Lp 4 096 bytes
Tps déplacement bras moyen Seek(step) 1 ms Taille pointeur d'enreg. Lptr(rec) 6 bytes
Vitesse de rotation speed 7 200 rev/min Taille pointeur de page Lptr(pg) 4 bytes
Taille d'un secteur bytes/sector 512 bytes Taux d'occupation fichier de base tb 0,8
Nbre de secteurs/piste sectors/track 900 sectors Taux d'occupation index ti 0,8
Nbre de pistes/cylindre tracks/cylinder 8 track s
Nbre de cylindre cylinders/disk 136 000 cylinders Overhead page de base Pb(overhd) 0 bytes
Overhead enreg. de base Rb(overhd) 0 bytes
Capacité d'une piste track capacity 460 800 bytes Overhead page d'index Pi(overhd) 0 bytes
Capacité d'un cylindre cylinder capacity 3 686 400 bytes Overhead entrée d'index Ri(overhd) 0 bytes
Capacité d'un disque (en MB) disk capacity 478 125 MB Overhead fichier File(overhd) 0 pages
Tps d'une rotation revol. time 0,0083 s Taille d'une extension Extent 100 pages
Tps lecture d'un secteur aléatoire rand. sector start 0,0122 s Taille du tampon Buffer size 20 pages
Tps lecture d'une piste aléatoires rand. track read 0,0205 s Nre de pages/piste pages/track 112
Tps lecture d'une page aléatoire rand. page read 0,012241 s

Logical parameters
Nbre d'enreg. Nr 1 000 000 records
Taille d'un enreg. Lr 200 bytes
Modèle de calcul : [Link] Taille de la clé Lk 40 bytes

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 71
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (application)

Application : calcul volume et tps de lecture fichier SI

Base file Index

Taille enreg. Lr(actual) 200 bytes Li(actual) 44 bytes Taille entrée d'index
Nbre max d'enreg./page Mrpp 20 Mipp 93 Nbre max d'entrées/page
Nbre moyen d'enreg./page Nrpp 16 Nipp 74,4 Nbre moyen d'entrées/page
Nbre de pages de base Npb 62 500 pages Npi 854 pages Nbre de pages d'index
Nbr of levels 3 levels Nbre de niveaux d'index

Ni(n) 62500 Niveau 3 : nbre d'entrées

Npi(n) 841 Niveau 3 : nbre de pages
Ni(n-1) 841 Niveau 2 : nbre d'entrées
Npi(n-1) 12 Niveau 2 : nbre de pages
Ni(n-2) 12 Niveau 1 : nbre d'entrées
Npi(n-2) 1 Niveau 1 : nbre de pages

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 72
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances (application)

Application : calcul volume et tps de lecture fichier SI

Total volume Times (worst case)

Volume du fichier de base Base file volume 62 500 pages Seq. file read 777 s Tps max de lect. séquentielle
Volume de l'index Index volume 854 pages Seq. rec read 0,000777 s Idem réduit à l'enreg.
Volume total Net total vol. 63 354 pages Seq. rec/sec 1287 rec/s Vitesse de lecture
Volume total réel Actual total vol. 63 400 pages Key rec read 0,037 s Tps d'accès par clé
... en MB or ... 247,7 MB
... en disque or ... 0,001 disk s Times (optimal)
Nbre de niveaux observés Nbr of levels (act) 3 levels Seq. file read 12 s Tps min. de lect. séquentielle
Nbre de niveaux calculés Nbr of levels (theor) 3 levels Seq. rec read 0,000012 s Idem réduit à l'enreg.
Taux d'occupation global t (actual) 77,1 % Seq. rec/sec 83 333 rec/s Vitesse de lecture

Key rec read 2 disk acc Accès par clé

Key rec read 0,025 s Idem en secondes
Key rec/sec 40 rec/s Vitesse de lecture par clé

Key buffer size 20 pages Taille du tampon

Key buffer used 14 pages Taille du tampon utilisée

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 73
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances

Dégradation des performances d'un fichier séquentiel indexé

Les opérations de modification entraînent principalement 2 phénomènes de

dégradation des performances :

1. Chute des taux d'occupation b et i :

Npb = Nr (b x Mrpp) augmente
 tlsf = Npb x tls1 augmente
 n = log(Npb) / log(i x Lp / Li ) augmente

2. Augmentation des ruptures de séquence :

r augmente  tlsf = (1 - r) x Npb x tls1 + r x Npb x tla1

0,184 ms 12,3 ms

Cependant : dégradation très progressive.

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 74
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances

Taux : observations et recommandations générales

1. Valeur optimale de 0 =  0,7.

0 = 1 admissible si aucune insertion (fichier en lecture seule par exemple)
2. Performances favorable pour les grandes valeurs de Mrpp (fichier de base et
index).

3.  et r deviennent défavorables à partir du pas 50, voire plus tôt.

Réorganisation du fichier recommandée dès que nop se rapproche de 30 à 50%
du nombre d’enregistrements au départ.
[Link]. à partir de 400.000 opérations dans un fichier de 1.000.000 enregistrements

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 75
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances

Réorganisation d'un fichier séquentiel indexé

Reconditionnement du fichier :
1. taux d'occupation favorable (70-80) uniforme (pour toutes les pages)
2. élimination des ruptures de séquences (r = 0)

Réorganisation par rechargement :

Processus très simple et rapide (linéaire en Nr mais attention à r !)
1. lecture séquentielle du fichier courant
2. rangement séquentiel des enregistrements dans le nouveau fichier, avec un taux
d'occupation initial favorable (p. ex. 0 = 0,7 à 0,8)
3. en parallèle, construction des différents niveaux d'index, avec un taux
d'occupation initial favorable.

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 76
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle 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.

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 77
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 78
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Principes

Deuxième technique de base d'implémentation d'un index

primaire

L'adresse d'un enregistrement est obtenue par une fonction de calcul

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 79
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Principes

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.

séquentiel
calculé
indexé

page [p]
k f k

conversion k  p conversion k  p
mémorisée calculée

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 80
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Principes

à démontrer !
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

Cette organisation ne permet pas l'accès séquentiel ordonné

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 81
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Principes

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
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 82
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Principes

Nature de la fonction f ?

K : valeurs de l'identifiant
p : adresse de la page de l'enregistrement k  K
Mrpp : capacité d'une page
Cas 1
K = {0, 1, 2, 3, ..., 99998, 99999}
p = k / Mrpp
Cas 2
K = {1, 3, 5, 7, ..., 99997, 99999}
p = ((k - 1)/2) / Mrpp
Cas 3
K = {1, 3, 4, 87, 162, 163, 164, 290, 1035, ..., 99991}
p= ?
Cas 4
K = {'Anselme', 'Bernard', 'Catherine', 'Eve', ..., 'Xavier'}
p= ?

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 83
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Principes

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 occupées voire vides
• certaines pages déborderont.

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 84
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Principes

Deux problèmes à résoudre :

1. Choix de la fonction f de calcul d'adresse

2. Gestion des débordements

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 85
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Principes

La fonction de calcul d'adresse

Objectif : répartir au mieux les valeurs de K dans l'espace des adresses.

f(k) = f3(f2(f1k)))

k = "Charles" numérisation

hachage

cadrage p = 1423

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

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 86
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Principes

La fonction de calcul d'adresse

Où ranger l’enregistrement d’identifiant "Charles" dans un fichier de 5.000 pages ?

• numérisation f1
Codes 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 f2
Technique du pliage : f2(789385842) = 78938 + 02485 = 81423.

• cadrage f3
Ajustement à 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
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 87
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Principes

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.

Exemple : on le stocke dans une page qui possède assez d'espace pour
accueillir l'enregistrement et dont l'adresse p' est stockée dans
la page [p].
On distingue donc : l’adresse de base p
l’adresse de stockage p’

espace
espace de base
de débordement
(Npb pages)
(extensible)

f(k)

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 88
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Principes

Gestion des débordements

page 82 page 83 page 84 page 85

A E H L
B F I M espace de
C G J N base
D K O

page 907 page 908 page 909 page 910

P R V
Q S espace de
T débordement
U

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 89
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Performances

Performances d'un fichier calculé

Un fichier calculé est défini par

1. Npb le nombre de pages de base
2. Mrpp la taille des pages

On connaît, à un moment déterminé,

1. Nr le nombre d'enregistrements qui ont été stockés (répartis entre espace de
base et espace de débordement)
2. Nrpp le nombre moyen d'enregistrements envoyés dans une page de base;
peut être > Mrpp

On définit :
ch = Nrpp / Mrpp, le taux de chargement du fichier (typiquement de 0,5 à 2)
On a : Nrpp = ch x Mrpp
Nr = ch x Mrpp x Npb

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 90
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Performances

Performances d'un fichier calculé

Volume du fichier

On connaît : Npb le nombre de pages de base

On cherche : Np le nombre total de pages
On pose : Np = ap x Npb
ap : taux d'accroissement du nombre de page dû aux débordements

On détermine la fonction ap = f(Mrpp, ch)

Disponible sous forme d'abaque

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 91
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Performances

Performances d'un fichier calculé

Volume du fichier

ap 2,60

2,40

2,20

2,00 Mrpp
50
5
1,80 10
15
1,62 5 20
1,60
25
30
1,40
35
40
1,20 45
50
1,00
0,5 0,6 0,7 0,8 0,9 1 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9 2 ch

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 92
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Performances

Performances d'un fichier calculé

Volume du fichier

Exemple Npb = 100 000

Mrpp = 20
Nr = 2 200 000

ch = Nr / (Mrpp x Npb) = 1,1

L'abaque nous donne, pour Mrpp = 20 et ch = 1,1 ap = 1,62
On a donc : Np = ap x Npb = 162 000 pages

Taux d'occupation global

 = Nr / (Mrpp x Np) = 0,679

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 93
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Performances

Performances d'un fichier calculé

Temps de lecture séquentielle

Ordre des enregistrements indifférent

tlsf = Np x tls1

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 94
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Performances

Performances d'un fichier calculé

Temps de lecture par clé

nombre moyen de lectures de pages : nlp = f(Mrpp, ch)

nlp 1,7

1,6

1,5

Mrpp
1,4
5
5 10
1,3 15
50 20
25
1,2
30
1,135 35
1,1 40
45
50
1,0
0,5 0,6 0,7 0,8 0,9 1 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9 2 ch

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 95
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Performances

Performances d'un fichier calculé

Temps de lecture

Exemple
L'abaque nous donne, pour Mrpp = 20 et ch = 1,1 nlp = 1,135
On a donc : tlk1 = nlp x tla1 = 14 ms
Vitesse de lecture : 71 enreg./s

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 96
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.6 Organisation séquentielle indexée - Performances

Réorganisation d'un fichier calculé

La croissance progressive de ch entraîne une augmentation du temps d'accès (nlp).

D'où la nécessité de restructurer le fichier, c'est-à-dire d'augmenter la taille de l'espace
de base. Par exemple : passer de ch = 1,2 à 0,7

Procédure de base :
Lecture séquentielle du fichier ancien et insertion de chaque enregistrement dans le
nouveau selon le procédé décrit plus haut.
Coût insertion  2 x tla1 x Nr (14,6 ms par enregistrement) + lecture
Procédure optimisée (à démontrer) :
A partir du fichier ancien, on constitue un fichier séquentiel augmenté d'un champ,
l'adresse de chaque enregistrement dans le nouvel espace de base.
On trie le fichier selon ce nouveau champ.
On procède comme ci-dessus avec le fichier trié.
Coût insertion  2 x tls1 x Nr (0,368 ms par enregistrement) + lecture + écriture +tri

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 97
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.7 Organisation calculée - Comparaison des techniques primaires

séquentiel indexé calculé

disponibilité très répandu plus rare
occupation espace disque moyen moyen à excellent
occupation mémoire centrale plusieurs milliers de pages 1 page
stabilité adresses faible bonne
accès par clé : temps moyen moyen, améliorable excellent
accès par clé : constance tps constant variable
tps d'accès par clé selon Npb logarithmique moyenne constante
accès ordonné oui non
accès par intervalle oui non
dégradation progressive (r !) progressive, faible,
extensibilité oui oui
reconstruction rapide lente

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 98
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.8 Les index secondaires

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 99
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.8 Les index secondaires

Index primaire Rappel

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 bonnes 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
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 100
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.8 Les index secondaires

Rappel
Index (dans un livre)

B
base de données active 167 les termes de la lettre B
base de données temporelles 153, 170
between 67

C
cardinalité d’attribut 182
cardinalité d’un role 187
catalogue 147, 169
cellules 280
Chen 29, 205
chimpanzé 364
circuit de dépendances 312, 392
classe d’objets 201 le terme clé étrangère
classe fonctionnelle 184, 185, 242, 245
numéros des pages
clé étrangère 34, 44, 77, 81, 156
close 145 qui contiennent ce terme
coalescing 155
COBOL 18, 143
Codd 27
codomaine 351
colonne 32, 35, 44

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 101
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.8 Les index secondaires

Rappel
Index (dans une base de données)

Index sur la colonne LOCALITE

01
02
03
04
05
Bruxelles 11
06
Genève 03 07
Lille 12 08
Namur 01 06 14 15 09
Paris 16 10
Poitiers 02 07 09 11
Toulouse 04 05 08 10 13 12
13
14
15
16
numéros des lignes dont
LOCALITE = 'Toulouse'
chaque ligne possède un numéro unique;
les valeurs de LOCALITE,
l'accès à une ligne de numéro donné est très rapide
triées par ordre alphabétique

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 102
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.8 Les index secondaires

Structure d'un index secondaire (non identifiant)

Fichier de base

F400 Jacob ... Bruxelles C2 ...

B332 Monti ... Genève B2 ...

Index (LOCALITE)
B062 Goffin ... Namur B2 ...

K111 Vanbist ... Lille B1 ...

C123 Mercier ... Namur C1 ...

Bruxelles
L422 Frank ... Namur C1 ...
Genève
S127 Vanderka ... Namur C1 ...
Lille
B112 Hansenne ... Poitiers C1 ...
Namur
Nv entrées S712 Guillaume ... Paris B1 ...
Paris
F011 Poncelet ... Poitiers B2 ...
Poitiers
F010 Toussaint ... Poitiers C1 ...
Toulouse
K729 Neuman ... Toulouse B3 ...

C400 Férard ... Poitiers B2 ...

D063 Mercier ... Toulouse A1 ...

C003 Avron ... Toulouse B1 ...

B512 Gillet ... Toulouse B1 ...

données de base

Accès aux enregistrements (liste de pointeurs)

Dictionnaire des valeurs

Index du dictionnaire des valeurs (séq. indexé ou calculé)

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 103
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.8 Les index secondaires

Structure d'un index secondaire (identifiant)

Index (NCLI) Fichier de base

B062 F400 Jacob ... Bruxelles C2 ...

B112 B332 Monti ... Genève B2 ...

B332 B062 Goffin ... Namur B2 ...

B512 K111 Vanbist ... Lille B1 ...

C003 C123 Mercier ... Namur C1 ...

C123 L422 Frank ... Namur C1 ...

C400 S127 Vanderka ... Namur C1 ...

peut remplacer D063 B112 Hansenne ... Poitiers C1 ...

un index primaire F010 S712 Guillaume ... Paris B1 ...

F011 F011 Poncelet ... Poitiers B2 ...

F400 F010 Toussaint ... Poitiers C1 ...

K111 K729 Neuman ... Toulouse B3 ...

K729 C400 Férard ... Poitiers B2 ...

L422 D063 Mercier ... Toulouse A1 ...

S127 C003 Avron ... Toulouse B1 ...

S712 B512 Gillet ... Toulouse B1 ...

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 104
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.8 Les index secondaires

Un fichier peut posséder plusieurs index secondaires

Index (NCLI) Fichier de base

B062 F400 Jacob ... Bruxelles C2 ...

B112 B332 Monti ... Genève B2 ... Index (LOCALITE)

B332 B062 Goffin ... Namur B2 ...

B512 K111 Vanbist ... Lille B1 ... Bruxelles

C003 C123 Mercier ... Namur C1 ... Genève
C123 L422 Frank ... Namur C1 ... Lille
C400 S127 Vanderka ... Namur C1 ... Namur
D063 B112 Hansenne ... Poitiers C1 ...
Paris
F010 S712 Guillaume ... Paris B1 ...
Poitiers
F011 F011 Poncelet ... Poitiers B2 ...
Toulouse
F400 F010 Toussaint ... Poitiers C1 ...

K111 K729 Neuman ... Toulouse B3 ...

K729 C400 Férard ... Poitiers B2 ...

L422 D063 Mercier ... Toulouse A1 ...

S127 C003 Avron ... Toulouse B1 ...

S712 B512 Gillet ... Toulouse B1 ...

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 105
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.8 Les index secondaires

Représentation pratique des listes de pointeurs

Toulouse

Toulouse

Toulouse
une entrée théorique Toulouse Toulouse
Toulouse
Toulouse
Toulouse
Toulouse Toulouse
Toulouse
Toulouse
Toulouse
Toulouse

ner entrées réelles

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 106
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.8 Les index secondaires

Les index bitmap

Chaque entrée K = k comporte une chaîne B de Nr bits.

Si l'enregistrement i est tel que K = k, alors B(i) = 1

Index (LOCALITE)

Bruxelles 1000000000000000

Genève 0100000000000000

Lille 0001000000000000

Namur 0010111000000000

Paris 0000000010000000

Poitiers 0000000101101000

Toulouse 0000000000010111

Chaînes très longues  compression par technique sans pertes (LZN par exemple)

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 107
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.8 Les index secondaires

Les index identifiants augmentés

Les entrées contiennent des valeurs de champs additionnelles.
Index (NCLI + [LOCALITE,CAT]) Fichier de base

B062 Bruxelles C2 F400 JACOB Bruxelles C2

B112 Genève B2 B332 MONTI Genève B2 Objectif :

B332 Namur

B512 Lille
B2

B1
B062 GOFFIN

K111 VANBIST
Namur

Lille
B2

B1
éviter l'accès au fichier de base.
C003 Namur C1 C123 MERCER Namur C1

C123 Namur C1 L422 FRANK Namur C1 select NCLI, LOCALITE, CAT

C400 Namur C1 S127 VANDERKA Namur C1 from CLIENT
D063 Poitiers C1 B112 HANSENNE Poitiers C1 where NCLI between k1 and k2
F010 Paris B1 S712 GUILLAUME Paris B1 and CAT like 'B%';
F011 Poitiers B2 F011 PONCELET Poitiers B2

F400 Poitiers C1 F010 TOUSSAINT Poitiers C1

K111 Toulouse B3 K729 NEUMAN Toulouse B3

K729 Poitiers B2 C400 FERARD Poitiers B2

L422 Toulouse A1 D063 MERCIER Toulouse A1

S127 Toulouse B1 C003 AVRON Toulouse B1

S712 Toulouse B1 B512 GILLET Toulouse B1

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 108
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.8 Les index secondaires

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é)

On dispose donc de tous les éléments pour calculer :

• 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"

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 109
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.9 Les techniques d'agrégation

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 110
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.9 Les techniques d'agrégation

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
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 111
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.9 Les techniques d'agrégation

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
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 112
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.9 Les techniques d'agrégation

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
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 113
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.9 Les techniques d'agrégation

Proximité logique  proximité physique

enregistrements couplés par des associations

select [Link], DATECOM, QCOM, NPRO

from COMMANDE M, DETAIL D
where [Link] = [Link];

 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
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 114
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.9 Les techniques d'agrégation

Deux techniques très répandues :

• le clustering index (p. ex. DB2, SQL Server)
• le cluster (p. ex. Oracle)

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 115
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.9 Les techniques d'agrégation

Le clustering index

• index secondaire sur une clé 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
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 116
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.9 Les techniques d'agrégation

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
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 117
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.9 Les techniques d'agrégation

Le cluster

• 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 d'une chaîne de pages
• on associe un index au cluster

Index (NCOM) Fichier de base : clusters <COMMANDE(NCOM), DETAIL(NCOM)>

30177
30178 30178 K111 22/12/2008 30178 CS464 0025
30179
30179 C400 22/12/2008 30179 CS262 0060 30179 PA60 0020
30182
30182 S127 23/12/2008 30182 PA60 0030
30184
30185 30184 C400 23/12/2008 30184 CS464 0120 30184 PA45 0020

30186 30185 F011 02/01/2009 30185 CS464 0260 30185 PA60 0015 30185 PS222 0600
30187

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 118
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.9 Les techniques d'agrégation

Le cluster

• 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%';

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 119
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.10 Un exemple : SQL Server de Microsoft

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 120
1. Motivation et introduction 5. Les SGBD ... 4.8 Les index secondaires
2. Concepts des bases de données 4.5 Les index 4.9 Les techniques d'agrégation
3. Modèle relationnel et normalisation 4.6 Organisation séquent. indexée 4.10 Un exemple : SQL Server
4. Implémentation des structures de données 4.7 Organisation calculée

4.10 Un exemple : SQL Server de Microsoft

voir annexe 4

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 121
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

Fin du module 4

azerty
I. Concepts des bases de données Bases de données   J-L Hainaut 2022 122
azerty Bases de données   J-L Hainaut 2022 123