非常に多数の文字列を考えると、いくつかの点に焦点を当てて選択する必要があります。
1. Are your indexing structures going to fit in memory?
ハッシュテーブルの場合、答えは明らかにそうではありません。したがって、アクセス時間は O(1) よりもはるかに遅くなります。それでも、必要なディスク アクセスは 1 つだけです (挿入プロセス全体は O(N) になります)。
b-treeについては、 b+tree (内部ノードのスペースを節約するため) と内部ノードが完全に占有されると仮定して、いくつかの理論計算を行いました。この分析では、メモリに収まりません。
- 通常のディスク ページ サイズは 4096 バイトです。これは、1 つの B ツリー ノードのサイズです。
- 文字列の平均サイズは 70 バイトです (小さいほど良い)。
- 子ノードのアドレスは 4 バイトです。
- 内部ノードは d 個のキーを保持し、d+1 個の子アドレスを持ちます:
**4096B = 4*(d+1)+70*d <=> d = 4096/75 => d = 54 **
* #メモリ内の内部ノード -> #ディスク内のノードを残す -> #マッピングされた文字列*
0 個の内部ノード -> 1 個の葉ノード -> 53 個の文字列がマップさ
れる 1 個の内部ノード -> 54 個の葉ノードが使用される (それぞれ 53 個の葉を持つ) -> 532 個の文字列がマップさ
れる 1+54 個の内部ノード -> 542 個の葉ノードが使用される -> 533 個の文字列がマップさ
れる . ..
...+54⁵ 内部ノード -> 54⁶ 葉ノード = 537 文字列がマッピングされる
53⁷ > 10^12 , but 54⁵*4096 bytes > 1TB of memory
文字列が均一に分散されていない場合は、一般的なプレフィックスを調べることができます。このようにして、内部ノードがより多くの子にアドレス指定できるようになり、メモリを節約できます。BerkeleyDBにはそのオプションがあります。
2. What kind of access are you going to employ? Large or small number of reads?
If you have large number of reads, are they random or sequential?
アクセスがシーケンシャルである場合でも、キャッシュされたノードを大量に使用し (ディスク アクセスを必要としない)、リーフがシーケンシャルにリンクされている (b+tree) ため、btree の利点が得られる可能性があります。これは、範囲クエリにも最適です (そうではないと思います)。アクセスが完全にランダムな場合、ハッシュテーブルは常に 1 つのディスク アクセスしか必要とせず、btree はディスクに格納されている各レベルのディスク アクセスを必要とするため、高速です。
少数のアクセスを行う場合は、挿入が常に高速になるため、ハッシュテーブルを使用することをお勧めします。
文字列の総数がわかっているので、それをハッシュテーブルに示すことができ、バケット スケール操作で時間を失うことはありません (これは、すべての要素が再ハッシュされることを意味します)。
注:あなたのukkonensサフィックス ツリーについて何かを見つけました。挿入は線形で、アクセスもシーケンシャルです。ただし、一部のGBでのみ使用されていることがわかりました。[ref1]、[ref2]、および[ref3]のサフィックス ツリー アルゴリズムに関するリファレンスを次に示します。
これが何らかの形で役立つことを願っています...