「インデックス化で効率的な検索を」（経理マン向けの超簡単ITコラム）

鈴与シンワートは、経理マン向けの超簡単ITコラム「インデックス化で効率的な検索を」を公開しました。

＃＃＃

こんにちは、新宮りつ子です。

みなさんは探し物をするとき、どのように探していますか。失くした物でしたら最後に記憶があった場所まで戻り、順路を追って探すといったコツがありますよね。
あるいは勘で探していますか…？

コンピュータを使っていて便利だな、と思うことの一つは、検索が速いことではないでしょうか。
例えば、1,000枚の写真の中から1秒もかからずに、目当ての写真を探し出してくれます。

ところが、写真が10万枚も溜まってしまったらどうでしょう。
個人ではそこまで溜まらないかもしれませんが、会社レベルであれば万単位のファイル所持はあり得ることです。
1,000枚で1秒かかっていた検索時間は、10万枚になると100秒もかかってしまうのでしょうか。

結論から言うと、そんなことはありません。
コンピュータ検索は古くから研究されてきた分野で、効率的な検索方法が多く存在します。
コンピュータ以外で使われている手法も取り入れられています。

一つは、「二分探索」という検索方法があります。
順序良く並べられたデータの中から効率的に検索をする方法で、私たちが辞書を開くときの方法と似ています。

分厚い辞書から、internet という単語を調べてみましょう。
辞書の単語はアルファベット順に規則正しく並んでます。まず辞書のど真ん中を開きます。
開いたページには、m から始まる単語が並んでいます。
internet の頭文字 i は m よりも前なので、開いたページより後ろはもう必要ありません。
残ったページのど真ん中を開きます。今度は h で始まる単語が並んでいます。
i は h よりも後ろなので、開いたページより前はもう必要ありません。
手元には辞書の4分の1のページが残っています。この中から i のページが見つかるまで、同じことを繰り返します。

この手法の画期的なところは、手元のページが、4分の1、8分の1、16分の1、32分の1…と、毎回半分に減っていくことです。
そのため、辞書の厚さが二倍になっても、検索時間は二倍になりません。
ページを開く回数が1回増えるだけなのです。

もう一つ、「インデックス検索」といわれるものを紹介します。

（この続きは以下をご覧ください）
(リンク »)