平成21年度春期 データベーススペシャリスト 午前Ⅱ 問10

索引探索を整理する一つの視点

索引を使う探索では、対象となるデータのまとまりと、検索条件がどのように照合されるかに注目し、探索の流れを段階ごとに整理して考えます。各段階の役割を混同せず、全体の関係を確認しましょう。

この問題で問われていること

この問題では、索引が参照する対象と検索条件の対応関係に焦点を絞り、探索の開始点から候補を確認するまでの役割分担を言葉で整理してください。個別の方式名や数値ではなく、対象の移り変わりに注目します。

視点

索引は、データ全体を直接確認する代わりに、検索条件に関係する候補へ目を向けるための手がかりとして捉えます。対象の範囲、条件との対応、候補確認の順序を分けて考えると、方式の違いを整理しやすくなります。

確認ポイント

• 検索条件と索引の対象が対応しているか
• 探索の各段階で確認する対象を区別できているか
• 候補を見つけた後の確認を別の段階として捉えているか

正解

エ

解説

各選択肢の総行数はいずれも1、200行です。値vの行数をn_vとすると、各行が等頻度で検索される場合、インデックス利用時の1行当たり平均検索量はΣn_v^2／1、200で比較できる。エはすべて200行なので、平均検索量が最小となり、インデックスによる改善が最も大きい。

理由

各選択肢の総行数は1、200行で共通している。インデックスで値を検索したとき、その値に属する行数が検索対象となる。各行が等頻度で検索されるため、1行当たり平均検索量は、値vの行数をn_vとしてΣn_v^2／1、200で求めて比較できる。エでは、200行の値が6種類あるため、200^2×6／1、200＝200行となる。

比較

アは600^2×2／1、200＝600行、イは1、000^2＋200^2を1、200で割って約866.7行、ウは20^2＋40^2＋80^2＋160^2＋300^2＋600^2を1、200で割って約403.3行となる。エの200行が最小なので、平均検索速度の向上が最も大きい。

選択肢ア

これは不正解だよ。総行数は1,200行だが、pとqに各600行ずつ集中している。等頻度検索では、インデックス利用時の平均検索量は(600^2＋600^2)／1,200＝600行となるため、エの200行より改善効果が小さい。

選択肢イ

これは不正解だよ。総行数は1,200行でも、pが1,000行、qが200行と大きく偏っている。平均検索量は(1,000^2＋200^2)／1,200で約866.7行となり、同じ値の行数が均等なエより検索対象が多い。

選択肢ウ

これは不正解だよ。行数は20、40、80、160、300、600と段階的に偏っている。平均検索量は(20^2＋40^2＋80^2＋160^2＋300^2＋600^2)／1,200で約403.3行となり、エの200行を上回るため、最も大きな改善にはならない。

選択肢エ（正解）

これは正解だよ。各データ値に対応する行数がすべて200行で、総行数は1,200行である。平均検索量は(200^2×6)／1,200＝200行となり、他の選択肢より小さい。検索対象の偏りがないため、インデックスによる平均検索速度の向上が最も大きい。

学習のポイント

インデックスの効果は、総行数だけでなく検索値ごとの行数の偏りで決まる。