ORGANISATION DES

FICHIERS

STRUCTURES SIMPLES
Présenté par Pr.Nabil KESKES.

Année 2022-2023.
1
 PLAN
Introduction.
Rappel.
Modèle de fichiers.
Caractéristiques.
Méthode d'accès.
Organisation Globale des blocs
Organisation interne de blocs
Taxonomie des structures simple de fichiers
Conclusion.

2
Objectifs du Chapitre

 Distinguer les différentes types d’organisation.

 Identifier les caractéristiques de mise en œuvre de chaque type d’ organisation, ses limites et ses

avantages.

3
Introduction

On désigne par organisation ,la manière dont son organisés physiquement les enregistrement du fichier sur

le support. Elle permet d’attribuer un emplacement sur le support physique pour tout enregistrement

logique du fichier.

4
Rappel
Un fichier est le concept à travers lequel, un programme ou une application stocke des données en MS. Les
fichiers sont utilisés à différents niveaux d'abstraction avec des sémantiques différentes:

Niveau application Niveau Système

5
Niveau application (ou langage de programmation de haut niveau),

Figure1: Fichiers au niveau applicatif 6

 Remarque

fichiers typés est un ensemble d'enregistrements (ou articles) persistants. l'accès aux enregistrements se
fait via des opérations spéciale pour les fichiers (ex en Pascal : read(f,e), write(f,e), reset(f), …).

On peut aussi définir un fichier comme étant une suite d'octets, on parle alors de flux (ex en C : FILE * ).
C'est des fichiers « non typés ». Ces flux (streams) généralisent la notion d'E/S pour être indépendante du
type de périphérique utilisé (disques, imprimantes, écrans, clavier, réseaux, …).

7
Niveau Système (niveau physique),

Figure1: Fichiers au niveau Système 8

Remarque
Toutes les opérations du niveau 'application' (niveau logique) passent par le système qui les traduit en
opérations de bas niveau pour accéder physiquement aux blocs d'E/S. Comme les opérations d'E/S sont
coûteuses (en temps), le système maintient en MC une zone spéciale de taille limitée (la zone tampon ou
"buffer cache") lui permettant de garder en MC les copies de quelques blocs physiques choisis selon
certaines stratégies (par exemple les plus utilisés). Cette zone tampon est totalement transparentes aux
programmes d'application qui utilisent les fichiers.

9
Exemple
une application demande la lecture d'un enregistrement donné, le système vérifie d'abord si le bloc
concerné ne se trouve pas déjà en MC (dans la zone tampon). S'il y est, l'enregistrement cherché sera
directement transmis à l'application, sans qu'il y ait de lecture physique.

10
Modelisation des fichiers
on modélise la MS par une zone contiguë de blocs numérotés séquentiellement (ces numéros
représentent les adresses de blocs).Les blocs sont des zones contiguës d'octets de même taille,
renfermant, entre autre, les données (enregistrements) des fichiers.

11
Figure3 : modèle de fichiers
Modelisation des fichiers
Pour écrire des algorithmes sur les structures de fichiers on utilisera la machine abstraite définie par
le modèle suivant:

{ouvrir, fermer, lireDir, ecrireDir, lireSeq, ecrireSeq, aff_entete, entete, allocbloc }

Dans ce modèle, on manipule des numéros de blocs relatifs au début de chaque ficher (adresses logiques).
L'utilisation des adresses physiques n'est pas d'une utilité particulière à ce niveau. Un fichier est donc un
ensemble de blocs numérotés logiquement (1, 2, 3, ... n)

12
Caractéristiques et bloc d'en-tête

Pour que le système puisse gérer un fichier, il a besoin de connaître les informations sur ses

caractéristiques : les blocs utilisés par le fichier, l'organisation du fichier, les droit d'accès associés, ...

13
Exemple 1

pour un certain type de système de fichier , le bloc 0 pourrait être réservé pour contenir une table

où chaque ligne renseigne sur les caractéristiques d'un fichier (nom, taille, blocs utilisés, ...). Quand

une application désire ouvrir un fichier de nom donné, le système récupère ses informations à partir

de cette table.

14
Exemple 2

Dans les MS séquentielles de type bandes magnétiques, ce type d'information (les caractéristiques)

se trouvait au début de chaque fichier (d'où le nom de "bloc d'en-tête").

15
Méthode d'accès

Une structure de fichier consiste à définir une organisation des blocs d'un fichier sur MS afin
d'implémenter certaines opérations d'accès pour la manipulation des données du fichier.

Une structure de fichier (méthode d'accès) consiste à définir :

- une manière d'organiser les blocs d'un fichier sur MS
- le placement des enregistrements à l'intérieur des blocs
- l'implémentation des opérations d'accès (recherche, insertion, suppression, ...).
Le but des structures de fichiers est d'optimiser les performances d'accès (temps d'exécution et
occupation mémoire).
16
Organisation globale des blocs
Dans un premier temps, on étudiera deux possibilités distinctes d'organiser les blocs au sein d'un fichier:

Fichier vu comme un tableau Fichier vu comme une liste

Organisation chainée
Organisation contigüe

17
Exemple
Dans la figure ci-dessous, on a deux fichiers vus comme tableau (E et F) et un fichier vu comme une
liste (G). Les blocs F1, F2, … F7 sont contigus, de même pour les blocs E1, E2, E3 et E4. Par contre
les blocs G1, G2, … G6 ne sont pas contigus, ils sont chaînés entre eux formant une liste de blocs.

Figure1: Organisation globale des blocs 18

Remarque 1

Parmi les caractéristiques nécessaires pour manipuler un fichier vu comme tableau, on pourra
avoir par exemple :

- Le numéro du premier bloc,

- Le numéro du dernier bloc (ou alors le nombre de blocs utilisés).

19
Remarque 2

Pour un fichier vu comme liste, il suffirait par contre de connaître le numéro du premier bloc (la tête de la
liste), car dans chaque bloc, il y a le numéro du prochain bloc (comme le champ suivant dans une liste).

Dans le dernier bloc, le numéro du prochain bloc pourra être mis à une valeur spéciale (par exemple -1)
pour indiquer la fin de la liste.

20
2) Organisation interne des blocs
Les blocs sont censés contenir les enregistrements d'un fichier.
Ces derniers peuvent être :

Longueur Fixe Longueur Variable

21
2.1 Enregistrements de longueur fixe
Chaque bloc pourra alors contenir un tableau d'enregistrements de même type.

Type Tenreg = structure // structure d'un Type Tbloc = structure // structure d'un bloc du fichier
enregistrement du fichier tab : tableau[1..b] de Tenreg; // un tableau pouvant contenir
matricule : chaine(10); (au max) b enreg.
nom : chaine(20); NB : entier; // nombre d'enreg insérés dans tab (entre 0 et b).
age : entier; fin;
...
fin;

22
2.2 Enregistrements de longueur variable
Chaque enregistrement sera vu comme étant une chaîne de cararactère (de longueur variable).

 il y a un ou plusieurs champs ayant des tailles variables,

le nombre de champs varie d'un enregistrement à un autre.

23
 Remarque 1
Pour séparer les champs entre eux (à l'intérieur de l'enregistrement), on pourra soit utiliser un caractère
spécial ('#') ne pouvant pas être utilisé comme valeur légale, ou alors préfixer le début des champs par leur
taille (sur un nombre fixe de positions). Dans l'exemple ci-dessous, on utilise 3 positions pour indiquer la
taille des champs.
...|0|2|7|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|a|0|1|7|b|b|b|b|b|b|b|b|b|b|b|b|b|b|0
|3|7|c|c|c|.......|c|c|.....
<-------------------------------------------------> <--------------------------------> <----------....------>
un champ sur 27 caractères un champ sur 17 caractères ….. Dans le cas d'enregistrements à taille variable, le
bloc ne peut pas être défini comme étant un tableau d'enregistrements, car les éléments d'un tableau24
doivent toujours être de même taille.
Remarque 2
Pour séparer les enregistrements entre eux, on utilise les mêmes techniques que celles utilisées dans la
séparation entre les champs d'un même enregistrement (soit avec un caractère spécial '$', soit on préfixe chaque
enregistrement par sa taille). Voici un exemple de déclaration d'un type de bloc pouvant être utilisé dans la
définition d'un fichier vu comme liste avec format (taille) variable des enregistrements.
Type Tbloc = structure
tab : tableau[1..b'] de caractères; // tableau de caractères pour les enreg.
suiv : entier; // numéro du bloc suivant dans la liste
fin;
Remarque: Même si les enregistrements sont de longueurs variables, la taille des blocs reste
25
toujours fixe.
chevauchement

Pour minimiser l'espace perdu dans les blocs (dans le cas : format variable uniquement), on peut
opter pour une organisation avec chevauchement entre deux ou plusieurs blocs:
Quand on veut insérer un nouvel enregistrement dans un bloc non encore plein et où l'espace vide
restant n'est pas suffisant pour contenir entièrement cet enregistrement, celui-ci sera découpé en 2
parties de telle sorte à occuper tout l'espace vide du bloc en question par la 1ere partie, alors que le
reste (la 2e partie) sera insérée dans un nouveau bloc alloué au fichier. On dit alors que
l'enregistrement se trouve à cheval entre 2 blocs.

26
3) Taxonomie des structures simples de fichiers

27
Remarque 1
Utilisons la notation suivante:
T : pour fichier vu comme tableau, L : pour fichier vu comme liste
O : pour fichier ordonné, O : pour fichier non ordonné
F : pour format fixe des enregistrements, V : pour format variable
C : avec chevauchement des enregistrements entre blocs, C : sans chevauchement

28
Exemple 1
Par exemple la méthode T O VC représente l'organisation d'un fichier vu comme tableau (T), non
ordonné (O), avec des enregistrements de taille variables (V) et acceptant les chevauchements entre
blocs (C) :

La recherche est séquentielle, l'insertion en fin de fichier et la suppression est logique.

29
Exemple 2
Dans le cas d'un fichier LOF (fichier vu comme liste, ordonné avec enregistrements à taille fixe), chaque
bloc pourra contenir par exemple, un tableau d'enregistrements (tab), un entier indiquant le nombre
d'enregistrements dans le tableau (nb) et un entier pour garder la trace du bloc suivant dans la liste (suiv) :

La recherche est séquentielle, l'insertion provoque des décalages intra-blocs (pour garder l'ordre des
enregistrements) et la suppression peut être logique ou physique. 30
Exemple 1
fichier de type « TOF » (fichier vu comme tableau, ordonné avec enregistrements à taille fixe)

 L'opération du chargement initial consiste à construire un fichier ordonné avec n enregistrements

initiaux, en laissant un peut de vide dans chaque bloc. Ce qui permettra de minimiser les décalages
pouvant être provoqués par les futures insertions.

 La recherche d'un enregistrement est dichotomique (rapide).

31
Déclaration du fichier:
const
b = 30; // capacité maximale des blocs (en nombre d'enregistrements)

type
Tenreg = structure // Structure d'un enregistrement :
effacé : booleen; // booléen pour la suppression logique
cle : typeqlq; // le champs utilisé comme clé de recherche
champ2 : typeqlq; // les autres champs de l'enregistrement,
champ3 : typeqlq; // sans importance ici.
...
Fin;

Tbloc = structure // Structure d'un bloc :

tab : tableau[1..b] de Tenreg; // un tableau d'enreg d'une capacité b
NB : entier; // nombre d'enreg dans tab ( <= b)
Fin;

32
var // variables globales (F et buf)
F : Fichier de Tbloc Buffer buf Entete (entier, entier);
/* Desription de l'entête du fichier F :
L'entête contient deux caractéristiques de type entier.
- la première sert à garder la trace du nombre de bloc utilisés (ou alors le numéro logique du dernier
bloc du fichier)
- la deuxième servira comme un compteur d'insertions pour pouvoir calculer rapidement le facteur de
chargement, et donc voir s'il y a nécessité de réorganiser le fichier.
*/

33
 Chargement_Initial( nomfich : chaine; n : entier; u : reel )
// u est un réel compris entre 0 et 1 et désigne le taux de chargement voulu au départ
var
e : Tenreg;
i,j,k : entier;
DEBUT
Ouvrir( F, nomfich, 'N' ); // un nouveau fichier
i ← 1; // num de bloc à remplir
j ← 1; // num d'enreg dans le bloc
ecrire( 'Donner les enregistrements en ordre croissant suivant la clé : ' );
POUR k←1 , n
lire( e );
SI j <= u*b // ex: si u=0.5, on remplira les bloc jusqu'à b/2 enreg
buf.tab[j] ← e
j ← j+1;
SINON // j > u*b : buf doit être écrit sur disque
buf.NB = j-1;
EcrireDir( F, i, buf );
buf.tab[1] ← e; // le kème enreg sera placé dans le prochain bloc, à la position 1
i ← i+1;
j ← 2;
FSI
FP
// à la fin de la boucle, il reste des enreg dans buf qui n'ont pas été sauvegardés sur disque
buf.NB ← j-1;
EcrireDir( F, i, buf );
// mettre à jour l'entête (le num du dernier bloc et le compteur d'insertions)
Aff-entete( F, 1, i );
Aff-entete( F, 2, n );
Fermer( F )
FIN // chargement-initial 34
Rech( c:typeqlq; nomfich:chaine; var Trouv:bool; var i,j:entier )
var
bi, bs, inf, sup : entier;
trouv, stop : booleen;
DEBUT
Ouvrir( F, nomfich, 'A' );
bs ← entete( F,1 ); // la borne sup (le num du dernier bloc de F)
bi : = 1; // la borne inf (le num du premier bloc de F)
Trouv ← faux; stop ← faux; j ← 1;
TQ ( bi <= bs et Non Trouv et Non stop )
i ← (bi + bs) div 2; // le bloc du milieu entre bi et bs
LireDir( F, i, buf );
SI ( c >= buf.tab[1].cle et c <= buf.tab[buf.NB].cle )
// recherche dichotomique à l'intérieur du bloc (dans la variable buf)...
inf ← 1; sup ← buf.NB;
TQ (inf <= sup et Non Trouv)
j : = (inf + sup) div 2;
SI (c = buf.tab[j].cle) Trouv ← vrai
SINON
SI (c < buf.tab[j].cle) sup ← j-1
SINON inf ← j+1
FSI
FSI
FTQ
SI ( Non Trouv ) j ← inf FSI
// fin de la recherche interne. j indique l'endroit où devrait se trouver c
stop ← vrai
SINON // non ( c >= buf.tab[1] .cle et c <= buf.tab[buf.NB] .cle )
SI ( c < buf.tab[1].cle )
bs ← i-1
SINON // c > buf.tab[buf.NB] .cle
bi ← i+1
FSI
FSI
FTQ
SI ( Non Trouv ) i ← bi FSI
fermer( F )
FIN 35
4. Conclusion

Le type d’organisation choisi ,le support de stockage utilisé, permettent de déterminer le mode d’ accès

aux données stockées

36
 TOVC
Organisation
taxonomie
interne Enr de long
TOF
fixe
TOV C

TOF

TOVC STURCTURE Organisation des

Enr de long
SIMPLE DE fichiers variable
FICHIER
TOVC

LOVC

LOF Organisation
LOVC LOVC globale
LOF
LOVC

Fichier vu tableau
Fichier vu liste

Une Carte Mentale de l’exposé

37
Références

Mc BELAID et Sabiha LIMAME née MERZOUK ,Fichiers Organisation  Accès,les pages bleues
internationales Maison d’ édition pour l’enseignement et la formation, ISBN: 978-9947-850-71-8

Sitographie

https://sites.google.com/a/esi.dz/hidouci/competences-professionnelles/algo2

38