Z-Kurve

Die Z-Kurve (Lebesgue-Kurve, englisch Z-order curve) ist eine Abbildung, die Punkte aus dem mehrdimensionalen Raum in eine lineare Ordnung, die Z-Ordnung oder Morton-Ordnung, bringt, eine Ordnung mit nachbarschaftserhaltenden Eigenschaften: Wenn zwei Raumpunkte im Mehrdimensionalen nah beisammen liegen, liegen mit hoher Wahrscheinlichkeit auch ihre Z-Werte nah beisammen. Der Z-Wert eines Raumpunktes wird durch bitweises Verschränken der binären Koordinatenwerte berechnet.

Mit Hilfe der Z-Ordnung lassen sich (effiziente) Verfahren, die auf einer linearen Ordnung beruhen, ins Mehrdimensionale übertragen. Dazu gehört Binäres Suchen, Binärer Suchbaum, Skip-Liste, B-Baum, oder ein B⁺-Baum.

Für eine effiziente mehrdimensionale Bereichssuche ist ein Algorithmus erforderlich, um, ausgehend von einem in der Datenstruktur außerhalb des Suchbereichs angetroffenen Punkt, den nächstmöglichen Z-Wert im Suchbereich zu bestimmen (BIGMIN/LITMAX)

Die Z-Ordnung ist beliebt aufgrund ihrer guten Nachbarschaftserhaltung und der einfachen Berechenbarkeit der Z-Werte. Bei der Hilbert-Kurve ist die Nachbarschaftserhaltung besser, doch sind die Rechnungen komplizierter.

Anwendungen finden sich bei der Nachbarschaftssuche in Datenbanken, bei diversen technischen Anwendungen, sowie – zur besseren Nutzung der Speicherhierarchie – in der linearen Algebra.

1. ↑ G. M. Morton: A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing. In: Technical Report. IBM, Ottawa, Canada 1966 (englisch). 
2. ↑ H. Tropf, H. Herzog: Multidimensional Range Search in Dynamically Balanced Trees. (PDF; 1,4 MB) In: Angewandte Informatik, 2/1981, S. 71–77.

1. ↑ Streng genommen ist nicht diese Abbildung, sondern allenfalls ihre Umkehrung eine raumfüllende Kurve.