R* fa | |||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Típusú | adatszerkezet | ||||||||||||
Feltalálás éve | 1990 | ||||||||||||
Szerző | Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider és Bernhard Seeger | ||||||||||||
Bonyolultság az O-szimbólumokban | |||||||||||||
|
|||||||||||||
Médiafájlok a Wikimedia Commons oldalon |
Az R*-fák a térinformációk indexelésére használt R-fák egy változata . Az R*-fák létrehozása valamivel magasabb költséggel jár, mint a szabványos R-fáké, mivel előfordulhat, hogy az adatokat újra kell rendezni (törlés + beszúrás), de az eredményül kapott fa általában jobb lekérdezési teljesítményt nyújt. A szabványos R-fához hasonlóan pontokat és térbeli adatokat is tárolhat. A fát Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider és Bernhard Seeger javasolta 1990-ben [1] .
A lefedettség és az átfedés minimalizálása fontos az R-fák teljesítménye szempontjából. Az átfedés azt jelenti, hogy adatlekérdezéskor vagy beszúráskor a fa egynél több ágát ki kell bontani (az adatok átfedhető területekre való felosztása miatt). A minimális lefedettség javítja a törlést azáltal, hogy lehetővé teszi a teljes oldalak gyakrabban történő kizárását a keresésekből, különösen a negatív tartományú lekérdezések esetében. Az R*-fa mindkét értéket megpróbálja csökkenteni a beolvasott csomópontfelosztó algoritmus és a csomóponttúlcsordulás esetén kényszerített újratelepítés koncepciójának kombinációjával. A megközelítés azon a megfigyelésen alapul, hogy az R-fa struktúrák nagyon érzékenyek a faelemek beillesztési sorrendjére, így a beillesztésen alapuló (nem tömeges terhelésű) struktúrák nagyobb valószínűséggel szuboptimálisak. A faelemek törlése és újbóli beillesztése lehetővé teszi számukra, hogy „találjanak” egy olyan helyet a fában, amely alkalmasabb, mint az eredeti helyük.
Amikor egy csomópont túlcsordul, néhány elemét eltávolítják a csomópontból, és újra telepítik a fába. (A művelet során egy másik csomópont túlcsordulása okozta végtelen lépcsőzetes alaphelyzetbe állítás elkerülése érdekében az alaphelyzetbe állítási eljárás csak egyszer hívható meg a fa minden szintjén új elem beszúrásakor.) Ez jobban fürtözött elemcsoportokat eredményez a csomópontok, csökkentve a csomópontok lefedettségét. Ezenkívül gyakran a csomópont felosztása gyakran késik, ami a csomópont átlagos kitöltésének növekedéséhez vezet. Az újrabeillesztés felfogható a növekvő fa optimalizálására szolgáló technikának, amikor egy csomópont túlcsordul.
R-fa négyzet alakú Gutman partícióval [2] .
Sok oldal balról jobbra terjed Németországban, és az oldalak nagyban átfedik egymást. Ez nem túl kedvező tulajdonság a legtöbb alkalmazás számára, amelyekhez gyakran csak kis téglalap alakú, sok csíkkal metsző területekre van szükség.
R-fa lineáris Anga-Tan partícióval [3] .
Bár a téglalapok nem olyan hosszúak, mint a Gutmann-féle csempézésnél, a sávozási probléma az oldalon szinte minden lapot érint. A lapoldalak kevéssé fedik egymást, de a kézikönyvoldalak sokat fedik egymást.
Egy fa R* topológiai partíciója [1] .
Az oldalak nagyon kevéssé fedik egymást, mivel az R* fa megpróbálja minimalizálni az átfedő oldalakat, az újrabeillesztés pedig tovább optimalizálja a fát. A particionálási stratégia sem részesíti előnyben a sávokat, így az így kapott oldalak alkalmasabbak leképezési alkalmazásokhoz.
A legrosszabb eset lekérdezései és az eltávolítás bonyolultsága megegyezik az R-fában lévőkkel. Az R*-fa beillesztési stratégia összetett , és összetettebb, mint az R-fa lineáris felosztási ( ) stratégiája, de kevésbé összetett, mint a négyzetes felosztás ( ) stratégia az objektumok oldalméretére vonatkozóan , és kis mértékben hozzájárul a az általános összetettség. A teljes beillesztési komplexitás hasonló marad az R-fához: az újrabeillesztés legfeljebb a fa egy ágát érinti, és ezért ismételt beillesztéseket ad, ami teljesítményében összemérhető egy normál R-fával. Tehát egy R*-fa általános összetettsége megegyezik egy normál R-fa összetettségével.
A teljes algoritmus megvalósításának számos sarokesetet és függő helyzetet kell kezelnie, amelyekről itt nem lesz szó.
Fa (adatstruktúra) | |
---|---|
Bináris fák | |
Önkiegyensúlyozó bináris fák |
|
B-fák | |
előtag fák |
|
A tér bináris particionálása | |
Nem bináris fák |
|
A tér felosztása |
|
Más fák |
|
Algoritmusok |
|
Adatstruktúrák | |
---|---|
Listák | |
fák | |
Számít | |
Egyéb |