はじめに
どうも、Pirikaraです。
終電を逃したので漫画喫茶で記事書いてます。よろしくお願いします。
前回の記事で簡単にDBのパフォーマンス検証をしてみたのですが、「そういえばindexを使うと検索速度がはやくなるって聞いたことがあるぞ」と思ったので今回はindexについて書いてみます。
indexについては〇〇エキスパートのカリキュラムでも勉強はしましたが、正直「検索がはやくなるよ」程度の知識しかなかったので頑張って掘り下げようと思います。
とりあえずキーワードの意味合いをざっと追いかけたあと、indexを使用した場合の検索パフォーマンスを検証してみたいと思います〜。
学習中なので間違ってたら指摘していただけると助かります。
##Indexってなに？
「データベーステーブル内の検索処理を高速化するために設定する、本の索引のようなデータ構造のこと」だそう。へえ。
要するに普通のデータベーステーブルとは別に「索引」が作られて、
indexが設定されたカラムについては索引を参照することで処理する量を減らす.....こんな感じなんか？？？
本では見たいページを探す時に、アルファベットやひらがな、カタカナ順の索引を参照し、キーワードをもとに該当ページを特定することで全てのページを順に調べていく手間から解放されていますね。
データベースにおいても同様に、「indexに指定されたカラムの値」が索引、「そのカラムに紐づくレコード」がキーワード、「対象レコードの場所を表すポインタ」がページ番号となって全てのレコードを１から順に調べていくことから解放されます。
例えば下図で『佐野達也』のレコードを検索しようとした場合、
データベースではid 1から順番に探索して、5番目に該当レコードを見つける形になります。
一方でindexを利用した場合、『佐野達也』が検索開始位置となり迅速な検索が可能となります。
この表だけ見ていると、
『indexでも佐野達也は上から5番目やん。なら5番目にレコード見つけてるんじゃないん？』
『むしろテーブル跨いでる分効率悪くない？』
『index貼る意味ある？』
と罵声を浴びせられそうです。
秘密はindexのデータ構造にあります。
インデックスには検索に特化した様々なデータ構造(と検索アルゴリズム)があります。
データ構造の特徴はこちらのサイトが参考になったので読んでみてください。
データベース性能を向上させる「インデックス」を理解する
ここでは、MySQLで一般的に使用されているB-tree(正確にはB+tree)と言うデータ構造について掘り下げながらindexについて理解していくことにしましょう。
B-treeインデックス（アルゴリズム）とは？
まずはネットでワード検索してみました。
B-treeとは、コンピュータサイエンスにおけるデータ構造のうち、特にツリー構造の一つ。
B-treeアルゴリズムとは、 ファイルシステムやデータベースの実装の基礎となる平衡探索木のアルゴリズムのこと。
B-Tree by Java -- B木のすごく簡単な実例
つまりB-treeインデックスとは、『B-treeというデータ構造において平衡探索木アルゴリズムによって検索するための索引』！
平衡......探索木......?
すごく......簡単......??
わからないことだらけなので、
- ツリー構造
- 二分探索木アルゴリズム
- 平衡探索木アルゴリズム
- B-tree(B+tree)
の順に掘り下げていきましょう。しょう。
###1. ツリー構造
ツリー構造とは、文字通り木(tree)のような（上下逆やけど）形状をしたデータ構造です。
木の根っこにあたるルート(root)からデータが枝分かれしていく構造になっており、階層構造を表す場合に有効だそう。
住所なんかが良い例ですね。
ツリー構造のうち、子ノードが最大2つしかないものを二分木(バイナリー・ツリー)と言い、二分木探索アルゴリズムによる検索でよく用いられます。
参考：一週間で身につくアルゴリズムとデータ構造
###2. 二分探索木アルゴリム
二分探索木とは、先ほどの二分木に
『 左の子の値 ＜ 親の値 ＜ 右の子の値 』
というルールを適用することでデータの探索効率を向上させたデータ構造のことです。
例えば上の図で『 17 』を見つける場合、
『 24 』と比較して『 17 』の方が小さいので、左に進む
↓
『 12 』と比較して『 17 』の方が大きいので、右に進む
↓
『 17 』が見つかりました
という順番で検索が行われます。
この場合、右側のブランチは検索しなくて済みます。
一度比較を行う度に検索対象が半分になるので効率的ですね。
また、アルゴリズムの性能を評価する指標として『計算量』というものがあります。
計算量は少なければ少ないほど『効率の良いアルゴリズム』であることの証です。
データ量をnとして、nが増えただけ計算量も比例して増えることをO(n)と表します。（O記法）
下図のように一本木の場合はデータが増える度に計算量も増えることになります。
二分探索木アルゴリズムでは比較の度に検索対象が半分になるので、O(log n)と表します。
両者をグラフで表すと......
データの量が多いほど計算量に差がでることがわかりますね。
ただし、二分探索木の場合、データの削除やデータの追加、データ追加の順序によって偏りが生まれ、計算量がO(n)となってしまうケースがあります。
例えば1,2,3,4....の順にデータを追加すると、
これでは計算量がO(n)となってしまい、非常に効率が悪いです。
二分探索木を改善し、計算量が常にO(log n)となるようにしたのが平衡探索木です。
###3. 平衡探索木アルゴリズム
平衡探索木では、二分木構造に偏りがでた場合に回転操作を加えることで偏りを調整します。
左側に偏りがある状態から......
回転操作を加えて偏りがなくなりました。
平衡探索木においては、いかなる場合にも計算量がO(log n)になります。
###4. B-tree
B-treeは平衡探索木を
『 1つのノードがm個(m >= 2)の子ノードを保持することができる 』
ように一般化したものです。
一般的にm個の子ノードをもつことができるB-treeを『m階のB-tree』と呼びます。
※ m = 3のB-tree
例えば上の図で『14』を見つける場合、
『14』は『9』以上『18』未満の数なので、真ん中に進む
↓
『14』は『12』以上『15』未満なので、真ん中に進む
↓
『14』が見つかりました
という順番で検索が行われます。
詳しい計算は省きますが、B-treeアルゴリズムの計算量はO(log n/log m)となり、階数が大きくなるほどB-treeアルゴリズムの恩恵を受けられます。
これを最初のUsersテーブルのような例に置き換えて考えると......
また、MySQLにおいてはこれをさらに発展させたB+treeが採用されています。
B+treeでは、リーフノード(最終階層 一番下のノード)が相互に連結されることにより、範囲検索が容易に行えるような構造になっています。
こんな感じです。
例えば『WHERE user_id = 2 AND created_at = '2019-09-15'』の検索については以下の通りです。
また、範囲検索を行う際は以下のようになります。
『WHERE user_id = 2 AND created_at BETWEEN '2019-09-01' AND '2019-09-30'』
リーフノード同士が相互にアクセス可能なため、上記のように効率的な検索が可能です。
##indexのパフォーマンス検証
では、indexを使用することで実際にどれだけ検索効率がよくなるのかを検証していきたいと思います。
まずはテストデータを作成します。
先程のグラフを見ると、データ量が少ない場合には線形探索（O(n)）の方が早いので、
とりあえず100万件のデータを作成します。
今回はUserモデルとItemモデルを作成し、それぞれ100万件のデータを作成します。
カラムはnameのみとし、Itemモデルのnameにindexを貼ります。
#usersテーブル
class CreateUsers < ActiveRecord::Migration[5.2]
def change
create_table :users do |t|
t.string :name
t.timestamps
end
end
end
#itemsテーブル
class CreateItems < ActiveRecord::Migration[5.2]
def change
create_table :items do |t|
t.string :name
t.timestamps
end
end
end
#itemsテーブル（index）
class AddIndexItemsName < ActiveRecord::Migration[5.2]
def change
add_index :items, :name
end
end
1000000.times do |index|
User.create!(name: "ユーザー#{index}")
end
1000000.times do |index|
Item.create!(name: "アイテム#{index}")
end
rails db:seedでデータベースにデータを放り込みます。
itemsテーブル
usersテーブル
では、それぞれname基準で検索してみましょう。
クエリ文はSELECT * FROM テーブル名 WHERE name = '〇〇1000'で統一します。
まずはユーザーから。
結果は374msでした。
続いてアイテムは......
え？
0.4ms
驚きの速さ。
なんと935分の1になりました。
大規模なデータを扱う際にはindexの恩恵が大きいことが伺えますね。
何回か試行してみましたが、おおよそ1/50〜1/1100くらいの幅で効率アップが見込めました。
##さいごに
indexについて、『検索に特化したデータ構造の索引を作ることで、検索効率をよくする』ということが理解できました。
読んでくれてありがとうございました。
また気が向いたらなんか書きます。
おわり。