∈"> ∉"> ] >
Le système et la couche physique exposent plusieurs notions de bas niveau:
On souhaite proposer des structures de données et des algorithmes génériques permettant d'implanter un moteur d'exécution de requêtes (SQL).
On abstrait les concepts bas niveau par la notion de fichier. Un fichier un ensemble d'enregistrements. Un enrigstrement contient des données structurées en champs. En pratique, les fichiers sont paginés
La couche physique propose plusieurs opérations sur les fichiers
(cf. cours 2 pour les différentes manières d'implanter ces
opérations).
Une table est généralement représenté par un fichier
(au sens collection d'enregistrements)
La structure la plus simple pour un fichier est la structure en tas (à ne pas confondre avec la structure de donnée du même nom). La couche physique du SGBD connait la liste des pages d'un fichier ainsi que l'espace libre sur chaque page, les enregistrements sont ajoutés ou supprimé dans les pages que le SGBD considère comme meilleures (du point de vue des E/S) sans considération sur les données.
Rechercher un enregistrement particulier, en fonction d'un critère sur son contenu (ex: id='5') nécessite un parcours séquentiel du fichier (scan)
Un index est un fichier auxiliaire, structuré qui va rendre plus efficace l'accès à certaines données, en fonction d'une clé d'index.
Un enregistrement d'un index s'appelle une entrée d'index. L'entrée associée à la clé k est notée k* et contient suffisament d'information pour retrouver le ou les enregistrements (de la table indexée) associés à k. On distingue trois types d'indexes:
Un index est dit groupant si ses entrées sont triées dans le même ordre que les enregistrement du fichier indexé. Il est dit non-groupant dans le cas contraire
Les enregistrements de la table initiale ne
sont jamais dupliqués. On ne garde donc jamais un indexe
de type I en plus de la table initiale (on supprime cette
dernière)
Un index dense s'il contient une clé par enregistrement et non dense sinon
Si une table possède un index non-dense, alors le
fichier de cette table est toujours trié selon la clé
d'index (sinon l'index ne sert à rien).
Un index pour lequel la clé d'index contient la clé primaire de la relation est appelé un index primaire. Les autres indexes sont appelés indexes secondaires
Deux entrées d'index possédant la même clé sont des doublons. Un index primaire ne contient pas de doublon.
Outre le fichier tas un index peut avoir les représentations internes suivantes:
On illustre sur une relation ayant le schéma Emp(Nom, Age, Salaire)
Un hash index repose sur une fonction de hash h
telle que:
h(k) = @page
où k est la clé d'index et @page est
l'adresse (sur le disque) de la page où se trouve
l'enregistrement associé à k
Remarque: index de type I
Arbre «n-aire» de recherche (avec n grand, généralement 100)
Remarque: index de type II, non groupant
Remarque: index de type II, non groupant
On pose: B : nombre de pages de données
R : nombre d'enregistrements par page
D : temps moyen de transfert d'une page
On suppose des indexes de type I
Fichier tas
Fichier trié
Hash index
Arbre B+
Une clé d'index peut être composée de plusieurs champs de la
relation originale.
Si une clé est composée de (c1, …,
cn), on peut l'utiliser pour toute requête
dont la valeur dépend de tous les i <= k,
pour k <=n.
Supposons une clé composée sur (age,salaire). On peut l'utiliser pour age > 30 ou pour age >30 AND salaire <4000 mais pas pour salaire <4000 ou age >30 OR salaire <4000
Table de hash classique = tableau de taille N contenant des listes chaînées de valeurs (bucket). On calcule h(k) mod N pour voir dans quel bucket insérer la nouvelle valeur. Si un bucket devient trop grand, on double la taille du tableau et on redistribue tous les contenus des bucket.
La redistribution est trop couteuse ici : on doit scanner/écrire tout l'index. On souhaite ne toucher que le tableau et le bucket trop grand, et pas les autres.
On n'utilise pas un simple tableau mais un tableau contenant un masque binaire. On garde aussi un compteur de profondeur globale et un compteur de profondeur local, pour chaque bucket
On sépare le bucket plein en deux (100 vs 000)
On double la taille du répertoire et on augmente les compteurs globaux et locaux
Le pointeur de 100 va vers le nouveau bucket les autres vont vers les anciens
Un Arbre B+ est un arbre «n-aire» dont les nœuds peuvent contenir entre M et 2M valeurs (sauf la racine, qui a entre 1 et 2M valeurs).
Les noeuds internes contiennent des valeurs et des pointeurs vers les fils.
Les feuilles contiennent les valeurs finales, un pointeur vers les données indexées et sont chaînées entre-elles
Exemple sur un noeud d'ordre 4 (i.e. entre 2 et 4 valeurs, 5 pointeurs vers les fils).
Arbre vide:
Insertion 4,19,22,39 (noeud plein)
Insertion
25
(partage du noeud, insertion
de 25, report de la plus petite valeur dans le parent, chaînage
des feuilles)
Insertion 90
Insertion 95
insertion de 54
Partage en 2 et insertion de la valeur mediane dans un nouveau parent
suppression 95 (simple)
suppression 71 (utilisation des voisins)
suppression 19 (fusion des voisins, suppression de l'entrée dans le parent)