A R-fák vannak adatstruktúrák formájában tengely használt űrkutatási módszerek . Többdimenziós információk ( földrajzi koordináták , téglalapok vagy sokszögek ) indexelésére szolgálnak . Antonin Guttman által 1984-ben feltalált R-fákat mind elméleti, mind alkalmazott összefüggésekben használják. Az R-fák tipikus felhasználási esete a földrajzi információk tárolása: például egy étterem éttermeinek elhelyezkedése a városban, vagy a térkép rajzait alkotó sokszögek (utak, épületek, partok stb.), Majd képes válaszolni az olyan kérdésekre, mint például "minden múzeum megtalálása 2 kilométeres körzetben", "az összes út megjelenítése 5 kilométeres körzetben" vagy "a tartózkodási helyemhez legközelebb eső benzinkút keresése. pozíció".
Az R-fákkal fel lehet gyorsítani a K legközelebbi szomszédok keresését is , különösen bizonyos mutatók, például a nagy kör távolsága esetén .
Az adatstruktúra fő gondolata az, hogy a közeli objektumokat a téglalap segítségével ábrázoljuk a fa következő magasabb szintjén (az R-fa "R" -je a "téglalap" kezdőbetűje). Más szavakkal, a fa egy adott csomópontjában tárolódnak az egyes részfák határoló téglalapjai , amelyeknek a szülője. Így a térinformációk keresésekor elegendő minden egyes ágnál ellenőrizni, hogy a keresett helyzet metszi-e a megfelelő téglalapot, és figyelmen kívül hagyni azokat a téglalaphoz tartozó ágakat, amelyeknek nincs metszéspontja. A fa minden levele egyetlen objektumot ír le, minden magasabb szint pedig egyre több objektum összegyűjtését írja le.
Mint egy B-fa , az R-fák is kiegyensúlyozott kutatási fák (minden levél azonos távolságra van a gyökértől), amelynek adatait oldalakba rendezik , és kifejezetten a lemezek tárolására vannak kijelölve. Például egy adatbázis esetében . Minden oldal maximális kapacitással rendelkezik, M jelöléssel (egy oldalon legfeljebb M bejegyzés található), és a fa garantálja az egyes oldalak minimális kitöltési arányát (a gyökér kivételével). Ez az oldalszervezés nagy mennyiségű adatra alkalmas: minden oldal szükség esetén betölthető a memóriába, még akkor is, ha az egész fa túl nagy volt ahhoz, hogy a memóriában tárolható legyen.
A térbeli keresési műveletek többségét ( metszéspont , befogadás , a legközelebbi szomszédok keresése ) az R-fa szerkezete egyszerűsíti: egy ág határoló téglalapját használjuk annak eldöntésére, hogy ott folytatjuk-e a feltárást, ami lehetővé teszi a legrelevánsabbak kiküszöbölését. csomópontok.
Az R-fák megvalósításának nehézsége abból adódik, hogy a fát egyensúlyban kell tartani, és el kell kerülni, hogy a határoló téglalapok túl sok üres teret fedjenek le, vagy hogy több téglalap ne takarja ugyanazt a területet. Enélkül az űrkutatási műveletek túl sok csomópont felesleges felderítését kockáztatnák, ami hatással lenne a teljesítményre. Kezdetben az elemek beillesztését úgy hajtották végre, hogy az elemet abba az alfába helyezték, amelynek a kötődoboza az új elem hozzáadásával növekedne a legkevésbé. Ha egy oldal megtelt, elosztjuk az elemeit, miközben megpróbáljuk minimalizálni a két részhalmaznak megfelelő téglalapok területét. Az R-fákkal kapcsolatos kutatások többsége az egyetlen adatforrásból felépített fa teljesítményének optimalizálására törekszik ( tömeges betöltés ), vagy éppen ellenkezőleg, a fa optimalizálására abban az esetben, ha az adatokat inkrementálisan adják hozzá.
Bár az R-fák a legrosszabb esetben sem nyújtanak jó elméleti teljesítményt, a gyakorlatban nagyon hatékonyak. Vannak olyan változatok, amelyek garantálják az optimalizálást a legrosszabb esetben a tömeges rakodáshoz is , de megvalósításuk bonyolultsága korlátozza a gyakorlati alkalmazásokban való felhasználásukat.
Az a képesség, hogy gyorsan megtalálja a távoli objektumok r egy adott pont vagy k legközelebbi szomszéd (abban az értelemben, bármilyen norme- p ) egy térbeli csatlakozzon művelet alapja sok algoritmus, amely támaszkodik a hatékony végrehajtás ilyen művelet, például a csoportosítás vagy anomáliák érzékelésére .