1

私は論文を読んでいて、B+-trees をメイン メモリのキャッシュに意識させています。セクション 3.1.2では、著者は CSB+ ツリー ノード内で検索するためのいくつかのアプローチについて説明しています。

基本的なアプローチは、従来の while ループを使用してバイナリ検索を実行することです。

統一されたアプローチは、すべてのキーが使用されていると仮定して、while ループをステートメントに展開するコード展開によるものです。if-then-else

著者は、最大 9 個のキーを持つノードの検索の展開を示す次の例を示しています。ifノード内の数字は、テストで使用されているキーの位置を表します

              4
            /   \
           2     6
          / \   / \
         1   3 5   8
                  / \
                 7   9

次に、紛らわしい部分があります。

実際に存在するキーが 5 つだけの場合、ちょうど3 回の比較でこのツリーをたどることができます。一方、最も深いサブツリーを右ではなく左に配置する展開では、一部の分岐で4 回の比較が必要になります。

では、なぜ次のツリーでさらに比較が必要になるのでしょうか。

              6
            /   \
           4     8
          / \   / \
         2   5 7   9
        / \
       1   3

さらに、

有効なキーが 5 つしかないとわかっていれば、平均して3 回ではなく2.67回の比較を使用するツリーをハードコーディングできます。

2.67はどのように発生しますか?

ヒントをいただければ幸いです。また、コード拡張の知識へのリンクも役立ちます。

実際、ここに転記したときにいくつかの重要な情報が省略されている可能性があるため、紙で質問することが適切かどうかはわかりません (質問を再フォーマットする必要がある場合があります)。たまたま新聞を読んだ人がいてくれたらいいのにと思います。

ありがとう

4

1 に答える 1

1

ここでの重要な点は、同じセクションからの次の引用です。

ノード内のすべての未使用のキー (keyList[nKeys..2d-1]) を可能な限り最大のキーでパディングします。

B+/CSB+ ツリーでは、ノード値ではなく、これらの値の間の間隔を検索することも重要です。可能な値のセットは、5 つのキーによって 6 つの間隔に分割されます。

右側のサブツリーのほとんどが可能な最大のキー (L) で満たされているため、通常よりも少ない比較で済みます。

              4
            /   \
           2     L
          / \   / \
         1   3 5   L
                  / \
                 L   L

ルート ノードの右の子孫には可能な最大のキーがあり、その右側のノードをチェックする必要はありません。そして、間隔ごとに正確に 3 つの比較が必要です。

interval   comparisons
up to 1    k>4, k>2, k>1
 1..2      k>4, k>2, k>1
 2..3      k>4, k>2, k>3
 3..4      k>4, k>2, k>3
 4..5      k>4, k>L, k>5
 5..L      k>4, k>L, k>5

最も深いサブツリーを左側に配置すると、空でないノードが 1 レベル深く配置されたツリーができます。

              L
            /   \
           4     L
          / \   / \
         2   5 L   L
        / \
       1   3

このツリーでノード「1」を検索するには、キーを 4 つの異なるノード (L、4、2、および 1) と比較する必要があります。

有効なキーが 5 つしかないことがわかっている場合、次のツリーがあります。

              2
            /   \
           1     4
                / \
               3   5

ここでは、平均で 2.67 回の比較が行われるように比較を整理できます。

interval   comparisons
up to 1    k>2, k>1
1..2       k>2, k>1
2..3       k>2, k>4, k>3
3..4       k>2, k>4, k>3
4..5       k>2, k>4, k>5
5..L       k>2, k>4, k>5

「コード展開」は広く使用されている用語ではないため、最も関連性の高いリンクを提供することはできません。これは「ループ巻き戻し」とさほど変わらないと思います。

于 2012-09-15T15:28:45.503 に答える