Cours bases de données indexation, optimisation des requêtes

Support de cours bases de données indexation, optimisation des requêtes, tutoriel & guide de travaux pratiques bases de données en pdf.

Organisation des données

Opérations sur les fichiers
Optimisation
Une organisation de fichier réussie devrait pouvoir exécuter efficacement les opérations que nous pensons appliquer fréquemment au fichier.
Exemples :
Si condition de recherche fréquente sur le numéro de Sécurité Sociale, il faut favoriser la localisation par rapport à la valeur de NoSS.
==> Soit trier par rapport à NoSS, soit définir un index sur NoSS.
Si, en plus, recherche d’employés par service, il faudrait stocker tous les enregistrements des employés dont la valeur de SERVICE est identique de façon contiguë. Mais cet arrangement est en conflit avec les enregistrements classés sur la valeur de NoSS.
==> Il faut trouver un compromis : optimisation
Conception logique de la base
Il existe plusieurs organisations primaires de fichiers qui déterminent la façon dont les enregistrements sont placés physiquement sur le disque, et donc la façon dont il est possible d’accéder à ces enregistrements.
Dans un fichier plat (ou fichier non ordonné) les enregistrements sont placés sur le disque sans observer d’ordre particulier et les nouveaux enregistrements sont simplement ajoutés en fin de fichier.
Dans un fichier trié (ou fichier séquentiel), ils sont ordonnés en fonction de la valeur d’un champ particulier nommé clé de tri.
Un fichier haché utilise une fonction de hachage appliquée à un champ particulier (la clé de hachage).
Les organisations secondaires, ou structures d’accès auxiliaire, permettent d’accéder rapidement aux enregistrements en se basant sur d’autres champs que ceux qui ont servi pour l’organisation primaire. La plupart de ceux-ci sont des index.
Fichiers non ordonnés (“heap files”)
Type d’organisation le plus simple.
Les enregistrements sont placés dans le fichier dans l’ordre de leur insertion.
Insertions/modifications d’un tuple :
En moyenne F/2 pages sont lues (donc transférées) si la page existe déjà
F+1 pages transférées si la page n’existe pas
Effacement d’un tuple :
En moyenne F/2 pages sont lues (donc transférées) si la page existe déjà
F pages transférées si la page n’existe pas
Fichiers ordonnés (“sorted files”)
Les enregistrements sont ordonnés physiquement sur disque en fonction des valeurs d’un de leurs champs (champ d’ordonnancement).
Si le champ d’ordonnancement est la clé primaire, le champ est appelé clé d’ordonnancement.
Avantages :
Les requêtes basées sur le champ d’ordonnancement ont un coût moyen de log!F par recherche binaire
Si les requêtes concernent des tuples successifs, l’utilisation de cache est très efficace
Aucun avantage si l’accès se fait par d’autres attributs que le champ d’ordonnancement
Problème (maintien de l’ordre):
Coût moyen : F/2 lectures (pour trouver l’endroit) + F/2 écritures (afin de pousser les enregistrements suivants
Solution partielle 1 : Laisser des espaces libres
Solution partielle 2 : Utilisation de pages d’overflow (et tri de temps en temps)
Désavantages
Les pages successives ne sont plus nécessairement stockées à la suite Les pages overflow ne sont pas dans l’ordre
Utilisation d’index
Mécanisme permettant de localiser efficacement les tuples (ou pages) sans avoir à scanner l’ensemble de la table (ou du fichier).
Basé sur une ou plusieurs clés de recherche.
Les entrées d’index peuvent contenir :
les données elles-mêmes (l’index et le fichier sont dits intégrés)
la valeur de la clé de recherche et le pointeur vers un enregistrement ayant cette valeur (l’index est dit non intégré).
Les entrées d’index sont stockée suivant les valeurs de la clé de recherche :
des entrées avec la même clé de recherche sont stockées ensemble (hachage, B-arbres)
les entrées peuvent être triées suivant la valeur de la clé (B-arbres)
Structures de stockage
Index intégré
Fichiers non triés (“heap files”)
Fichiers triés (“sorted files”)
Fichiers intégrés contenant l’index et les enregistrements
ISAM (Index Sequential Access Method)
B+ arbres
Hachage

1. Stockage des données
1.1. Supports physiques
1.2. Techniques de stockage
2. Structures de données
2.1. Indexation de fichiers
2.2. L’arbre-B
2.3. Hachage
2.4. Les index bitmap
2.5. Structures de données multidimensionnelles
3. Évaluation des requêtes
3.1. Algorithmes de base
3.2. Jointures
3.3. Compilation d’une requête et optimisation