El árbol UB propuesto por Rudolf Bayer y Volker Markl es un árbol equilibrado para almacenar y recuperar de manera eficiente datos multidimensionales . 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 en 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 próximo valor Z que se encuentre 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"). Más adelante se describió una solución para esta "parte crucial de la consulta de rango del árbol UB". [2] Este método ya se describió en un artículo anterior [3] donde se propuso por primera vez el uso del orden Z con árboles de búsqueda.