UB-Baum

Der UB-Baum („Universal B-Tree“) wurde von Rudolf Bayer und Volker Markl vorgeschlagen und ist eine Datenstruktur für mehrdimensionale Datenbanksysteme. Es ist ein B⁺-Baum, bei dem die Daten nach der Z-Kurve (Berechnen der Z-Werte durch bitweise Verschränkung der Schlüssel) sortiert abgelegt werden. Die Kernidee dieses Verfahrens wurde schon sehr viel früher (für Suchbäume im Allgemeinen von Tropf und Herzog^[1] sowie für B-Bäume von Orenstein und Merrett^[2]) vorgeschlagen.

Einfügen, Löschen und exakte Anfragen werden behandelt wie bei normalen B+ Bäumen. Für mehrdimensionale Bereichsanfragen benötigt man ein Verfahren, um, ausgehend von einem in der Datenstruktur angetroffenen Z-Wert, den nächsten zu finden, der innerhalb des mehrdimensionalen Suchbereichs liegt.

Das hierfür ursprünglich von Rudolf Bayer angegebene Verfahren war im Aufwand exponentiell mit der Anzahl der Dimensionen und somit für mehr als 4 Dimensionen nicht praktisch verwendbar^[3]. Eine Lösung für das Problem („crucial part of the UB-tree range query“), linear mit der Bitlänge der Z-Werte, wurde später beschrieben^[4] („GetNextZ-address“); diese Methode war bereits beschrieben worden in ^[1] ("BIGMIN"-Berechnung).

Siehe auch

Quadtree, K-d-Baum, R-Baum, Bereichsbaum, Gridfile als Alternative

Einzelnachweise

1. ↑ ^{a b} [1]H. Tropf, H. Herzog: Multidimensional Range Search in Dynamically Balanced Trees, Angewandte Informatik, 2/1981, pp 71-77.
2. ↑ [2]J. A. Orenstein and T. H. Merrett. A Class of Data Structures for Associative Searching. In PODS, 1984.
3. ↑ [3]V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999.
4. ↑ [4]F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp 263-272.