問題タブ [b-tree]

私は、B+Treesを使用する単純なキー/値ストアが必要な楽しいプロジェクトに取り組んでいます。私は数年前にそれらを研究しましたが、正直なところ、車輪の再発明はしたくないので、プロジェクトに含めることができるb+treeのCでの簡単な実装を探しています。

私はsqlite、dbm、tokyocabinetを知っていますが、私のニーズには少し「複雑」すぎます。あなたが私に紹介することができるこれに関する（教育学的でさえ）仕事はありますか？共有するコードはありますか？

どうもありがとう！

重複の可能性：
btree実装でのセグメンテーション違反

次のコードでBツリーのレベル数を見つけるにはどうすればよいですか？

INNODB がテーブルを構造化する方法を理解していると思います (クラスター化された btree インデックス = PK と行自体を含むリーフを使用して)。同じ原理を使用するセカンダリ インデックス (btree クラスター化インデックス = セカンダリ インデックス) とリーフには、ポインターとして使用される PK が含まれます (これが、2 番目のインデックス ルックアップが必要になる理由です)。

http://www.chenyajun.com/wp-content/uploads/2008/12/3-9.jpg したがって、ソートは INNODB のインデックスに基づいています。

しかし、クラスタリングbtreeインデックスの原則を使用して、INNODBのカバー/複合インデックスを物理的にソートおよび保存する方法を本当に理解できません。

バイテンポラルスキーマと、バイテンポラル形式でIUDを作成するperlライブラリを開発しました。すべてのデータはSQLServer2008にあり、システム全体は常に非常に多くのリーダーとライター（両耳側性形式での書き込み）でビジー状態です。

SQLサーバーの内部インデックスはB+ツリーベースであるため、スケーリング/デッドロックは発生しませんか？

過去に非両耳側性システムで多くのデッドロックが発生しましたが、より良いインデックスを追加し、NOLOCK、ROWLOCKを慎重に追加した後、最近はあまり頻繁に発生していません。

バイテンポラル形式では、すべてのリーダーとライターは主に範囲クエリを実行します。内部インデックスがB+ツリーであることを考えると、デッドロックの問題がさらに増えると思われます。ここでは、空間インデックスの方が優れているとは言えませんか？

私の仮定は正しいですか？何か案は ？

btree をメモリに実装する方法は知っていますが、btree をディスクに格納する方法については明確ではありません。大きな違いは次の2つだと思います。

1. メモリ ポインタとディスク アドレス間の変換については、この投稿を参照してください。
2. 新しい k/v アイテムを挿入するときにページを分割する方法は? メモリに実装するのは非常に簡単です。

ありがとう

私はレールを使用しており、次のシナリオがあります。ユーザーには多数のリストがあり、各リストには多数の単語が含まれており、各単語には独自の定義があります。リスト表示ビューには、30 の倍数でページ分割されたすべての単語が表示されます。私は b/ca リストが 4,000 語以上になる可能性があることを懸念しています。アルファベット順。これを行うための最速の方法は何だろうと思っています。多分単語にインデックスを追加しますか？

スペースで区切られたリスト内のすべての単語を含むリストに文字列を保存することを検討しました。次に、この文字列に対して split(" ") を実行し、この配列に対してページネーションを使用できますが、正規表現を使用して、このリストから単語を追加および削除し、単語オブジェクトを保存する必要があります。

また、tokyo Cabinet のようなキーバリュー ストアも検討しました。B-Tree インデックスが機能するようです。

私の仕事は、操作中に影響を受けなかったすべてのエンティティをデータベースから削除することです。2 つの列を持つ別のテーブルを作成しました。最初はテーブルの名前を再設定し、2 番目はそのテーブル内のレコードの ID です。

たとえば、テーブルがある場合

そしてその中のレコード

このレコードを編集すると、次のデータが edit_entities に入れられます。

次に、影響を受けていないエンティティ (edited_entities テーブルにない ID) をすべて削除する必要があり、次のようにします。

このような操作 (MySql) に最適なエンジンは何でしょうか? デフォルトのデータベース エンジンは InnoDB です。メモリ（ヒープ）について考えましたが、削除操作を高速化できるかどうかはわかりません。

必要な操作を最適化するにはどうすればよいか提案があれば、喜んでここにいたします。

子犬のテーブルに列を追加したくありません。

3-4-5-6 ツリーを実装しようとしています。マージによってルートにキーが 1 つしかなく (アンダーフロー)、その子のキーの総数が 5 を超える場合 (したがって、すべてがマージされるとアンダーフローが発生します)、どうすればよいですか?

TツリーとB-/B+ツリーの定義を調べました。Web上の論文から、ディスクドライブやキャッシュメモリなどの階層メモリでBツリーのパフォーマンスが向上することがわかりました。

私が理解できないのは、フラットメモリでもTツリーが使用された理由です。

それらは、AVLツリーのスペース効率の良い代替手段として宣伝されています。

最悪の場合、Tツリーのすべてのリーフノードには1つの要素のみが含まれ、すべての内部ノードには許容される最小量が含まれます。これはほぼ満杯です。これは、割り当てられたスペースの平均で半分しか使用されないことを意味します。私が誤解しない限り、これは、Bツリーのノードが半分いっぱいになっている場合のBツリーの最悪の場合と同じ使用率です。

両方のツリーがキーをノードにローカルに格納し、ポインタを使用してレコードを参照すると仮定すると、唯一の違いは、Bツリーが各ブランチのポインタを格納する必要があることです。これにより、キーのサイズにもよりますが、通常、最大50％以下のオーバーヘッド（Tツリーに対して）が発生します。実際、これは、親ポインター、ノードに埋め込まれたレコード、レコードに埋め込まれたキーがないと仮定すると、AVLツリーで予想されるオーバーヘッドに近いものです。これは、代わりにBツリーを使用できないようにする期待される効率の向上ですか？

Tツリーは通常、AVLツリーの上に実装されます。AVLツリーはBツリーよりもバランスが取れています。これはTツリーのアプリケーションと関連付けることができますか？

B +ツリーを使用してkey1に従ってソートされたトゥープル{key1、key2}のリストがあります。この構造は、セカンダリメモリ（HDD）にあります。key1でソートされたリストを必要とするが、key2を使用してリストにランダムアクセスする必要があるアルゴリズムを実装したいと思います。アルゴリズムのリスト全体は必要ありません。必要に応じてディスクからブロックを取得するため、B+Treeは発生するすべての挿入と削除でうまく機能します。

私は1週間頭を悩ませてきましたが、key2で2番目の構造（たとえば2番目のBツリー）を使用するのが唯一の方法だと思いますが、これにより、ツリーの更新に必要なすでに大きなスペースと時間が2倍になります。

ハッシュテーブルについてはよくわかりませんが、これらを使用してキーを特定の値にマップすることはできないと思いますよね？

データを2倍にすることなくkey2へのランダムアクセスを提供できる構造について何か考えがありますか？

あるいは、ランダムアクセスを必要としない代替アルゴリズムを使用することもできますが、それを最後の解決策として残したいと思います。

前もって感謝します