B木（Bツリー）とは？データ構造の特徴と基本操作をわかりやすく解説
本記事では、B木（B-Tree）について詳しく解説します。B木は、m-way探索木を特殊化したデータ構造であり、ディスクアクセスを目的として広く利用されています。
B木の基本構造
次数（オーダー）が m のB木では、1つのノードが最大で m-1 個のキーと m 個の子を持つことができます。この特性により、1つのノードに大量の要素を格納できるため、木全体の高さが比較的低く抑えられる点が大きな利点です。高さが低いということは、検索時にアクセスするノード数が少なくて済むため、ディスクI/Oのコストが高い環境、たとえばデータベースやファイルシステムにおいて特に有効です。
B木の満たすべき性質
B木はm-way木のすべての性質を備えているほか、以下のような固有の性質も持っています。
- すべてのノードは最大で m 個の子を持つ
- 根（ルート）と葉以外のノードは、最低でも ⌈m/2⌉ 個の子を持つ
- 根ノードは最低でも2個の子を持つ必要がある
- すべての葉ノードは必ず同じレベル（深さ）に存在する
B木の例
下図はB木の構造イメージです。
基本操作とキーの並び順
B木では、検索・挿入・削除といった基本的な操作をサポートしています。各ノード内の要素（キー）は常にソートされた状態で保持されます。位置 i にあるキーに対して、その前後に子ノードが対応しており、左側の子にはより小さい値が、右側の子にはより大きい値が格納されます。この規則性により、二分探索と同様の要領で効率的に目的のキーをたどることができます。
-
B木（B-Tree）の探索：データ構造におけるB木クエリの仕組み
B木（B-Tree）は、データベースやファイルシステムなどで広く利用されている平衡多分木構造です。ここでは、B木における要素の探索方法、いわゆる「B木クエリ」の実行手順について詳しく解説します。 B木の探索例 以下のようなB木を例に考えてみましょう。 B木の例： B木の探索手法は、二分探索木（Binary Search Tree）と非常によく似ています。例として、上記の木から「66」という値を検索する場合の手順を見てみましょう。 まず根（ルート）から探索を開始します。目的の値66は根の要素46よりも大きいため、右側の子ノードへ移動します。 右の子ノードには複数の要素がソートされた状態で
-
ハーフエッジデータ構造（HalfedgeDS）とは？基本概念とCGAL実装例をわかりやすく解説
はじめにテンプレートパラメータとして用いられるハーフエッジデータ構造（Halfedge Data Structure、略称 HalfedgeDS）は、頂点・辺・面の接続情報（インシデンス情報）を管理できる、辺を中心としたデータ構造として定義されています。平面地図（planar map）や多面体など、任意の次元空間に埋め込まれた向き付け可能な2次元曲面の表現に適した構造です。このデータ構造では、各辺が逆向きの向きを持つ2つのハーフエッジ（半辺）に分割されます。各ハーフエッジは、隣接する1つの面と1つの頂点への参照を保持し、逆に各面および各頂点にも、それぞれ1つの接続ハーフエッジが格納されます。さ