詳説 データベース ―ストレージエンジンと分散データシステムの仕組み

4章Bツリーの実装

前章では、バイナリフォーマット構成の一般的な原則について検討し、どのようにしてセルを作成し、階層を構築するか、さらにポインタを使用してそれらをどうページと接続するかを学習しました。これらの概念は、データの更新を直接上書きするストレージ構造でも、追記のみのストレージ構造でも、両方に適用できます。この章では、Bツリーに固有の概念をいくつか検討します。

この章のセクションは、3つの論理的なグループに分かれています。最初に、構成について検討します。つまり、キーとポインタの間の関係を確立する方法、およびヘッダとページ間のリンクを実装する方法について検討します。

次に、ルートからリーフへと下っていくプロセスについて検討します。つまり、二分探索を実行する方法、およびパンくずリスト（たどってきた経路を戻れるように残すポインタのこと）を収集し、後でノードのスプリットまたはマージが必要になるときに備えて親ノードを追跡する方法について検討します。

最後に、最適化技術（リバランシング、右側限定の追加、バルクロード、メンテナンスのプロセス）、およびガベージコレクションについて検討します。

4.1　ページヘッダ

ページヘッダには、ページに関する情報が保持されます。この情報は、ナビゲーション、メンテナンス、および最適化に使用できます。この情報には通常、ページの内容とレイアウトを記述したフラグ、ページ内のセルの数、セルのオフセットとデータを追加するために使用される空き領域の範囲を示す下限オフセットと上限オフセット、およびその他のメタデータが含まれます。

たとえば、PostgreSQL（https://databass.dev/links/12）では、ページのサイズとレイアウトのバージョンがヘッダに格納されます。MySQL ...