私は、CouchDBに似たファイルアーキテクチャ、つまり追加専用のb+treeを使用して単純なキー/値ストアを作成することを計画しています。
私はB+ツリーで見つけることができるすべてのものとCouchDBの内部で見つけることができるすべてのものを読みましたが、ソースコードを処理する時間がありませんでした（非常に異なる言語であるため、それ自体の権利）。
だから私はB+ツリーノードのサイズについて質問があります：キーの長さが可変である場合、ノードを同じ長さ（バイト単位）に保つ方が良いですか、それとも同じ数のキーを与える方が良いですか？ / child-pointersは、どれだけ大きくなっても？
従来のデータベースでは、データファイルのスペースが固定サイズのページで管理されているため、B +ツリーノードはバイト単位の固定長（たとえば8K）に保たれていることに気付きました。ただし、ドキュメントの長さを指定でき、更新されたツリーノードが後に書き込まれる追加専用ファイルスキームでは、固定サイズのノードを使用する利点はないようです。
Bツリーの目標は、ディスクアクセスの数を最小限に抑えることです。ファイルシステムのクラスターサイズが4kの場合、ノードの理想的なサイズは4kです。また、ノードは適切に配置されている必要があります。ノードの位置がずれていると、2つのクラスターが読み取られ、パフォーマンスが低下します。
ログベースのストレージスキームでは、アライメントを改善するためにログにギャップが作成されない限り、4kノードサイズを選択することはおそらく最悪の選択です。それ以外の場合、99.98％の時間で1つのノードが2つのクラスターに格納されます。ノードサイズが2kの場合、これが発生する確率は50％弱です。ただし、ノードサイズが小さい場合は問題があります。つまり、bツリーの平均の高さが高くなり、ディスククラスターの読み取りに費やされる時間が十分に活用されません。
ノードサイズを大きくするとツリーの高さが低くなりますが、ディスクアクセスの数も増えます。ノードが大きくなると、ノード内のエントリを維持するためのオーバーヘッドも増加します。ノードサイズがデータベース全体をカプセル化するのに十分な大きさのBツリーを想像してみてください。ノード自体、おそらく別のBツリー内に、より良いデータ構造を埋め込む必要がありますか？
私は、追加のみのログ形式でb-tree実装のプロトタイプを作成することに時間を費やし、最終的にはその概念を完全に拒否しました。ノード/クラスターの不整合によるパフォーマンスの低下を補うために、非常に大きなキャッシュが必要です。従来のストレージアプローチでは、RAMをより有効に活用できます。
最後の打撃は、ランダムに並べられたインサートのパフォーマンスを評価したときでした。これにより、ディスクでバックアップされたストレージシステムのパフォーマンスが低下しますが、ログベースの形式ではさらに多くの問題が発生します。最小のエントリでも書き込むと、複数のノードがログに書き込まれ、内部ノードは書き込まれた直後に無効になります。その結果、ログは急速にゴミでいっぱいになります。
BerkeleyDB-JE（BDB-JE）もログベースであり、そのパフォーマンス特性も調べました。それは私のプロトタイプがしたのと同じ問題、つまりゴミの急速な蓄積に苦しんでいます。BDB-JEには、残っているレコードをログに再追加する「よりクリーンな」スレッドがいくつかありますが、ランダムな順序は保持されます。その結果、新しい「クリーンな」レコードは、ゴミでいっぱいのログファイルをすでに作成しています。システムの全体的なパフォーマンスが低下し、実行されているのはよりクリーンなものだけになり、すべてのシステムリソースが占有されます。
ログベースの形式は、堅牢なデータベースをすばやく実装できるため、非常に魅力的です。アキレス腱はクリーナーであり、重要です。キャッシング戦略も正しく行うのが難しいです。