インデックス（索引）とは？

インデックス（索引）の意味

データベースの検索速度を向上させるために、特定の列の値と、対応する行の物理的な位置をあらかじめ対応付けて整理しておく仕組み。書籍の索引と同様、目的のデータへ全件走査（全表探索）せずに素早くたどり着けるようにする。多くのDBMSではB＋木構造で実装され、範囲検索や整列にも効く。

インデックス（索引）の具体例

会員番号にインデックスを設定しておくと、会員番号を条件に検索する際、表の全行を1件ずつ調べる（フルスキャン）よりはるかに高速に該当行を見つけられる。

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

インデックスは検索を高速化する一方、データの追加・更新・削除のたびにインデックス自体も更新する必要があるため、更新性能はやや低下するというトレードオフがある。また値の種類が少ない列（性別など）では絞り込み効果が薄く、効果が出にくい。

インデックス（索引）と関連する用語

• 関係データベースと正規化
• DBMS
• 3層スキーマ

インデックス（索引）が出た過去問

• 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）