PARTIE 2:

MÉMOIRE RELATIONNELLE
MÉMOIRE RELATIONNELLE: DÉFINITION
La mémoire relationnelle est une couche du SGBD qui accède à la BD
Quatre fonctions principales
1. Présenter une vision relationnelle des fichiers qui constituent la BD : Fichiers,
enregistrements, champs

2. Gérer la mémoire centrale (MC)

Relations stockées par page en MS
Chargées en MC sur demande (mémoire virtuelle)
MS est décomposée en segments
Un segment est constitué de plusieurs pages
La page est l’unité de transfert entre MS et MC
Un fichier est sauvegardé dans un seul segment (plusieurs pages)
3. Gérer les différentes relations de la BD
Tables, index, Vues, catalogues, etc.
4. Etablir des méthodes d’accès
Hachage, index, b-arbre, etc.
COMMENT EST ORGANISÉ LE STOCKAGE DANS LES
SGBD?
• Le stockage dans les SGBD (Systèmes de Gestion de Base de Données) est organisé de
manière hiérarchique et structurée pour garantir l'efficacité de l'accès, de la manipulation et
de la gestion des données.
• Les principaux niveaux d'organisation du stockage :
• Fichiers
• Pages,
• Blocs,
• Tables,
• Index,
• Schéma,
• tabespace
FICHIERS
• Fichiers de données : Contiennent les données des tables et des index. Chaque table
peut être stockée dans un ou plusieurs fichiers.
• Les fichiers d’indexe: Un fichier d'index est une structure qui permet de référencer
les enregistrements d'une table en fonction de la valeur d'une ou plusieurs colonnes
(appelées clés d'index). Leurs rôles est d’améliorer la vitesse des opérations de
recherche, de tri et de filtrage des données dans les tables
• Fichiers de journalisation (log files) : Utilisés pour enregistrer les transactions et
garantir la durabilité et la récupération en cas de panne.
PAGES

• Pages de données : Une page est une unité de stockage au niveau du SGBD. Les
fichiers de données sont divisés en pages. Une page contient généralement plusieurs
enregistrements (Un enregistrement ou ligne est une instance de données qui
correspond à une entrée dans une table. Il est constitué de plusieurs attributs, chacun
représentant une colonne de la table.).

• Pages d'index : Utilisées pour stocker les structures d'index qui accélèrent l'accès aux
données.
BLOCS

• Blocs de disque : La plus petite unité de lecture ou d'écriture pour le système de fichiers sous-
jacent (utilisé par le SE). Les pages sont généralement alignées sur les blocs de disque pour
optimiser les opérations d'E/S.

• En effet, Les pages sont généralement conçues pour être de la même taille ou d'un multiple de
la taille des blocs. Cela signifie que si un bloc est de 4 Ko, une page pourrait également faire
4 Ko ou 8 Ko. Lorsqu'une page est lue à partir du disque, le SGBD peut effectuer deux
opérations de bloc pour charger la page entière.
• Si la page était de taille variable ou non alignée, cela pourrait entraîner des lectures
supplémentaires et une complexité inutile..
MÉTHODES DE STOCKAGE
• Fichier Commun (Tas de données)

 Les enregistrements sont placés à la queue dans des pages successives.

 Un enregistrement ne peut pas être stocké sur 2 pages
 Le seul accès aux données dans le cas de la recherche d’un enregistrement est un balayage
séquentiel des tuples. C’est une Opération très coûteuse.

 L’insertion d’un nouvel enregistrement s’effectue dans la dernière page. Si cette dernière est saturée,
alors une nouvelle page est allouée et l’enregistrement est inséré.
 La suppression est assurée logiquement grâce à un indicateur de suppression.
Cette organisation a été implémentée par défaut dans le système INGRES
STOCKAGE PAR HACHAGE
 Disposer d’une fonction de hachage h(c ) qui permet de calculer un numéro de bloc ou paquet,
contenant un ensemble de pages, à partir d’une clé.

 La recherche de l’enregistrement s’effectue ensuite séquentiellement dans le bloc.

HACHAGE ALGORITHME
Algorithme de recherche

 Entrée : valeur de clé c

 Calcul h ( c ) : numéro de bloc

 Consultation de la table des blocs : récupération de la première page du bloc

 Recherche dans cette page l’enregistrement ayant pour clé c.

Algorithme de modification :

 rechercher l’enregistrement à l’aide de l’algorithme précédent

 réaliser la modification
 HACHAGE
• Algorithme d’insertion :
Lorsqu'un nouvel enregistrement est inséré, la clé est d'abord hachée pour déterminer
l'emplacement.
Si l'emplacement est libre, l'enregistrement est ajouté.
Si l'emplacement est déjà occupé (collision), différentes stratégies peuvent être utilisées,
comme :
Chaînage : Créer une liste liée des enregistrements à cet emplacement.
Open Addressing : Trouver un autre emplacement disponible selon une certaine méthode (par exemple, linéaire,
quadratique).

Inconvénient: si Le bloc est saturé cela signifie qu’il va y avoir débordement. C’est la gestion
des débordements qui va dégrader les performances dans les techniques de hachage.

• Algorithme de suppression :
Rechercher l’enregistrement à supprimer
Soit libérer la place qu’occupait cet enregistrement en mettant à jour le chaînage,
soit mettre un indicateur de suppression dans l’en-tête de l’enregistrement à
supprimer.
 Données à Insérer

HACHAGE EXEMPLE:
Imaginons que nous voulons stocker des noms
d'étudiants avec leurs identifiants (ID) dans une
table de hachage.

Supposons que notre fonction de hachage soit

très simple, où nous prenons l'ID de l'étudiant Calcul des Index
modulo la taille de la table.

Si la taille de la table de hachage est de

7.index=ID mod 7 :

Ici, nous avons plusieurs collisions (Alice, Bob,

Charlie, et David ont tous le même index).

Nous utiliserons la méthode de chaînage pour

gérer ces collisions :Pour l'index 1 : [Alice, Bob,
Charlie, David]Pour l'index 2 : [Eve]

Table de Hachage Finale

EXEMPLE (SUITE)

• Recherche d'un Employé:

• Pour rechercher des informations sur un employé par son ID :

• Supposons que nous voulons rechercher David (ID 4).
• Calculons l'index : 4 mod 3=1.
• Nous vérifions l'index 1 dans la table de hachage, qui indique que David est dans le
Bloc 2.
• Nous accédons au Bloc 2 pour récupérer les informations sur David.
 FICHIER INDEXE
• Un fichier index contient un ensemble de couples (c,p) où c est la clé du premier enregistrement de la page p.
• Index dense : il contient toutes les clés du fichier
• Index non dense : on crée des enregistrements index pour certains enregistrements du fichier : dans ce cas le
fichier est trié et divisé en blocs. A chaque bloc lui est associée une entrée dans l’index.
• (c,p) = < plus grande clé du bloc, adresse relative du bloc>
FICHIERS • Algorithme de recherche

INDEXES Accès à l’index,

Recherche dans l’index de la clé d’enregistrement désiré,

Récupération dans l’index de l’adresse relative de
l’enregistrement ( si index dense), ou de l’adresse relative du

bloc qui le contient (si index non dense),

Conversion de l’adresse relative en adresse réelle,

Accès à l’enregistrement ou au bloc,

Transfert de l’enregistrement dans la zone du programme

utilisateur.
EXEMPLE

La table des films, avec :

1 000 000 (un million) de films

Un enregistrement = 120 octets

Un bloc = 4K => 34 enregistrements par bloc

environ 30 000 blocs, 120 Mo
TYPES DE RECHERCHE :
• Recherche par clé : on associe une valeur à chaque attribut de la clé
• Recherche par intervalle : on associe un intervalle de valeurs à chaque attribut de
la clé
• Recherche par préfixe : on associe une valeur à un préfixe de la clé
• Exemple:
 Le titre du film (c’est aussi la clé primaire)
 l’année du film (recherche par intervalle)
 le titre plus l’année
• Opérations :
 Rechercher Vertigo
 Rechercher les films parus entre 1960 et 1975
 Rechercher les films commençant par ’V’
INDEXE
1.Comment est organisé cet index?
2. Quelle est sa particularité?
3. De quoi est composé un enregistrement de cet index?
4. quelle est la condition quant à l’organisation du fichier de
données ?
5. Quelle est la taille du fichier indexe ?(titre occupe 20 octets et
l’adresse 8 octets, taille fichier données est 120 M, taille d’un bloc
4K)
6. quel est l’inconvénient de cette organisation ?
 1. quelle est le type de cet indexe ?
INDEXE (2) 2. comment est représenté un
enregistrement dans l’index ?
3. quelle est la taille de
l’index ?(année=4 octets, adr=8
octets, nombre films= 1000000);
conclure.
4. comparer les 2 indexes lors de la
recherche par clé ou par intervalle.
INDEXE (3)
Si l’index est trop gros ? On l’indexe à son tour.
Essentiel : l’index est trié, donc on peut l’indexer par
un second niveau
non-dense
Donc dès le second niveau on diminue
drastiquement la taille. On peut continuer jusqu’à
un niveau avec une seule page.
On obtient une structure séquentielle indexée
B_ARBRE

Est structures de données/ méthodes qui permettent la localisation rapide du fichier (archives ou des
clés), en particulier dans base de données, réduire le nombre de fois qu'un utilisateur a besoin d'accéder
à la mémoire où les données sont enregistrées.
• Un B-arbre est un index basées sur l’ordre des données. c’est un arbre équilibré
• chaque nœud est un index local il se réorganise dynamiquement
• Utilisé universellement !
• Si l’index est trop gros ? On l’indexe à son tour.
• Essentiel : l’index est trié, donc on peut l’indexer par un second niveau
• non-dense
• Donc dès le second niveau on diminue drastiquement la taille. On peut continuer
jusqu’à un niveau avec une seule page.
• On obtient une structure séquentielle indexée
B-ARBRE
• Un B-arbre d’ordre d (nombre de descendants directs d’un nœud interne) et de profondeur p est défini
comme une arborescence ayant les propriétés suivantes :

Chaque nœud a au plus d fils, c’est-à-dire d pointeurs.

Chaque nœud excepté la racine et les feuilles a au moins [d/2] fils.

La racine a au moins 2 fils.

Toutes les feuilles apparaissent au même niveau : (profondeur p),

Un nœud ayant k fils (k<= d) c’est-à-dire k pointeurs, contient k-1 clés. (une arbre d’ordre 3 a au max 2
clés)
Les données (tuples) sont rangées dans les feuilles ou nœuds terminaux.
Les nœuds non terminaux ne contiennent que des clés et des pointeurs vers d’autres nœuds de
l’arborescence.
 NŒUD D’UN B-ARBRE
Un nœud est un index local, les enregistrements servant de clé, intercalés avec des pointeurs.

C1 R1 C2 R2 ... Cn Rn

P1 P2 Pn Pn+1

Le sous-arbre pointé par P2 contient tous les

enregistrements dont la clé est comprise
entre C1 et C2.
B-ARBRE
Algorithme de recherche

Soit la recherche d’un tuple de clé c

1. Lire la racine et rechercher quelle valeur de clé recouvre la valeur c.

2. Lire la valeur de pointeur associé.

3. Aller à la page pointée par le pointeur sélectionné.

4. Rechercher quelle valeur de clé recouvre c, lire la valeur de pointeur associé et

aller à la page pointée.

5. Répéter l’opération précédente jusqu’à trouver la page feuille contenant la

clé.
B-ARBRE (EXEMPLE)
B-ARBRE
Un arbre, avec trois niveaux, une racine, les enregistrements répartis dans les
nœuds.
On veut insérer Casablanca.
On veut insérer Smoke
B-ARBRE: INCONVENIENT

• Le B-arbre est plaçant: stocke directement les données dans les

noeuds
• les enregistrements sont stockés directement dans les nœuds des
feuilles, et les valeurs de clé déterminent l'ordre physique des
enregistrements.

• Les enregistrements sont déplacés pendant la construction (pb

d’adressage)
L’ARBRE B+

• est une variante non plaçante, Construit uniquement sur les

clés
• les nœuds ne contiennent que des pointeurs vers les
enregistrements réels, qui sont stockés séparément.
• Cela permet de maintenir l'ordre des clés sans être contraint
par la structure physique des données
• Toutes les clés sont conservées dans les feuilles
• Dans les feuilles, à chaque clé est associée l’adresse de l’enregistrement
 EXEMPLE: FICHIER DE 120 MO

.
Taille d’une
une entrée = 28 octets. Donc ⌊ 4096 ⌋ = 146 entrées par bloc
28 bloc 4K

⌈ 1000000 ⌉ = 6850 blocs pour le premier niveau de l’arbre-B+.

146

⌊ 6850 ⌋ = 47 blocs pour le second niveau

146
un bloc avec 47 entrées pour le troisième niveau.
RECHERCHE PAR CLÉ

• SELECT * FROM Film WHERE titre = ’Impitoyable’

• on lit la racine de l’arbre : Impitoyable étant situé dans l’ordre
lexicographique entre Easy Rider et Manhattan, on doit suivre le
chaînage situé entre ces deux titres ;
• on lit le bloc feuille dans lequel on trouve le titre Impitoyable associé à
l’adresse de l’enregistrement dans le fichier des données ;
• il reste à lire l’enregistrement.
RECHERCHE PAR INTERVALLE

• SELECT * FROM Film WHERE annee BETWEEN 1960 AND 1975

• On fait une recherche par clé pour l’année 60
• on parcourt les feuilles de l’arbre en suivant le chaînage, jusqu’à l’année 1975
• à chaque fois ont lit l’enregistrement
• Attention, les accès aux fichiers peuvent coûter très cher.
CAPACITÉ ET EFFICACITÉ DE L’ARBRE B+

• avec un niveau d’index (la racine seulement) on peut donc référencer 146 films ;
• avec deux niveaux on indexe 146 blocs de 146 films chacun, soit 1462 = 21316
films ;
• avec trois niveaux on indexe 1463 = 3112136 films ;
• enfin avec quatre niveaux on index plus de 450 millions de films.
• L’efficacité d’un arbre-B+ dépend de la taille de la clé : plus elle est petite, plus
l’index sera petit et efficace.
• On a très rarement besoin de plus de trois niveaux
• Le coût d’une recherche par clé est le nombre de niveaux, plus 1.
• L’arbre B+ supporte les recherches par clé, par intervalle, par préfixe,
• Seulement il occupe de la place….
COMPARAISON ARBRE B+ ET HACHAGE

• Le hachage est un concurrent de l’arbre-B+

• Il est Meilleur pour les recherches par clé
• N’occupe aucune place
• Mais
• se réorganise difficilement
• ne supporte pas les recherches par intervalle
 APPLICATION DU HACHAGE
On veut créer une structure de hachage
pour nos 16 films (hyp. : 4 enregistrements
par page)
on alloue 5 pages (pour garder une
marge de manœuvre) un répertoire à 5
entrées (0 à 4) pointe vers les pages
On définit la fonction
h(titre) = rang(titre[0]) mod 5
 RECHERCHE ET MAJ

Recherche:
Avec la hachage on peut faire des recherche par clé mais pas des recherche par
intervalles,

MAJ:

La structure simple décrite précédemment n’est pas dynamique

On ne peut pas changer un enregistrement de place
Donc il faut créer un chaînage de pages quand une page déborde Et donc les
performances se dégradent...
COMPARAISON (SUITE)

• La hachage, intéressant quand :

• Le jeux de données est figé
• Les recherches se font par clé
• Ce sont des situations relativement courantes : le hachage n’occupe alors
pas de place.

• Sinon l’arbre-B est meilleur.

LES CHOIX D’ORACLE

• Oracle propose à peu près toutes les structures d’index vues précédemment.
• Par défaut l’index est un arbre B+
• Il est possible d’organiser une table en arbre B (plaçant) Le hachage
(non dynamique) existe aussi

• Les index bitmap Les arbres R

L’ARBRE B+

• Dès qu’on utilise une commande PRIMARY KEY, Oracle crée un

arbre B+ sur la clé primaire
• ◮ l’arbre est stocké dans un segment d’index

•On peut organiser la table en arbre B avec l’option

ORGANIZATION INDEX
• ◮ plus efficace car évite les accès par adresse
• ◮ moins valable pour les enregistrements de grande taille
HACHAGE

• Structure appelée Hash Cluster. Utilisée en deux étapes:

• On crée la structure avec tous ses paramètres
• On affecte une ou plusieurs tables à la structure

le hachage dans Oracle n’est pas dynamique

CRÉATION D’UN HASH CLUSTER

• CREATECLUSTER HachFilms (id INT) SIZE 500

HASHKEYS 500;
• La clé de hachage est de type INTEGER ;
• Oracle fournit automatiquement une fonction avec de bonnes propriétés
• Nombre de valeurs de la fonction donné par HASHKEYS
• Taille de chaque entrée estimée par SIZE
• Donc ici 8 entrées par bloc