要素のサイズが異なる場合のBツリー不変量の維持方法

Question

オーダーmのBツリーの場合、ルートを除くすべてのノードはm-1から2m-1までの要素を含んでいなければならず、各要素は少なくとも1つのキーであり、いくつかの追加のデータ（例えば値）である。しかし、各ノードは、下にあるブロックデバイスで良好なパフォーマンスを得るために、一定の合計サイズを選択する必要があります。要素が可変サイズの場合はどうなりますか？

SQLite3には、ブロックサイズの部分をノードに追加するスキームがあるようですが、MySQLではレコードのサイズを宣言することができます（たとえば、文字列だけでなく、 。他にどんなソリューションがありますか？そして、他のものを選ぶとき、人々は何を考えますか？

編集：そして、前の文で、私は意味、データベース開発者はが他の上、そのB-木一つの方法を実施することを決定するときについてどう思いますか？

（私は今、データベースのコースにいるので、私は特定のシステムの詳細よりも、理論と設計角度でより興味があります。）

Answer 1

私は、これは非常に良い質問だと思います。 RDBMSベンダーはすべてわずかに実装が異なりますが、基本的な理論は同じで、ベンダー選定の決定要因としてbツリー実装を使用する人はいないでしょう。

私が理解するように、各bツリーページの基本構造にはキーとポインタが含まれています。ポインタは、関連するデータレコードを参照する最終的なポインタとともに、より多くのキーとポインタを含む他のページを絶えず参照します。

可変長キーを処理する方法は面白いです。おそらく他のベンダーはベンダー固有の解決策を明らかにすることができます。

Answer 2

SQL Serverのキーの長さは最大900バイト、ページサイズは8192バイトです。実際に900バイトのキーがある場合は、インデックスの中間レベルのページに9（または8）行しか収まらないでしょう。これは、分岐因子が通常よりも低いことを意味します。これは理論的なBツリー不変量に違反するかもしれませんが、これは単なる学術的な関心事であり、パフォーマンスを著しく損なうものではありません。関与するアルゴリズムの漸近的な複雑さは変化しません。

要するに、これはまったく学問的な問題です。