応用情報２２年秋　午前　問６ - 実践！情報処理試験講座

【中分類】
アルゴリズムとプログラミング−２．アルゴリズム
　　　−（２）代表的なアルゴリズム−１　整列・併合・探索のアルゴリズム

【問題を解く前に】

　探索やソート（整列）のアルゴリズムは、データの状況によって、向き不向きがちがいます。ちょっと前までのデータベースでは、実務上でも、それを意識しないといけませんでした（最近は、テキトーに自動でＤＢがやってくれるのかしら？）

　データのキーの散らばりかたとか、使用頻度などを考えなければ、
　　　Ｂ＋木によるインデックスを張った検索が、平均的に早くなります。
　　　→２分探索木

　ただし、キーの値がキレイに散らばるのであれば、ハッシュが早いです。
　　ハッシュは、計算で格納位置を求めますので・・・
　　ところが、キーの値の散らばりに偏りがあり、計算で求めるハッシュ値
　　で、同じものが（＝シノニム）がいっぱい出来てしまうと・・・

　　・・・シノニム内はシーケンシャルでアクセスするため、遅くなります。

　データの使用頻度に偏りがあるなら
　　当然、使用頻度順に、順番に（線形に）並べたほうが早いです。

問題は、この知識を聞いています。

【解き方】

まず、Ｃは、ハッシュのことを差していますので、ハッシュ表探索です。
上記説明から、Ｂは、線形探索がよさそうですね。
Ａは、普通にインデックスを貼る、つまり、２分探索

順番に書くと、

二分探索、線形探索、ハッシュ表探索の順なので・・・

【答え】
（ア）

【解き終わって】

実務では、もう少し深い知識が必要かな・・・

●ハッシュを使う場合、そこで、キーの値を順番に採番している場合(AUTO_INCREMENTとか)は、キレイに値が散っているので、いいんだけど、
コードの組み合わせがキーの場合は、偏りが出てしまう。

たとえば、

　　　年号：社員番号：フラグ

フラグ：０のとき、現在利用、１のとき(論理）削除

　：はとって、一続きの数字をキーとした場合、もし、ハッシュの計算式が、仮に１０で割ったあまりごとに分けるとすれば（こんな簡単な式はないですよ、もちろん）、０と１ばかりに偏り、シノニムができる。

　なので、コードの組み合わせを「嫌う人もいる」
　→ほかに、便利なことがあるので、嫌わない人も多い。

●それと、各データベースにおいて、上記アルゴリズムが、どんなインデックスに対応するのかを知っているのもいいかも・・・

Oracleの場合はたぶん。。。

・使用頻度順にアクセスしたければ、使用頻度順に格納しなおして、シーケンシャルアクセスにするのかなあ？

・２分探索、は普通のインデックス（Ｂ＋）を貼ればなると思う

・ハッシュは、ハッシュ

・このほかに、ビットマップインデックスというのがある。

→詳しくは、自分で調べてね！

MySQLの場合は・・・

・InnoDBは、Ｂ＋
・ハッシュインデックスっていうのもある。
　メモリーインデックスのときに使うんだけど、
　これは、奥深〜いものがあるので、
　自分で調べてくれ・・・

・・・というように、自分の使っているＤＢのインデックスは、どういう検索手法を使っているのかを調べておくと、いいと思います。
（調べても、わかんないものもありますけどね・・・）

そして、実務と関連ある分野の知識

データベース
ネットワーク

などは、基礎理論とあわせて、そのレベルまで深めて勉強しておくと、
仕事をしながら、受験勉強の復習をしていることになるので、有利。