Les SGBD doivent gérer des volumes de données parfois considérables (plusieurs gigas-octets qui sont accédés de façon concurrente par plusieurs utilisateurs simultanément). Ceci impose des contraintes de gestion efficace des données avec un contrôle fin au niveau de l’utilisation afin d’assurer une certaine sécurité et un confort d’utilisation maximum. Le niveau physique d’un SGBD adresse cette problématique. La figure 1 montre les différents composants qui assurent la gestion physique de la base de données.
L’objectif est donc de stocker les données afin d’assurer les performances maximales au niveau des requêtes d’interrogation, d’insertion, de suppression et de mise à jour.
- Support physique
- Méthodes d'accès
- Arbre B+
- Arbre B
- Hachage
Afin d’assurer la pérennité de l’information, les données de la base de données sont stockées sur un support de mémoire secondaire. Il existe différents types de mémoire :
les mémoires accessibles directement par la CPU (MC, mémoires caches) - mémoires volatiles -.
les mémoires secondaires (disques, BM, ...) plus lentes d'accès mais en général avec une capacité plus grande. Non directement accessibles, - mémoires non volatiles -.
Les données d'une base de données sont en général trop volumineuses pour tenir entièrement en mémoire centrale (RAM). Les données sont stockées sous la forme de fichiers d'enregistrements. Les échanges entre la mémoire secondaire et la mémoire centrale se font par transfert de page.
Définition
Une page est une granule d'allocation d'espace mémoire secondaire (unité de lecture/écriture sur le support).
Chacune des pistes comporte la même quantité d'information. Un bloc (une page) représente l'unité de transfert entre disque et zone tampon (buffer) qui est une zone réservée en mémoire centrale. Il est possible de transférer plusieurs blocs à la fois (cluster). Le temps d'accès au premier bloc se situe entre 15 et 60 ms; il est de l'ordre de 1 à 2 ms pour le bloc suivant.
L’utilisation de plusieurs buffers permet d’améliorer les performances en réduisant considérablement les temps d'accès. Ceci est possible dans le cas d'une machine multi-processeurs ou d'un processeur d'E/S dédié.
Le Système de Gestion de Fichiers (SGF) gère les différentes méthodes d'accès. Il alloue de l’espace pour les fichiers. Un fichier peut être considéré comme un ensemble de pages sur le disque. Cette vision facilite la gestion en faisant correspondre des adresses relatives et des adresses physiques.
@relative (n°page, déplacement) ® @absolue (n°cylindre, n°piste, n°secteur)
Le gestionnaire d'entrées/sorties gère les différentes structures pour chaîner les différentes pages affectées à un fichier d'enregistrements. Un enregistrement n'est pas nécessairement de taille fixe (champ de taille variable ou champs optionnels). On utilise donc des séparateurs de champs et d'enregistrements pour faciliter le parcours de l’information. Un fichier peut contenir des enregistrements de différents types (cluster). On utilise des indicateurs de type d'enregistrements. Un bloc peut contenir plusieurs enregistrements (facteur de blocage).
Le nombre d'enregistrements/bloc est soit fixe, soit variable (chaînage).
Les blocs sont soit consécutifs, soit chaînés.
Le but est de minimiser le nombre d'accès pour retrouver un bloc particulier. Un descripteur de fichier donne le nom du fichier, le nom du propriétaire, la liste des droits associés, la date de création, la taille, l'organisation, le nombre de champs...
Un chemin d'accès spécifie la structure de données accélérant la recherche d'enregistrements (un fichier, plusieurs chemins d'accès). Une méthode d'accès est un ensemble des fonctions assurant l'exploitation d'un chemin d'accès. L’organisation de fichiers concerne le mode de stockage des enregistrements (1 fichier, 1 organisation).
L’organisation la plus triviale est l’organisation séquentielle non triée.
L’algorithme d’insertion est très simple et consiste à transférer le dernier bloc dans le buffer. L’ajout de l'enregistrement, ré-écriture du bloc). En revanche les recherches sont coûteuses. La suppression nécessite des indicateurs de suppression et provoque des trous ce qui engendre des réorganisations.
L’organisation séquentielle triée
Elle repose sur une notion de champ clé. Elle permet d’accélérer les recherches.
L’insertion est très coûteuse : on peut laisser de la place libre dans chaque bloc ou réserver une zone non triée pour les insertions.
L’organisation relative stockage séquentiel,
enregistrements de taille fixe.
L’organisation hachée
Un fichier est découpé en paquets de faible taille qui peuvent être composés d'une ou plusieurs pages. Les enregistrements sont répartis dans ces paquets en utilisant une fonction de hachage : Fonction H : Clé ----> Paquet.
L’indexation a pour but d’accélérer les traitements en ajoutant des structures de servitude. Il existe différentes techniques (indexation, hachage) selon le contexte. L’évaluation d'une technique se fait selon des critères de temps d'accès, délai d'insertion, délai d'effacement, occupation mémoire.
Pour une même relation, il est possible d'avoir plusieurs index :
Un Index primaire (plaçant) qui fait l’ordonnancement des clés dans l'index correspond à l'ordonnancement des enregistrements dans le fichiers.
L’index secondaire (non plaçant) qui fait l’ordonnancement des clés dans l'index correspond à un ré-ordonnancement logique des enregistrements dans le fichier.
Un fichier séquentiel indexé est un fichier à accès séquentiel où l’ensemble des enregistrements sont ordonnés selon une clé de tri. Cette définition est une vision logique d’un fichier d’enregistrement car physiquement il est possible que l’ordre de stockage ne corresponde pas à l’ordre logique.
Un exemple nous est donné par le fichier DISQUE où l’on suppose avoir un index sur le titre.
Fichier DISQUE
| Titre | Auteur | Année |
| T1 | A1 | 1998 |
| T2 | A2 | 1999 |
| T3 | A3 | 1997 |
Cette organisation pose un problème de maintien de l'ordre. Lors de la suppression d’un enregistrement on voit apparaître des trous dans le fichiers. Une insertion peut nécessité la gestion d’une zone de débordement. Elle nécessite également la gestion d’un fichier d’index dont on mesure la densité.
Définition
La densité est le quotient du nombre de valeurs de clé de tri dans l'index sur le nombre d'enregistrements dans le fichier.
On distingue les index denses et les index non denses.
Définition
Dans un index dense on trouve un enregistrement d'index pour chaque valeur de la clé de tri du fichier.
Définition
Dans un index non dense on trouve un enregistrement pour certains enregistrements du fichier.
En général, on spécifie un index non dense pointant sur chaque page disque. Il faut néanmoins essayer de respecter la contrainte de taille car il est préférable que l’index tienne en mémoire centrale. Un index non dense requiert moins de mises à jour lors des opérations d’insertion et de suppression. Il faut établir un compromis entre temps d'accès / espace mémoire. Par exemple si l’on a 100 000 enregistrements , 10 enregistrements / page. Si l’index contient 1 enregistrement / page il faudra 10 000 enregistrements d'index.. Soit 100 enregistrements d'index/ page et donc un index sur 100 pages. En cas de recherche dichotomique (b pages d'index) il faudra transférer .1 + log2(b) pages. Soit ici 8 pages !
Il est possible de spécifier un index secondaire, en général sur des attributs non-clés. Ce type d’index est utilisé si la le fichier n'est pas trié sur la clé d'index. Il nécessite une indirection pour regrouper les pointeurs. Ceci implique une optimisation.
Les fichiers séquentiels indexés perdent leurs performances quand leur taille grandit. On propose donc des organisations différentes tels que les fichiers indexés par arbre B+ (B Balanced, équilibré) , qui sont très utilisés si l’on a des modifications fréquentes. Ils sont efficaces, quelque soit les opérations d'insertion ou d'effacement de données. Servitude lors des opérations d'insertion ou de suppression. Un arbre B+ est sous la forme d'un arbre équilibré.
Tous les chemins qui mènent de la racine à une feuille ont la même longueur. Chaque noeud de l'arbre possède de n/2 à n enfants. La valeur n est fixée pour chaque arbre.
Un pointeur Pi pointe soit sur le premier enregistrement de clé Ki, soit sur un paquet de pointeurs qui pointent sur Ki.
Un noeud terminal comprend n - 1 valeurs de clés de tri K1, K2, …, Kn-1et n pointeurs P1, …Pn. Pour les valeurs i telles que 1 <= i <= n , Pi pointe vers un groupe de pointeurs qui pointent vers les enregistrements de clé Ki. Les valeurs de clés de tri, ordonnées : si i < j alors Ki < Kj.
Les fichiers indexés par arbre B ont le même aspect que les arbres B+ mais les redondances des clés de tri sont éliminés.
Néanmoins la structure des noeuds non terminaux est différente. Il y a moins de noeuds que les arbre B+. Dans le cas d'une recherche, on est pas on est pas obligé d'aller au bout d'un chemin. En revanche, cette représentation possède quelques inconvénients : Inconvénients : les noeuds terminaux et non terminaux n'ont pas la même dimension. L'effacement est très complexe. Aussi pour les index de grande dimension on choisira les arbres B+.
Le hachage a pour but d’éviter de parcourir un index pour accéder à une donnée. Etant donnée une valeur clé d'un enregistrement, l'application d'une fonction de hachage doit permettre de trouver la position de cet enregistrement dans la structure contenant tous les enregistrements (tableau, fichier). Lors d'une insertion, l'application de la fonction de hachage permet de déterminer la place ou l'enregistrement doit être inséré. Il peut se poser des problèmes de collision (différentes techniques sont alors utilisées (place libre suivante, chaînage, seconde fonction de hachage). Au dessus d'un taux de remplissage de 70%, les techniques de hachage s'avèrent inefficaces.
- Conclusion
Il n'y a pas de technique meilleure qu'une autre dans l'absolu. Doit-on utiliser l'une ou l'autre des techniques? Le coût des réorganisations périodiques dues à l'indexation ou au hachage est-il acceptable? Quelles sont les fréquences comparées des insertions et des suppressions? Est-il souhaitable d'optimiser le temps d'accès moyen et d'avoir des cas critiques? Quelles requêtes sont le plus fréquemment faites sur la BD?
