szó jelentését keresi. A DICTIOUS-ban nem csak a
szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a
szót egyes és többes számban mondani. Minden, amit a
szóról tudni kell, itt található. A
szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. A
és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.
Főnév
R-tree (tsz. R-trees)
- (informatika) Az R-tree egy speciális hierarchikus adattároló fa, amelyet térbeli adatok (spatial data) indexelésére fejlesztettek ki. Ilyen adatok lehetnek például:
- geometriai objektumok: pontok, vonalak, poligonok (pl. térképeken utak, területek)
- téglalap alakú (bounding box) körülhatárolások: képekben, CAD rendszerekben, adatbázisokban
Az R-tree-t 1984-ben javasolta Antonin Guttman a “R-trees: A Dynamic Index Structure for Spatial Searching” című publikációban.
Motiváció
A hagyományos adatbázis indexelési technikák (például B-tree, B+-tree) lineáris vagy egydimenziós adatokra optimalizáltak.
Probléma:
- Hogyan indexeljünk térbeli objektumokat, amelyek nem pontszerűek, hanem kiterjedéssel rendelkeznek?
- Hogyan lehet hatékonyan végrehajtani olyan kereséseket, mint pl. “mely poligonok metszenek egy adott téglalapot?” vagy “mely objektumok vannak ebben a körben?”?
Megoldás: az R-tree.
Alapötlet
Az R-tree téglalapokat (bounding boxokat) használ, hogy hierarchikusan csoportosítsa a térbeli objektumokat.
- Minden objektumhoz hozzárendelünk egy legkisebb befoglaló téglalapot (MBR - Minimum Bounding Rectangle).
- Ezeket az MBR-eket hierarchikus szinteken helyezzük el.
- A belső csomópontok olyan téglalapokat tartalmaznak, amelyek a gyermekcsomópontok MBR-jeit fedik le.
Az eredmény: hierarchikus fa, ahol a gyökérből lefelé haladva egyre finomabb térbeli felbontást kapunk.
Fa felépítése
Az R-tree B-tree-hez hasonló:
- Minden csomópont egy lemezes blokk (disk page) – optimalizált I/O.
- Minden csomópontban van minimum m és maximum M bejegyzés (gyermek vagy adat).
- Belső csomópontok: MBR + pointer a gyermekcsomópontra.
- Levelek: MBR + pointer az eredeti objektumra.
Általános szerkezet
Gyökér
├── Belső csomópont
│ ├── Belső csomópont
│ │ ├── Levélcsomópont
│ │ ├── Levélcsomópont
│ ├── Belső csomópont
│ ├── Levélcsomópont
│ ├── Levélcsomópont
Minimális és maximális M értékek
- M: csomópont kapacitása (pl. 50)
- m: alsó korlát (pl. M/2 → 25)
Műveletek
1. Keresés (Search)
Például: mely objektumok metszik az adott kereső téglalapot?
Algoritmus:
- Indulás a gyökérből.
- Rekurzívan bejárjuk azokat a gyermekcsomópontokat, amelyek MBR-je metszi a kereső téglalapot.
- A levelek szintjén ellenőrizzük az egyes objektumokat.
- Eredmény: a megfelelő objektumok halmaza.
Jellemzője: hatékony, mert sok ágat korán kizárunk (MBR alapján).
2. Beszúrás (Insert)
Új objektum beszúrása:
- Számítsuk ki az új objektum MBR-jét.
- Induljunk a gyökérből, és válasszuk azt az ágat, amelyhez legkisebb bővítést kell végezni az MBR-en.
- Haladjunk lefelé a levelekig.
- Ha a levél csomópont tele van, akkor felosztás történik (split), a fa egyensúlya megmarad.
- MBR-eket visszafele frissítjük.
3. Törlés (Delete)
- Keressük meg a levélben az eltávolítandó objektumot.
- Töröljük a bejegyzést.
- Ha a csomópont alulcsordul (m alá esik), újraszervezzük a fát (reinsert vagy egyesítés).
R-tree változatok
1. R*-tree
- R-tree* (Beckmann et al., 1990) a gyakorlatban a legjobban teljesítő** variáns.
- Fő újítások:
- Jobb beszúrási heurisztika.
- Minimális átfedés a csomópontok között.
- Újraszervezés beszúráskor (reinsert technika).
- Nagyon elterjedt adatbázis rendszerekben (pl. PostGIS, MySQL Spatial, Oracle Spatial).
2. R+-tree
- MBR-ek nem átfedhetik egymást a belső csomópontokban → gyorsabb keresés.
- Hátrány: egy objektum többször is előfordulhat (több ágra másolódik).
3. R++-tree
- Teljes átfedésmentességet próbál elérni, de bonyolultabb és ritkábban használt.
Alkalmazások
R-tree-t használják bármilyen térbeli indexelési feladatra:
- GIS rendszerek (geographical information systems)
- CAD rendszerek (computer-aided design)
- 3D modellek kezelésére
- Játékok (collision detection, spatial partitioning)
- Térképek, navigációs rendszerek
- Képadatbázisok, multimédiás keresés
Előnyök
✅ Hatékony a térbeli keresésekben (range query, intersection query).
✅ Dinamikus: könnyen bővíthető, törölhető.
✅ Többdimenziós: 2D, 3D vagy akár n-D tér is kezelhető.
✅ Lemezhez optimalizált (disk-friendly): B-tree-re emlékeztető blokk alapú működés.
Hátrányok
❌ Átfedések miatt a keresés több ágat is kénytelen bejárni (→ R*-tree javít ezen).
❌ Nem hatékony pontszerű adatokra → quad-tree, kd-tree jobbak.
❌ Fa degenerálódhat, ha a beszúrás rossz térbeli eloszlású.
Összehasonlítás más térbeli adatszerkezetekkel
| Adatszerkezet
|
Legjobb felhasználás
|
Korlátok
|
| R-tree
|
Általános térbeli adatok
|
Átfedés
|
| R*-tree
|
Legjobb teljesítmény
|
Komplex beszúrás
|
| R+-tree
|
Gyors keresés
|
Duplikált objektumok
|
| kd-tree
|
Pontok, kisméretű adatok
|
Nem skáláz jól lemezre
|
| quad-tree
|
2D felosztás, pontok
|
Kevésbé hatékony nagy objektumokra
|
| BVH (Bounding Volume Hierarchy)
|
Játékokban, collision detection
|
Fadekonstrukció bonyolult
|
Példa
Tegyük fel, hogy van 5 poligon:
- P1: (1,1) - (2,2)
- P2: (3,3) - (5,5)
- P3: (2,4) - (4,6)
- P4: (6,1) - (7,3)
- P5: (5,5) - (7,7)
A fa hierarchikusan csoportosítja ezeket az MBR-eket:
Gyökér
├── MBR1
│ ├── P1
│ ├── P2
│ ├── P3
├── MBR2
│ ├── P4
│ ├── P5
Ha pl. keresünk az (3,3)-(4,4) téglalapban:
- Csak azokat az ágakat nézzük, ahol az MBR metszi a kereső téglalapot → gyorsabb, mint minden poligont ellenőrizni.
Összegzés
Az R-tree egy alapvető fontosságú adatstruktúra a térbeli adatok kezelésében.
- Hierarchikus, dinamikus.
- Hatékony térbeli lekérdezésekhez.
- Széles körben alkalmazzák GIS, CAD, multimédia, játékfejlesztés területén.
- **R-tree* a gyakorlatban az egyik legjobb variáns.