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

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

特定の列の値から目的の行へ素早く到達するための補助構造。多くのDBMSはB+木を使い、葉に実データへの参照を並べて順序も保つため、等値検索に加え範囲検索や整列にも効く。検索は速くなるが、更新時に索引の保守コストが増える。

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

1,000万行の表を主キー以外の列で検索すると全走査で数十秒かかるが、B+木索引があれば数ミリ秒で済む。一方、夜間の一括登録前に索引を落とし、登録後に作り直すと全体の処理時間が半分になる、といった判断も生じる。

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

索引は多いほど良いのではなく、更新の重い表では逆効果になる。また性別のように値の種類が少ない列は絞込み効果が乏しく使われないことが多い。列に関数や演算を適用した条件も索引が効かなくなる。

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

• データベースの再編成（REORG）と整合性チェック
• 結合の種類（内部結合・外部結合）

インデックスと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）