次数 m の B ツリーの場合、ルートを除くすべてのノードには m-1 から 2m-1 の要素が含まれている必要があります。ここで、すべての要素は少なくともキーであり、場合によっては追加のデータ (値など) も含まれます。ただし、基礎となるブロック デバイスで良好なパフォーマンスを得るには、各ノードで一定の合計サイズを選択する必要があります。要素のサイズが可変の場合はどうなるでしょうか。
SQLite3 には、追加のブロック サイズの断片をノードに追加するスキームがあるようです。MySQL では、レコードのサイズを宣言できます (たとえば、フィールドを単なる文字列ではなく、ある程度のサイズの文字列にすることができます)。他にどのような解決策がありますか? そして、どちらかを選ぶとき、人々は何を考えますか?
編集: 前の文で、データベース開発者は、B ツリーを実装する方法を決定するときに何を考えているのでしょうか?
(私は現在データベースのコースにいるので、特定のシステムの詳細よりも理論と設計の角度に興味があります。)
SQL Server は、8192 バイトのページ サイズで最大 900 バイトのキー長を持つことができることを知っています。実際に 900 バイトのキーがある場合、インデックスの中間レベルのページには 9 (または 8) 行しか収まりません。これは、分岐係数が通常よりも低いことを意味します。これは、理論上の B ツリーの不変条件に違反する可能性がありますが、これは単に学術的な問題であり、パフォーマンスを大幅に妨げるものではありません。関連するアルゴリズムの漸近的な複雑さは変わりません。
要するに、これは純粋に学術的な問題です。
これはかなり良い質問だと思います。RDBMS ベンダーはすべて実装がわずかに異なりますが、根底にある理論は同じであり、ベンダーを選択する際の決定要因として B ツリーの実装を使用する人はいないと思います。
私が理解しているように、各 b ツリー ページの基本構造にはキーとポインターが含まれています。ポインターは、より多くのキーとポインターを含む他のページを継続的に参照し、最後のポインターは関連するデータ レコードを参照します。
可変長キーの扱い方が面白い。おそらく、他の人がベンダー固有のソリューションに光を当てることができます.