在Rails中實現k-d樹 - 需要幫助開始

Question

我需要根據兩個值的範圍來查詢我的數據庫，這兩個值本質上是數據庫中float類型的兩列。

做了一些研究之後，我縮小我的選擇與算法實現這個使用兩種：

1. 2D正交幅度搜索
2. kd樹結構

現在我淘汰了一號選項，因爲我的數據是聚集的，因此它不會有用。

所以我需要使用k-d樹結構。但是如何？我從來沒有做過，也不知道從哪裏開始。我在我的一個控制器中有一個方法，它被設置爲存根以檢索此搜索的結果，但搜索本身未實現。

我試圖獲得創建此功能所涉及的系統步驟。到目前爲止，這是我認爲我需要去做的事情，但是如果這是正確的路要走的話，我不知道。

1. k -d樹必須從DB中的數據在內存中構建。 （但是不知道什麼時候應該這樣做，既可以當軌啓動或當一個請求進來？）

2. 當更新發生到數據，編輯樹，整個樹保存到數據庫中

3. 是否有任何方法可以將數據結構保存在數據庫本身而不用明確構建？

此外，我搜索了一下，但想知道有沒有人有任何資源，他們可以爲此推薦？

Answer 1

有，我們在以前的項目使用的寶石：

https://rubygems.org/gems/kdtree

還有它的一個線程安全的叉：

https://rubygems.org/gems/tupalo-kdtree

也許看，實施之前，你的擁有。