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

6章Bツリーの亜種

Bツリーの亜種には、共通点がいくつか見られます。たとえばツリー構造、スプリットとマージによるバランシング、検索と削除のアルゴリズムなどです。同時実行性に関連するその他の詳細、たとえばディスク上でのページの表現、兄弟ノード間のリンク、メンテナンスプロセスなどは、実装ごとに異なっている場合があります。

この章では、効率的なBツリーの実装に使用できるいくつかの技術と、それらを採用した構造について議論します。

• コピーオンライトBツリー（Copy-on-write B-Tree）は、構造がBツリーと似ていますが、ノードはイミュータブルであり、変更箇所の上書きは行われません。その代わりに、ページのコピー、更新、および書き込みは新しい場所で行われます。
• 遅延Bツリー（Lazy B-Tree）は、ノードへの更新をバッファリングすることで、後続の同じノードへの書き込みでI/O要求を削減します。次の章では、2コンポーネントLSMツリー（「7.1.1.1　2コンポーネントLSMツリー」）を取りあげる予定ですが、このツリーでは、バッファリングをもう一歩進めて、完全にイミュータブルなBツリーを実装します。
• FDツリー（FD-Tree）は、バッファリングに対して異なるアプローチをとります。これは、LSMツリー（「7.1　LSMツリー」）に少し似ています。FDツリーでは、小さなBツリーで更新をバッファリングします。このツリーが一杯になると、すぐにその内容がイミュータブルな配列として書き込まれます。更新は、イミュータブルな配列のレベルの間で上位レベルから下位レベルまでカスケードして伝播します。
• Bwツリー（Bw-Tree）は、Bツリーのノードがいくつかの小さな部分に分割され、それらが追記型で書き込まれます。これにより、更新を異なるノードに一括して行うことで、小さな書き込みのコストを削減します。 ...