物理設計・インデックス・障害回復 重要度:★★★出題: AM2・PM1・PM2
B+木索引（B+-Tree Index）の構造と索引更新コスト
びーぷらすきさくいんのこうぞうとさくいんこうしんこすと / B+-Tree Index Structure and Maintenance Cost
ルートページ・中間ページ・リーフページの平衡木構造をもち、すべてのリーフページを双方向ポインタで連結することで等値検索と範囲検索の両方を高速化するRDBMSの標準索引。
3行速習ポイント
- ルートからすべてのリーフまでの深さ（段数）が常に等しい平衡木であり、O(log N)の少ないページ読込みで目的のキーに到達できる
- 実データ行へのポインタ（ROWID/TID）はリーフページのみに保持され、リーフページ間がポインタで順序連結されているため範囲走査（Index Range Scan）が高速
- 一方で、索引構成列の値がUPDATEされるたびに索引エントリーの削除・挿入および索引ページのロックが発生するため、頻繁に状態遷移する列への索引付与はロック競合の原因となる
図解
図B+木索引の3層ページ構造（平衡木）
Depth 1
ルートページ（Root Page）
木構造の最上位1ページ（バッファプール常駐）。探索の起点となる
↕
Depth 2
中間ページ（Branch / Internal Page）
キー範囲の境界値と下位ページへのポインタを保持し分岐探索を行う
↕
Depth 3
リーフページ（Leaf Page）
全キー値とデータ行ポインタ（ROWID）を保持し、双方向ポインタで範囲走査に対応
概要と本質
RDBMSで最も標準的に使われる索引構造です。検索性能を飛躍的に高める一方、INSERT・DELETE時および「索引キー列のUPDATE時」には索引自体のメンテナンスコストと索引ページへの排他制御が発生します（令和7年午後I問3設問3でも出題）。
重要ポイント・コア概念
- 複合索引（列A, 列B）では、先頭列（列A）が検索条件に指定されないと原則として通常のB+木レンジスキャンが効かない（最左プレフィックス原則）
- カーディナリティ（値の種類数）が極端に低い列（フラグ列や処理状況区分など）かつ値が頻繁に更新される列を索引キーに含めると、処理が進むたびに索引キーの値が変わって索引更新とロック待ちが多発する
- カバリング索引（Index-Only Scan）：SELECT句・WHERE句で必要なすべての列が索引内に含まれていれば、データページへのアクセス自体を省略できる
午後I・午後II記述試験での攻略ポイント
午後Iで「なぜこの複合索引から『処理状況』列を除外した方がよいのか」と問われたら、『処理が進むたびに索引キーの値が変わるから（UPDATEのたびに索引の更新が発生しオーバヘッドやロック競合が生じるから）』と、索引キー列の更新頻度の観点から記述します。
午後記述で使える加点キーワード（クリックでコピー）
この用語が出題された過去問を解く（1分演習）
即時アウトプットで定着データベーススペシャリスト 過去問演習で実践力を鍛える
