爲了在系統設計中快速進行搜索而創建的數據結構是如何實際存儲的？

Question

假設我正在設計一個像Yelp這樣的餐廳推薦系統。我需要執行的一些基本事項如下：

1. 用戶應該能夠添加/刪除/更新位置。
2. 考慮到它們的位置（經度/緯度），用戶應該能夠找到給定半徑內的所有附近地點。
3. 用戶應該能夠添加關於某個地點的反饋/評論。反饋可以包含圖片，文字和評分。

從存儲的角度來看，我決定爲每個地方的緯度，經度，名稱，描述和評分都提供像LocationId這樣的字段。假設每個LocationId和緯度和經度的字節數大約爲8個字節，如果我爲5億個位置設計系統，那麼我就需要〜500 x 10^6 MB的存儲空間。到現在爲止還挺好。

爲了更快獲得位置查詢結果，我決定使用Quadtree，如圖所示，由網格組成，每個網格由500個位置組成。如果一個網格超過500個位置，它將被拆分成另一個網格，每個網格的最大網格數爲4.假設我也創建了Quadtree。我不確定創建Quatree後，其中和我們如何存儲這棵樹？我能想到的

一種可能的方式是，我將序列的四叉樹和一些類似的線像我們序列化一個N叉樹並將其存儲在一個文本文件中。考慮到我在我的樹的節點中保留了LocationId，Longitude和Latitude詳細信息，如果每個字段都是8個字節，我需要爲每個位置存儲24kb的數據。對於500個這樣的位置，我的樹的總內存需求爲〜24 * 500M = 12 GB。每當我的機器重新啓動時，我只是反序列化存儲的樹並按服務器的請求執行查詢操作。

我用這種方法看到的一個問題是，爲了保留有關位置的最新信息，我需要每隔一段時間後更新我的文件。

任何人都可以建議在其他方式可以存儲QuadTree，我將在哪裏存儲它？我相信按照我上面的建議，有更好的方法來存儲QuadTree。

Answer 1

四叉樹是對細的內存中，但存儲數據時，數據庫管理系統通常使用某種類型的R樹，例如R*Tree或排序瓦片遞歸R-樹（STR-樹）。 R-Trees經過優化，使得一個節點適合磁盤頁面。 STR-Trees最適合一次批量加載整個數據，然後提供最佳性能。 R *樹更適合您希望添加/移動/移除單個點的場景。

從性能的角度來看，每個四叉樹節點使用少於500個條目可能更好，10或50多少？

如果你想玩弄不同的空間樹，看看here或here（全部用Java）。