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

  1. ^ 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