ORGANISATION DES FICHIERS
E
Une organisation de fichier est une manière de disposer les enregistrements dans un fichier stocké sur le disque. Un fichier peut être accédé et modifié de différentes façons, et une organisation de fichier peut être bonne pour un type d'accès et mauvaise pour un autre type.
Un fichier trié sur le nom des employés n'est pas une bonne organisation quand on veut avoir les employés ayant un salaire supérieur à 100. Un SGBD offre plusieurs organisations possibles. C'est a l'administrateur que revient le choix de l'organisation adéquate. Les fichiers triés sont meilleurs pour les requêtes mais la mise à jour est plus compliquée à gérer.
1.1) Modèle de coût
Pour pouvoir comparer différentes organisations, il nous faut un modèle de coût. Pour cela, on va considérer les paramètres :
P: Le nombre de pages contenant des données,
E: Le nombre d'enregistrements par page,
T: Le temps "moyen" pour lire ou écrire une page,
Ainsi le coût d'une opération est exprimée en fonction de ses paramètres.
Dans ce modèle simplifié, on ne considère pas le coût C des traitements en unité centrale (typiquement C = T/25)
1.2) Opérations et Organisations considérées
Balayage : (Scan) parcourir tout le fichier.
Recherche avec égalité : On cherche les enregistrements ayant un champs X égal a une valeur particulière.
recherche avec intervalle : On cherche les enregistrements ayant un champs X compris dans un intervalle particulier.
Insertion : (1) On doit identifier la page qui doit contenir l'enregistrement a insérer (2) la modifier en zone tampon (mémoire) et (3) la réécrire sur disque.
Suppression : Suppression d'un enregistrement identifié par son IdE. (1) ramener la page correspondant en mémoire, (2) la modifier ensuite la réécrire sur disque.
Fichiers hachés
Un fichier haché est caractérisé par :
un champ particulier appelé clé de recherche (Rien à voir avec la notion de "clé" dans une table).
une fonction de hachage h qui associe a chaque valeur de la clé de recherche un entier.
Exemple: h: String N. h(X) = ASCII(X) modulo(100).
L'entier associée a une valeur correspond au numéro de la page où l'enregistrement correspondant doit se trouver. Plusieurs valeurs de la clé peuvent être associées au même entier. Nous avons donc une zone de débordement.
Exemple : h(abc) = h(bca).
0
1
Zone de débordement
99
Fichier tas
Balayage : coûte .B x T.. Il faut transférer toutes les pages en mémoire.
Si on sait qu'il y a un seul enregistrement, alors en moyenne, on lit la moitié du fichier le coût est .P x T / 2.
Si l'on ne sait pas le nombre d'enregistrements, alors le coût est .P x T.. C’est le pire des cas car on balaye tout le fichier ! Dans le meilleurs des cas, la première page lue contient l’information recherchée donc le coût est : T.
Recherche avec intervalle : On doit balayer tout le fichier : le coût est .B x T.
Insertion : On suppose que l'insertion se fait a la fin du fichier.
On lit la dernière page (1er transfert), puis
On la modifie en mémoire et on la réécrit sur disque (2ème transfert).
le coût est .2 x T.
Suppression : On cherche d'abord l'enregistrement, donc charger sa page (1 transfert), ensuite, on fait la modification en mémoire et on réécrit la page le coût est .2 x T..
Si la suppression se fait par valeur (ex : supprimer tous ceux dont le nom est toto) :
balayer tout le fichier (PxT) ;
s’il y a n personnes répondant au nom toto n P ;
si chacune se trouve dans une page distincte, il nous faut alors modifier n pages, puis les réécrire n x T donc le coût est : .(P x n) x T.
On a supposé que les pages ne sont pas compactées. Et on donne plutôt que l'IdE, une condition sur le(s) enregistrement(s) à supprimer ?
Fichiers triés
Balayage : Le coût est P x T.
Recherche avec égalité :
Même coût que le fichier tas, si le champs de recherche n'est pas celui du tri.
Sinon, avec une recherche dichotomique, on peut retrouver l'enregistrement en log2(P) transferts le coût est .log2(P) x T.
Ici, on a considéré qu'un seul enregistrement trouvé.
Dans le pire des cas, par une recherche dichotomique :
on se place au milieu du fichier (lire page P/2). On restreint le fichier à P/2 pages.
on se place à 3P/4 donc P/22
n. il reste P/2n pages = 1 P/2n = 1 P = 2n log P = log 2n log2 P = n
Recherche avec intervalle : On fait d'abord une recherche dichotomique jusqu'à trouver une valeur dans l'intervalle spécifié ; le coût est log2(P) x T. Là aussi, on a considéré qu'un seule valeur. S'il y a x enregistrements, alors il nous faudra transférer au maximum (X/R + 1) autres pages. Le coût est majorée par .(log2(P) + X/R + i) x T.
Chaque page contient E enregistrements donc X/E.
X/E + 1 page où X est le nombre d’enregistrements qui satisfont la condition. La recherche se fait en deux parties :
Trouver la valeur dans l’intervalle (ex : les valeurs entre 15 et 25 ans). Au pire des cas, on fait log2(P) x T. Au meilleur des cas, on ne fera qu’une seule lecture (la page du milieu contient une valeur comprise dans l’intervalle).
Ensuite, on recherche les x valeurs restantes. Celles-ci se trouvent sur au maximum X/E pages : on doit donc lire X/E pages.
Insertion : Il faut d'abord chercher la bonne page où le placer. Ceci peut se retrouver en lisant log2(P) pages. On peut supposer qu'en moyenne la page intéressante se trouve au milieu du fichier. Comme on risque d'avoir besoin d'avancer tous les enregistrements dans les pages suivantes P/2, on doit donc toutes les lire et les réécrire. Ce qui donne un coût global approximatif de .(log2(P) +2 x P/2) x T. Le coût est donc .(log2(P)+P) x T.
Suppression : On retrouve la page de l'enregistrement en un transfert. Ensuite on charge les pages suivantes pour tasser les enregistrements. Ce qui fait un coût global approximatif de (1 + P/2) x 2 x T. En fait cela dépend du nombre de page (pair ou impair). Le coût est P x T
9
5 6
7 8
1 2
3 4
On supprime l’enregistrement 8
IdE < 2, 4 >
n° page n°enregistrement ds la page
Si l’on veut compacter, il faut placer le 9 à la place du 8 (coût supplémentaire). Donner une estimation du coût si on veut avoir une organisation compacté. On suppose que la suppression se fait dans la page du milieu.
On lit la page du milieu, (T) puis celle qui vient juste après. P/2 et P/2 + 1
A partir de la page du milieu jusqu’à la dernière page, chacune sera lue et écrite une fois d’où un coût de (P/2) x (Tx2) P x T
Nombre de page lues chaque page sera lue et écrite
Dans l’estimation de ce coût, on n’a pas tenu compte du temps de la réorganisation des pages au niveau de la zone tampon.
7
Fichiers hachés
On suppose qu'il n'y a pas de débordement
Balayage : Pareil que pour le fichier tas le coût est donc P x T
Recherche avec égalité :
Si X est la valeur recherché, alors on peut savoir la page en calculant h(X) et on fait un accès direct : le coût est .T.
S'il y a plusieurs enregistrements, comme on a supposé qu'il n'y a pas de débordement, alors tous les autres enregistrements sont dans la même page.
Recherche avec intervalle : On est obligé de balayer tout le fichier le coût est P x T
Insertion : Le coût est 2T on accède directement à la page
Suppression : On lit la page puis on la réécrit le coût est donc 2T
Conclusion
Il n'y a pas une organisation meilleure que toutes les autres pour tous les types d'opérations. Pour le balayage, c’est pareil, et pour la recherche, mieux vaut des fichiers hachés (ne tiens pas compte de débordement).
|
Tas
|
Trié
|
Haché
|
Balayage
|
P x T
|
P x T
|
P x T
|
Recherche =
|
0.5 (P x T)
|
Log2 (P) x T
|
T
|
Recherche []
|
P x T
|
Log2 (P) x T
|
P x T
|
Insertion
|
2 x T
|
(Log2 (P) + P) x T
|
2T
|
Suppression
|
[(P+1) x T] /2
|
P x T
|
2T
| |
