UB-Baum – Wikipedia

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“), wurde später beschrieben^[4]. Eine Lösung war bereits viel früher beschrieben worden in ^[1] („BIGMIN/LITMAX“-Berechnung).

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

1. ↑ ^{a b} H. Tropf, H. Herzog: Multidimensional Range Search in Dynamically Balanced Trees, Angewandte Informatik, 2/1981, pp 71-77. (PDF; 1,5 MB)
2. ↑ J. A. Orenstein and T. H. Merrett. A Class of Data Structures for Associative Searching. In PODS, 1984.
3. ↑ V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999. (Memento vom 4. März 2016 im Internet Archive) (PDF; 1,4 MB)
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. (Memento vom 4. März 2016 im Internet Archive) (PDF; 136 kB)