B木

昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。

輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。

B木がなぜ重要なのか

B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディスクI/Oを効率良く行えるかがパフォーマンス維持の要であるということは良くご存知かと思います。そのディスク上のデータを効率良く操作できるデータ構造なのですから、B木は、昨今最も重要なデータ構造のひとつであるとも言えるでしょう。

近頃のコモディティな計算機の2次記憶装置と言えばハードディスクですが、ディスクアクセスにはその構造上、データの探索に円盤の回転待ちとヘッドの移動が伴います。この円盤の回転とヘッドの移動は電気的な操作、すなわち磁気からの読み出しに比べると非常に低速で、ミリ秒単位の時間がかかります。一方、一次記憶装置のメモリへのアクセス時間はナノ秒単位で、ディスクとの差は10進で5桁以上にもなります。ディスクからデータを一回探し出すのと、メモリ上のデータを探し出すのでは105倍以上の速度差があるということです。

このディスク読み書きに伴うオーバーヘッドを最小化するために OS からのディスクアクセスはブロック単位で行われるのが一般的です。一度にまとめてデータを読み出したり、まとまったデータはディスク上でも隣接させて配置するなどして回転待ちを極力抑える工夫がなされています。

さて、B木は多分木です。木の各頂点に持たせるキーの個数を調整することで、その頂点のサイズを任意のサイズに固定させることができます。このサイズをブロックサイズと同程度に設計し、木の頂点を一つのブロックに対応させると、木の頂点の一回の移動がディスクの一回の読み出しに対応します。同じ頂点内のデータであればディスク読み出しは一度だけで探索が可能になります。

B木は平衡木で、その高さは常にデータ件数の対数オーダーです。例えば 100万個のデータがあって、各木の頂点が m = 200 の枝を持てるとすると、その高さはたったの 3 です。探索にかかる計算量はこの高さ分ですから、100万件のデータに対してほんの数回(最大4回)の探索で目的のデータを特定できます。そして、うまく設計されたB木では木の頂点の一回の移動 = ディスク読み出し一回ですから、この数回の探索がそのままディスクからのブロック読み出し回数に相当します。このように、B木なら、ディスクのオーバーヘッド抑えて大量のデータを扱うことができます。

Oracle や MySQL など近年の RDBMS はインデックスのデータ構造にB木 (の変種) を採用していますが、その理由はここにあります。

SSD がコモディティになると状況は変わる (追記アリ)

ところで、昨今は SSD の高性能化、コモディティ化がかなりの勢いで進んでいます。

SSD はディスクと違い、円盤の回転待ちやヘッドの移動を伴いません。よってハードディスクの時にあったミリ秒単位のオーバーヘッドがありません。そのため、SSD にはランダムアクセスを非常に高速に行うことができます。この違いは非常に重要です。(SSD には SSD なりのオーバーヘッドがあるとは言え) これはアーキテクチャのレベルで動作が異なる技術革新です。単にディスクと比べて○○倍高速になった、というよりももっと大きな意味を持っています。

よい実例があります。

先日 PFI さんが検索エンジンSedueのセミナーを開催されていました(Sedue の文脈ではてなブックマークを何度も紹介していただいたようです。ありがとうございました) が、この中で注目すべきは「SSD 向け全文検索エンジン」という田中さんの発表です。Suffix Array (接尾辞配列) を SSD 上に構築し SSD のランダムアクセス性能を活かすことで、二次記憶上でも大量のデータを高速に検索できるようになったという話です。Suffix Array の探索にはデータ構造上でのランダムアクセスを伴います。従来のハードディスクでは、このランダムアクセスにヘッド回転待ちのオーバーヘッドがあったために二次記憶上での大きな Suffix Array の活用は速度面で厳しかったようですが、SSD になってその障壁がなくなりました。

以下に少し前から公開されている Sedue on SSD のデモンストレーションサイトがあります。

二次記憶上での検索用のインデックスにはこれまで B木のようなディスクに最適なデータ構造が必然的に選択されてきましたが、SSD に変わると、現実的に利用可能なデータ構造にも幅が出て、アプリケーションによっては劇的な改善が可能になるというわけです。

この先 SSD の普及によって、色々なソフトウェアで、驚くような改善が行われる機会を目にすることが多くなるのではないかと思います。その時、単に SSD に変わったから速くなったと捉えるのではなく、どのようなデータ構造が選択されて、そのデータ構造の特性が SSD とどのようにマッチしたのかという視点で見ていくことが大切ではないかと思います。

追記 (2009年4月15日)

NAND フラッシュは HDD と比べるとランダムアクセス性能はずっと高いけど、やっぱりブロックデバイスとしてしか扱えない (参考: NAND型フラッシュメモリ - Wikipedia とか) ので、ほとんどの場合 B+-tree が使われるってのは変わらないんじゃないかと。

id:kazuhooku さんから返信をいただきました。ありがとうございます。少し煽りすぎましたね、反省。

追記#2 (2009年4月16日 14:30)

id:taroleo さんが最近の論文をまとめてくださいました。(午前中だけで8本読んだって...すごい) ありがとうございます。

Python によるB木の実装のソース

以下、アルゴリズムイントロダクション 18章を参考に実装したB木の実装です。練習用の実装なので、特にディスクに置くことは考慮していません。多分平衡木の動きを実装しただけのシンプルな実装です。

書籍では探索 (search) と挿入 (insert) は擬似コードが提示されていますが、delete の擬似コードは解答のない演習問題の問題になっており、掲載されていません。解説を読みながら実装したのですが、検証が不十分なのでバグがあるかもしれません。擬似コードではキーや各節点でのキーの数、子の位置などは全てグローバルな表で管理されていますが、本実装ではそれらをクラス内に収めています。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

class BTree:
    def __init__ (self, t = 2):
        self.t    = t 
        self.root = BTree.Node(t)
        self.root.is_leaf = True

    def insert(self, k):
        r = self.root
        if len(r) == 2 * self.t - 1:
            s = BTree.Node(self.t)
            s.children.append(r)
            s.split_child(0, r)
            s.insert_nonfull(k)
            self.root = s
        else:
            r.insert_nonfull(k)

    def delete(self, k):
        r = self.root
        if r.search(k) is None:
            return
        r.delete(k)
        if len(r) == 0:
            self.root = r.children[0]

    def search(self, k):
        return self.root.search(k)

    def show(self):
        self.root.show(1)

    class Node:
        def __init__(self, t):
            self.t        = t
            self.keys     = []
            self.children = []
            self.is_leaf  = False

        def __len__(self):
            return len(self.keys)

        def search(self, k):
            i = 0
            while (i < len(self) and self.keys[i] < k):
                i += 1

            if i < len(self) and self.keys[i] == k:
                return (self, i)

            if self.is_leaf:
                return
            else:
                return self.children[i].search(k)

        def split_child(self, i, y):
            t = self.t
            z = BTree.Node(t)

            z.is_leaf = y.is_leaf
            z.keys    = y.keys[t:]
            if not y.is_leaf:
                z.children = y.children[t:]

            self.children.insert(i + 1, z)
            self.keys.insert(i, y.keys[t - 1])

            y.keys     = y.keys[0:t-1]
            y.children = y.children[0:t]

        def locate_subtree(self, k):
            i = 0
            while (i < len(self)):
                if k < self.keys[i]:
                    return i
                i += 1
            return i

        def insert_nonfull(self, k):
            if self.is_leaf:
                i = 0
                for i in xrange(len(self)):
                    if k < self.keys[i]:
                        self.keys.insert(i, k)
                        return self
                self.keys.append(k)
            else:
                i = self.locate_subtree(k)
                c = self.children[i]
                if (len(c) == 2 * self.t - 1):
                    self.split_child(i, c)
                    if k > self.keys[i]:
                        c = self.children[i + 1]
                c.insert_nonfull(k)

        def show(self, pad):
            print "%s%s" % ('-' * pad, self.keys)
            if self.is_leaf:
                return
            else:
                for c in self.children:
                    c.show(pad + 1)

        ## 要検証
        def delete(self, k):
            t = self.t
            flag = False
            
            for i, x in enumerate(self.keys):
                if k == x:
                    flag = True # 現在着目中の節に k が見つかった
                    if self.is_leaf:
                        ## 1. キーが x に存在し、x が葉
                        self.keys.remove(k)
                    else:
                        ## 2. キーが x に存在し、x が内部節点
                        if i > 0 and len(self.children[i]) > t - 1:
                            ## 2a
                            self.keys[i] = self.children[i].keys.pop()
                        elif len(self.children[i + 1]) > t - 1:
                            ## 2b
                            self.keys[i] = self.children[i + 1].keys.pop(0)
                        else:
                            ## 2c
                            self.children[i].keys += [ self.keys.pop(0) ] + self.children[i + 1].keys
                            del(self.children[i + 1])
                            self.children[i].delete(k)

            if not flag:
                ## 3. 現在着目中の節 x に k がなかった => k がある部分木の根cを決める
                i = self.locate_subtree(k)
                c = self.children[i] 
                if len(c) > t - 1:
                    c.delete(k)
                else:
                    ## 3a. c自身はt-1個しかキーを持たないが、兄弟がt以上持ってる
                    if i > 0 and len(self.children[i - 1]) > t - 1:
                        flag = True
                        c.keys.insert(0, self.keys[i - 1])                 ## cと左兄弟を分離するxのキーをcに
                        self.keys[i - 1] = self.children[i - 1].keys.pop() ## 左兄弟の最後のキーをxに
                    elif len(self) > i and len(self.children[i + 1]) > t - 1:
                        flag = True
                        c.keys.append(self.keys[i])                     ## c と右兄弟を分離するxのキーをcに
                        self.keys[i] = self.children[i + 1].keys.pop(0) ## 右兄弟の最初のキーをxに

                    if flag:
                        c.delete(k)
                    else: 
                        ## 3b. 左右兄弟もt - 1しか持ってなかった
                        if i > 0:
                            l = self.children[i - 1]
                            c.keys = l.keys + [ self.keys.pop(i - 1) ] + c.keys
                            del(self.children[i - 1])
                        else:
                            r = self.children[i + 1]
                            c.keys += [ self.keys.pop(i) ] + r.keys
                            del(self.children[i + 1])
                        c.delete(k)
                        
import sys
import random

## order 5 の BTree の例
tree = BTree(5)
list = range(100)
random.shuffle(list)

for x in list:
    tree.insert(x)
tree.show()

if len(sys.argv) > 1:
    result = tree.search(int(sys.argv[1]))
    if result:
        print "HIT: %d" % result[0].keys[result[1]]

実行結果は以下になります。他の書籍ではオーダーが m の場合、子を m/2 ~ m 個とするものが多かったのですが、アルゴリズムイントロダクションではオーダー t に対して t ~ 2t という方式になっています。

% python btree.py 10
-[58]
--[5, 14, 21, 30, 36, 42, 48]
---[0, 1, 2, 3, 4]
---[6, 7, 8, 9, 10, 11, 12, 13]
---[15, 16, 17, 18, 19, 20]
---[22, 23, 24, 25, 26, 27, 28, 29]
---[31, 32, 33, 34, 35]
---[37, 38, 39, 40, 41]
---[43, 44, 45, 46, 47]
---[49, 50, 51, 52, 53, 54, 55, 56, 57]
--[65, 73, 78, 86, 92]
---[59, 60, 61, 62, 63, 64]
---[66, 67, 68, 69, 70, 71, 72]
---[74, 75, 76, 77]
---[79, 80, 81, 82, 83, 84, 85]
---[87, 88, 89, 90, 91]
---[93, 94, 95, 96, 97, 98, 99]
HIT: 10

小話

B木の B は何なんだ、という話がよくありますが

Rudolf Bayer and Ed McCreight invented the B-tree while working at Boeing[1], but did not explain what, if anything, the B stands for.

ということで、はっきりしてないみたいですね。続きにもありますが、Bayer さんの名前を取って Bayer Tree ではないのか、ということが多いようではあります。

参考文献

*1:内部節にはデータを持たせず、葉にだけデータを持たせることで内部節のキーの密度を最大化するよう改良されたB木