Tableau de bits
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
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.
