用於搜索文件的最佳磁盤數據結構？

我花了幾個小時閱讀與這個問題相關的帖子，試圖提出一個解決方案，但我沒有真正成功地提出一個解決方案。用於搜索文件的最佳磁盤數據結構？

所以這裏有雲：我曾經問在接受採訪時，其數據結構如果在一個文件中存在一個特定的詞我會用搜索。該文件也被認爲足夠大以至於無法適應內存，而訪問者確實在尋找磁盤上的解決方案。

B-Tree是磁盤上的數據結構嗎？

二叉搜索樹是在內存中的數據結構，是不是？

2011-02-22 user183037

我把你的問題作爲「B盤在磁盤上嗎？」。「二叉樹是否在磁盤上？」。看起來像你寫東西，但實際上意味着別的東西:-)令人驚訝的是，讀這個問題的人似乎已經明白你真正想要的東西！ – 2011-02-22 22:14:45

如果我迷惑了你，我很抱歉 - 我試圖做的是建立一個上下文，然後提出問題。實際上，我正在研究是否有任何我沒有聽說過的數據結構，以及我的答案（給面試官）是否正確。 :) – user183037 2011-02-22 22:23:54

有真的在這裏對兩個不同的問題：

第一個問題是有效地與博耶-Moore和通過文件線性搜索求解。如果你只搜索一次，建立一個索引是完全浪費時間。

關於第二個問題，這聽起來像面試官真正推動B-樹。

2011-02-22 22:03:01

這可能是這樣，我就是這麼告訴他的:) – user183037 2011-02-22 22:06:26

兩者都只是數據結構，可以在磁盤上或內存中。這取決於你如何選擇使用它們。

順便說一句，B樹被需要對磁盤結構的動機。二叉搜索樹只是一種B樹的特例。

2011-02-22 22:01:11

@Moron（lol！） - 如何指定數據結構是在磁盤上還是在內存中使用？（對不起，如果這是一個非常天真的問題！） – user183037 2011-02-22 22:04:10

@user：它不是它是一個配置參數！你必須考慮將數據結構存儲在磁盤上需要做些什麼。例如，在二叉搜索樹（甚至是Btree）中，可以將指向另一個節點的指針轉換爲您在文件中尋找的偏移量。 – 2011-02-22 22:06:40

哦！我現在明白了......謝謝。 – user183037 2011-02-22 22:19:07

你想用映射一個節點到一個頁面的磁盤空間的數據結構。這會使磁盤活動最小化。

因爲B樹經常用於此。請參閱http://en.wikipedia.org/wiki/B-tree，特別是「搜索排序文件的時間」部分。

2011-02-22 22:01:23 corsiKa

那麼B-Tree是最好的數據結構嗎？（只是確認） – user183037 2011-02-22 22:05:07

回答