はじめに
最近業務で、DBのパフォーマンスチューニングをする機会があったのでインデックスについて有用性と長所について自分なりにまとめてみようと思う。
インデックスの有用性
インデックスはDBのパフォーマンスチューニングにおいて以下の観点から非常に有効な手段といえる。
- アプリケーション透過性
- インデックスを使う場合、単にDBにインデックスを追加するだけでよくアプリケーションにプログラムを変更する必要がない
- データ透過性
- インデックスの追加によって、テーブル内のデータの中身や構造が変化することはない
- 性能改善の効果が大きい
- 多くの場合インデックスの追加は、デメリットよりメリットが上回る
- しかしやみくもに追加すればよいわけではない
B-tree インデックスの長所
ここでは、インデックスの構造でよく使用される B-tree についてまとめる。
B-tree インデックスの長所は、全体的にバランスの取れた性能を持つ点ある。以下の5つの項目で平均的に高い性能を持つ。(B-treeで最下層のリーフノードが配列のようになっているものはB+treeと呼ばれ、これが主流。最下層のリーフノードにのみ格納されるデータ構造)
均一性：各キー値の間で検索速度にばらつきが少ない
- B-treeは平衡木(どのリーフもルートからの距離が一定の木)であるため、どのリーフへの探索時間もすべて同じ計算量。
- ただし、最初に作られた時はきれいな平衡木でもテーブルの挿入・更新・削除が行われると徐々に平衡木じゃなくなっていく。自動修復機能もあるが、長く使い続けると探索時間にばらつきが出る。
持続性：データ量の増加に対して、パフォーマンス低下が少ない
- B-treeのデータ探索時間はO(logn)なので、データ量が多いほどフルスキャンより速くなる
処理汎用性：検索、挿入、更新、削除のいずれの処理もそこそこ速い
- B-treeは挿入・更新・削除の計算量も探索と同様にO(logn)なので処理汎用性がある
非等値性：等号(＝)に限らず、不等号(<, > ≤, ≥)でもそこそこ速い
- B-treeは構築されるときに必ずキーの値でソートされるため、ある値以上のデータや以下のデータを効率よくとることができる。そのため、不等号(<, > ≤, ≥)でもそこそこ速い。一方で否定条件(<>, !)では特定のリーフ以外の全データになるので効果なし。
親ソート性：group by, order by, count, max, minなどのソートが必要な処理を高速化できる
- SQLはデータをどのように経路で取得するかの指示はしないので、以下の処理の場合は暗黙的にDBMS内でソートが行われる。
- 集約関数(count, sum, avg, max, min)
- order by
- 集合演算(union, intersect, except)
- olap関数(rank, row_numberなど)
ソートはコストの高い演算。そのため、DBMS内に専用のメモリ領域が割り当てられている。ただし、メモリに乗りきらないくらい大量のデータを処理する場合は、一時ディスクにデータをかき出す必要があるがこの際にI/Oのコストが非常に大きなものになる。そのため、SQLを記述する際は、極力大きなソートは避けることが望ましい。B-treeはキーの値でソートされて格納されるので、キーの値のソートが必要な場合、その処理をスキップすることができる。これが大きい。
まとめ
B-treeインデックスは、検索性能だけでなく、更新・範囲検索・ソートなど様々な処理でバランスよくパフォーマンスを発揮する優れた構造である。
特にRDBMSではほぼ標準的に使われており、まず最初に理解しておくべきインデックス構造と言える。
参考文献
本記事を書くにあたって以下の書籍を参考にしました。
- 『達人に学ぶDB設計 徹底指南書』ミック 著、翔泳社