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

2章Bツリーの基本

前章では、ストレージ構造をミュータブルとイミュータブルという2つのグループに分類し、イミュータビリティがストレージの設計と実装に影響する中核的な概念の1つであることを確認しました。ミュータブルなストレージ構造の大半では、上書きメカニズムが使用されます。つまり、挿入、削除、または更新の操作時に、ターゲットファイル内のもとと同じ箇所でレコードが直接更新されます。

ストレージエンジンでは多くの場合、同じデータレコードの複数のバージョンがデータベース内に存在することが可能です。たとえば、マルチバージョンの同時実行制御（「5.3.6　マルチバージョン同時実行制御」）や、スロット化ページの構成（「3.5　スロット化ページ」）を使用するときです。説明を単純にするために、今のところは各キーが個別の場所に格納された1つのデータレコードのみと関連付けられていると仮定します。

Bツリーは、もっともポピュラーなストレージ構造の1つです。多くのオープンソースデータベースシステムがBツリーに基づいており、長年に渡って大多数のユースケースに対応できることが証明されてきました。

Bツリーは、最近考案されたわけではありません。1971年にRudolph BayerとEdward M. McCreightによって紹介され、長年に渡って支持を得てきました。1979年までには、かなりの数のBツリーの亜種がすでに存在していました。Douglas Comerがそれらの一部を調査して体系化しました[COMER79]。

Bツリーの検討に入る前に、たとえば二分探索木、2–3ツリー、AVLツリーなどの伝統的な検索ツリーに代わる手段を考慮する理由を先に説明します[KNUTH98]。そのために、二分探索木がどのようなものであるかについて復習しましょう。 ...