El árbol UB propuesto por Rudolf Bayer y Volker Markl es un árbol equilibrado para almacenar y recuperar datos multidimensionales de manera eficiente . Básicamente es un árbol B + (información solo en las hojas) con registros almacenados según el orden Z , también llamado orden Morton. El orden Z se calcula simplemente entrelazando las claves bit a bit.
La inserción, eliminación y consulta de puntos se realizan como con los árboles B + ordinarios. Sin embargo, para realizar búsquedas de rango en datos de puntos multidimensionales, se debe proporcionar un algoritmo para calcular, a partir de un punto encontrado en la base de datos, el siguiente valor Z que está en el rango de búsqueda multidimensional.
El algoritmo original para resolver este problema clave era exponencial con la dimensionalidad y, por lo tanto, no era factible [1] ("GetNextZ-address"). Una solución a esta "parte crucial de la consulta de rango de árbol UB" lineal con la longitud de bits de la dirección z se ha descrito más adelante. [2] Este método ya se ha descrito en un artículo anterior [3] donde se propuso por primera vez el uso del orden Z con árboles de búsqueda.
Referencias
- ^ Markl, V. (1999). "MISTRAL: Procesamiento de consultas relacionales mediante una técnica de acceso multidimensional". CiteSeerX 10.1.1.32.6487 . Cite journal requiere
|journal=
( ayuda ) - ^ Ramsak, Frank; Markl, Volker; Fenk, Robert; Zirkel, Martin; Elhardt, Klaus; Bayer, Rudolf (10 al 14 de septiembre de 2000). Integración del árbol UB en un núcleo de sistema de base de datos (PDF) . 26ª Conferencia Internacional sobre Bases de Datos Muy Grandes . págs. 263-272.
- ^ Tropf, H .; Herzog, H. "Búsqueda de rango multidimensional en árboles dinámicamente equilibrados" (PDF) . Angewandte Informatik (Informática aplicada) (2/1981): 71–77. ISSN 0013-5704 .