SQLアタマアカデミー

第7回 性能改善の鍵,インデックスの特性を知る~B-treeとハッシュ (1)B-tree

この記事を読むのに必要な時間:およそ 4 分

処理汎用性

ビットマップインデックスのようなインデックスは,検索速度は時にB-treeを凌駕しますが,更新処理に多大な時間がかかるという欠点を持ちます。しかし,B-treeの場合,挿入/更新/削除のコストも,検索と同じくデータ量n に対してO (logn )であるため,いずれの処理も「まあまあ」速く,かつデータ量が増えてもパフォーマンスがほとんど悪化しません。

非等値性

B-treeは,構築されるとき必ずキー値をソートします(文字型などの列でも,アルファベット順とか適当な順序でソートします⁠⁠。したがって,たとえばWHERE句で「100以上」という条件を指定した場合,まずはキー値=100のリーフを探し(これは平均3~4回のアクセスで見つかる⁠⁠,それ以降のリーフ全部を読み込むことで,条件に合致するキー値を漏れなく選択できます。

これによって,B-treeは,等号だけでなく,不等号やBETWEENを使った条件に対しても高速な検索が可能ですリスト2⁠。これは,あとで紹介するハッシュにはない利点です。

リスト2 B-treeは不等号や範囲検索もそこそこ速い

SELECT *
  FROM TestTbl
 WHERE indexed_col > 100;

SELECT *
  FROM TestTbl
 WHERE indexed_col <= 100;

SELECT *
  FROM TestTbl
 WHERE indexed_col BETWEEN 10 AND 100;

ただそうは言ってもやはり,不等号の検索は,等号の検索に比べれば遅いですし,また,否定条件(<>,!=)に対しては,B-treeはまるで役に立ちません。また一般的に,B-treeはNULLをキー値として保持しないため,IS [NOT] NULLを指定した場合もインデックスは使われませんリスト3⁠。

リスト3 否定条件やIS NULLでは役に立たない


SELECT *
  FROM TestTbl
 WHERE indexed_col <> 100;

SELECT *
  FROM TestTbl
 WHERE indexed_col IS NULL;
親ソート性

遅いSQL文によくありがちなパターンとして,巨大なソートをしている場合があります。SQLは明示的にソートを記述することはしませんが,次のような処理を記述したとき,内部でソートを行います。

  • 集約関数(COUNT,SUM,AVG,MAX,MIN)
  • ORDER BY句
  • 集合演算(UNION,INTERSECT,EXCEPT)
  • OLAP関数(RANK,ROW_NUMBERなど)

ソートがメモリ上で行われている間はそれほど大きなパフォーマンス低下は引き起こさないのですが,データ量が膨大でメモリ上には収まりきらない場合,データベースはしかたなく,ディスクへデータを書き出すディスクソートを行います。これが発生すると,ガクンとSQLのパフォーマンスが落ちます。そのため,ディスクソートはハイパフォーマンスを要求されるシステムにとって鬼門の1つです。

しかし,B-treeインデックスの存在する列をGROUPBY句やORDER BY句のキーとして指定することで,ソート負荷を軽減することが可能になるのですリスト4⁠。これは複数の列にインデックスを作成する複合インデックスの場合にも当てはまります。

リスト4 B-treeインデックスが高速化することがある処理の例


SELECT SUM(col)
  FROM TestTbl
 GROUP BY indexed_col;

SELECT indexed_col
  FROM TestTbl
ORDER BY indexed_col;

SELECT COUNT(*)
  FROM TestTbl;

SELECT MAX(indexed_col)
  FROM TestTbl;

SELECT MIN(indexed_col)
  FROM TestTbl;

著者プロフィール

ミック

SI企業に勤務するDBエンジニア。主にデータウェアハウス業務に従事している。自身のサイト「リレーショナル・データベースの世界」でデータベースとSQLについての技術情報を公開している。『Web+DB Press』で「SQLアタマアカデミー」を連載中。

著書:『達人に学ぶ SQL徹底指南書』(翔泳社、2008)訳書:J.セルコ『SQLパズル 第2版』(翔泳社、2007)

SQLアタマアカデミー:サポートページ