Ugrás a tartalomhoz

R+ tree

A Wikiszótárból, a nyitott szótárból


Főnév

R+ tree (tsz. R+ trees)

  1. (informatika) Az R+ fa (R+ tree) egy térbeli adattároló adatstruktúra, amelyet térbeli objektumok (pl. pontok, vonalak, téglalapok, poligonok, stb.) hatékony keresésére használnak, főleg adatbázisokban, GIS rendszerekben (földrajzi információs rendszerek), CAD alkalmazásokban, stb.

A R+ tree az R-tree egyik módosított változata, célja a keresési hatékonyság növelése, bizonyos kompromisszumokkal.

  • R-tree: egy hierarchikus fa szerkezet, amelyben a belső csomópontok téglalap alakú tartományokat (MBR – minimum bounding rectangle) reprezentálnak, és a levelek tartalmazzák az adatobjektumokat.
  • R+ tree: hasonló szerkezet, de az átfedések elkerülésére törekszik → egy objektum több részre is felosztható, és több levélcsomópontban is tárolható.

Kulcs különbség R-tree vs. R+ tree

R-tree R+ tree
Egy objektum 1 levélben van Objektum több levélben is lehet
MBR-k átfedhetik egymást Belső csomópontok MBR-jai nem fedhetik egymást
Keresés során sok ág követhető Keresés során egyetlen ágat követünk
Egyszerűbb beszúrás/törlés Bonyolultabb beszúrás/törlés
Lassabb keresés Gyorsabb keresés (kevesebb átlapolás miatt)


Motiváció

Az R-tree egyik hátránya, hogy a belső csomópontok átfedhetik egymást → keresésnél gyakran több ágon is végig kell menni.

→ Az R+ tree megoldja ezt úgy, hogy:

  • Belső csomópontok tartományai nem fedhetik egymást
  • Ha egy objektum több tartományba esik → szétvágjuk → több helyen tároljuk

→ Ez drágább beszúrás/törlés esetén, de sokkal gyorsabb keresést eredményez.


Felépítés

Csúcstípusok

  • Belső csomópont (internal node):
    • Gyermekekre mutató pointereket és hozzájuk tartozó MBR-eket tartalmaz
    • Belső csomópontok MBR-jei nem fedhetik egymást!
  • Levélcsomópont (leaf node):
    • Objektumokra mutató pointereket tartalmaz
    • Egy objektum több levélben is tárolható → ha az MBR-jének több belső csomóponthoz is kell tartoznia


Műveletek

1. Keresés (Search)

  • Előny az R-tree-hez képest → mivel nincs átfedés → csak 1 út járható végig a fában.
  • Ha egy keresett téglalap egy belső csomópont több MBR-jébe is esne → az R+ tree szerkezete miatt az objektum minden releváns ágba be van másolva.

Algoritmus:

  1. Kezdjük a gyökérnél.
  2. Minden csomópontban kiválasztjuk azokat a gyermekeket, amelyek MBR-jébe beleesik a keresett téglalap.
  3. Mivel nincs átfedés → determinisztikus → egy útvonal követhető le.
  4. Leveleknél megnézzük az objektumokat.

2. Beszúrás (Insertion)

  • Hasonló az R-tree-hez, de átfedés nem megengedett:
    • Ha az objektum egy MBR-be nem fér be, akkor:
      • Objektumot daraboljuk (splitting) → minden érintett ágba beszúrjuk a megfelelő részét.
  • Ha egy csomópont megtelik, felbontjuk (split).

→ Beszúrás bonyolultabb, mint az R-tree-ben.

3. Törlés (Deletion)

  • Objektumot az összes levélcsomópontból ki kell törölni, ahol jelen van.
  • Ha a törlés után egy csomópont alultöltött → lehet hogy újraépítés vagy egyesítés (merge) szükséges.


Példa

Tegyük fel, hogy ilyen objektumokat akarunk tárolni:

  • Téglalapok a síkon.

Ha a következő objektumokat tároljuk:

  • Téglalap A
  • Téglalap B
  • Téglalap C

→ Ha az A téglalap átfedné a belső csomópontok MBR-jének határát, akkor R-tree-ben egy helyre kerülne (és a belső MBR-k is átfednének). → Az R+ tree-ben → az A objektumot felbontjuk és több levélbe másoljuk be.


Előnyök

✅ Gyors keresés:

  • Egyértelmű útvonal a fában (nincs backtracking)

✅ Jó teljesítmény pont- és területkereséseknél

✅ Kisebb keresési idő mint R-tree-ben → konstans faktorral gyorsabb lehet.


Hátrányok

❌ Objektumok több példányban is szerepelhetnek → helyigény nőhet.

❌ Beszúrás és törlés bonyolultabb:

  • Objektumok darabolása
  • Többszörös beszúrás
  • Többszörös törlés


Mikor használjuk?

  • GIS rendszerekben, ahol gyors térbeli keresés kell
  • CAD alkalmazásokban
  • 3D-s játékokban → gyors láthatósági/ütközés tesztelés
  • Térbeli adatbázisok (pl. PostGIS, Oracle Spatial)

→ Ha sok olvasás, kevés írás van → R+ tree jó választás.

→ Ha sok beszúrás/törlés → R-tree vagy más alternatíva lehet jobb.


Összehasonlítás más struktúrákkal

Adatstruktúra Fő tulajdonság
QuadTree Rekurzív térbeli négy részre bontás
KD-Tree Axis-aligned partíciók, pontokra jó
R-Tree Általános térbeli objektumokra jó
R+ Tree Gyors keresés, átfedés nélküli MBR-k
R* Tree Optimalizált R-tree (jobb eloszlás)


Összefoglalás

  • R+ tree egy R-tree variáns → fő célja a keresés gyorsítása.
  • Az átfedés megszüntetése érdekében objektumokat többször is tárolhat.
  • Beszúrás/törlés bonyolultabb, keresés viszont sokkal hatékonyabb.
  • Használati eset: ahol gyors olvasási teljesítmény kritikus.


Egyszerű ábra (vizuális szemléltetés):

R-Tree:                        R+ Tree:

 [A]                           [A1][A2]
 / \                             |   |
[B] [C]                       [B]   [C]
 |    |                          |     |
obj1  obj2                    obj1  obj2
                                A1 A2 (két példány)
A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=R%2B_tree&oldid=3502573”