Hilbert R-tree

Hilbert R-tree (tsz. Hilbert R-trees)

1. (informatika) A Hilbert R-tree az R-tree egy speciális továbbfejlesztése, amelyet a térbeli adatokhoz használnak, de sokkal jobb keresési teljesítményt kínál azáltal, hogy:

✅ Csökkenti az MBR-ek közötti átfedést ✅ Csökkenti a fastruktúra “szétesését” (degenerációját) ✅ Jobb térbeli lokalitást biztosít → hatékonyabb disk I/O

Az R-tree hierarchikus téglalapokra épül, de sokszor probléma:

• Az MBR-ek átfedik egymást → sok ágat be kell járni keresésnél.
• Random eloszlású adatok esetén az R-tree nem lesz hatékony.

Hilbert R-tree → a megoldás: 👉 Használjunk egy egyedi sorrendezést a térbeli objektumokra → Hilbert görbe!

A Hilbert görbe egy folyamatos, rekurszív, önmagát lefedő fraktálgörbe, amely kitölti a síkot (space-filling curve):

• Egy 1D görbét vetít a 2D térre, úgy hogy a szomszédos pontok a görbén is szomszédosak a síkban.
• Így a térbeli közelség megmarad → jobb adateloszlás a fában.

+---+---+
| a | b |
+---+---+
| d | c |
+---+---+

Bejárási sorrend:

1. a
2. b
3. c
4. d

Növekvő Hilbert index szerint.

Minden térbeli objektumot (pl. poligon MBR-jét, pontot) hozzárendelünk egy:

• Hilbert indexhez (Hilbert value, Hilbert key).

Ez a Hilbert index:

• egyetlen 1D szám, amely a térbeli pozícióját “kódolja”.
• Ezen az indexen rendezzük az objektumokat → térbeli lokalitás megőrzése!

• Alapja ugyanaz, mint az R-tree: hierarchikus fa MBR-ekkel.
• De minden objektumhoz tároljuk a Hilbert indexet.
• A csomópontok növekvő Hilbert index szerint vannak rendezve → térbeli közeli objektumok a fán belül is közel kerülnek.

Levelek: (Hilbert index, MBR, objektum pointer)

Belső csomópontok: (legnagyobb Hilbert index a gyermekben, gyermek pointer, MBR)

• Számoljuk ki az új objektum Hilbert indexét.
• Keressük meg a megfelelő csomópontot Hilbert index alapján (binary search vagy scan).
• Illesszük be.
• Ha a csomópont tele → split, MBR frissítés.

• Ugyanúgy működik, mint az R-tree-ben.
• De mivel a Hilbert index alapján rendezettek a csomópontok, a keresési bejárás sokkal hatékonyabb → kevesebb branch!

• Keressük meg a Hilbert index szerint.
• Töröljük.
• Újraszervezzük a fát szükség esetén.

✅ Nagyon alacsony MBR átfedés → kevesebb keresési branch → gyorsabb keresés. ✅ Térbeli közelség jól megmarad a fán belül. ✅ Jó lemezes I/O → cache-barát, mert a hasonló adatok egymás mellett tárolódnak. ✅ Pontszerű adatokra is kiváló (ellentétben a hagyományos R-tree-vel).

❌ A Hilbert index kiszámítása nem triviális → külön algoritmus kell. ❌ Beszúrás költségesebb lehet, mivel globális sorrendet kell tartani → többet kell frissíteni. ❌ Törlés is bonyolultabb, ha meg akarjuk tartani a tökéletes Hilbert sorrendet. ❌ Térbeli változás esetén (mozgó objektumok) újra kell Hilbert indexet számolni.

• Geoadatbázisok (pl. térképadatok, POI-k, GPS útvonalak)
• Multimédiás adatbázisok (pl. képkeresés bounding box alapján)
• Adattárházak, ahol térbeli clustering fontos
• Nagy térbeli időbeli adatok (pl. IoT szenzoradatok → tér + idő kombináció)
• Játékfejlesztés: collision detection, spatial queries → nagyon gyors!

struct Entry {
    uint64_t hilbertIndex;
    Rectangle mbr;
    Object* obj;
};

struct Node {
    bool isLeaf;
    vector<Entry> entries;
    vector<Node*> children;
};

Keresés során:

void search(Node* node, Rectangle query, vector<Object*>& results) {
    for (auto& entry : node->entries) {
        if (entry.mbr.intersects(query)) {
            if (node->isLeaf) {
                results.push_back(entry.obj);
            } else {
                search(node->children], query, results);
            }
        }
    }
}

Beszúrás során:

• Hilbert indexet kiszámoljuk.
• Oda helyezzük, ahol a Hilbert index szerint kell.
• Split esetén is Hilbert sorrendet tartunk.

👉 A Hilbert R-tree a legteljesítményesebb R-tree típusok közé tartozik:

• Nagyon gyors keresés → kevesebb átfedés, lokalitásmegőrzés.
• Széles körben használják nagy térbeli adatbázisoknál.
• Hátránya: a beszúrás/törlés komplexebb, de statikus vagy ritkán változó adatokra tökéletes.

👉 Minden modern GIS rendszerben, sok NoSQL motorban, adattárházakban már Hilbert R-tree vagy hasonló space-filling curve alapú indexet használnak.

• Hilbert R-tree - Szótár.net (en-hu)
• Hilbert R-tree - Sztaki (en-hu)
• Hilbert R-tree - Merriam–Webster
• Hilbert R-tree - Cambridge
• Hilbert R-tree - WordNet
• Hilbert R-tree - Яндекс (en-ru)
• Hilbert R-tree - Google (en-hu)
• Hilbert R-tree - Wikidata
• Hilbert R-tree - Wikipédia (angol)