インデックス（B+木）とは？

インデックス（B+木）の意味

表の特定列の値と行の格納位置を対応づけ、検索を高速化する索引。多くのデータベースは階層の深さが揃うB+木を使い、大量データでも少ない参照回数で目的行に到達できる。性能問題やバッチ遅延の原因分析でしばしば問われる。

インデックス（B+木）の具体例

100万件の取引明細から日付で抽出する処理が全件走査で30分かかっていたが、日付列に索引を作ると数秒になる。監査人は、夜間バッチの遅延が業務時間に食い込んだ事象について、性能設計のレビュー記録と索引の設計根拠が残っているかを確かめる。

インデックス（B+木）は試験でどう引っ掛けられる？

索引は多いほど良いわけではない。更新のたびに索引も書き換わるため、登録・更新が多い表に索引を増やすと逆に遅くなる。また列を加工した条件（関数を適用するなど）では索引が使われないことがあり、作っただけでは効かない。

インデックス（B+木）と関連する用語

• 正規化
• ストアドプロシージャ
• データウェアハウスとデータマート

インデックス（B+木）が出た過去問

• B+木インデックスが定義されている候補キーを利用して、1件のデータを検索するとき、データ総件数Xに対するB+木インデックスを格納するノードへのアクセス回数のオー…

  正解：logX

  要点：B+木の探索コストは件数の対数オーダ

  B+木は根から葉まで階層をたどる木構造で、1つのノードが多数の子を持つため木の高さはデータ件数の対数に比例します。候補キーで1件を検索する場合、根から葉までのノードをたどる回数がアクセス回数になるので、オーダは log X です。件数が増えても高さの伸びが緩やかなことが、大規模な表でも高速に検索できる理由です。

  出典：平成28年度 秋期 応用情報技術者試験 午前 問27（IPA）

• “部品”表のメーカコード列に対し，B+木インデックスを作成した。これによって，“部品”表の検索の性能改善が最も期待できる操作はどれか。ここで，部品及びメーカのデ…

  正解：メーカコードの値が4001以上，4003以下の部品を検索する。

  要点：B+木インデックスは範囲検索で最も効果を発揮する

  B+木インデックスは値が大小順に並び、葉ノードが順につながっているため、ある範囲に含まれる値をまとめて取り出す範囲検索で効果が大きい。値の種類が多く均一に分散していれば、絞り込まれる行数も少なくて済む。

  出典：平成29年度 春期 応用情報技術者試験 午前 問28（IPA）

• “部品”表のメーカコード列に対し，B+木インデックスを作成した。これによって，“部品”表の検索の性能改善が最も期待できる操作はどれか。ここで，部品及びメーカのデ…

  正解：メーカコードの値が4001以上，4003以下の部品を検索する。

  要点：B+木インデックスは絞り込みの効く範囲・等値検索で効果が大きい。

  B+木インデックスは葉ノードがキー順に連結されているため、ある範囲に収まる値を探す検索や、特定の値に等しい行を探す検索で効率がよい。値の種類が多く均一に分散している状況で、限られた範囲だけを取り出す検索は、絞り込みが強く働くのでインデックスの効果が大きい。一方、否定条件のように表の大部分が該当する検索では、表全体を読むほうが速く、インデックスは活かせない。

  出典：平成30年度 秋期 応用情報技術者試験 午前 問29（IPA）

• 関係データベースのテーブルにレコードを1件追加したところ、インデックスとして使う、図のB+木のリーフノードCがノードC1とC2に分割された。ノード分割後のB+木…

  正解：イ：中間ノードAからB、C1、C2、Dの4つ全てに矢印。リーフノードは B⇔C1⇔C2⇔D の順で相互連結。

  要点：B+木は全リーフを親が参照し順序どおり連結する

  B+木ではすべてのキーがリーフノードに置かれ、リーフ同士が順次アクセス用のポインタで連結される。リーフが分割されたときは、新しいリーフも親ノードから参照されるようポインタを追加し、リーフ間の連結もキー順を保つよう張り替える必要がある。したがって親AからB・C1・C2・Dの4つすべてへポインタがあり、リーフがB⇔C1⇔C2⇔Dの順で連結された構造が正しい。

  出典：平成30年度 春期 応用情報技術者試験 午前 問26（IPA）

• 関係データベース管理システム（RDBMS）のデータディクショナリに格納されるものはどれか。

  正解：スキーマの定義情報

  要点：データディクショナリはスキーマ定義などのメタデータを保持

  データディクショナリ（データ辞書）は、表・列・ビュー・インデックス・利用者権限といったスキーマの定義情報を格納するシステム表の集まりである。実データそのものではなく、データの構造や属性を記述したメタデータを管理する点が本質である。

  出典：平成30年度 春期 応用情報技術者試験 午前 問29（IPA）