De R-træer er datastrukturer i form af akslen anvendes som rumforskningsprojekter metoder . De bruges til at indeksere flerdimensionel information ( geografiske koordinater , rektangler eller polygoner ). Opfundet af Antonin Guttman i 1984 bruges R-træer både i teoretisk og anvendt sammenhæng. En typisk anvendelse af R-træer er lagring af geografiske oplysninger: for eksempel placeringen af restauranter i en by eller polygoner, der udgør tegningerne på et kort. (veje, bygninger, kyster osv.) og derefter være i stand til at svare på anmodninger som "find alle museer inden for en radius af 2 kilometer", "vis alle veje inden for 5 km" eller "find den nærmeste tankstation til min position ", for eksempel i en navigationsapplikation.
R-træer kan også bruges til at fremskynde søgningen efter de K nærmeste naboer , især efter bestemte målinger som afstanden til den store cirkel .
Hovedidéen bag datastrukturen er at repræsentere objekter i nærheden af deres afgrænsende rektangel på det næste højere niveau i træet ("R" for R-træet er initialen for "rektangel"). Med andre ord lagres de afgrænsende rektangler i hvert undertræ, som det er forælder , i en given node af træet . Når man leder efter rumlig information, er det således tilstrækkeligt at kontrollere for hver gren, om den søgte position skærer det tilsvarende rektangel, og at ignorere de grene, der er knyttet til et rektangel, for hvilket der ikke er nogen skæring. Hvert blad på træet beskriver et enkelt objekt, og hvert højere niveau beskriver en samling af et stigende antal objekter.
Ligesom et B-træ er R-træer afbalancerede forskningstræer (alle blade er i samme afstand fra roden), hvis data er organiseret i sider og er specielt angivet til disklagring. F.eks. I tilfælde af en database . Hver side har en maksimal kapacitet, bemærket M (en side har højst M- poster), og træet garanterer en minimum fyldningshastighed for hver side (bortset fra roden). Denne sideorganisation er velegnet til et stort datamængde: hver side kan indlæses i hukommelsen, når det er nødvendigt, selvom hele træet var for stort til at blive gemt i hukommelsen.
De fleste af de geografiske søgningsoperationer ( skæringspunkt , inklusion , søgning efter nærmeste naboer ) er forenklet af R-træets struktur: vi bruger en grænses rektangel til at afgøre, om vi fortsætter udforskningen der, hvilket tillader eliminering af mest irrelevant noder.
Vanskeligheden ved at implementere R-træer kommer fra behovet for at holde træet afbalanceret, mens man undgår, at de afgrænsende rektangler dækker for meget tomt rum, eller at flere rektangler ikke dækker det samme område. Uden det ville rumsøgningsoperationer risikere at udforske for mange noder unødigt, hvilket ville have en effekt på ydeevnen. Oprindeligt blev indsættelsen af elementerne gjort ved at placere elementet i undertræet, hvis afgrænsningsboks ville vokse mindst ved at tilføje det nye element til det. Hvis en side er fuld, deler vi dens elementer, mens vi prøver at minimere arealet af rektanglerne, der svarer til de to undergrupper. Det meste af forskningen vedrørende R-træer søger at optimere ydeevnen for et træ bygget fra en enkelt datakilde ( bulkbelastning ) eller tværtimod at optimere træet i det tilfælde, hvor dataene tilføjes trinvist.
Selvom R-træer i værste fald ikke tilbyder god teoretisk præstation, er de meget effektive i praksis. Der er varianter, der tilbyder optimale garantier, selv i værste fald til bulk-loading , men kompleksiteten af deres implementering begrænser deres anvendelse i praktiske anvendelser.
Evnen til hurtigt at finde de objekter i en afstand r fra et givet punkt eller k nærmeste naboer (i betydningen enhver norme- p ) ved hjælp af en rumlig medlemshandling grundlag for mange algoritmer, der er afhængige af en effektiv gennemførelse af disse operationer, for eksempel til klynge- eller anomaliedetektion .