使用B-Tree代替Trie

Question

这是一个面试问题，不是家庭作业。

“你有N个文档，其中N非常大。每个文档都有一组单词，比如说w1，w2..wm，其中m对于每个文档可能不同。现在给你一个K个单词的列表，比如说q1，q2…qk。编写一个算法来打印包含K个单词的文档列表。”

现在，我可以使用散列和trie找出解决方案。但发布问题的人也写道，面试官想要一个使用B-tree的解决方案。

我真的不能弄清楚如何使用B-Tree来做这件事，以及它的效率如何。有人能帮帮忙吗？

Answer 1

如果我们的数据集存储在随机访问速度较慢的介质上，例如在常规硬盘驱动器上，则B-Tree优于Trie。面试官注意到N很大，这可能意味着它太大了，不适合放在内存中，应该放在磁盘上。

正如评论中指出的:当数据真的很大并且存储在磁盘上时，数据结构的效率更多地取决于磁盘块访问的数量，而不是所有操作的总量。B-Tree在一个节点中包含许多记录(可以被认为是一个“数据块”)，因此需要的块访问次数比Trie少得多。

这就是为什么大多数DB将它们的索引存储在B-Tree中的原因。他们需要快速搜索位于传统硬盘上的索引。实际上，您的问题可以通过将(word-documentId)对放在DB表中并在word列或整个列上创建索引来解决。

Answer 2

您可以尝试三元trie。它不会占用太多空间。你也可以找一辆卡丁车。它使用一个密钥和两个leafs:http://code.dogmap.org/kart/。