■検索時にINDEX(インデックス)がどう役立つのか？

質問

いつもお世話になっております。
MySQLのカテゴリにて質問をさせて頂きますが、このことに意味はありません。
SQLにおける、INDEXの考え方を知ることができれば良いなと思っております。
SQLについては初心者ですので、分かりやすく教えて頂けると助かります。

では、本題へ。
-------------
あるデータテーブルの検索速度を上げる方法として、
INDEXを設定することもその１つに挙げられるかと思いますが、
あるテーブルにおける、ある列（フィールド）に対しINDEXを設定した場合、
検索時、それはどう利用されるのでしょうか、というのが質問です。

例えば、

会員データベース
・会員番号：id
・年齢：age
※その他、複数のフィールドを持つ、とする。

上記の会員データベースにおいて、
CREATE INDEX idx ON tbl_member(id);
という風に、tbl_memberテーブルに対し、
会員番号（id）をINDEXに設定したとします、
idは唯一無二の（ユニークな）データです。

この会員テーブルにおいて、
年齢（age)フィールドをもとに、40歳以上の会員を抽出（検索）したい場合、
INDEX（idが設定されている）はこの検索において、
どういう仕組みで活かされることになるのでしょうか？

ageと無関係のidが、どう役に立つのか分からずにいる、ということです。
ネット上で色々調べたのですが、
あるフィールドをINDEXに設定した場合に、
それが検索時にどう活かされるのかについて説明されているページを
私は見つけることができませんでしたので、質問させて頂きました。

どうぞ、宜しくお願い致します。

回答No.4

chukenkenkou · ベストアンサー

>MySQLのカテゴリにて質問をさせて頂きますが、このことに意味はありません。

特定のRDBMSに限定した話しでないなら、「その他(データベース)」カテゴリに質問してください。

>年齢（age)フィールドをもとに、40歳以上の会員を抽出（検索）したい場合、
>INDEX（idが設定されている）はこの検索において、
>どういう仕組みで活かされることになるのでしょうか？
>ageと無関係のidが、どう役に立つのか分からずにいる、ということです。

インデクスというか、書籍の索引と考えてもいいですが、索引とはどんな
ものか考えてみてください。
索引は、特定のキーワードをアルファベット順や五十音順に並べ、それが
どのページにあるかを示すものですよね？

id列の値が索引に載っていたとしても、ageの値は索引に載せるようにして
いないのだから、インデクスによる絞込みはできません。

次に、DBMSでの索引、つまりインデクスの実装方法について説明します。

多くのRDBMSで実装されている代表的なインデクスの構造として、B-TREE構造が
あります。

B-TREE構造と、その利用方法については、下記を参照してください。
http://itpro.nikkeibp.co.jp/article/COLUMN/20060113/227239/?ST=develop

なお、こういった内部構造、内部処理については、RDBMSによる違いがあるので、
特定のRDBMSを例にして説明されています。

インデクスが活用されるのは、例えば次のような処理です。

(1)「=」、範囲、LIKEの前方一致などの検索条件の場合のデータの絞込み
(2)ORDER BY、GROUP BY、DISTINCTなど、ソートが必要な処理
(3)COUNT、MAX、MINなどの集計（集合）関数
(4)重複チェック

なお、「表のデータ件数が少ない」場合や「重複データが多い」場合、RDBMSのオプティマイザが「インデクスを利用するより、表のデータを見た方が速い」と判断し、上記のような操作であってもインデクスを利用しない場合があります。
これは最終的には、利用者側の環境で、EXPLAINで確認する以外には「答え」はありません。

一方、insert、delete、updateでのインデクスのキー更新といった操作では、インデクスの更新がオーバヘッドとなるため、無闇にインデクスを多く定義すればいいというものではありません。

PRIMARY KEY、UNIQUEなど一意性を保証する表定義を行った場合も、重複
チェックを効率的に行うため、主要なRDBMSの実装では、内部的にインデクスを作成します。
また、RDBMSによっては、クラスタリング、クラスタ化などの名前で、インデクス上だけでなく、表のデータもキー値が近いものはなるべく近傍に格納するといった独自機能を実装している場合があります。

>たとえば、idフィールドであれば、大抵の場合、小さい値から大きい値へと
>プラス１ずつ増えていくでしょうから、基本的にソートする意味はなさそう
>なので、このフィールドをindexに設定する意味というのはなさそうなのかな？
>と感じました。

これは「一意なキー値を作るための手段の一つ」でしかなく、完全な思い込みです。
仮に昇順 or 降順で、+1 or -1 することを考えた場合、最大値または最小値を得るにはどういう処理が必要になるか考えてみましょう。
インデクスがなければ、「最新のデータは物理的に末尾に格納し続ける」といった制御が必要であったり、それが保証できないなら全件検索するしかありません。

>つまり、上の例で言えば、a～lまでを検索することなく、
>一気に「mから始まるデータ」から検索をスタートできるので

表のデータは、物理的な格納位置は保証されません。「最後に格納した行が必ず末尾に格納される」といった保証もされていないし、「キー値順に格納する」といったことも一部のRDBMSでの独自機能を使う以外には行われません。
したがって、インデクスがなければ、検索開始位置も停止位置も決められず、全件検索することになります。

お礼

詳しい回答をどうもありがとうございます。

参照URLの記事を読む前に一読した際には、
ほとんどその内容を理解することはできませんでしたが、
今、こうして参照URLを経由し、予備知識を得てから読ませて頂くと、
本回答が要所を押さえた回答であることがよく分かります。

＞インデクスが活用されるのは、例えば次のような処理です。
＞これは最終的には、利用者側の環境で、EXPLAINで確認する以外には「答え」はありません。
＞これは「一意なキー値を作るための手段の一つ」でしかなく、完全な思い込みです。
＞表のデータは、物理的な格納位置は保証されません。
＞したがって、インデクスがなければ、検索開始位置も停止位置も決められず、全件検索することになります。

以上がとても参考になりました。
この度は、貴重な回答をどうもありがとうございました。
また機会がありましたら、色々と教えて下さい。

回答No.6

o123459876

テーブルにデータをinsertした時に必ずしもinsertした順番に
登録されている保障はありません。

なのでデータベースはselectしたときに全部のデータを
チェックしないと条件のデータを取得できません。

indexを作るとinsertで登録した場所とは異なる場所に
データをソートした形で登録されます。
今回の場合[id]+[insertしたデータのアドレス（場所）]です。

そうすると全てのデータを検索しなくても条件にマッチするデータを
select出来るのでパフォーマンスがアップする可能性があります。

今回（age）を検索する場合、ageを使ったindexが無いので
indexは使われなくて全件検索になると思います。

-----------------------
indexはデータと異なる場所に同じ情報を持ちます。
index項目を更新したり、insertした場合はindexの更新や追加・削除が
発生するので検索は早くなるかもしれないですが、更新・登録・削除は
遅くなります（気にならない程度です）

お礼

コンパクトにまとめられた分かりやすい回答を
どうもありがとうございます。

＞必ずしもinsertした順番に登録されている保障はありません。

DBと物理ディスクとの兼ね合い等について、現在、難解なページを読み、
勉強しているところですが、どうやらそのようですね。

＞indexを作るとinsertで登録した場所とは異なる場所に
データをソートした形で登録されます。
今回の場合[id]+[insertしたデータのアドレス（場所）]です。

このことについては、本質問を通して色々と勉強をさせて頂いた今でこそ、分かるようになっていますが、
質問当初は全く分かっていませんでしたので、回答１でこちらの回答を得られていたら、
非常に助かったであろうと思います。

簡単ではありますが、以上をお礼のコメントとさせて頂きます。
どうもありがとうございました。

回答No.5

chukenkenkou

#4回答者です。

#1への補足で、

>提示頂いた参考ＵＲＬの内容を（１）～（３）まで見てきました。

とのことですが、#4で提示したリンク先は、その連載記事の（８）であり、インデクスの構造などに触れられています。

>上記の会員データベースにおいて、
>CREATE INDEX idx ON tbl_member(id);
>という風に、tbl_memberテーブルに対し、
>会員番号（id）をINDEXに設定したとします、
>idは唯一無二の（ユニークな）データです。

ユニークであることを、誰が保証しているのでしょうか？
RDBMS側では、PRIMARY KEYにしたり、CREATE UNIQUE INDEXでインデクス定義しないと重複チェックしません。
また、より有効なインデクス利用を行いたいなら、重複度合いなどをRDBMSに教えるため、MySQLであればANALYZE TABLE文でコスト情報を取得する必要があります。

>今回、一般化した形での回答を求めるような質問形式を取っているためか、具体例を挙げて回答下さる方がいらっしゃらない

具体的なアドバイスが欲しいなら、具体的に質問するようにしてください。

過去に、インデクス定義例と検索条件例について回答したことがあるので、下記を参照してみてください。

http://oshiete1.goo.ne.jp/qa3631362.html

お礼

まずは簡単にお礼をさせて下さい。

頂いた回答を可能な限り理解した上で、
お返事をさせて頂けたらと思い、
現在、
#4で提示したリンク先（連載記事の（８））
はもとより、このページに関連するページを
片っ端から読ませて頂いている所でして、
返事がまだ出来てない状態となっています。

私の使用経験のあるDBは、SQLite2のみ（SQLite3は勉強中）で、
また、そのSQLiteですら、まだよく分かっていない状況ですので、
私の質問の仕方には問題があったのだろうと思います。
何度か頂いたご指摘により、よく分かりました。

具体的には、
回答者の方から、具体例のある回答を引き出すにしても、
もう少し、こちら側で条件を絞り込む必要がある
ということに気が付きました。

お返事に時間が掛かるかもしれませんが、
誠意をもって対応させて頂きますので、どうぞ宜しくお願い致します。

普段から、「お礼蘭」も使って返事をすることが多いため、
お礼のためだけにコメント欄を使ってしまうのはもったいなく私は思っていて、
そのために、今回、お礼が遅れてしまいましたが、＃４、＃５と、２度連続で回答を頂けたおかげで、
このようにお礼だけの返事をさせて頂くことが出来ました。

それでは、今しばらくお待ち下さい。
DBに関して、大変お詳しい方のようなので、期待しております。

ちなみに、DBはPHP5との連携で使うつもりでいます。
（PHP5.2.5とSQLite3.3.7　の組み合わせです。)

補足

補足回答をありがとうございます。

＞ユニークであることを、誰が保証しているのでしょうか？

idフィールドを、PRIMARY KEYにするという設定のもと、
「idは唯一無二の（ユニークな）データです。」と書かせて頂きました。
分かりにくかったとしたら、すみません。

＞過去に、インデクス定義例と検索条件例について回答したことがあるので、下記を参照してみてください。

参考にさせて頂きます。
どうもありがとうございまいｓた。

回答No.3

dell_OK

これは索引検索アルゴリズムに関するご質問ですね。
索引がどのように構築され、どのように利用されるのかは、私は詳しくありませんので説明できません。
その項目が数値型なのか、文字型なのか、また、検索の条件（=,<,>,like）などによっても、そのアルゴリズムは異なってくる、としか言えない程度です。

たとえば、こちらによると、
http://dev.mysql.com/doc/refman/5.1/ja/mysql-indexes.html
「もし... LIKE '%文字列%'そして文字列は3文字より長い場合、ＭｙＳＱＬはTurbo Boyer-Moore アルゴリズムを使用して、文字列のパターンを初期化してから、このパターンを使用して検索をすばやく実行します。」とあります。
対象が文字型で like で ３文字より長い場合は Turbo Boyer-Moore 。
と言う事から、Turbo Boyer-Moore について調べてみると、こちらがみつかりました。
http://www.hgc.ims.u-tokyo.ac.jp/~tshibuya/classes/2007Shinryoiki_01matching1.pdf
※ PDF ファイルですので、読み込める環境が必要です。
この中に Turbo Boyer-Moore の動作について書かれています。

これらは質問者様の知りたい事のほんの一部でしかありません。
数値型ですと、もっと簡単な構造と利用がされますでしょうし（私の想像）、文字型でも、３文字以下だとどうなるのか、までは私は調べていません。

キーワードに「アルゴリズム」あるいは「アーキテクチャ」などの言葉を追加して、もう一度検索されてみたら、何かヒントになるような情報がみつかるかも知れません。

補足

>索引がどのように構築され、どのように利用されるのかは、私は詳しくありませんので説明できません。

私が知りたいことは、まさに仰る通り、
「索引がどのように構築され、どのように利用されるのか」
ということですので、こちらを説明頂けると大変助かりました。

＞キーワードに「アルゴリズム」あるいは「アーキテクチャ」などの言葉を追加して、もう一度検索

こちらをトライしてみましたが、
さらに難解なページが増え、手も足も出なくなりました。
私が知ろうとしていることは、それだけ複雑なことなのでしょうかね。
（私の質問の仕方のマズさに問題があるのかもしれませんが…。）

さて、話を戻し、

今回、一般化した形での回答を求めるような質問形式を取っているためか、
具体例を挙げて回答下さる方がいらっしゃらないのですが、
私としては、

ある１例でも良いから、インデックスが通常どの様に利用され、
また、その場合において、そのインデックスにはどのような利点があるのか、

を示して頂けると、理解が格段に進むのではと思っています。

もっとも、その１例で全てのケースを理解できないことは承知しています。

木を見て、森を見ない。
という言葉がありますが、
今の私は、
漠然と森を見るより、１本の木でいいから、
ある程度しっかり見せて欲しい。

そんな気持ちなのかもしれません。

例えば、以下のようなデータをまとめるDBを用意するとして、

id（会員番号）
name（会員名）
age（会員の年齢）
date（入会日）

このDBからは、様々な観点で、データを抽出・検索することができるかと思います。

このDBを例にとり、
「このDBにおいて、
○○（ある程度複雑な条件）なデータを抽出・検索する場合には、
●●フィールドをインデックスとして設定すると、
▲▲という意味で検索が速まることが予想される。」

ということを何パターンかの例を通じて示して頂けると、
インデックスというものの概念が、より鮮明に見えてくるように思うのです。

大変わがままな、そして、欲張りな質問をしているかもしれません。
もし、またよろしければ教えて下さい。

頂いた回答を受け、

「私が私を分からせるのに、私は皆さんへ向けて、どのように質問したら良いか」

ということをより強く意識させられたように思います。
今回、こちらで書かせて頂いた補足が、次への一歩となればと思っています。

この度は、回答して頂き、どうもありがとうございました。

回答No.2

yambejp

この場合idにインデックスをつけても検索条件につかわれていないので
年齢で検索するときには全く利用されません。

まずはEXPLAINの使い方から学習なさるとよいでしょう。

お礼

回答をどうもありがとうございます。

＞EXPLAIN

こちらを調べて来ましたが、私にはなかなか難しい概念のようでした。
私が本件で知りたいと思っている「indexの意義、仕組み」について、
「回答１の補足」の所で長々と書かせて頂きましたが、
そこで説明させて頂いている内容を理解する上で、EXPLAINの理解は必要そうでしょうか？
もっとも、知って損はないのでしょうが、
そのEXPLAINを理解するには、さらに多くの予備知識を必要としそうなので、
今のところは、さらっとindexについてだけ理解できたらと思っています。

理解の効率を考えれば、
おそらく、EXPLAINの理解もセットでした方が何かと良いのだと思いますが、
まだまだDBについて詳しくない私には、少々ハードルが高いなと感じました。

またよろしければ、「回答１の補足」をお読み頂き、
アドバイスを頂けると嬉しいです。
宜しくお願い致します。

回答No.1

akina_line

こんにちは。

　下記サイトをご参照ください。
　　http://itpro.nikkeibp.co.jp/article/COLUMN/20060111/227100/?ST=develop
　　目次に飛んで（１）から読んだほうが分かりやすいかもしれません。
　　超簡単に言うとインデックスは本の巻末にある索引と同じようなものです。本文を読みながら検索するよりも断然早いのはお分かりになるでしょう。

では。

補足

レスポンスが遅くなり、申し訳ありません。
回答をどうもありがとうございます。

提示頂いた参考ＵＲＬの内容を（１）～（３）まで見てきました。
こちらを読み、ＳＱＬ文によってデータが検索されるそのメカニズムについて、なんとなく理解することができました。
しかし、indexがそもそもどういう意味を持つものであるかについての記述はなかったように思います。
つまり、
「indexを使った説明」はありましたが、
「indexそのものの詳細な説明」はなかったのでは、
と思いました。

indexについて別のページで調べたところ、
特定のフィールドをindexとして設定することで、
そのフィールドをソートし、検索時に便利に使えるようにできるようですね（？）。
たとえば、idフィールドであれば、
大抵の場合、小さい値から大きい値へとプラス１ずつ増えていくでしょうから、
基本的にソートする意味はなさそうなので、
このフィールドをindexに設定する意味というのはなさそうなのかな？
と感じました。

一方、文字列で構成されるフィールドでは、
例えば、

id　　fluit

１　　orange
２　　apple
３　　melon
４　　pear
５　　banana

のようなＤＢにおけるfluitフィールドをindexに設定した場合、
fluitフィールドでは、indexとして、
下記のようなソートが行われるものと思われます。

apple
banana
melon
orange
pear
（アルファベット順）

こうしておくことで、
例えば、melonを検索する場合、
アルファベット順に並んでいるfluitフィールド(index)の中から、
「mから始まるデータ」にまず視点を持っていき、
そこから、注意深くmelonを見つけ出そうとするような、
そんな効率的なデータ検索をするようになるのかな、
と私は理解したのですが、
indexを設定する意義とは、こういう事にあるのでしょうか？

つまり、上の例で言えば、a～lまでを検索することなく、
一気に「mから始まるデータ」から検索をスタートできるので
検索速度は上がるだろう、という意味です。

私はindexに関する、本当に基本的なことをお聞きしていると思います。

なお、indexを設定する（CREATE INDEX）とは、
そのindexとして設定されたフィールドを取り出し、
常に新鮮な状態に保ち、それをソートした状態で、
テーブルとは別にインデックステーブルのようなものを用意し、
そこで管理しておく、というような仕組みなのでしょうか？
つまり、検索時に使われる場合には、

通常のテーブル内にある、そのindexとして設定されているフィールドから検索するのではなく、

インデックステーブルとしてソートされてあり、かつ新鮮に保たれているフィールドから検索をするのかな？

なんて、考えたりしましたが、このあたりはどういった仕組みになっているのでしょうね？

もし、またよろしければコメントを頂けると嬉しいです。
宜しくお願い致します。