algorithm - 使用 B-Tree 代替 Trie

Question

这是一道面试题，不是作业。

“您有 N 个文档，其中 N 非常大。每个文档都有一组单词，假设为 w1、w2..wm，其中每个文档的 m 可能不同。现在给定一个包含 K 个单词的列表，假设为 q1 ,q2…qk。 编写一个算法来打印其中包含 K 个单词的文档列表。"

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

我真的无法弄清楚如何为此使用 B 树以及它的效率如何。有人可以帮忙吗？

Answer 1

如果我们的数据集存储在随机访问速度较慢的介质上，例如传统硬盘驱动器，则 B-Tree 优于 Trie。面试官注意到 N 非常大可能意味着它大到无法放入内存，应该放在磁盘上。

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

这与大多数数据库将其索引存储在 B 树中的原因完全相同。他们需要通过位于传统硬盘驱动器上的索引进行快速搜索。 实际上，您的问题可以通过将 (word-documentId) 对放入数据库表中并在 word 列或整个列上创建索引来解决对。