IPA インデックス・物理設計 — 頻出論点と過去問

頻出論点

1. この分野は何か

関係データベースに蓄積された大量のデータから目的の行を素早く取り出すために、記憶装置上でデータをどのように配置し、どの経路で探索するかを設計する分野です。論理的な表の構造が同じであっても、インデックスの方式や表の結合手順の選び方によってディスクへのアクセス回数と応答時間が大きく変わります。

2. 実際の出題のされ方

検索を高速化する目的で設定する仕組みの名称を選ぶ問題があります。この基本用語はITパスポートで問われており、応用情報技術者の午前になると、3層スキーマのうち内部スキーマの設計作業に含まれるものを選ぶ問題や、コストベースのオプティマイザがSQLの実行計画を立てる際に参照する情報を問う問題が出ています。

データベーススペシャリストの午前IIでは、索引の内部動作や処理効率の定量的な評価まで踏み込んで問われます。1件を探すときに読むノードの数が件数に対してどう増えるかを問う問題や、2つの表を入れ子ループ法で結合するときの計算量のオーダーを求める問題が出題されています。さらに、行の追加でリーフが2つに分かれたあとのノード間の矢印のつなぎ方を図から選ぶ問題や、転置インデックスの説明を選ぶ問題も出ています。

3. 学習のポイント

インデックスのデータ構造ごとの特徴と、検索条件との対応関係が最優先で押さえるべき論点です。

• B+木インデックス: ルートから中間ノードを経てリーフノードへ枝分かれする平衡木構造を持ち、すべてのリーフノードが横のポインタで順につながっています。値の大小の順に並んだ構造なので、ある値と一致する行を探すだけでなく、値の範囲で絞り込む検索にも使えます。木の段数はデータ件数の対数でしか増えないので、件数が大きく増えても、1件を探すときに読むノードの数はわずかしか増えません。また、行を足してリーフが入り切らなくなると、リーフを2つに分け、左右のリーフとの横のつながりに入れ直したうえで、親のノードに新しいリーフを指す矢印を1本足します。
• ハッシュインデックス: 検索キーの値をハッシュ関数に入力してデータの格納位置を直接算出する方式です。ハッシュ値は元の値の大小の順を保たないので、一致する値を探す検索には速い一方、範囲で絞り込む検索には使えません。
• 転置インデックス: 単語ごとに、その単語が出てくる文書の一覧を引けるようにした索引で、全文検索の高速化に用いられます。

実データの物理的な並び順とインデックスの関係も整理しておく必要があります。

• クラスタ化インデックス: 表の行そのものを、索引にした列の値の順に並べて格納します。主キーに対して設定されることが一般的で、順序どおりに連続して読み出す範囲検索の効率を高められます。
• 非クラスタ化インデックス: 行の並びを変えず、キーの値と行の置き場所の組を別に持ちます。

問合せの処理手順を決めるオプティマイザと結合アルゴリズムも重要なテーマです。コストベースのオプティマイザは、テーブルの行数やブロック数、値の分布といった統計情報を基にアクセス経路ごとの処理コストを見積もり、実行計画を作成します。入れ子ループ法（ネステッドループジョイン）は、外側の表の1行ごとに内側の表を端から照合するので、外側が $m$ 行、内側が $k$ 行なら比較は $m \times k$ 回になります。

4. 間違えやすいところ

ハッシュインデックスが向く検索を選ぶ問題では、「売上金額が1万円以上の売上を検索する。」のような範囲の条件が誤答肢にありました。

また、B+木インデックスを設定していても、検索条件の書き方によっては性能改善が見込めない場合があります。値が均一に分散した列に対する「メーカーコードの値が1001以外の部品を検索する。」のような否定条件が誤答肢にありました。このように表のほとんどの行が該当する検索では、インデックスをたどるよりも表全体を先頭から走査する方が効率的になるため、インデックスによる高速化は期待できません。

クラスタ化インデックスは1つの表に複数作れるとする誤答肢がありました。行そのものの並び順は1通りしか取れないので、1つの表に作れるのは1つです。