data-structures - Bツリーページとは

Question

B ツリーとは何かは知っていると思いますが、B ツリー ページとは何ですか?

Answer 1

B ツリーは、データベースに見られるような非常に大きなコレクションの一般的なデータ構造です。一度にメモリに保持するには大きすぎることが多いため、ディスク上のファイルに格納され、現在の操作に必要な部分のみがメモリに読み込まれます。

1 つの単位としてディスクに格納される (およびメモリに読み込まれる) データは、ページと呼ばれます。B ツリーでは、ノード サイズがファイル システムの自然なページ サイズと等しくなるように、1 つのノードに多数のレコードを格納するのが一般的です。このようにして、ディスクアクセスを最適化できます。

たとえば、ファイル システムが本来 16 kb のデータ ブロックで動作し、B ツリー内のレコードのサイズが 500 b (ノードの次のレベルへのリンクを含む) である場合、32 個のレコードを B ツリーに格納できます。ノードのサイズをページ サイズと等しくし、ディスク アクセスを最適化できるようにします。

Answer 2

Bツリーはn個のアリティを持つツリーであるため、ページは現在のノードからの要素を収容する正確に「n」個のセルであり、それらは下を参照します。B+ ツリーの場合、データを格納するためのメタノード (参照のみを保持する) およびリーフノードとして使用できます。