R + strom - R+ tree
An R + strom je metoda pro vyhledávání dat pomocí umístění, často (x, y) souřadnice a často pro umístění na webu povrchu Země. Hledání na jednom čísle je vyřešený problém; hledání na dvou nebo více místech a dotaz na místa, která jsou poblíž v obou směrech x a y, vyžaduje řemeslné algoritmy.
V zásadě je strom R + a stromová datová struktura, varianta R. strom, používá indexování prostorových informací.
Rozdíl mezi stromy R + a stromy R.
Stromy R + jsou kompromisem mezi nimi R. stromy a kd-stromy: zabrání se překrývání vnitřních uzlů vložením objektu do více listů, pokud je to nutné. Dosah je celá oblast k pokrytí všech souvisejících obdélníků. Překrytí je celá oblast, která je obsažena ve dvou nebo více uzlech.[1] Minimální pokrytí snižuje množství „mrtvého prostoru“ (prázdné oblasti), který je pokryt uzly R-stromu. Minimální překrytí snižuje množinu vyhledávacích cest k listím (ještě důležitější pro přístupovou dobu než minimální pokrytí). Efektivní vyhledávání vyžaduje minimální pokrytí a překrytí.
Stromy R + se liší od stromů R v tom, že: uzly nemají zaručené alespoň poloviční vyplnění, položky kteréhokoli interního uzlu se nepřekrývají a ID objektu může být uloženo ve více než jednom uzlu listu.
Výhody
Vzhledem k tomu, že se uzly navzájem nepřekrývají, výhody výkonu bodového dotazu, protože všechny prostorové oblasti jsou pokryty nejvýše jedním uzlem. Je sledována jedna cesta a je navštíveno méně uzlů než u R-stromu.
Nevýhody
Vzhledem k tomu, že obdélníky jsou duplikovány, může být strom R + větší než strom R postavený na stejné datové sadě. Stavba a údržba stromů R + je složitější než stavba a údržba stromů R + a dalších variant stromu R +.
Poznámky
- ^ Härder, Rahm, Theo, Erhard (2007). Datenbanksysteme (2., überarb. Aufl. Ed.). Berlín [atd.]: Gardners Books. 285, 286. ISBN 978-3-540-42133-7.
Reference
- T. Sellis, N. Roussopoulos a C. Faloutsos. R + -Strom: Dynamický index pro vícerozměrné objekty. Ve VLDB, 1987.