Bitmap-Index
Ein Bitmap-Index ist ein Datenbankindex, der dazu dient, mehrdimensionale Daten effizient zu indizieren. Auf Grund seiner Eigenschaften findet der Bitmap-Index vor allem bei Data Warehouses Einsatz.
Die Bezeichnung rührt daher, dass der Bitmap-Index ein oder mehrere Attribute in Form eines Bitmusters (engl. Bitmap) speichert. Er ist vor allem sinnvoll einsetzbar für die Indizierung von Tabellenspalten mit einer geringen Kardinalität (Anzahl der in dieser Spalte vorhandenen unterschiedlichen Werte). Das ist genau der Bereich, in dem ein konventioneller Index, realisiert durch einen B-Baum, keine Steigerung der Zugriffsperformance bringt.
Beispiel
Ein einfaches Beispiel: in einen Index einer Personendatenbank werden die Attribute Geschlecht (zwei mögliche Werte, Kardinalität = 2) und Familienstand (Kardinalität = 3) eingetragen. Die Indextabelle könnte so aussehen:
| Name | männlich | weiblich | ledig | verheiratet | geschieden |
|---|---|---|---|---|---|
| Anne | 0 | 1 | 0 | 1 | 0 |
| Emil | 1 | 0 | 0 | 0 | 1 |
| Fritz | 1 | 0 | 0 | 1 | 0 |
| Hans | 1 | 0 | 0 | 1 | 0 |
| Willi | 1 | 0 | 1 | 0 | 0 |
Funktionsweise
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 die Möglichkeit, einzelne Werte eines Wertebereichs auszulassen, wenn diese nicht in vorliegenden Daten vorkommen. Weiterhin besteht die Möglichkeit, eine nicht uniforme Basis anzugeben.
Literatur
- Chee-Yong Chan und Yannis Ioannidis: Bitmap Index Design and Evaluation. Proceedings of the 1998 ACM SIGMOD Conference.
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.