なぜBTreeがIndexに使われているのか

※この内容は個人的な考察なので、間違っている箇所もあると思います。そういう部分を見つけた際はぜひ教えて下さい。

RDBMSの検索を早くするためにIndexって使いますよね。例えばこんなテーブル

CREATE TABLE user (
    id INT UNSIGNED NOT NULL,
    name VARCHAR(255) NOT NULL, 
    UNIQUE INDEX (id)
);

idカラムにIndexを張っています。これはidでの検索を高速にするためです。ここでidカラムにIndexが貼っていない場合と比べると検索時間が大幅に変わってきてしまいます（特にレコードが多くなった時)

ではなぜIndexを貼ると検索が早くなるんでしょう？？

Indexとはその名の通り索引を意味します。特定のカラムの索引を作成しておくことで検索を高速化します。 (本の最後によみがな順で単語が並べられたりしていますよね)

で、その索引の実装としてRDBMSのIndexでよく使われるのがBTreeと呼ばれるアルゴリズムです。 (正確にはBTreeを改良したB+Treeというアルゴリズムが使われることが多いようです)

まずはBTreeについて説明する前に二分探索、計算量、二分探索木について説明します。

二分探索

次のようなソート済みの数列があるときに10がどこにあるかを探索するにはどうすればいいでしょうか？

1, 3, 4, 5, 10, 11, 13

一番愚直に調べる方法は前から順に調べていく事です(線形探索)

しかしもっと高速に検索する方法があります。それは二分探索と呼ばれる手法で、ソート済みの数列から任意の値を探索するのに使われます。 二分探索は探索する範囲を1/2にしながら目的の値を見つけ出します。

1. 初めに数列の真ん中を調べて5を得ます
2. 10は5より大きいので右半分だけを探索対象に変更します
3. 右半分の真ん中を調べて11を得ます
4. 10は11より小さいので左半分だけを探索対象に変更します
5. 10を見つけることができました

では線形探索と二分探索はどの程度速度が違うのでしょうか？ 次はアルゴリズムの評価に使われる計算量について説明します。

計算量

計算量とはプログラムへの入力量に対する実行時間の関係を大雑把に表したものです。 (一般的に計算量と言えば、実行時間を表すものですが、空間量を表す場合もあります)

例えば先程の線形探索として以下の様なプログラムを考えます。

#include <stdio.h>
int main(void){
    int input[] = {1, 3, 4, 5, 10, 11, 13};
    int len = (int)(sizeof(input)/sizeof(int));
    int target = 10;
    int i;

    for(i = 0; i < len; i++){
        if (input[i] == target) {
            printf("target index is %d\n", i);
            break;
        }
    }

    return 0;
}

3行目から6行目は数列の長さによらず一定です。8行目から13行目が数列の長さに応じて変動します。計算量は入力によらず一定の時間となるような処理については無視します。また計算量は一般的には最悪の場合について考えます。 つまり線形探索は数列の長さがNの時に、最悪N回の探索が必要になります。これをO(N)と書きます。これは入力Nに対して比例することを表します。 (読み方は"おーだーえぬ"です)

入力Nが10倍ずつ増えていくと、計算量も10倍ずつ増えることになります。よって、入力Nが非常に大きい値の場合、探索にかかる時間も増えてしまいます。

では二分探索の場合、計算量はいくつになるでしょうか？

二分探索は検索する範囲を1/2に縮めながら探索をしていき、最悪の場合、探索範囲が1になるまで実行することになります。つまり「入力される数列の長さN」を「2で割り続けて1になった時の割った回数」が「探索回数t」となります。そして「探索回数t」が二分探索の計算量になります。式で表すと以下のとおりです。

これをtについて変形すると

探索回数tが計算量となるので、O(log N)になります。二分探索では入力Nが10倍ずつ増えていっても、計算量はO(log N)ですむため、線形探索とは違い性能があまり劣化しません。

例えばNが1024の時、線形探索の計算量は1024になりますが、二分探索の計算量は10となり、圧倒的に早いことがわかります。

二分探索木

二分探索は小さいものと大きいものを振り分けながら探索を進めていきますが、この振り分けを二分探索木というデータ構造で表現することができます。

与えられた数列を二分探索木で表現することにより、二分探索での探索を実現することができます。

BTreeとはこの二分探索木を一般化してものとして扱うことができます。

BTree

BTreeは二分探索木を一般化したものと言いましたがどのように一般化したかというと、1つのノードがm個(m>=2)の子ノードを保持することができるものを言います。m=2の場合が二分検索木になります。一般的にm個の子ノードを持つことが可能なBTreeを「m階のBTree」と呼びます。 (詳しくはBTreeを参照してください)

これだけだとわかりにくいと思うので、m=3の場合に1 .. 26の数列をBTreeで表現したものが以下になります。

それぞれのノードは2個の値を持ち、3個の子ノードを持ちます。例えば頂点(rootノード)は9,18の値を持ち、「9未満の数」「9以上、18未満の数」「18以上の数」というように子ノードを3つのグループに分けています。

ではこのBTreeを使って17という値を探索してみます。

1. Rノードを探索して17が含まれる範囲を見つけます
2. 17は9以上、18未満の数なので次はAノードを探索します
3. Aノードを探索して17が含まれる範囲を見つけます
4. 17は15以上の数なので次はBノードを探索します
5. Bノードを探索して17を見つけることができました

次にBTreeの計算量を求めてみましょう。 BTreeは探索する範囲を1/mに縮めながら探索をしていき、最悪の場合、探索範囲が1になるまで実行することになります。つまり「入力される数列の長さN」を「mで割り続けて1になった時の割った回数」が「探索回数t」となります。この「探索回数t」が計算量になります。式で表すと以下のとおりです。

これをtについて変形すると

しかしBTreeの計算量はこれだけではなく、各ノード内での値の探索も行います。これはt回行うことになるのですが、二分探索を使った場合log (m-1)になります。つまり計算量は以下のとおりです。

これはlog N以下の計算量になることがわかります。

またm階のBTreeは子ノードの数が最悪m/2になるようにすればよいので、全てのノードがm/2個の子ノードをもつ場合は以下のようになります

これでもlog N以下になることがわかります。 というわけでBTreeの説明が終わりました。次はなぜBTreeがIndexに使われているのかを説明します。

なぜBTreeなのか？

計算量だけをみるとBTreeのほうが二分探索木よりも良いようですが、処理が複雑になってしまっています。もしかするとその分BTreeのほうが実行時間が長くなる可能性があります(計算量はあくまで目安なので計算量が少ないからと言って必ずしも早いわけではない) なのに、なぜIndexには二分探索木ではなくBTreeが使用されているのでしょうか？

それはBTreeがハードディスク(ブロックデバイス)と相性が良いからです。BTreeとハードディスクの相性は、ハードディスクからデータを読み取る方法に関係します。

ハードディスク

ハードディスクからデータを読み取る場合、あるサイズ単位の塊でデータを読み取ります。この塊をブロックと呼び、512バイトや1024バイトなどファイルシステム・設定によって様々です。 つまりブロックサイズが512バイトの場合、700バイトのデータを読み取るときには2ブロック(1024バイト)を読み取ることになります。

小さなデータを沢山読み取る必要がある場合、複数のブロックを読み取る必要があります。複数のブロックを読み取る必要があるということは、ハードディスクのヘッドの移動やディスクの回転などを伴うため、非常に遅くなってしまいます（メモリ読み込み時間やCPUの演算速度と比べて)

つまりハードディスクを効率的に扱うには、なるべくブロックの読み取り回数を少なくして機械駆動の部分を使わないことです。このことを考えた上でBTreeがなぜハードディスクと相性が良いか考えてみます。

BTreeとハードディスクの相性

m階のBTreeは1つのノードにm-1個の値を持つことができました。このノードを1ブロックに収まるようにすることで、BTreeを使った探索を行うときにブロックの読み取り回数を最小限に抑えることができます。

例えばハードディスクのブロックサイズが512バイトだった場合、int型(4バイト)の値を1ブロックに128個保存することができます。これはint型のカラムにIndexを貼ったい場合に129階のBTreeを構成できることを表します。 (実際は子ノードのブロック位置を保存する必要もあるので、128より少なくなります)

一方、二分探索木の場合は1つのノードに1つの値しか入れていません。同じブロックに入っているノードもありますが、探索する順序やIndexの構成によっては全て異なるブロックを読み取らないといけない可能性もあります。

ではBTreeと二分探索木ではブロックの読み取り回数はどれほど違うのでしょうか。ブロックの読み取り回数は木の深さ(探索回数t)になります。 BTreeの場合log N / log m、二分探索木の場合log Nになります。これはmが大きくなればなるほど、差が出てきます。

このような理由によってBTreeはハードディスクと相性が良いと言われており、Indexの実現方法として採用されています。

まとめ

線形探索を行うよりも索引を作ったほうが高速に探索でき、その索引の実装としては二分探索木やBTreeがあります。ハードディスクとの相性を考えるとBTreeのほうが優位なため、Indexの実現にBTreeが使われています。

最後に

DBの検索を高速化するためにIndexを構築するというのはよく聞きますが、じゃあなぜIndexを構築すると早くなるのかって気にはなっていたものの放置していました。

しかし最近ようやく仕事でDBを触るようになり、良い機会なので個人的に考察してみました。納得行くまで考えてみるのは面白いですね。ソースコードを読んだわけじゃないので、実際はもっと複雑で様々な工夫がなされているとは思います。考察するにあたって一行もコードは読んでいません。「IndexってBTreeで実現されているんだよ」という情報を頼りに色々考えてみた結果がこれです。

うまく説明できている自信は無いですが、誰かIndexについてもやもやしている人の助けになれば嬉しいです。