Index B-Tree et Bitmap
Rappel : Index
Un index de base de données est une structure de données complémentaire aux tables, qui permet d'optimiser les recherches dans une ou plusieurs colonnes.
Les index sont donc appropriés pour optimiser les accès SQL comprenant une opération de restriction (clause WHERE).
Une jointure étant la composition d'un produit cartésien et d'une restriction, elle est également optimisable grâce à l'indexation (donc les clés étrangères sont de bons candidats à l'indexation).
Voir Indexation
Rappel : Index B-Tree
Un index de type B-Tree est fondé sur la notion d'arbre équilibré, qui permet dans le cas général d'assurer un temps de recherche constant quelle que soit la valeur recherchée.
Un tel index est utile pour optimiser l'accès à une colonne comportant de nombreuses valeurs distinctes et en particulier lorsque chaque valeur concerne un petit nombre d'enregistrements : donc lorsque le rapport D entre le nombre de valeurs distinctes et le nombre d'enregistrements tend vers 1.
Attention : Index B-Tree et discrimination
Si le rapport D est trop petit, alors l'index est peu utile car chaque recherche dans l'index renverra un grand nombre d'enregistrements.
Par exemple si la question est "quelles sont les noms des femmes vivant en France" (SELECT nom FROM personne WHERE genre='Femme' AND pays='France'), un index sur le genre aura très peu d'intérêt par rapport à une recherche directe dans la table et au contraire pourra conduire à occuper un volume important dans la BD.
Définition : Index Bitmap
Les index Bitmap sont destinés à l'indexation de colonnes qui comportent peu de valeurs distinctes et beaucoup d'enregistrements pour chacune de ces valeurs : donc lorsque le rapport D tend vers 0.
A l'inverse des index B-Tree, les index Bitmap ne stockent pas un pointeur vers un enregistrement dans un fichier trié sur l'index, mais une valeur codée sur un bit (vrai ou faux) pour chaque valeur de la colonne indexée (2 bits pour une cardinalité 2, 3 pour une cardinalité 3, etc.) dans un fichier trié sur la clé.
De tels index optimisent la recherche relative à une question du type : "l'enregistrement appartient-il à un sous ensemble du domaine sur l'index ?".
Par exemple pour savoir si un enregistrement est de genre "Femme", il suffit de consulter un bit au lieu de comparer des chaînes.
Remarque :
De plus pour répondre à la question "Quelles sont les femmes ingénieurs" (SELECT nom FROM personne WHERE genre='Femme' AND metier='Ingénieur'), si genre et métier sont indexés avec un index bitmap, alors la clause AND sera résolue par une simple opération logique sur les deux bits concernés. Cela fonctionne de la même façon pour OR.
Remarque :
Enfin notons que les index Bitmap peuvent être compressés et donc consomment peu d'espace disque.
Attention :
Les index Bitmap sont encore plus sensibles aux modifications des données que les index B-Tree (décompression, reconstruction, re-compression).
Syntaxe : Index B-Tree et Bitmap
La syntaxe classique crée par défaut un index de type B-Tree. Pour créer un index Bitmap le mot clé BITMAP doit être ajouté.