Ich möchte den R-Baum und den Quadtree für Geodaten vergleichen. Während es Literatur gibt, habe ich Mühe, Dokumente zu finden, die einen echten grundlegenden Vergleich abdecken. Also habe ich beschlossen, diese Frage zu stellen.R-Tree und Quadtree Vergleich
Meiner Meinung nach hat der R-Baum den Vorteil, ausgeglichen zu sein und der Baum hat keine leeren Blätter. Als Nachteil kann die grundlegende Operation wie Einfügen oder Löschen den gesamten Index restrukturieren.
Der Quadtree ist das Gegenteil, es ist nicht ausgeglichen und hat leere Blätter, aber es muss nicht wiederhergestellt werden.
Also als ein Fazit von dem würde ich sagen, dass der R-Baum weniger Speicher benötigt und schneller für die Suche wegen der minimalen Höhe ist. Der Quadtree ist besser, wenn es viele Update-Operationen gibt, aber der resultierende Baum könnte unausgewogen sein.
Sind diese Punkte Ihrer Meinung nach richtig? Gibt es irgendwelche Dokumente, die dieses Thema abdecken?
Auf Wiedersehen, Andre
„um den gesamten Index Umstrukturierung“. Nein. Die Umstrukturierung beschränkt sich auf einen einzigen Pfad, nicht auf den "ganzen" Index. Überlegen Sie, beide zu implementieren und einige Benchmarks selbst zu machen, um wirklich zu wissen, wie sie funktionieren. Benutze nicht nur Theorie. –
Es gibt viele verschiedene Quad-Tree-Typen, also lerne die meisten kennen, bevor du versuchst zu vergleichen. Ferner kann eine geringfügige Variation in der Implementierung eine sehr unterschiedliche Ausführungszeit ergeben (z. B. ein Rechteckobjekt im Vergleich zu dem Übergeben von 4 Parametern x, y, Breite, Höhe). – AlexWien