imported>Invisigoth67: form

2024-12-17T15:12:53Z

form

Neue Seite

Der '''UB-Baum''' („Universal B-Tree“) wurde von [[Rudolf Bayer (Informatiker)|Rudolf Bayer]] und [[Volker Markl]] vorgeschlagen und ist
eine Datenstruktur für mehrdimensionale Datenbanksysteme. Es ist ein [[B+-Baum|B<sup>+</sup>-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<ref name="tropf">[https://hermanntropf.de/media/multidimensionalrangequery.pdf H. Tropf, H. Herzog: Multidimensional Range Search in Dynamically Balanced Trees, Angewandte Informatik, 2/1981, pp 71-77.] (PDF; 1,5 MB)</ref> sowie für B-Bäume von Orenstein und Merrett<ref>[http://portal.acm.org/citation.cfm?id=588037 J. A. Orenstein and T. H. Merrett. A Class of Data Structures for Associative Searching. In PODS, 1984.]</ref>) 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.<ref>{{Webarchiv|url=http://mistral.informatik.tu-muenchen.de/results/publications/Mar99.pdf |wayback=20160304044305 |text=V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999. }} (PDF; 1,4 MB)</ref> Eine Lösung für das Problem („crucial part of the UB-tree range query“), wurde später beschrieben<ref>{{Webarchiv|url=http://mistral.informatik.tu-muenchen.de/results/publications/RMF+00.pdf |wayback=20160304060154 |text=F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp. 263–272. }} (PDF; 136 kB)</ref>. Eine Lösung war bereits viel früher beschrieben worden in<ref name="tropf"/> („BIGMIN/LITMAX“-Berechnung).

== Siehe auch ==
* [[Quadtree]]
* [[K-d-Baum]]
* [[R-Baum]]
* [[Bereichsbaum]]
* [[Gridfile]] als Alternative

== Einzelnachweise ==
<references />

[[Kategorie:Suchbaum]]
[[Kategorie:Datenbankindex]]

UB-Baum - Versionsgeschichte

imported>Invisigoth67: form