BSTよりもB +ツリーの利点？

Question

私はデータベースに関するクラスのB +ツリーについて学んでいます.B +ツリーがバイナリ検索ツリーに与える具体的なメリットは何ですか？

ほとんどの操作でO（logN）の複雑さがあるようですが、B +ツリーでは、明らかにO（1）時間しかかからない各子ノードでの検索時間がわずかですどの子ノードに進むかを指定します。

B +ツリーは、BSTよりもデータベースで人気があります。

Answer 1

バイナリ検索ツリーよりもB +ツリー（および一般にBツリー）の主な利点は、キャッシュでうまくいくことです。ノードが多かれ少なかれランダムな順序でメモリに格納されているバイナリ検索ツリーを持っている場合は、ポインタをたどるたびにマシンは新しいメモリブロックをプロセッサキャッシュにプルする必要があります。既にキャッシュにあるメモリにアクセスします。

B +ツリーおよびBツリーは、各ノードに膨大な数のキーまたは値を格納させ、多数の子を持つことによって機能します。それらは、通常、単一のノードがキャッシュにうまく収まるように（または、ディスクに格納されている場合は、単一の読み取り操作でディスクから引き出されるように）一緒にパックされます。ノード内のキーを見つけたり、次に読み取る子を決定したりするためには、さらに多くの作業を行う必要がありますが、単一のノードで実行されるすべてのメモリアクセスがディスクに戻らずに済むため、アクセス時間は非常に短くなります。これは、基本的にBSTがメモリアクセスの番号の点でより良いかもしれないが、B +ツリーおよびBツリーは、これらのメモリアクセスのランタイムの点でより良好に実行できることを意味する。

B +ツリーまたはBツリーの一般的な使用例は、膨大な量の情報があり、データが非常に多く、メインメモリにすべて収まるわけではないデータベースにあります。したがって、データは、どこかのハードディスク上のB +ツリーまたはBツリーに格納することができます。これにより、検索中にデータをプルするのに必要なディスク読み取りの回数が最小限に抑えられます。いくつかのファイルシステム（ext4のようなものだと思いますが）は、同様の理由でBツリーも使用します。必要なディスクルックアップの数を最小限に抑えます。これは実際のボトルネックです。

希望すると便利です。

Answer 2

データの実際の保存（DBなど）には、多くのデータを保存する必要があります。データ検索は基本的な操作であるため、RAMよりもディスクからデータを読み取るのに時間がかかります。

さて、これは... B +木に比べてノードに少ないデータ

BST格納キャッチあります。この結果、B +ツリーよりもBSTの高さが高くなります。したがって、それらはRAMではなくディスクに保存されます。

ツリーからデータを取り出す必要があるたびに、ディスクからのデータをメインメモリにロードする必要があります（もちろん、時間がかかるプロセスです）.B +ツリーの場合は、データは既にRAMに格納されており、必要なノードは直接フェッチされ、多くの子を含むノードからデータが取得されます（ただし、ディスクからデータをロードする必要がないため、B +ツリーの場合はデータ取得時間が短くなります） RAMへ）。