R-tre

R-trær eller R - trær er en type tre som ligner på B-tre , men brukes til å indeksere flerdimensjonale rom, for eksempel romlige koordinater (X, Y) for geografiske data. Et eksempel på forespørsel ved bruk av et R-tre vil være "Finn alle museer innen 2 km fra min nåværende plassering".

Datastrukturen deler rommet inn i MBR ( minimumsgrensende rektangler , faktisk R-tre stammer fra Rectangle) nestet hierarkisk og når det er mulig overlappende.

Hver node i R-treet har et variabelt antall oppføringer (opp til et forhåndsbestemt maksimum). Hver oppføring som ikke er en bladnode inneholder to enheter: den ene identifiserer undernoden, den andre MBR som inneholder alle oppføringene til undernoden.

Algoritmen for å sette inn og slette oppføringer fra MBR-er sikrer at "naboelementer" plasseres på samme sted (bladnoden): et nytt element vil gå til bladnoden som krever minst antall utvidelser av størrelsen på MBR-en.

Søkealgoritmene bruker MBR-er for å bestemme om de skal søke i undernoden til den gjeldende noden eller ikke. På denne måten blir de fleste nodene ikke utforsket av algoritmene. Av denne grunn, som med B-trær , gjør dette R-trær egnet for databaser , der noder kan kopieres inn i minnet bare når det er nødvendig.

Flere algoritmer kan brukes til å dele noder når de blir for store, det vil si når et antall elementer som overskrider den forhåndsbestemte grensen legges til en node.

R-trær garanterer ikke optimal worst case-ytelse, men generelt presterer de veldig bra med ekte data. Av denne grunn ble det i 2004 utviklet en ny algoritme (Priority R-tree), som prøver å være effektiv og samtidig utmerket sammenlignet med verste fall.

Algoritmer

Søk

Inngangen er et MBR-rektangel. Søket ligner på B-trær . Den starter fra rotnoden og strekker seg til hver underordnet node (inneholder både MBR-rektangler og pekere til undernoder). En gang ved bladnoden har du de virkelige flerdimensjonale objektene. For hver MBR som påtreffes, kontrolleres det om den overlapper søke(inndata) rektangelet eller ikke. Hvis den er overlagret, søkes den tilsvarende noden også, ellers er den ikke det. Søket fortsetter deretter på en rekursiv måte, og stopper når alle de overlappende MBR-ene er skannet. Et objekt legges til søkesettet (algoritmeutgangen) når det er i en MBR som overlapper spørringen MBR.

Legge til noder

For å sette inn et objekt besøkes treet rekursivt av rotnoden. En vare settes inn i en MBR som trenger minst mulig utvidelse av størrelsen som tillegget vil medføre. Med samme antall utvidelser velges noden med minimumsareal MBR. Når den riktige bladnoden er funnet, legges det faktiske objektet til. Hvis en node legges til en MBR som allerede inneholder et begrenset antall elementer (vanligvis kalt "C", kapasitet), deles regionen (MBR) i to regioner med en delt algoritme. Denne algoritmen realiserer de to nye regionene som har en tendens til å lage MBR med minimumsareal (blant alle mulige).

Relaterte elementer

Lenker

Andre prosjekter

Eksterne lenker