algorithm - B+木の構築

Question

次の B+ ツリーを作成するように依頼されたとします。

i) n = x. 

ii) order = x.

iii) degree = x.

iv) p = x.

いいえ何をする必要があります。上記の各ケースで、各ノードに含めることができるキーとポインターの数は?

Answer 1

B+ ツリーでは、Orderは各内部ノードの子ポインターの最大数を示します。つまり、B+ ツリーの Order が m の場合、各内部ノードは最大で m 個の子 (その後、m-1 個のキー) と少なくともCEILを持つことができます。 (m/2) 子ポインターの数 (ルートを除く)。

B+ ツリーの次数については、このから、d が B ツリーの次数である場合、各ノードには最大 2d の項目 (キー) を含めることができるという情報を取得しました。さて、B木もB+木も多元木なので、次数の定義は変わらないと思います。同じ事実を示すコメントとして指定された $LINK も確認してください。

n の場合、JustinDanielson が述べたように、ノードに格納されているキーの総数である可能性があり、その場合、子ポインターの数は n+1 (質問の場合は x+1) になります。