私は索引付けのために B+tree を研究しており、構造を覚えるだけでなく、それ以上のことを理解しようとしています。私が理解している限り、B ツリーの内部ノードは葉にインデックスを形成し、葉にはディスク上のデータが格納されている場所へのポインターが含まれています。正しい？では、ルックアップはどのように行われるのでしょうか。B+木が二分木よりはるかに優れているのなら、どこでも二分木の代わりに B+木を使用しないのはなぜですか?
B+ ツリーに関するウィキペディアの記事を読み、構造は理解していますが、実際の検索がどのように実行されるかは理解していません。読み物へのリンクを教えていただけませんか？
データベースのインデックス作成以外に、B+ ツリーにはどのような用途がありますか?
私はインデックス作成のために B+tree を研究しており、構造を覚えるだけでなく、それ以上のことを理解しようとしています。私が理解している限り、B ツリーの内部ノードは葉にインデックスを形成し、葉にはディスク上のデータが格納されている場所へのポインターが含まれています。正しい？
いいえ、インデックスは内部ノード (非リーフ) によって形成されます。実装に応じて、リーフにはキーと値のペアまたはキーと値のペアへのポインターのいずれかが含まれる場合があります。たとえば、データベース インデックスは後者を使用しますが、IOT (Index Organized Table) の場合は値がリーフにインライン化されます。これは主に、値がキーに対して非常に大きいかどうかに依存します。
では、ルックアップはどのように行われるのでしょうか。
ルート ノードが葉ではない一般的なケース (最初はそうです) では、ルート ノードには、N 個のキーと N+1 個のポインターの並べ替えられた配列が含まれます。2 つのキー S0 と S1 を二分検索するとS0 <= K < S1(K は探しているものです)、次のノードへのポインターが得られます。
キーと値のペアの並べ替えられたリストを含むリーフ ノードに (最終的に) ヒットするまでプロセスを繰り返し、最後のバイナリ検索をそれらに渡します。
B+木が二分木よりはるかに優れているのなら、どこでも二分木の代わりに B+木を使用しないのはなぜですか?
読み物へのリンクを教えていただけませんか？
私が説明した大まかなアルゴリズムがお役に立てば幸いです。それ以外の場合は、コメントでお気軽にお問い合わせください。
データベースのインデックス作成以外に、B+ ツリーにはどのような用途がありますか?
同様に、ファイル システムのインデックス作成にもメリットがあります。
アイデアは常に同じです。B+Tree は、小さなキー/大きな値とキャッシングで非常に優れています。アイデアは、すべてのキー (内部ノード) を高速メモリ (CPU キャッシュ >> RAM >> ディスク) に保持することであり、B+Tree はキーを一番下にプッシュすることで大規模なコレクションを実現します。すべての内部ノードが高速メモリ内にあるため、(値を取得するための) 検索ごとに低速メモリ アクセスが 1 回しかありません。
B+ ツリーは、すべての dbms が使用するバイナリ ツリーよりも優れています。
B+Tree でのルックアップは、LOGF N が LOG のベースであり、ファン アウトです。ルックアップはバイナリ ツリーとまったく同じように実行されますが、ファン アウトが大きく、高さが低いため、はるかに優れています。
B+Tree は通常、葉にデータがあることで知られています (クラスター化されていない場合はおそらくそうではありません)。これは、データを取得するためにディスクに再度ジャンプする必要がなく、葉から取得するだけであることを意味します。
B+Tree はほぼどこでも使用されており、オペレーティング システムは B+Tree を使用しており、データ ウェアハウス (ここではあまり使用されていませんが、現在も使用されています)、多くのアプリケーションで使用されています。
B+Tree は範囲クエリに最適で、主キーなどの一意の値がある場合やカーディナリティの低いフィールドがある場合に使用されます。
この本http://www.amazon.com/Database-Management-Systems-Raghu-Ramakrishnan/dp/0072465638を入手できれば、最高の本です。それは基本的に、すべてのデータベース担当者のバイブルです。