In
mathematical analysis and
computer science,
Z-order,
Morton order, or
Morton code is a
function which maps multidimensional data to one dimension while preserving locality of the data points. It was introduced in 1966 by G. M. Morton. The z-value of a point in multidimensions is simply calculated by interleaving the
binary representations of its coordinate values. Once the data are sorted into this ordering, any one-dimensional data structure can be used such as
binary search trees,
B-trees,
skip lists or (with low significant bits truncated)
hash tables. The resulting ordering can equivalently be described as the order one would get from a depth-first traversal of a
quadtree.