Bitmap-Index
Bitmapindex
Ein Bitmapindex ist ein Datenbankindex, bei dem ein oder mehrere Attribute in Form eines Bitmusters gespeichert sind.
Ein einfaches Beispiel: in einen Index einer Personendatenbank werden die Attribute "Geschlecht" (2 mögl. Werte, Kardinalität=2) und "Familienstand"(Kardinalität = 3) eingetragen. Die Indextabelle könnte so aussehen:
männl. weibl. ledig verh. gesch. (Fritz) 1 0 0 1 0 (Willi) 1 0 1 0 0 (Emil) 1 0 0 0 1 (Anne) 0 1 0 1 0 (Hans) 1 0 0 1 0
Wie bei allen Datenbankindizes existiert von jedem dieser Einträge ein Verweis auf einen (externen) Datenbankeintrag.
Das Durchsuchen der (vorzugsweise intern gespeicherten) Indextabelle geschieht über einfache binäre Operationen, im Beispiel über UND-Verknüpfung mit einer Suchmaske. Sucht man in dem Beispiel nach Personen die männlich und verheiratet sind, so ist die Suchmaske 10 010 (die Verweise der Treffer führen zu Fritz und Hans).
Ausnutzung der binären Operationen auf Prozessorebene bietet einen Geschwindigkeitsvorteil bei Vergleichsoperationen. Durch diese Repräsentation wird Rechenaufwand gegen Speicherplatz getauscht.
Abbildung des Wertebereichs
Die Zuordnung von einem Wert eines Wertebereichs zu einem Bitvektor geschieht durch die Wahl der Basis des Bitvektors. Wird jedem Wert des Wertebereichs eindeutig ein einziger Bitvektor zugeordnet, so entspricht die Länge des Bitvektors im einfachen Fall genau der Kardinalität des Wertebereichs und ist gleichzeitig Basis des Bitvektors. Ein Vorteil dieser Darstellung ist Möglichkeit einzelne Werte eines Wertebereichs auszulassen, wenn diese nicht in vorliegenden Daten vorkommen. Weiterhin besteht die Möglichkeit eine nicht uniforme Basis anzugeben.
Encodierungs Schemata
Es können unterschiedliche binäre Repräsentationen gewählt werden, die je nach Informationsbedürfsnis unterschiedliche Eigenschaften in der Auswertung haben.
Literatur
- Chee-Yong Chan und Yannis Ioannidis. Bitmap Index Design and Evaluation. Proceedings of the 1998 ACM SIGMOD Conference.