Chapitre 07 - Structure des fichiers et du système 07 - Structure des... · GPA775 Chapitre 7 - Structure des fichiers et du système 3 Introduction Nous savons que… ØLes performances

Chapitre 7

Structure des fichiers et du système

GPA775 Chapitre 7 - Structure des fichiers et du système

2

Introduction

Au cours des chapitres précédents, nous nous sommes intéressés au niveau logique des données. Nous avons vu des collections:Øde tableaux (modèle relationnel), Ød'enregistrements et d'ensembles (modèle réseau),Ød'arborescences (modèle hiérarchique).

Pour l’utilisateur: ØC'est au niveau logique qu’il s’approprie les données

pour lui permettre des manipulations aisées. ØLes détails relatifs à la structure physique des

données ne l'intéressent pas.


3

Introduction

Nous savons que…ØLes performances d'une BD dépendent

étroitement de son organisation.ØLe temps de réponse doit rester compatible

avec la patience de l'utilisateur. Ainsi…ØLes structures de données qui composent la

BD et son système de gestion doivent être soigneusement étudiés pour optimiser les performances.


4

Introduction

Comme toujours, en informatique, on doit se contraindre au compromis habituel entre :

espace mémoire et rapidité d'exécution

…et faire des choix entre les programmes d'exploitation sur le critère de leur efficacité opérationnelle.


5

Introduction

Maintenant, qu’allons-nous faire?ØÉtudier l'implantation physique des différents

modèles et langages. ØDécouvrir des structures de données qui autorisent

un accès rapide aux données et adaptées aux types d'opérations que l'on désire effectuer sur les données.

Les choix définitifs de ces structures reposent sur :

w l'exploitation prévue du SGBD w la machine sur laquelle elles sont implantées.


6

Contenu

Dans ce chapitre, nous étudierons les points suivants :

ØStructure du système

ØSupport physique des données

ØOrganisation des fichiers

ØGestion de la mémoire tampon (disque)

ØRépartition des bases relationnelles en fichiers

ØRépartition des bases réseaux en fichiers

ØRépartition des bases hiérarchiques en fichiers


7

Structure du systèmeGestionnaire de requête: traduit

les requêtes de l'utilisateur en langage de bas niveau

Optimiseur: tente de formuler la requête de l'utilisateur de façon

optimale

Gestionnaire d’accès et d’intégrité: conserve

l'intégrité des données et gère les habilitations des utilisateurs, Module de

récupération: assure que la BD conserve sa cohérence même à la suite d'un crash

système

fichier système:conserve les

données relatives àla structure de la

base(autorisations d'accès,

dictionnaire des données).

gère les allocations d'espaces disque et

les structures de données.

supervise les échanges entre les

disques et la mémoire centrale

Fichiers de données

Contrôleur multitâche: traite les conflits entre les traitements simultanés de

plusieurs utilisateurs

Assurent la rapidité d’accès aux donnéesFichiers statistiques


8

Support physique des données

Plusieurs types de stockage sont utilisés par les SGBD. Classés par :Øordre de rapidité d'accès;

Øcoût de stockage des informations;Ø fiabilité.

Le type de mémoire que l'on rencontre sur les machines sont les suivantes:ØMémoire cache ;

ØMémoire principale;ØMémoire à accès direct;ØMémoires à accès séquentiel (bandes magnétiques).


9

Les mémoires

ØMémoire cache :• très rapide et de petite taille, elle est ignorée par le

SGBD ØMémoire principale :

• utilisée en permanence par la machine;• ne peut contenir la totalité de la BD;• perdue en cas de crash .

ØMémoires à accès séquentiel (bandes magnétiques).• utilisées principalement pour les archivages et les

sauvegardes;• accès très lent car il est séquentiel;• très fiables.


10

Les mémoires

ØMémoire à accès direct :• support utilisé pour le stockage des BD;• des fractions de la base sont lues en mémoire

principale pour le traitement puis réécrites sur disque;

• les données peuvent être lues dans un ordre quelconque;

• elle résiste aux pannes de système (sauf au "crash disk");

• elle nécessite d'archiver régulièrement sur bandes magnétiques. (« backup » )


11

Mémoire à accès direct

Une unité de disques-packs contient un empilement de disques entraînés par le même axe, et gérés chacun par un bras de lecture particulier.

Axe de rotation

PisteBras de lecture

Mécanisme de lecture (Servo-Mécanisme) : Actionne les

bras de lecture

Cylindre (ensemble des

pistes)

Têtes de lecture et

écriture (2 par bras)


12

Mémoire à accès direct

Temps d’accès à l’information:Un cylindre contient des données auxquelles on peut accéder sous un délai maximum du temps de latence. Le délai du temps de latence est très court parce que la vitesse de rotation du disque est élevée.

Par contre, le temps mis par le bras de pour se positionner est beaucoup plus grand, on l'appelle le temps de recherche.

Nous avons donc:

temps de recherche

temps d'accès maximum = +

temps de latence

REMARQUE: Il est intéressant de stocker les informations fortement liées sur la même piste du cylindre pour réduire le temps d'accès.


13

Organisation des fichiers

Sur les disques, les données sont réparties dans des fichiers.Un fichier est une suite d'enregistrements (ou de données)…Ø organisés de façon logiqueØ et découpés en blocs.

Même si la dimension des blocs dépend:Ø des caractéristiques de l'unité de disque Ø et du système d'exploitation,

… la taille des enregistrements varie elle aussi.

Il existe 2 modes de découpage des données en enregistrements:1. enregistrements de longueur fixe;2. enregistrements de longueur variable.


14

Enregistrements de longueur fixe

Exemple: Soit des enregistrements de la base de données bancaire:struct Dépôt {

char agence[20];int n° compte;char client [20];float solde;

};struct Client {

char client[20];char rue[20];char localité[20];

};

Ø un caractère occupe 1 octet (8 bits),Ø un entier occupe 4 octets, Ø un réel en consomme 8.

Un total de 52 octets par enregistrement

Dépôt

Un total de 60 octets par enregistrement

Client


15


Fichier garni avec les enregistrements de Dépôt :Agence NoCompte Client Solde

enregistrement 0 Perryridge 102 Hayes 400enregistrement 1 Round Hill 305 Turner 350enregistrement 2 Mianus 251 Smith 700enregistrement 3 Downtown 101 Johnson 500enregistrement 4 Redwood 222 Lindsay 700enregistrement 5 Perryridge 201 Williams 900enregistrement 6 Brighton 217 Green 750enregistrement 7 Downtown 110 Peterson 600enregistrement 8 Perryridge 218 Lyle 700

20 octets 4 octets 20 octets 8 octets


16


Cette structure semble très simple puisque tous les enregistrements de la relation Dépôt et Client auront la même longueur. Problèmes:

Ø l’effacement d'un enregistrement est difficile: il y a le problème de remplacement de l'information avec des enregistrements de longueurs différentes. (ex: Client (60 octets) != Dépôt (52 octets));

Øun enregistrement peut être à cheval entre deux blocs;

ex: si un bloc comporte 512 octets,

Pour la relation Dépôt qui comporte 52 octets * 10 enregistrements = 520 octets, le dixième enregistrementsera donc à cheval sur deux blocs.


17


Solution 1: Décaler d'un rang tous les enregistrements lors d’un effacement.

Ønécessite de remuer beaucoup d'enregistrements.

enregistrement 0 Perryridge 102 Hayes 400enregistrement 1 Round Hill 305 Turner 350enregistrement 3 Downtown 101 Johnson 500enregistrement 4 Redwood 222 Lindsay 700enregistrement 5 Perryridge 201 Williams 900enregistrement 6 Brighton 217 Green 750enregistrement 7 Downtown 110 Peterson 600enregistrement 8 Perryridge 218 Lyle 700

Effacement de l’enregistrement 2


18


Solution 2: Remplacer l'enregistrement effacé avec le dernier enregistrement

enregistrement 0 Perryridge 102 Hayes 400enregistrement 1 Round Hill 305 Turner 350enregistrement 8 Perryridge 218 Lyle 700enregistrement 3 Downtown 101 Johnson 500enregistrement 4 Redwood 222 Lindsay 700enregistrement 5 Perryridge 201 Williams 900enregistrement 6 Brighton 217 Green 750enregistrement 7 Downtown 110 Peterson 600

Remplacement de

l’enregistrement 2 par 8


19


Comparaison des solutions:La dernière solution est meilleure que la première, mais n'est pas très souhaitable, car les insertions sont généralement plus fréquentes que les suppressions.

Ø Il serait préférable de laisser l'emplacement vide disponible pour une insertion ultérieure.

MAIS… comment se souvenir des emplacements disponibles???

Nouvelle solution:

Une structure avec en-tête de fichier et pointeurs aux enregistrements effacés.


20

Fichier avec en-tête et pointeurs

À l'insertion, il faut copier l'adresse du 2e vide (enregistrement 4) dans l'en-tête et l'enregistrement à insérer prend la place du premier vide.

Ce mécanisme demande une programmation soignée !Avantages : Insertion ou suppression très facile.

Ø les dimensions des espaces sont connues à l'avance (longueur fixe).

En-tête enregistrement 0 Perryridge 102 Hayes 400 enregistrement 1 enregistrement 2 Mianus 251 Smith 700 enregistrement 3 Downtown 101 Johnson 500 enregistrement 4 enregistrement 5 Perryridge 201 Williams 900 enregistrement 6 enregistrement 7 Downtown 110 Peterson 600 enregistrement 8 Perryridge 218 Lyle 700

En-tête de fichierPointeurs


21

Enregistrements de longueur variable

Ces types d’enregistrements sont très fréquents.Types:

♦ des enregistrements à champs variables,♦ des enregistrements à champs répétitifs.

Comment doit-on les traiter?Ex: Soit des enregistrements d’une BD bancaire. Une agence peut superviser plusieurs clients.

struct Dépôt {char agence [20];struct info-compte {

int n°compte;char client [20];float solde;struct info-compte *suivant;

};};

info-compte est un tableau dont le nombre d‘enregistrements est

arbitraire. Longueur

fixeLongueurvariable


22


Ex: Enregistrement de longueur variable au moyen de chaîne d’enregistrements de longueur fixe.

• La longueur d'un enregistrement Dépôt n’est limité que par un indicateur de fin d'enregistrement (⊥).

Inconvénients :

Ø difficulté de réutilisation des espaces effacés; (ex: effacer le client Williams)

• multiplication des fragments d'espaces disques éparpillés;

Ø augmentation difficile de la taille des enregistrements: il fautalors déplacer tout l'enregistrement.

0 P e r r y r i d g e 1 0 2 H a y e s 4 0 0 2 0 1 W i l l i a m s 9 0 0 2 1 8 L y l e 7 0 0 ⊥ 1 R o u n d H i l l 3 0 5 T u r n e r 3 5 0 ⊥ 2 M i a n u s 2 5 1 S m i t h 7 0 0 ⊥ 3 D o w n t o w n 1 0 1 J o h n s o n 5 0 0 1 1 0 P e t e r s o n 6 0 0 ⊥ 4 R e d w o o d 2 2 2 L i n d s a y 7 0 0 ⊥ 6 B r i g h t o n 2 1 7 G r e e n 7 5 0 ⊥


23


Deux façons de traiter les enregistrements de longueur variable:

1. Par espaces réservés:1. On détermine la longueur maximale de l’enregistrement à

longueur variable.

2. À sa création, l’enregistrement est créé à sa longueur maximale.

3. Les espaces non utilisés sont remplis de symboles spéciaux.

2. Par pointeurs : 1. Dans le fichier, on ajoute un nouveau champ contenant des

pointeurs aux enregistrements.

2. À sa création, l'enregistrement de longueur variable est représenté par une liste enregistrements de longueur fixe.

3. Les enregistrements appartenant à une même agence sont chaînés.


24


Exemple de fichier organisé suivant la méthode des espaces réservés.

Désavantage :

Utile lorsque tous les enregistrements sont environ de la même longueur (ex: toutes les agences ont approximativement le même nombre de client),

… sinon gaspillage de l'espace disque.

0 Perryridge 102 Hayes 400 201 Williams 900 218 Lyle 7001 Round Hill 305 Turner 350 ⊥ ⊥ ⊥ ⊥ ⊥ ⊥2 Mianus 251 Smith 700 ⊥ ⊥ ⊥ ⊥ ⊥ ⊥3 Downtown 101 Johnso

n500 110 Peterso

n600 ⊥ ⊥ ⊥

4 Redwood 222 Lindsay 700 ⊥ ⊥ ⊥ ⊥ ⊥ ⊥5 Brighton 217 Green 750 ⊥ ⊥ ⊥ ⊥ ⊥ ⊥


25


Exemple de fichier organisé au moyen de pointeurs

Désavantage :

Øperte d'emplacement mémoire dans tous les enregistrements, sauf les premiers de la chaîne.

0 Perryridge 102 Hayes 400 1 Round Hill 305 Turner 350 2 Mianus 251 Smith 700 3 Downtown 101 Johnson 500 4 Redwood 222 Lindsay 700 5 ---------------- 201 Williams 900 6 Brighton 217 Green 750 7 ----------------- 110 Peterson 600 8 ----------------- 218 Lyle 700


26


Nouvelle solution: Répartition en blocs

Øbloc d'accrochage: contient les premiers enregistrements des chaînes,

Øblocs de débordement: contient les autres enregistrements.

Øtous les enregistrements d'un bloc auront la même longueur bien que ces enregistrements soient de longueur variable.

ØCette structure est la plus intéressante et la plus utilisée.


27

Organisation des enregistrements par blocs

La lecture et l’écriture des fichiers de données sont effectuées par groupes de blocs de longueur fixe. Les échanges se font entre l'unité centrale et le disque.La dimension d’un bloc varie de 512 octets à plusieurs milliers d'octets;Plusieurs approches permettent d'optimiser la vitesse de transfert entre le disque et la mémoire centrale:ØMéthode simple : inscrire les données sur le disque

dans l'ordre même où elles seront appelées lors de leur exploitation… mais c'est presque impossible à réaliser;ØApproche par l'optimisation des temps d'accès:

découpage approprié des données en blocs.


28


Problème:

ØLes accès disque sont le point d'embouteillagepermanent de l'exploitation des BD.

Solution:

Ø Il faut organiser les accès disque de sorte que la lecture d'un bloc soit optimale en appliquant les deux techniques suivantes:

• Grouper les enregistrements fortement liés.

• Grouper les blocs fortement liés.


29


1. Un bloc devrait réunir les enregistrements fortement liés.

Ø Utilisation des structures à groupage de blocs.Bloc 0 Perryridge

102 Hayes 400201 Williams 900218 Lyle 700

Bloc 1 Round Hill305 Turner 350

Bloc 2 Mianus251 Smith 700

Bloc 3 Downtown101 Johnson 500110 Peterson 600

Bloc 4 Redwood222 Lindsay 700

Bloc 5 Brighton217 Green 750

Les données sont groupées

par agence.


30


2. Lors d’un débordement d'un bloc, il faut essayer de grouper les blocs qui ont un rapport entre eux par pistes et par cylindres:

.

.

.

Perryridge

.

.

.

.

.

.

Round Hill

.

.

.

.

.

.

.

.

.

Mianus

Bloc 0

Bloc 1

Bloc 2

Bloc 3

Bloc 4

Bloc 5

Utilisation de pointeurs


31

Gestion de la mémoire tampon

Nous avons vu comment…

Øoptimiser l'espace occupé sur le disque.

Ø réduire les échanges entre la mémoire tampon et l’unitédisque.

Pour optimiser le temps d'accès, il faut placer en mémoire centrale le maximum de blocs:Ø il est cependant impossible de stocker la BD complète;Ø il faut donc organiser les stockages de façon rationnelle,

en fonction des applications (des requêtes)!


32


Fonction du gestionnaire de mémoire tampon:

Øgère un espace mémoire réservé pour les données de la BD,

Ø intercepte toutes les requêtes du systèmes relatives aux blocs de la base de données,

• si le bloc désiré est déjà en mémoire, le gestionnaire fournit son adresse;

• si le bloc n'est pas en mémoire, le gestionnaire :1. émet un appel au disque;2. stocke le bloc;3. fournit son adresse.


33


Il existe diverses méthodes pour optimiser la tâche du gestionnaire de mémoire tampon, nous en verrons trois.

Méthodes de gestion

1. Stratégie de remise en place des blocs;

2. Clouage des blocs (pinned blocks);

3. Expulsion des blocs sur disque.


34

Stratégie de remise en place des blocs

Objectif : Minimiser les accès disque

Lorsque la mémoire tampon est saturée, il faut retirer un bloc avant d'en lire un nouveau (pour créer de l’espace).

Problème :

Il est souvent impossible de prédire quels blocs ont avantages à être retournés sur disque.

Solution :

Les systèmes d'exploitation font appel à l'historique des blocs appelés. Il existe 2 méthodes:

• méthode LRU

• méthode MRU


35


méthode LRU (least recently used)ØHypothèse : un bloc récemment appelé a plus de

chance d'être bientôt rappelé.• le bloc remis en place sera « le moins récemment utilisé » .

Note : ce mode est utilisé par les systèmes d'exploitation.

méthode MRU (most recently used)ØHypothèse : le bloc le "plus récemment utilisé" a le

moins de chance d'être bientôt rappelé.• Ce bloc sera remis en place.


36

Exemple d'utilisation des stratégies LRU et MRU

Crédit lXl ClientèleCette équijonction est définie par le pseudo-code suivant:

for each tuple b de Crédit dofor each tuple c de Clientèle do

if b[client] = c[client]then begin

soit t un tuple tampon défini comme suit :t[agence] : = b[agence]t[prêt] : = b[prêt]t[client] : = b[client]t[montant] : = b[montant]t[rue] : = c[rue]t[localité] : = c[localité]inclure t dans le résultat de Crédit |X| Clientèle

end end

end

Lorsqu'un tuple b de Crédit a été traité, il n’est plus utile. Une fois qu'un bloc entier de tuples de la relation Crédit a été passé, on peut l'éliminer de la mémoire centrale.

stratégie à employer : MRU

Par contre, les tuples c reviennent pour tous les tuples b de Crédit. Ici aussi la stratégie MRU est plus efficace, ainsi le bloc le plus récemment utilisé sera retourné immédiatement sur le disque.


37


Le gestionnaire de la mémoire tampon peut "anticiper" la méthode de gestion à utiliser en fonction de la connaissance de certains facteurs :

Øconnaissance de la requête en cours (le système sait quels blocs il lui faudra conserver);

Ødictionnaire de données est la partie la plus souvent consultée, le gestionnaire devrait s'abstenir d'éliminer les blocs appartenant au dictionnaire;

Ø fichiers index sont aussi des fichiers très souvent utilisés à ne pas éliminer.


38


Méthode 2: Clouage des blocs (pinned blocks)Pour pouvoir récupérer le SGBD en cas de panne (chapitre 11), le nombre de ré-écritures d'un bloc sur disque est limité. Un bloc ainsi empêché est dit clouer. Cette fonctionnalité est essentielle dans tous SGBD résistant aux crashs.

Méthode 3: Expulsion des blocs sur disqueOn rencontre des situations où il faut renvoyer un bloc sur le disque même si le système n'a aucun besoin d'espace pour la mémoire tampon. Il s'agit d'une expulsion (chapitre 11). Cette expulsion est quelques fois requise pour protéger les données contre les pannes système.

Øe.i. Ré-écriture d’un bloc qui est depuis trop longtemps en mémoire.


39

Répartition des BD relationnelles en fichiers

Les tuples sont généralement représentés par des enregistrements de longueur fixe (normalisation 1NF: pas de groupes répétitifs dans un attribut de la relation).Les ordinateurs personnels et les gros ordinateurs (serveur) ne stockent pas leurs fichiers de la même façon.Sur ordinateurs personnels :Ø Les SGBD relationnelles stockent leurs relations sur des fichiers

disjoints; • les données liées ne sont pas stockées ensemble.

Note : Le fait que les appels au système d'exploitation pour la gestion de l'emplacement mémoire éparpillent les blocs occasionne des temps de recherche très longs lors de requêtes.

De plus, ces systèmes utilisent la stratégie LRU. Pourtant, nous avons vu que l'opération d'équijonction, qui représente le coeur du modèle relationnel, est beaucoup plus efficace avec une stratégie MRU!


40

Répartition des BD relationnelles en fichiers

Sur les gros ordinateurs :ØLes relations sont souvent stockées dans un seul

fichier;ØC'est le SGBD qui gère l'information sans s'appuyer

sur le système d'exploitation;Ø Il y a possibilité de définition de structures en grappe.

• Cette structure permet d'associer les données liées par contiguïté de manière à accéder à la plupart des enregistrements utilisés par une requête en une seule lecture de bloc.

Remarque: Attention, cette structure peut:

w optimiser le traitement de certaines requêtes;w mais peut ralentir fortement d'autres requêtes.


41

Exemple de structure en grappe

Ex: On désire réaliser la requête SQL suivante :Select compte, client, rue, localitéFrom Dépôt, ClientèleWhere Dépôt.client = Clientèle.client

La relation Dépôt La relation Clientèle

agence compte client position

Perryridge 102 Hayes 400

Mianus 220 Hayes 600

Round Hill 503 Hayes 700

Round Hill 305 Turner 350

client rue localité

Hayes Main Harrison

Turner Putman Stamford


42


Ici, la structure en grappe optimise le traitement de l'équijonction (Dépôt |X| Clientèle) puisque les comptes d'un client sont près de leur information.

Cependant, les requêtes suivantes sont fortement ralentit par cette structure:

Select * Select *From Clientèle From Dépôt

Hayes Main Harrison







43


Pour régler ce problème, on peut chaîner tous les tuples de la relation Clientèle et tous les tuples de la relation Dépôt.

Ø Il est donc très important de connaître au préalable le genre de requêtes qui seront le plus souvent effectuées sur la BD.

Hayes Main Harrison







44

Répartition de BD réseaux en fichiers

Rappel: Le modèle réseau est composée d'enregistrementsunis par des liens. Il faudra donc créer des fichiers qui tiennent compte de la représentation des enregistrements et de celle des liens.

Beck San FranciscoMaple 66200

Katz San JoseNorth100 000256

Doner Palo AltoSidehill

667347

10 533301


45


Pour l’implantation physique, on utilise des champs pointeurs accolés aux champs enregistrements; il y aura autant de champs pointeurs par enregistrement que de liens qui leur sont attribués.

Beck Maple San Francisco 200 55

Katz North San Jose 256 100000

347 667

Doner Sidehill Palo Alto 200 55

Beck San FranciscoMaple 66200

Katz San JoseNorth100 000256

Doner Palo AltoSidehill

667347

10 533301

nécessite des enregistrements de longueur variable.


46


Il n’est pas possible de limiter le nombre de pointeurs d’un enregistrement avec le modèle de base qui permet les relations n vers n.Ainsi, même si la longueur d’un enregistrement est fixe, son implantation physique sera de longueur variable.Ces complications ont conduit les auteurs du modèle DBTG àrestreindre les liens entre les enregistrements aux types 1 vers 1 ou 1 vers n:

Øpermet la réduction du nombre de pointeurs;

Øpermet d'utiliser des enregistrements de longueur fixe.


47

Modèle DBTG et la structure en anneau

Exemple :Supposons que le lien CliCom soit du type 1 vers n et qu’il est représenté par l'ensemble DBTG CliCom comme suit :

set name is CliComowner is Clientèlemember is Compte

Clientèle CompteCliCom


48


L‘utilisation d’une structure en anneau permet de représenter les relations 1 vers n.

Base de données pour l’ensemble DBTG CliCom

Structure en anneau de l’ensemble DBTG CliCom

Lowman

Downridge

Square Dallas

Camp Garland

Kahn Bayside Plano

305 500

226 336

177 205

155 62

Lowman

Downridge

Square Dallas

Camp Garland

Kahn Bayside Plano

305 500

226 336

177 205

155 62

Notez que les enregistrements

sont tous de longueur fixe.

Cette structure cyclique permet de minimiser le nombre de pointeurs.


49


La structure en anneau a orienté la stratégie d'extraction des données:

Rappel des instructions définies au chapitre 5:

find first “type enregistrement” within “type d'ensemble”

et

find next “type enregistrement” within “ type d'ensemble”

Une fois le possesseur trouvé, il est facile d'opérer un find first et un find next puisque le système n'a qu'à suivre un pointeur.


50


La forme cyclique du modèle DBTG peut être améliorée de façon à créer l'instruction find owner. Elle permet de retourner au possesseur à l'aide d'un second pointeur ajoutéà chaque enregistrement.

Lowman

Downridge

Square Dallas

Camp Garland

Kahn Bayside Plano

305 500

226 336

177 205

155 62


51


Contraintes d'écriture contiguëComme les instructions find first et find next sont très fréquemment utilisées lors de requêtes, il est avisé de stocker les enregistrements de façon quasi contiguë:

Ø il est possible de le faire avec la clause : Placement

Lors de la définition du type d’enregistrement Compte, on ajoute:

Placement clustered via CliComLe système stocke alors les membres d'un ensemble sur un même bloc (Voir figure de la page suivante).


52


Mise en place d’enregistrement en grappe


53


Il est aussi possible de stocker ensemble les enregistrements de type "parent" et "enfant" tout en conservant les enregistrements d'ensembles DBTG de façon contiguë par la clause: near owner

Placement clustered via CliCom near owner


54

Répartition des BD hiérarchiques en fichiers

Rappel: Une BD hiérarchiques se compose d'un ensemble de diagrammes arborescents. Pour respecter l’arborescence, l’implantation physique consiste à associer un pointeur à un enregistrement donnépour chaque enfant.

SquareLowman Dallas

305 500

DownridgeCamp Garland BaysideKahn Plano

226 336 177 205 155 62


55


Cette structure parent-enfant, ne constitue pas une structure idéale du fait qu'un parent peut avoir un nombre arbitraire d'enfants, donc un nombre arbitraire de pointeurs par parents (enregistrements de longueur variable).

SquareLowman Dallas

305 500

DownridgeCamp Garland BaysideKahn Plano

226 336 177 205 155 62


56


Au lieu d'utiliser des pointeurs parent-enfant, on peut faire appel à des pointeurs enfant le plus à gauche et frère immédiat.

Cette structure permet des enregistrements de longueur fixeavec 2 pointeurs. Remarque : Plusieurs champs pointeurs restent inutilisés. En général, le dernier enfant d'un parent n'a pas de frère.


57


Ainsi, il est avisé d'y placer des pointeurs pour faciliter la recherche en pré-ordre.

Cette façon de faire permet d'exécuter de façon optimale les instructions get first, get next et get next within parent au moyen d'un accès minimum d'accès bloc.

Documents

Chapitre 07 - Structure des fichiers et du système 07 - Structure des... · GPA775 Chapitre 7 - Structure des fichiers et du système 3 Introduction Nous savons que… ØLes performances