UB-Baum
aus Wikipedia, der freien Enzyklopädie
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 .
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.[1]. 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[2] ("GetNextZ-address") ; diese Methode war bereits beschrieben worden in [3] ("BIGMIN"-Berechnung), wo die Anwendung der Z-Kurve für Suchbäume erstmalig vorgeschlagen wurde.
[Bearbeiten] Siehe auch
Quadtree, K-d-Baum, R-Baum, Bereichsbaum, Gridfile als Alternative
[Bearbeiten] References
- ↑ [1]V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999.
- ↑ [2]F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Lage Databases, (VLDB) 2000, pp 263-272.
- ↑ [3]H. Tropf, H. Herzog: Multidimensional Range Search in Dynamically Balanced Trees, Angewandte Informatik, 2/1981, pp 71-77.
