Chcę porównać R-Tree i Quadtree dla danych geoprzestrzennych. Podczas gdy istnieje literatura, walczę o znalezienie dokumentów, które obejmują prawdziwe porównanie podstawowe. Postanowiłem zadać to pytanie.Porównanie R-Tree i Quadtree
Moim zdaniem, R-drzewo ma tę zaletę, że jest zrównoważone, a drzewo nie ma pustych liści. Wadą podstawowej operacji, takiej jak wstawianie lub usuwanie, może być restrukturyzacja całego indeksu.
Quadtree jest przeciwieństwem, nie jest zbalansowane i ma puste liście, ale nie trzeba go ograniczać.
Więc jako fazit z tego chciałbym powiedzieć, że R-drzewo potrzebuje mniej pamięci i jest szybsze do wyszukiwania ze względu na minimalną wysokość. Czwórnik jest lepszy, gdy istnieje wiele operacji aktualizacji, ale wynikowe drzewo może być niezrównoważone.
Czy uważasz, że te punkty są prawidłowe? Czy są jakieś dobre dokumenty, które obejmują ten temat?
Auf Wiedersehen, Andre
„restrukturyzacji całego indeksu”. Nie. Restrukturyzacja jest ograniczona do jednej ścieżki, a nie do "całego" indeksu. Zastanów się nad wdrożeniem i wykonaniem pewnych testów porównawczych, aby naprawdę wiedzieć, jak działają. Nie używaj tylko teorii. –
Istnieje wiele różnych typów drzewek quad, więc zapoznaj się z nimi przed próbą porównania. ponadto niewielka różnica w implementacji może dostarczyć znacznie różnych czasów wykonania (np. passimg obiektu Rectangle vs przekazanie 4 params x, y, width, height). – AlexWien