基于磁盘的Trie树？

Question

10

我正在尝试构建一个Trie，但是在内存容量非常有限的手机上进行。我认为最好将整个结构存储在磁盘上，只有在需要时才加载，因为我可以容忍一些磁盘读取。但是，经过几次尝试，似乎这是一件非常复杂的事情。

有哪些方法可以将Trie存储在磁盘上（即仅部分加载），并保持快速查找属性？这是一个好主意吗？

- chakrit

1

在这种情况下，我会选用 B 树而不是 Trie，但我很想知道这个问题的答案。 - zwol

Tries是支持快速查找的数据结构。这似乎是一些嵌入式数据库引擎（如SQLite）或一些http://en.wikipedia.org/wiki/Dbm衍生产品的好用例。 - permeakra

2个回答

4

我只是简单地浏览了一下，但Shang的“用于二级存储上文本和空间数据的Trie方法”讨论了分页trie表示法，并可能是一个有用的起点。

- Matthew Slattery

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user497981 · Accepted Answer

这篇论文磁盘字符串管理的B树回答了你的问题。

它提出了以下观察：

据我们所知，文献中尚未提出过一种基于trie的数据结构（例如burst trie），该数据结构可以高效地驻留在磁盘上，以支持常见的字符串处理任务。