我花了几个小时阅读与该问题相关的帖子，以尝试提出解决方案，但我并没有真正成功地提出解决方案。
所以这里是这样的：我曾经在一次采访中被问到，如果文件中存在特定的单词，我将使用哪种数据结构来搜索。该文件也被认为大到无法放入内存中，面试官确实在寻找磁盘上的解决方案。
B-Tree 是磁盘上的数据结构吗？
二叉搜索树是一种内存数据结构，不是吗？
问问题
1905 次
3 回答
4
这里确实有两个不同的可能问题：
给定一个庞大的文件和一个单词，如何检查该单词是否存在于文件中？
给定一个庞大的文件，如何建立索引以便有效地检查文件中是否存在任意单词？
第一个问题通过 Boyer-Moore 和对文件的线性搜索有效地解决了。如果您只搜索一次，那么构建索引完全是浪费时间。
关于第二个问题，听起来面试官真的是在推B-Trees。
于 2011-02-22T22:03:01.603 回答
2
两者都只是数据结构，既可以在磁盘上，也可以在内存中。这取决于您选择如何使用它们。
顺便说一句，B-Trees 的动机是需要具有磁盘结构。从某种意义上说，二叉搜索树只是 B 树的一种特殊情况。
于 2011-02-22T22:01:11.423 回答
2
您想使用一种将一个节点映射到一页磁盘空间的数据结构。这将最大限度地减少磁盘活动。
因为通常为此使用 B 树。请参阅http://en.wikipedia.org/wiki/B-tree，特别是“搜索排序文件的时间”部分。
于 2011-02-22T22:01:23.580 回答