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
Certes, l'appellation tableau Ă©voque une grille semblable Ă celle des mots croisĂ©s, mais un tableau de bits peut trĂšs bien ĂȘtre en trois dimensions ou plus. Pour autant, le nombre d'Ă©lĂ©ments Ă©tant fini, connu, voire dĂ©fini, la collection peut ĂȘtre inventoriĂ©e selon un chemin parcourant chaque « colonne » et chaque « ligne ». Cette polygraphie de l'espace se rĂ©duit alors Ă un seul fil d'Ariane utilisĂ© par ThĂ©sĂ©e dans le labyrinthe de DĂ©dale. Voici pourquoi, en anglais, les notions de carte (map), de jeu, d'assortiment (set), d'ensemble ou de rĂ©seau (array) mais aussi de fil (string) se rencontrent en un seul objet utile Ă la programmation.
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
- 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)
- Olivier Heurtel, Oracle 11g : Administration (lire en ligne)
- « Bitmap Index vs. B-tree Index: Which and When? », sur www.oracle.com (consulté le )