SQLアタマアカデミー

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

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

特性

均一性

B-treeは,かなり特徴的な形をした木です。まず,どのリーフもルートからの距離(高さ)が一定です図3⁠。これは平衡木balanced tree )と呼ばれる木の特徴です。とくにB+treeはリーフにしかキー値を持たないので,探索に必要な読み込みブロック数(計算量はほぼこれで決まる)は,木の高さによって決まります。すると,リーフまでの距離が一定ということは,どのキーを使っても探索を同じ計算量で行えるということですから,検索や更新にかかる時間がキー値によらず一定になるのです。

図3 平衡木:ルートからすべてのリーフまでの距離が同じ

図3 平衡木:ルートからすべてのリーフまでの距離が同じ

仮に,インデックスが非平衡木だったとしたらどうでしょう図4⁠。たとえば,5というキーを持つリーフの高さが3で,100というキーを持つリーフまでの高さが30だとすれば,WHERE句で条件に100を指定するクエリは,5を指定するクエリより10倍多くの時間がかかってしまいます。このように,同じ構造のクエリなのに指定する条件値によって応答時間にガタツキが生じるのは,システムのサービスレベルを維持するうえで大きな不確定要因になります。一方,B-treeインデックスでは,どちらのクエリもほぼ同じ時間で処理できますリスト1⁠。

図4 非平衡木:ルートからリーフまでの距離がバラバラ

図4 非平衡木:ルートからリーフまでの距離がバラバラ

リスト1 B-treeインデックスは,どちらのクエリもほぼ同じ時間で処理する

SELECT *
  FROM TestTbl
 WHERE indexed_col = 5;

SELECT *
  FROM TestTbl
 WHERE indexed_col = 100;

普通,木に対して挿入,削除など更新処理が繰り返されると,平衡木はバランスを失い,非平衡な木になってしまいますが,B-treeの場合,これを自動的に修復してバランスを保つアルゴリズムが組み込まれています。そのためB-treeは自己組織的な構造の一種でもあります。

持続性

B-treeの第2の特徴は,非常に「平べったい(broad⁠⁠」木,言い方を変えると,背の低い木だということです。背が低い,という主観的な表現で恐縮ですが,Bayerによれば,典型的なB-treeの高さは3~5です。これはデータ量が何百万,何千万行となっても変わりません注1⁠。

平べったい形をしていることのメリットは,データ量が増えても検索や更新にかかる時間がほとんど増えないことです。先ほども述べたように,B-treeの検索に必要なディスク読み込みブロック数は,木の高さによって決まります。ということは,B-treeの場合,最悪のシナリオでも,まず4~5回のディスクアクセスで済んでしまうのです。

もう少し厳密に言うと,B-treeの検索と更新にかかる時間は,データ量に対して対数関数的(logarithmic)です。聞き慣れない言葉かもしれませんが,よく変化量に対して増加量が非常に大きいことを,⁠指数関数的」と表現します。対数は指数の反対で,増加のしかたが非常に緩やかであることを意味します注2図5⁠。

図5 B-treeはデータ量の増加に対して性能劣化が緩やか

図5 B-treeはデータ量の増加に対して性能劣化が緩やか

ただ,対数関数的といっても,厳密にそうというわけではなく,実際には挿入と削除を繰り返してインデックスの構造が崩れたりすると,多少のズレは生じます。したがってこれは,⁠だいたい」対数関数的という程度の目安だと思ってください。こういう大雑把な計算量を示すとき,ランダウの記号O で表現することがありますが,それを使えば,O (logn )となりますn はデータ量⁠⁠。

注1)
したがって,インデックスの高さが4を超えたら,まず再構築を検討するころあいだと思って良いでしょう。
注2)
「B-treeのデータ検索は非常に速く,その速度はデータのサイズにはほとんど影響を受けない。その理由はインデックスのサイズと検索速度が,データのサイズに対して対数関数的にしか増加しないからだ。このとき,対数の底は非常に大きく,今日のストレージアーキテクチャであれば最低でも1以上だ。」⁠Rudolf Bayer ⁠B-tree and UB-tree⁠, 2008, Scholarpedia, 3(11):7742.)

著者プロフィール

ミック

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

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

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