Tableau de bits

Un tableau de bits (en anglais bitmap) est une structure de données, en particulier un tableau de données binaires. Il s'agit d'une collection ordonnée de bits assimilables à des booléens.

Dénomination

L'appellation tableau de bits évoque une grille 1D ou 2D (comme par exemple une grille de mots croisés), mais un tableau de bits peut être en trois dimensions ou plus. Cependant, le nombre d'éléments d'un tableau de bits est fini et connu, donc la collection des valeurs dans le tableau peut être parcourue à l'aide d'un index qui indique la position selon chaque dimension.

Par exemple, pour une grille 2D de taille 2x3 (2 lignes et 3 colonnes), la séquence d'indices (1,1),(1,2),(1,3),(2,3),(2,2),(2,1) permet de parcourir l'intégralité du tableau. Cette polygraphie de l'espace peut être comprise comme un « fil d'Ariane ».

Application

Une application graphique du tableau de bits est l'image binaire. Le filtre de Bloom, structure de données, utilise un tableau de bits.

Support par les langages de programmation

• APL : support natif compact (1 bit par bit) par toutes les implémentations majeures (Dyalog APL, APL2, APL Next, NARS2000, GNU APL, etc.)
• C : si la taille de la mémoire le permet, la représentation de chaque bit sur un caractère est souhaitable pour des raisons de performance (car l'octet est adressable et en général le bit ne l'est pas). Pour une plus grande compacité, au prix de performances plus faibles, il faut passer par des sous programmes simulant un accès au bit dans un tableau de caractères, en lecture comme en écriture.

Index bitmap

Un index de base de données de type bitmap est un tableau de bits qui fonctionne selon le principe de la cardinalité[1]. Ce tableau comporte une ligne pour chaque n-uplet de la table indexée et une colonne pour chaque valeur distincte de la colonne indexée. Il est généralement considéré que les index bitmap sont préférables aux autres index lorsque la colonne à indexer a une faible cardinalité[2] même si c'est contesté[3]. Par exemple, les années sont généralement peu nombreuses et ordonnées.

Exemple. Considérons la table Personne suivante représentant des personnes avec leur année de naissance.

Personne
Identifiant	anneeNaissance
1	1988
2	1990
3	1992
4	1990

L'index bitmap correspondant à l'indexation de la colonne anneeNaissance donne le tableau suivant. La première ligne a la valeur 1 pour la colonne 1988 et 0 pour les autres colonnes puisque cette personne est née en 1988.

Identifiant	1988	1990	1992
1	1	0	0
2	0	1	0
3	0	0	1
4	0	1	0

L'index bitmap précédent, nommé BIDX_PERS_ANNEE est créé avec la commande :

CREATE BITMAP INDEX BIDX_PERS_ANNEE ON Personne (anneeNaissance )

En pratique chaque ligne d'un index bitmap est également associée à une adresse physique permettant ainsi de la retrouver rapidement. Tout l'intérêt des index bitmap est d'une part qu'ils peuvent être compressés en utilisant des techniques telles que le codages par plages et d'autre part qu'ils sont utilisés pour répondre à des requêtes en effectuant des opérations bit à bit.

Notes et références

1. Christian Soutou, SQL pour Oracle : Applications avec Java, PHP et XML : Optimisation des requêtes et schémas - Avec 50 exercices corrigés (lire en ligne)
2. Olivier Heurtel, Oracle 11g : Administration (lire en ligne)
3. « Bitmap Index vs. B-tree Index: Which and When? », sur www.oracle.com (consulté le 15 novembre 2016)

Voir aussi

• Arbre B