問題タブ [b-plus-tree]

私は、クラビング手法を使用して B+Tree のメモリ内バージョンを開発していました (親のロックを解放する前に、子のロックを取得する必要があります)。

実装のターゲット言語は C# です。私の実装ではバッキングがDictionary<Page, Node>あります。XS および U ラッチの場合、Dictionary で使用可能なすべてのノードに対して個別の ReaderWriterLockSlim を使用します。したがって、SLatch の取得は基本的に次のようになります。

マルチスレッド テストを実行すると、ツリーの動作に非常に奇妙なパターンが見られます。テストでは、16 コアのマシンと 10 000 000 ロングを使用しました。ツリー キーの数は 16 であるため、600,000 近くの DataNode オブジェクトと 70,000 の IndexNode オブジェクトがあります。

8 つのスレッドで同時にテストを実行すると、ツリーに値が挿入されます。最初は、コアの使用量が 1 コアから 3 に直線的に増加していることがわかります。しかし、開始からしばらくすると、平均で 1.5 コアに戻り、コア使用率が一定になります。並列プロファイラでは、ピーク前は 3 つのコア プロセスが互いに待機してほとんどスリープしていましたが、ピーク後には互いにブロックされるのを待機し始めました。

問題をどこで見るべきか、または私が使用するアプローチの欠陥は何か、誰かがアイデアを提案できますか?

ありがとう。

私が作成した以前の B ツリーの実装から B+ ツリーを作成しようとしていますが、ここで本当に失われました...実装しようとしている B と B+ の唯一の違いは、葉を削除するのではなく、葉にキーを保存することです。
例:
最終 B ツリー
3 6 false
1 2 true
4 5 true
7 8 9 10 true

最終 B+ ツリー
3 6 偽
1 2 真
3 4 5 真
6 7 8 9 10 真

これは私が B ツリーのために持っているものです (コード全体を投稿したくはありませんでしたが、すべてを説明するのは難しく混乱するでしょう)。少なくともいくつかのアイデアをいただければ幸いです...

MAIN

BツリーNODE

Bツリー

練習問題の 1 つにこの質問があり、どうすればそれを行うことができるのか疑問に思っていました。どんな助けでも大歓迎です。

ノードに 2 つの検索キー値と 3 つのポインターを含めることができる次の B+ ツリーを考えてみましょう。

検索キーの値が 38 の新しいレコードを挿入した後、B+ ツリーを再描画します。

これが私が答えるべきだと思ったものです

データ ストレージに CSharpTest.Net.BPlusTree ライブラリを使用しています。異なるプロセスから同じツリーを読み取るにはどうすればよいですか?