Hilbert Çeşidləməsi

Verilənlər bazasındakı elementlərin ədədi açara görə yerləşdirilməsi nəinki konkret elementin axtarışını asanlaşdırır, həm də mərkəzi prosessorun keşindən daha səmərəli istifadəyə kömək edir: istənilən ardıcıl yaddaş seqmenti yaxın açar dəyərlərinə malik elementləri ehtiva edir. Bu, məsələn, açarları verilmiş aralıqda olan bütün elementlərə müraciət edildikdə xüsusilə faydalıdır.

Açarlar iki ölçülü şəbəkədəki nöqtələri təmsil etdikdə, məsələn GPS-naviqasiya sistemlərində olduğu kimi, vəziyyət mürəkkəbləşir. Əgər $(x,y)$ nöqtələri əvvəlcə $x$-ə, sonra isə $y$-ə görə çeşidlənsə, yaddaşda yanaşı yerləşən elementlər eyni $x$ dəyərlərinə malik olacaq, lakin $y$ dəyərlərinə görə əhəmiyyətli dərəcədə fərqlənə bilər. Eyni zamanda, eyni $y$ dəyərlərinə malik nöqtələr müstəvidə bir-birindən uzaqda yerləşə bilər. Məkansal lokalığı daha yaxşı qorumaq üçün məlumatlar fəzanı dolduran kəsilməz əyri boyunca çeşidlənir.

Belə əyrilərdən birini — Hilbert əyrisini nəzərdən keçirək. O, $(0,0)$ nöqtəsindən başlayır və $(S,0)$ nöqtəsində bitir, $(0,0)$ və (S, S) künclü kvadratın bütün nöqtələrindən keçir. Əyri rekursiv olaraq aşağıdakı kimi qurulur: kvadrat ümumi (S/2, S/2) nöqtəsi olan dörd bərabər hissəyə bölünür, bundan sonra hər hissə tam Hilbert əyrisinin kiçildilmiş və müvafiq şəkildə fırladılmış nüsxəsi ilə doldurulur.

Əvvəlcə sol alt kvadrat doldurulur — əyri $(0,0)$-dan (0, S/2)-yə keçir. Sonra sol üst kvadrat doldurulur — (0, S/2)-dən (S/2, S/2)-yə. Bundan sonra sağ üst kvadrat işlənir — (S/2, S/2)-dən (S, S/2)-yə. Nəhayət, sağ alt kvadrat doldurulur — (S, S/2)-dən $(S,0)$-a.

Digər tərəfdən, Hilbert əyrisi sınıq xətlər ardıcıllığının hədd obyekti kimi də baxıla bilər, onların ilk bir neçəsi şəkildə göstərilmişdir.

Sizə çeşidlənməsi tələb olunan nöqtələr toplusu verilir; onlar Hilbert əyrisi ilə bypass edilmə sırasına görə çeşidlənməlidir. Əyri sonsuz sayda özü-özünü kəssə də (məsələn, (S/2, S/2) nöqtəsində), $S$-in tək ədəd olması şərti tam koordinatlı hər nöqtənin tam olaraq bir dəfə ziyarət edildiyinə zəmanət verir.