java - ファイルを検索するための最適なディスク上のデータ構造？

Question

質問に関連する投稿を読んで解決策を考え出すために数時間を費やしましたが、解決策を見つけるのに実際には成功しませんでした。

だからここに行く：私はかつてインタビューで、特定の単語がファイルに存在するかどうかを検索するためにどのデータ構造を使用するかを尋ねられました。また、ファイルはメモリに収まらないほど大きいと思われ、インタビュアーは実際にディスク上のソリューションを探していました。

Bツリーはディスク上のデータ構造ですか？

二分探索木はメモリ内のデータ構造ですよね？

Answer 1

ここには、実際には2つの異なる質問があります。

1. 巨大なファイルと単語がある場合、その単語がファイルに存在するかどうかをどのように確認しますか？

2. 巨大なファイルがある場合、ファイルに任意の単語が存在するかどうかを効率的に確認できるように、どのようにインデックスを作成しますか？

最初の問題は、Boyer-Mooreとファイルの線形検索によって効率的に解決されます。一度だけ検索する場合、インデックスの作成は完全に時間の無駄です。

2番目の問題に関しては、インタビュアーが実際にBツリーをプッシュしているようです。

Answer 2

どちらも単なるデータ構造であり、ディスク上またはメモリ内の両方にすることができます。それはあなたがそれらをどのように使うかによります。

ところで、Bツリーはディスク上の構造を持つ必要性によって動機付けられました。二分探索木は、ある意味ではB木の特殊なケースにすぎません。

Answer 3

1つのノードを1ページのディスクスペースにマップするデータ構造を使用する必要があります。これにより、ディスクアクティビティが最小限に抑えられます。

これにはBツリーがよく使用されるためです。http://en.wikipedia.org/wiki/B-tree、特に「ソートされたファイルを検索する時間」のセクションを参照してください。