私は論文を読んでいて、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はどのように発生しますか?
ヒントをいただければ幸いです。また、コード拡張の知識へのリンクも役立ちます。
実際、ここに転記したときにいくつかの重要な情報が省略されている可能性があるため、紙で質問することが適切かどうかはわかりません (質問を再フォーマットする必要がある場合があります)。たまたま新聞を読んだ人がいてくれたらいいのにと思います。
ありがとう