Ruby中的樹數據結構持久性

Question

我有一個需要在Ruby中構建和存儲大型數據樹的項目。我正在考慮序列化，反序列化和查詢樹的不同方法，我想知道什麼是最好的方法。我的主要限制是讀取時間，查詢效率和跨版本/跨平臺兼容性。最常見的操作是基於id /值和/或特徵的組合來檢索節點組。樹可以高達15-20層深。移動子樹是一個不常見的過程，但應該可以沒有太多的黑魔法。 Rails集成並不是主要關心的問題。我想過，有一些問題，以及我關心的選項，如下：

• 元帥的樹木，並在需要它們加載到內存時和紅寶石對它們進行查詢（低效率樹的生長，交叉版本兼容性？）
• 與上述相同，但使用YAML（更跨版本兼容，但效率較低？）
• 與上述相同，但使用自定義XML解析器（需要重新創建從頭每次樹對象被加載？）
• 將樹序列化爲XML，將它們存儲在XML數據庫（例如Sedna）中並使用XPath查詢樹（沒有使用這種方法的經驗h，不知道效率？）
• 使用鄰接表來查詢存儲在無模式數據庫中的樹（在計算子樹時效率低下嗎？）
• 使用物化路徑（潛在的溢出最深的樹的最大字符串長度？）
• 使用嵌套集（複雜SQL查詢？）
• 使用array of ancestors方法？在根據MongoDB頁面查詢效率方面看起來很有趣，但我還沒有找到任何有關此算法的嚴肅討論。

根據您的經驗，哪種方法更適合我描述的約束？如果我去尋找一個XML數據庫，有沒有更適合這個項目的？是否有其他方法我忽略了這會更有效率？謝謝你的時間。

Answer 1

樹木的工作真的很好用圖形數據庫，如Neo4j的：http://neo4j.org/learn/

Neo4j的是一個圖形數據庫，存儲節點和圖形的關係的數據。最通用的數據結構，圖形優雅地表示任何類型的數據，保留域的自然結構。

Ruby有樹木，不見一個好的界面： https://github.com/andreasronge/neo4j

起搏器是JRuby的庫，使極富表現圖遍歷。 Pacer允許您使用非常快速且高效的內存流處理來創建，修改和遍歷圖形。這也意味着幾乎所有的處理工作都是在純Java中完成的，所以當談到通常的Ruby表現力與速度問題時，你可以擁有你的蛋糕並且也可以吃它，它速度非常快！

https://github.com/pangloss/pacer

Neography就像neo4j.rb寶石，並在評論由Ron建議（感謝羅恩！）

https://github.com/maxdemarzi/neography

Answer 2

你看過ancestry gem？我已經將它用於簡單的樹木，但通過描述它看起來符合您的要求。

Answer 3

由於您正在考慮採用SQL方法，因此需要考慮一些事項。

首先，樹有多大？對於許多應用來說，10,000片葉子看起來很大。但對於數據庫來說這很小。在任何體面的數據庫系統（如筆記本電腦）上，您應該能夠在內存中存儲數千或數百萬扇葉片。

什麼數據庫給你買了其他方法是：

- 不必擔心內存/磁盤性能。當數據泄漏到磁盤時，您不會對性能產生重大影響。通過比較，考慮當散列表溢出內存時會發生什麼。

- 能夠添加索引以優化性能。

- 如果能夠通過修改SQL

一個標準SQL的問題，改變了樹「只是」你的訪問路徑是可以代表一個樹節點作爲一個簡單的對：，，。然後，通過簡單的加入，您可以在父母和葉子之間移動。但是，隨着您向上移動樹，連接會累積。

感嘆。不同的數據庫有不同的解決方案。 SQL Server具有遞歸CTE，可讓您遍歷樹。 Oracle有另一種樹結構的方法。

這開始變得複雜。

也許更好的方法是根據樹中的層次結構分配一個「葉」ID。所以，如果這是一棵二叉樹，那麼「10011」就是右分支，左分支，左分支，右分支，右分支的節點。你會存儲信息。 。 。比如它是否有孩子等等。獲得父母很容易，因爲你可以截斷最後一位數字。

你可以看到這將如何推廣到非二叉樹。有任何數量的孩子可能會帶來一點挑戰。

我相信這可能與「祖先陣列」方法有關。

正如我想到的，我認爲這會工作得很好。那麼我建議你定義每個動作要單獨存儲過程：

usp_tree_FetchNode（節點Id） usp_tree_GetParent（節點Id） usp_tree_NodeDelete（節點Id） usp_tree_FetchSubTree（節點Id） 等等，等等等等

雖然SQL並不真正支持面向對象的編程，但您仍然可以使用乾淨的命名約定和良好的函數包裝來組織您的代碼。

我實際上認爲這可能工作，並提供了一個很好的方法來開發代碼。一個不錯的副作用是你可以分析應用程序之外的樹，這可能表明未來的增強。