問題タブ [b-tree]

だから、ここに私の小さな問題があります。

それぞれ L <= c ₀ ... c _n < H の項目を含むバケット a ₀ ... a _{nのリストがあるとします。}LとHのリミットを決めることができます。あまり役に立たないとは思いますが、動的に更新することもできます。

バケットの順序は重要です。私は行ってそれらを交換することはできません。

ここで、次のようにこれらのバケットにインデックスを付けたいと思います。

• アイテムの総数を知っている
• i番目の要素を検索できます
• 任意のバケットからアイテムを追加/削除し、インデックスを効率的に更新できます

簡単そうですよね？これらの基準を見て、私はすぐにフェンウィック ツリーについて考えました。それが彼らが本当に意図していることです。

ただし、ユースケースについて考えると、他のいくつかのユースケースが忍び寄ります。

• バケツの数が L を下回った場合、バケツは消える必要があります (まだ項目について心配する必要はありません)。
• バケット数が H に達すると、新しいバケットがいっぱいになるため、新しいバケットを作成する必要があります

フェンウィック ツリーを効率的に編集する方法がわかりません。ツリー全体を再構築せずにノードを削除/追加します...

もちろん、L = 0 に設定して、削除が不要になるようにすることもできますが、アイテムの追加は実際には避けられません。

だからここに質問があります：

このインデックスのより良い構造または Fenwick Tree を更新する方法を知っていますか?

主な関心事は効率です。私はそれを実装する予定があるため、キャッシュ/メモリの考慮事項は心配する価値があります。

背景:

私は、B ツリーやランク付けされたスキップ リストに多少似た構造を考え出そうとしていますが、ローカライズされたインデックスを使用しています。これら 2 つの構造の問題は、インデックスがデータに沿って保持されることです。これは、キャッシュの観点から非効率的です (つまり、メモリから複数のページをフェッチする必要があります)。データベースの実装では、インデックスを実際のデータから分離したままにしておくと、キャッシュが使いやすくなり、効率が向上することが示唆されています。

B+Tree のオンディスク実装がどこにあるか知っている人はいますか? 私はグーグルを前後に調べましたが、残念ながら賢明なものは見つかりませんでした。他のスレッドは、おそらく sqlite、sqljet、または bdb からツリーを取得することを提案していますが、これらのツリーはデータベース全体にネストされており、実際には B+Tree を「単に」除外することはできません。私は本当にディスク上の B+Tree だけを探しています...周りに派手なものはありません。

私はslady.netの非常にクールな btree アプレットで遊んでいます。特定の動作を理解するのに苦労しています。この開始状態を見てください。

代替テキスト http://www.freeimagehosting.net/uploads/db2931c7da.jpg

この特定の状態は、10、15、30、16、70、1、9、27、45、50、55 のシーケンスを挿入することによって達成されました。

私の質問は、シーケンスに次の値 65 を挿入すると [45, ] ノードに何が起こるかに関するものです。

代替テキスト http://www.freeimagehosting.net/uploads/3b70c1d302.jpg

[55,70] ノードは 65 で分割され、中間値である 65 は上に移動し、[30,50] ノードも分割します。私の質問は: [45, ] ノードが [30, ] ノードの子になるのはなぜですか? その親にはもともと 3 つの子があり、一番左と一番右が新しい別のノードになりました。45 はこれらの値の間にあり、[65, ] ノードの下にも同様に配置された可能性があるようです...なぜですか?

テラバイトの情報を、インデックスの前と圧縮メソッドの後に保存します。

ソートファイルなどを使用してバイナリツリーデータベースを手動でコーディングする必要がありますか、それともMongoDBやMySQLのようなものを使用する必要がありますか？

MySQLや他のDBのようなものが出回っている場合、レコードあたりの（スペース）コストが心配です。一部のデータベースでは圧縮も可能ですが、読み取り専用テーブルに変換されることも知っています。これらのテーブル/レコードには、かなり頻繁にアクセスして新しいデータで上書きする必要があります。C ++で何かをコーディングすると、レコードあたりのスペースのコストを最小限に抑えることができると思います。

私は何をすべきか？

並べ替えられたデータセットがあり、シーケンシャル読み取りとランダムルックアップの両方に最適な方法でディスクに保存したい場合は、Bツリー（またはバリアントの1つが適切な選択です）のようです。 ..このデータセットがすべてRAMに収まるわけではないと仮定します）。

問題は、ページ分割を行わずに、ソートされたデータセットから完全なBツリーを構築できるかどうかです。ソートされたデータを順番にディスクに書き込むことができるようにします。

大学のBツリーを実装する必要があります。

root属性と_degree属性を持つ「外部」クラスのBツリーがあります。ノードを表すクラスは、静的メンバークラスとして実装されます。

したがって、今の私の問題は次のとおりです。静的メンバークラスとしてNodeクラスを実装したため、外部クラスの度属性にアクセスできません。

今、私は選択する必要があります：

1. Nodeクラスを内部クラス（非静的メンバークラス）にするOR
2. Nodeクラスのコンストラクターを作成し、Nodeを構築する必要があるたびに学位を渡します。

最良の選択は何でしょうか？これを内部クラスにすると、ノードはすべてBtree（外部クラス）への参照を持つことになりますが、静的メンバークラスにすると、毎回学位を渡す必要があります。

「アルゴリズムの紹介」の「B-Trees」の章に従って、B-Tree を実装しようとしています。

私がよくわからないのは、「最小限の程度」です。この本では、次数は、ノードが保持できるキーの数の下限/上限を表す数値であると述べられています。それはさらに次のように述べています。

1. すべての非ルート ノードは、少なくともキーを格納し、子t - 1を持ちますt。
2. すべてのノードは最大でもキーを格納し、子2*t - 1を持ちます2*t。

したがって、t = 2 の場合は次のようになります。

1. t - 1= 1 キーおよび t = 2 子
2. 2*t - 1= 3 つのキーと 4 つの子

t = 3 の場合

1. t - 1= 2 つのキーと t = 3 つの子
2. 2*t - 1= 5 つのキーと 6 つの子

ここで問題があります。B ツリーのノードは、満杯のときに奇数のキーしか格納できないようです。

最大で 4 つのキーと 5 つの子を持つノードを作成できないのはなぜですか? ノードの分割と関係がありますか?

インデックスにb-treeを使いたいのですが、ORクエリの解決策が思いつきません。

OR クエリの場合、 select * from table where id between 1 and 5 OR id between 10 and 15; のようなものを意味します。

B ツリーで id をキーとして使用する場合、B ツリーで上記のようなクエリを実行するにはどうすればよいですか?

b ツリーを検索するときは、6 より小さいキーと 6 より大きいキーが異なるサブツリーにあると仮定します。検索パスが 6 より小さいキーを含むサブツリーを通過する場合よりも、 1 から 5 の間は取得できますが、10 から 15 の間の id はどうでしょうか。

b+tree を使用する必要がありますか? ID 1 を指すキーが見つかったら、ID 15 を指すキーが見つかるまで、リーフ ノードを 1 つずつスキャンし続けますか? この種のクエリの悪い解決策ですか: select * from table where id between 1 and 5 OR id between 10000000 and 10000005 ???

または、他の解決策はありますか？

どうもありがとうございました！

C＃（オープンソース）にファイルシステムベースのB + Tree実装はありますか。いくつかのプロジェクトを見つけましたが、それらはファイル (ディスク) ベースの実装ではありません。特にファイル システム ベースの B+ ツリーを探しています。

POSIXバイナリツリー関数のマンページには、次のステートメントが含まれています。

tdelete()削除されたアイテムの親へのポインタを返すNULLか、アイテムが見つからなかった場合に返します。

tdelete()ツリー内のノードに必要なメモリを解放します。ユーザーは、対応するデータ用にメモリを解放する責任があります。

これは、呼び出しから特定のキーのノードのデータにアクセスする方法がないことを意味しtdelete()ます。tfind()（指定されたキーを追加しないためではなく）呼び出しtsearch()、ノードのデータの破棄を実行してから、同じキーで呼び出しtdelete()て、バイナリツリーからノードを削除する必要があります。

私はこれを正しく解釈しましたか？このアプローチの制限であると私が感じるものを回避する方法はありますか？

1. キーがヒープに割り当てられている場合、ノードが削除される前にキーを解放することはできません（または使用中の比較機能で使用できなくなります）。これにはtfind()、データへのポインタを取得するために呼び出しtdelete()、ノードを削除してから、呼び出しから取得したデータを破棄する必要がありtfind()ます。
2. ノードを削除し、囲まれたデータを破棄するには、2回のルックアップが必要です。