問題タブ [b-tree]

C で記述された B ツリー ライブラリの無駄のない適切に構築されたオープン ソース実装を探しています。商用アプリケーションで使用できるようにするには、非 GPL ライセンスである必要があります。理想的には、このライブラリはディスク ファイルとして格納/操作される B ツリー インデックスをサポートし、構成可能な (つまり、最小限の) RAM フットプリントを使用して大きなツリーを構築できるようにします。

注: 少し混乱しているように見えたので、バイナリ ツリーと B ツリーは同じものではありません。

著者から毎日新しい本を手渡されると想像してみてください。本は進行中の作業です。彼は自分が何を変更または追加したかを教えてくれません。

あなたの仕事は、変更と追加を特定し、これらのみを出版社 (毎日本全体を読む時間がない) に渡すことです。

この問題を解決するために、本は 100 万行の ASCII テキストで構成され、拡大しています (実際には MySQL バックアップ ファイル)。

私の現在のアイデアは、各行 (1k 文字) の安全なハッシュ (たとえば SHA256) を作成し、それを HD に保存することです。ハッシュは 32 バイトしかないため、ファイルは 32MB しかありません。

次に、明日次のファイルを取得すると、1 行ずつ調べて、各行の新しいハッシュを作成し、それを前日のハッシュと比較します。

プロセスが終了すると、翌日のためにハッシュ ファイルが上書きされます。

比較は、文字列比較 ( > < オペランド) の二分探索法を使用します。これにより、平均 4 回の反復で結果が返されます。

私はまだ btree インデックス ソリューションをコーディングしていませんが、これにどのように取り組みますか?

このテーマについていくつか読んだこと：

MySQL クエリのキャッシュ

http://www.danga.com/memcached/

私の SQL キャッシングの問題: http://www.petefreitag.com/item/390.cfm

http://framework.zend.com/manual/en/zend.cache.html#zend.cache.introduction

私は非常にユニークな (狭い) クエリのセットを持っており、現在の FastCGI C API 実行可能ファイル (PHP ではない) 内でキャッシュを簡単に実装できると思います。

Zend はそのフレームワークを次のように説明しています。キャッシュ レコードは、ID とタグの柔軟なシステムを通じて、バックエンド アダプター (ファイル、Sqlite、Memcache...) を介して保存されます。

これはどのように実装されていますか？

テーブルが変更された場合、同じクエリが異なる結果を返す可能性があるため、クエリだけでなく、UPDATE、INSERT、および DELETE も監視する必要があります (今のところ MySQL)。これはプロセスの 1 つからのみ発生するため、簡単に追加できます。テーブルの変更時にキャッシュを削除するステートメント。

クライアントが許可するのは SELECT のみです。この場合、クエリをハッシュして、結果を含むファイルへのポインターと共にハッシュ テーブルまたは Btree インデックスに格納できます。

より良い方法はありますか？

B+ツリーなどのファイルベースのデータ構造があるとします。私の理解では、データはディスクに保存されることが期待されていますが、インデックスは通常メモリにロードされます。インデックスでさえメモリに収まらないほど大きなファイルがある場合はどうなりますか？それは通常どのように処理されますか？次に、インデックスはデータの線形セットではなくツリーであるため、通常、ディスク上にどのように配置されますか？

私は基本的に、実際のプロジェクト（Berkeley DBなど）でどのように行われるのかについて興味があります。明らかに、私は幅広いストロークに興味があります。私はアイデアを得たいと思っているので、データベースブックのBツリーセクションを掘り下げるとき（または数年前のCS XYZから私の記憶をジョギングするとき）にいくつかのコンテキストがあります

私は最近、Postgres データベースの最適化に取り組んでおり、伝統的に B-Tree インデックスしか使用していません。ただし、Postgres 8.3 のドキュメントで、GiST インデックスが一意でない複数列のインデックスをサポートしていることを確認しました。

しかし、それらの実際の違いが何であるかはわかりませんでした。私の仲間のコーダーが、それらの間の長所と短所は何か、そしてさらに重要なことに、私が一方を他方よりも使用する理由を説明できることを望んでいましたか?

Btree（バイナリのものはわかりません）をディスクファイルに保存したいと思います。そしてそれをメモリに読み込みます。いくつかのレベル順トラバーサルは、バイナリBtreeの良い方法かもしれません。しかし、それがバイナリのものでない場合。メモリ内のリーフノードからルートノードまでBtreeを構築します。ディスクファイルにいくつかの構造を定義し、ツリーノードを出力する必要があると思います。ファイル内のノードを識別するためにいくつかの追加のタグを使用していますか？ここでは、トラバーサルの方法が重要な問題になる可能性があります。ノードとポインタを保存する良い方法がわかりません。そしてそれを読んでください。メモリ内のツリーを再構築します。何か良いアイデアはありますか？どうもありがとう。

それは簡単な質問です。JavaでBツリーを描画するためのAPIはありますか？車輪の再発明に多くの時間を費やしたくありません。私はsiごとのアルゴリズムに問題はありません。多くの読み取り（特にJavaでのLaforeのデータ構造とアルゴリズム）の後、私のものは完全に正常に機能します。Bツリーを適切な方法で印刷する方法がわかりません。

前もって感謝します。

必要な機能のみが必要な場合に、キーと値のペアを格納するために使用するデータ構造を決定しようとしています

• 挿入
• 調べる

具体的には、ペアを削除したり、キー/値/ペアを反復処理したりする必要はありません。

キーは整数タプルで、値はポインター (参照など) です。（多くの）オブジェクトに分散した数百万のペアのみを保存しています。

現在、私はどちらかを使用することを検討しています

• ハッシュテーブル
• kd ツリー
• bツリー

私は（挿入/検索時間のために）ハッシュテーブルに傾いていますO(1)が、自分の傾向を確認したかったのです。

どの構造（上記またはその他の構造）をお勧めしますか、またその理由は何ですか? ハッシュ テーブルを推奨する場合、オブジェクトごとに個別のテーブルを作成するか、単一のテーブルを作成してオブジェクトの ID をキー タプルの一部として使用する必要がありますか?

Javascript での単純な BTree 実装の良い例を知っている人はいますか? ランダムに届くたくさんの「もの」があり、それぞれを効率的に挿入したい。

最終的に、新しいものはそれぞれ、ツリー内の最終的な場所に基づいて DOM に挿入されます。

これをゼロからコーディングすることはできますが、車輪を再発明したくはありません。

ありがとう

プログラマーとして、RBツリー、Bツリー、またはAVLツリーの使用をいつ検討する必要がありますか？選択を決定する前に考慮する必要がある重要なポイントは何ですか？

重要なポイントを参照して、なぜそれが他のものよりも選ばれるのか、各ツリー構造のシナリオで誰かが説明できますか？