5

挿入、取得、更新、削除に最適化された大規模なブロック ベースのデバイス (機械式ハード ドライブなど) でうまく機能するアルゴリズム/データ構造を探しています。 ID のフィールドは可変長です。

B-Tree は一般的に引用される構造のようですが、主に固定長レコード用です。また、挿入や削除よりも取得や更新の方がはるかに多いと予想しています。B ツリーの O(log m) ルックアップを取り除くことはできますか?

結合されたシステムであることに非常に満足しています。たとえば、ISAM は B ツリーと線形ファイル ストレージを結合し、アプローチとして可変長レコードを操作できるように見えます。もっと良いものはありますか？

いくつかのさらなる制約:

1) ID は疎である可能性がありますが、線形の数字のブロックにすることができますが、範囲は広い (64 ビット)

2) DBMS を使用したくありません。特定の問題に対するパフォーマンスはあまり良くありません。完全な DBMS が使用する操作は必要ありません。検索も必要ありません。簡単に微調整して最適化できるものが必要です。それをアカデミックな好奇心と呼んでください。MySQL よりもパフォーマンスが優れている場合は、それを使用しますが、より速く実行する必要があります。

3) データセットはメモリに収まりきらないサイズですが、インデックスはキーやオフセットのように単純な場合はメモリに収まる可能性があります。私は確かに、ストレージ内に 10 億以上のエンティティを見ています。

4) 理想的には、レコードが削除されたときにスペースを回復する必要があります。それは圧縮によるものかもしれませんが、より良い方法があるかどうかを知りたいです（たとえば、Bツリーはスペースを簡単に回復します）。

4

5 に答える 5

11

簡単な方法: Berkeley DB などを使用します。任意のバイト文字列のキーと値のストアを提供し、すべての面倒な作業を自動的に行います。必要に応じて、インデックス作成用の「セカンダリ データベース」も提供します。

自分でやる方法: プロトコル バッファ (または選択したバイナリ形式) を使用して、B ツリー ノードとデータ項目構造を定義します。データベースに追加専用ファイルを使用します。新しいレコードを書き込んだり、既存のレコードを変更したりするには、レコード自体をファイルの末尾に書き込んでから、変更された B ツリー ノード (たとえば、レコードの親ノード、その親ノードなど)を書き込みます。根）。次に、ツリーの新しいルートの場所を、ファイルの先頭にあるヘッダー ブロックに書き込みます。ファイルを読み取るには、最新のルート ノードを見つけて、他のファイルと同じように B ツリーを読み取るだけです。このアプローチにはいくつかの利点があります。

  • 書き込まれたデータは決して変更されないため、リーダーはロックを取得する必要がなく、読み取りを開始した時点のルート ノードに基づいて DB の「スナップショット」ビューを取得します。
  • ノードとレコードに「以前のバージョン」フィールドを追加することで、基本的に無料で以前のバージョンの DB にアクセスできるようになります。
  • 変更をサポートするほとんどのディスク上のファイル形式と比較して、実装とデバッグが非常に簡単です。
  • データベースの圧縮は、最新バージョンのデータと B ツリーを読み込んで新しいファイルに書き込むだけです。
于 2009-05-18T10:23:00.923 に答える
0

データベースが非常に重要な場合は、Key-Valueストアを検討してください。

本当に自分で実装する場合は、ディスクベースのハッシュテーブルまたはBツリーを使用してください。可変長値の問題を回避するには、値を別のファイルに保存し、データファイルのインデックスとしてBツリーを使用します。値の削除後のスペースの再利用は注意が必要ですが、可能です（たとえば、データファイルの空きスペースのビットセットによって）。

于 2009-05-18T07:03:30.040 に答える
0

商用のデータベース エンジンを使用するのが最適な場合があります。

インデックスを格納することで、B ツリーの O(log m) ルックアップを取り除くことができます。つまり、{"logical ID" は "physical location" にマップされます} 値のペアをハッシュ マップ (論理 ID でハッシュ) に格納します。 ...または、ID値がスパースでない場合、bdonlanが示唆するように、連続したベクトルにインデックスを格納します(オフセット値のベクトルへのインデックスとして使用される論理IDを使用)。

重要な実装の詳細は、インデックスにアクセスするために使用する API である可能性があります。それを RAM (O/S がシステム ページ ファイルでバックアップします) に格納し、ポインターを使用してインプロセスでアクセスするか、および/またはインデックスに格納するかどうかです。ディスク (O/S がファイル システム キャッシュにキャッシュする) にアクセスし、ファイル I/O API を使用してアクセスします。

于 2009-05-17T20:57:46.430 に答える