AccueilđŸ‡«đŸ‡·Chercher

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

  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 )

Voir aussi

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.