Hilbert R-tree
Főnév
Hilbert R-tree (tsz. Hilbert R-trees)
- (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
Alapötlet
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!
Mi az a 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.
Hilbert görbe példája (2. rendű)
+---+---+ | a | b | +---+---+ | d | c | +---+---+
Bejárási sorrend:
- a
- b
- c
- d
Növekvő Hilbert index szerint.
Hilbert index
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!
Hilbert R-tree szerkezete
- 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.
Tárolás
Levelek: (Hilbert index, MBR, objektum pointer)
Belső csomópontok: (legnagyobb Hilbert index a gyermekben, gyermek pointer, MBR)
Működés
1. Beszúrás
- 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.
2. Keresé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!
3. Törlés
- Keressük meg a Hilbert index szerint.
- Töröljük.
- Újraszervezzük a fát szükség esetén.
Előnyök
✅ 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).
Hátrányok
❌ 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.
Összehasonlítás R-tree vs. Hilbert R-tree
| Tulajdonság | R-tree | Hilbert R-tree |
|---|---|---|
| Térbeli közelség | Gyenge | Jó (Hilbert görbe miatt) |
| MBR átfedés | Magas lehet | Alacsony |
| Keresés | O(n log n), sok branch | Sokkal gyorsabb, kevesebb branch |
| Beszúrás költsége | Alacsony | Közepes/magas |
| Törlés költsége | Alacsony | Magasabb |
| Pontszerű adatok | Nem optimális | Nagyon jó |
| Általános használat | GIS rendszerek, poligonok | Nagy térbeli adathalmazok, DB indexelés |
Tipikus alkalmazások
- 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!
Példakód (egyszerűsítve)
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[&entry - &node->entries[0]], 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.
Összefoglalás
👉 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)