インデックスとは？

インデックスの意味

表の特定の列の値から目的の行の位置を素早く求めるための補助的なデータ構造。検索を高速にする代わりに、更新時の維持コストと記憶領域を要する。

インデックスの具体例

頻繁に検索条件になる顧客コードにB+木索引を作る。

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

更新・挿入が多い列に索引を多数作ると全体の性能が落ちる。また列に関数や演算を適用した条件（WHERE SUBSTR(コード,1,3)='ABC'）では索引が使われないことが多い。

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

• B+木
• ビットマップインデックス
• クラスタ化インデックス

インデックスが出た過去問

• B+木インデックスとビットマップインデックスを比較した説明のうち、適切なものはどれか。

  正解：少数の異なる値をもつ列への検索は、ビットマップインデックスの方が有効である。

  要点：値の種類が少ない列にはビットマップインデックスが有効

  ビットマップインデックスは、列がとり得る値ごとに行の該当有無をビット列で表す方式である。値の種類（カーディナリティ）が少ないほどビット列の本数が少なく済んで効率がよく、性別や区分コードのような列に向いている。

  出典：平成30年度 春期 データベーススペシャリスト試験 am2 問15（IPA）

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

  正解：log X

  要点：B+木の探索は木の高さ分、つまり対数オーダー

  B+木は根から葉へ向かって多分岐でたどる平衡木で、木の高さはデータ件数の対数に比例する。検索は根から葉まで1経路をたどるだけなので、アクセス回数のオーダーは件数の対数になる。よってイが正しい。

  出典：令和5年度 秋期 データベーススペシャリスト試験 am2 問4（IPA）

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

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

  要点：B+木索引が効くのは値の順序を活かせる範囲検索

  B+木は葉ノードがキー値の順に並んでいるため、範囲の下限を索引で探し当てた後は葉をたどるだけで該当行を集められる。一方、否定条件やNULL以外といった条件は対象がほぼ全件に及ぶので、索引を経由するより表を直接走査したほうが速く、性能改善は期待できない。よってウが最も効果を見込める。

  出典：令和5年度 秋期 データベーススペシャリスト試験 am2 問13（IPA）

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

  正解：選択肢イ：AがB,C1,C2,Dの4ノードを指し、B↔C1↔C2↔Dの順で連結。

  要点：リーフ分割後も2つとも親直下、リーフ列はキー順連結

  B+木でリーフがあふれて分割されると、分割後の2つのリーフはどちらも親（中間ノード）から直接ポインタで参照される。親に空きがある前提なので、親へキーとポインタを1つ追加するだけで済み、それ以上は上位へ波及しない。またB+木のリーフはキー順の双方向リストでつながっているため、分割後もキーの順序どおりに前後のリーフと連結し直される。この2条件を同時に満たす構造が正解となる。

  出典：令和6年度 秋期 データベーススペシャリスト試験 am2 問3（IPA）

• 転置インデックスに関する記述として、適切なものはどれか。

  正解：テキストに含まれる単語に対して、その単語を含むテキストへのポインタをインデックスとして使用する。

  要点：転置インデックスは単語から文書を引くための索引

  転置インデックスは全文検索で使われる索引で、文書に出現する単語を見出し語とし、その語を含む文書（および出現位置）へのポインタを並べた構造をとる。文書から単語を引く通常の並びを逆にしているので「転置」と呼ぶ。これにより、語を指定して該当文書を一発で絞り込める。

  出典：令和6年度 秋期 データベーススペシャリスト試験 am2 問4（IPA）