B +ツリー検索は、リーフノードのすべてのキーデータがメモリ内にあるバイナリ検索ツリー検索よりも優れたパフォーマンスを発揮できますか？

Question

メモリにB +ツリーを実装し、内部ノードにキーがあり、リーフノードにキーデータペアがあるとします。 ファンアウトfのB +ツリーの場合、B +ツリーの高さはlog_f N（Nはキーの数）、対応するBSTの高さはlog_2 Nとなります。 実行していない場合ディスクの読み取りと書き込み、B +ツリーの検索パフォーマンスはバイナリ検索ツリーの検索のパフォーマンスより優れていますか？どうやって？ 各内部ノードのB +ツリーでは、BSTに対して1を選択すると、Fに対して多くの選択肢が決定されるため、

Answer 1

少なくともキャッシュと比較すると、メインメモリはディスクドライブと同じ特性の多くを持っています。これはかなり高い帯域幅を持ちますが、キャッシュよりもはるかに高い遅延です。それは、かなり大きい最小読み取りサイズを有し、読み取りが予測可能である場合（例えば、連続したアドレスに多数のキャッシュラインを読み取った場合）、実質的により高い帯域幅を与える。そのように、それは同じ一般種類の最適化の恩恵を受ける（ただし、詳細はしばしば変化する）。

Bツリー（およびB *ツリーやB +ツリーなどのバリアント）は、ディスクドライブで十分にサポートされているアクセスパターンとうまく機能するように明示的に設計されています。とにかくかなりの量のデータを読まなければならないので、読んでおく必要のあるメモリ量を最大限に活用するためにデータをパックすることもできます。いずれの場合も、予測可能なパターン（特に、連続するアドレスでの連続した読み取りの回数）で最小限の読み取りの何倍かを読み取ることによって、頻繁に大きな帯域幅を得ることができます。そのため、1ページのサイズを、一度に読むことができる最小サイズよりもさらに大きくすることがよくあります。

同様に、どちらの場合も、私たちが実際に気にするデータを見つける前に、ツリー内のいくつかのノードの層を降りる予定です。ディスクから読み込むときと同じように、私たちが実際に気にするデータが見つかるまで、読み込んだデータのキーの密度を最大にすることができます。典型的なバイナリツリーの場合：

template <class T, class U> 
struct node { 
    T key; 
    U data; 
    node *left; 
    node *right; 
}; 

...私たちは実際には使用していないデータ項目の数を読み上げます。それは、私たちが必要とする適切なキーが見つかったときにのみ、関連するデータを取得したいときです。公平に、我々はノード構造にのみ、かなりマイナーな変更で、同様のバイナリツリーであることを行うことができます。

template <class T, class U> 
struct node { 
    T key; 
    U *data; 
    node *left; 
    node *right; 
}; 

今、ノードは、データへのポインタではなく、データそのものが含まれています。 dataが小さい場合、これは何も成し遂げられませんが、大きければ大きな成果を上げることができます。

要約：CPUの観点からは、メインメモリからの読み出しは、ディスクからの読み出しと同じ基本的な特性を持っています。ディスクには同じ特性の極端なバージョンが表示されます。したがって、Bツリー（およびバリアント）の設計につながった設計上の考慮事項のほとんどは、主メモリに格納されたデータに同様に適用されるようになりました。

Bツリーはうまく機能し、メモリ内ストレージに使用すると大きなメリットが得られることがよくあります。