12

「アルゴリズムの紹介」の「B-Trees」の章に従って、B-Tree を実装しようとしています。

私がよくわからないのは、「最小限の程度」です。この本では、次数は、ノードが保持できるキーの数の下限/上限を表す数値であると述べられています。それはさらに次のように述べています。

  1. すべての非ルート ノードは、少なくともキーを格納し、子t - 1を持ちますt。
  2. すべてのノードは最大でもキーを格納し、子2*t - 1を持ちます2*t。

したがって、t = 2 の場合は次のようになります。

  1. t - 1= 1 キーおよび t = 2 子
  2. 2*t - 1= 3 つのキーと 4 つの子

t = 3 の場合

  1. t - 1= 2 つのキーと t = 3 つの子
  2. 2*t - 1= 5 つのキーと 6 つの子

ここで問題があります。B ツリーのノードは、満杯のときに奇数のキーしか格納できないようです。

最大で 4 つのキーと 5 つの子を持つノードを作成できないのはなぜですか? ノードの分割と関係がありますか?

4

2 に答える 2

3

B-Tree のノードは奇数のキーしか格納できないようですか?

絶対にありません。あなたが書いた数字は、それぞれキーの最小数と最大数であるため、 の場合t = 2、1、2、3 キーを持つノードが許可されます。の場合t = 3、2、3、4、5 個のキーを持つノードが許可されます。

さらに、ツリーのルートは 1 つのキーのみを持つことができます。

たとえば、ツリーを定義 (および実装) することができます。ノード内の 1 つまたは 2 つのキー (いわゆる 2 ～ 3 ツリー)。B ツリーがもう 1 つ収容できるように定義されている理由は、これによりパフォーマンスが向上するためです。特に、これにより償却されたO(1)(分割操作と結合操作をカウントする) 削除操作と挿入操作が可能になります。

于 2010-08-18T22:23:46.843 に答える
1

不可能ではありませんが、最適ではありません。奇数の子を持つノードをどのように分割しますか?

于 2010-08-18T21:52:36.497 に答える