モチベーション

MySQLの基本的な使い方はわかっているがインデックスの役割が曖昧だったので今一度整理する。

記事概要

MySQLに詳しい人は”インデックスを設定しろ！検索が早くなるから！”と言う。一方、自分はSQLでDBの簡単な操作はできるけど、インデックスに関しては”ふーん、インデックスを使うと早くなるのね。”程度の理解。しかし、DBの設計をするならインデックスの理解は必要不可欠である。そこで、DB、特にMySQLにおけるインデックスの役割となぜ検索が早くなるのかを計算量の観点から整理する。

MySQLのクエリに対する応答

MySQLのインデックスを理解するには、MySQLのクエリに対する応答をまず知らなくてはならない。

1つ例を挙げてみよう。今、Twitterのようなアプリを作成しており、ユーザ情報を格納するusers、全ユーザのtweet情報を格納するtweetsテーブルを以下のクエリで作成したとする。

CREATE TABLE twitter_modoki.users
  (id integer, 
   name varchar(250),
 );

CREATE TABLE twitter_modoki.tweets
  (tweet_id integer,
   uid integer, 
   content varchar(250),
);

この時、ユーザTaroのtweetを全て取得するには、Taroが持つusers.idをキーとしてtweetsテーブルから該当するレコードを全て抽出すれば良い。tweetsテーブルのuidがTaroのレコードを全て抽出するクエリは以下のようになる。

SELECT content FROM tweets WHERE uid = 'Taroのusers.id'

上記、クエリを実行した時のMySQLの応答は,

  1. tweetsテーブル内の全てのレコードを読み込む
  2. uidフィールドを調査し、文字列’Taroのusers.id’と一致するか比較する

となるが、これだとtweetsテーブルのレコードの数が増加するにつれて抜き出したいレコードの探索時間が増加する。この探索の計算量はtweetsテーブルにあるレコード数を*n*とした場合、*O(n)*となる(=線形探索の計算量)。

インデックスを設定した場合の計算量

それでは本題のインデックスの説明に入ろう。

インデックスはもともと、索引や見出しの意味を持つ。”データベース”という単語を国語辞典で引くときに、1ページ目から順に”データベース”という単語を調べる人はいないだろう。”て”の索引がついたページから”データベース”のページを探すのか普通だ。

DBでも同様に探索時間を効率的にするためのインデックスをつけることができる。

Twitterの場合、ユーザ情報をまとめたusersテーブルとユーザのtweetをまとめたtweetsテーブルが有り、ユーザ”Taro”のtweetをtweetテーブルから抽出するとき、普通にクエリを投げると全ユーザのtweetレコードに比例した探索時間が必要になることは既に説明した。

この時、以下のようにtweetテーブルのuidをインデックスとして設定すれば、Taroのusers.idとtweets.uid一致するレコードのみ探索することができる。

CREATE TABLE twitter_modoki.users
  (id integer, 
   name varchar(250),
 );

CREATE TABLE twitter_modoki.tweets
  (tweet_id integer,
   uid integer, 
   conent varchar(250),
   INDEX (uid)
);

MySQLのインデックスはB-Treeと呼ばれるデータ構造で実現されている。そのため、Taroのtweetを抽出するために必要な探索時間は*O(log n)*になる。

インデックスの有無による計算量の違い

tweetsテーブルのuidにインデックスを設定しない場合の計算量はO(n),インデックスを設定する場合の計算量は*O(logn)*であることは説明した。前者の計算量はレコードが増えるほど線形に増加するため効率が悪いことがわかる。

試しに具体的な計算量を算出してみよう。レコード数をn=1024,*n=1048576*とした時のそれぞれの計算量は以下のようになる。

  • tweetsテーブルに登録されているレコード数 n = 1,024の時
    • インデックスなしの計算量はO(1,024)
    • インデックスありの計算量O(10)
  • tweetsテーブルに登録されているレコード数 n = 104,8576の時
    • インデックスなしの計算量はO(104,8576)
    • インデックスありの計算量O(20)

このように、レコード数が増加すればするほどインデックスの有無が計算量に効いてくることがわかる。 なるほど、レコード数が多い場合、確かにインデックスを設定した方が検索が早い。

補足: MySQLのB-Tree

MySQLで利用されているB-Treeの記事も書いてみたので後日別記事でまとめる。

参考情報