Bitmap index

Bitmap index

Ein Bitmapindex ist ein Datenbankindex, der dazu dient, mehrdimensionale Daten effizient zu indizieren. Auf Grund seiner Eigenschaften findet der Bitmapindex vor allem bei Data Warehouses Einsatz.

Die Bezeichnung rührt daher, dass der Bitmapindex 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.

Inhaltsverzeichnis

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.

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Bitmap index — A bitmap index is a special kind of database index.Bitmap indexes have traditionally been considered to work well for data such as gender, which has a small number of distinct values, e.g., male and female, but many occurrences of those values.… …   Wikipedia

  • 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… …   Deutsch Wikipedia

  • Index (database) — A database index is a data structure that improves the speed of data retrieval operations on a database table at the cost of slower writes and increased storage space. Indexes can be created using one or more columns of a database table,… …   Wikipedia

  • Index (base de donnees) — Index (base de données) En informatique, et en particulier dans le contexte des bases de données, un index est un élément de redondance que l on va spécifier pour permettre au Système de Gestion de Base de Données d optimiser certaines requêtes.… …   Wikipédia en Français

  • Bitmap Brothers — The Bitmap Brothers war ein Entwicklerstudio für Computerspiele aus Großbritannien. Das Entwicklerstudio programmierte mehrere Spiele für den Amiga und den Atari ST und gehörte zu den erfolgreichsten Entwicklern für diese Plattformen. Ihre… …   Deutsch Wikipedia

  • Index (base de données) — En informatique, dans les bases de données, un index est une structure de données utilisée et entretenue par le système de gestion de base de données (SGBD) pour lui permettre de retrouver rapidement les données. L utilisation d un index… …   Wikipédia en Français

  • BitMaP — Windows bitmap Pour les articles homonymes, voir BMP. Windows bitmap Extension de fichier .bmp Type MIME image/x ms bmp (non officiel) Type de format …   Wikipédia en Français

  • Windows Bitmap — Vorlage:Infobox Dateiformat/Wartung/Standard fehltVorlage:Infobox Dateiformat/Wartung/Website fehlt Windows Bitmap Dateiendung: .bmp, .dib MIME Type: image/x ms bmp, image/x bmp, image/bmp …   Deutsch Wikipedia

  • Windows/OS2 Bitmap — Windows Bitmap („BMP“) oder device independent bitmap (DIB) ist ein zweidimensionales Rastergrafikformat, das für die Betriebssysteme Microsoft Windows und OS/2 entwickelt und mit Windows 3.0 eingeführt wurde. Die Dateiendung ist .bmp, seltener… …   Deutsch Wikipedia

  • Windows bitmap — („BMP“) oder device independent bitmap (DIB) ist ein zweidimensionales Rastergrafikformat, das für die Betriebssysteme Microsoft Windows und OS/2 entwickelt und mit Windows 3.0 eingeführt wurde. Die Dateiendung ist .bmp, seltener .dib.… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”