The UB-tree as proposed by Rudolf Bayer and Volker Markl is a balanced tree for storing and efficiently retrieving multidimensional data. It is basically a B+ tree (information only in the leaves) with records stored according to Z-order, also called Morton order. Z-order is simply calculated by bitwise interlacing the keys. Insertion, deletion, and point query are done as with ordinary B+ trees.
![UB-tree - Wikipedia](https://cdn-ak-scissors.b.st-hatena.com/image/square/b5010e22ea6e0c6823c7e52817c3b93faa04c159/height=288;version=1;width=512/https%3A%2F%2Fupload.wikimedia.org%2Fwikipedia%2Fcommons%2Fthumb%2F2%2F29%2FZ-curve45.svg%2F1200px-Z-curve45.svg.png)