Árbol UB

El árbol UB , también conocido como árbol B universal , ^{[ 1 ]} propuesto por Rudolf Bayer y Volker Markl, es un árbol equilibrado para almacenar y recuperar eficientemente datos multidimensionales . Al igual que un árbol B+ , la información se almacena únicamente en las hojas. Los registros se almacenan según el orden Z , también llamado orden de Morton. El orden Z se calcula mediante el entrelazado bit a bit de las claves.

La inserción, la eliminación y la consulta de puntos se realizan como en los árboles B+ convencionales. 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 se encuentre dentro del rango de búsqueda multidimensional.

El algoritmo original para resolver este problema clave era exponencial con la dimensionalidad y, por lo tanto, no factible ^{[ 2 ]} ("GetNextZ-address"). Una solución a esta "parte crucial de la consulta de rango del árbol UB" se ha descrito más adelante. ^{[ 3 ]} Este método ya se ha descrito en un artículo anterior ^{[ 4 ]} donde se propuso por primera vez el uso del orden Z con árboles de búsqueda.