1

これは宿題からです：

各ページ (ディスク ブロック) が 16K バイトで、各 KVP が 8 バイトであるとします。したがって、最小サイズ (16000/8)/2 = 1000 の B ツリーを使用することにします。T をそのような B ツリーとし、T の高さを 3 と仮定します。 Tに保存されますか？あなたの答えを簡単に説明してください。

B ツリーのプロパティにより、次の点に注意してください。
各ノードには最大 2000 個のキーがあります。
各ノードには少なくとも 1000 個のキーがあります (ルート ノードを除く)。

メモリがどのようにキーの数を制限しているのか理解できません。各ページには 16000 バイトのスペースがあり、各キーは 8 バイトを占めるため、各ページには 2000 個のキーを格納できます。これは、とにかく各レベルで格納できるキーの最大数です。

以下は私の計算です:
キーの最小数 = 1000(1001)(2) + 1 = 最小で 2002001 キー
(ルートは少なくとも 1000 キーを持つように制限されていないため) キー
の最大数 = 2000(2001)(2001 ) = 最大 8008002000 キー

質問がこれほど単純ではないため、何か重要なものが欠けていると感じています。

4

1 に答える 1

2

やや露骨なヒント: 各非リーフ ノードには、右と左の子があります。さらに、キーと値のペアへのポインターがありますが、それらは格納されている可能性があります。(1000 は多いように思えます...) 1000 以上のデータ ポイントをどのように保存するかを考えてみてください。

+-------------+
| | ルート | ルート
| | 左右 |
+---+------+---+
    | | | |
    | | +---+----------+
    | | | | レベル 2 +---データ: リスト、ハッシュ テーブルなど
    | | | | 左右 |
    | | +---+------+---+
    | | | | | |
    | | 等等
    | |
+---+----------+
| | レベル 2 +---データ: リスト、ハッシュ テーブルなど
| | 左右 |
+---+------+---+
    | | | |
    等等
于 2010-11-07T03:48:28.347 に答える