B+木の概要と実装

B+木とは

B+木は、m分木をもとにしたデータ構造です。 m分木とは節が最大  m (m \geqq 2) の子をもつことができる木構造で、二分木の一般化といえます。 B+木では、データをもつのは葉のみで、葉以外の節はキーだけをもつ構成をとっています。

以下の条件を満たすものをm階のB+木と呼びます。

  1. 根は葉であるか、あるいは 2 \sim m 個 の子をもてる
  2. 根、葉以外の節は、  \lceil m/2 \rceil \sim m 個の子をもっている。
  3. 根からすべての葉までの経路の長さが等しい。

条件3によって、B+木は常に長さが等しくバランスがとれていることになります。 n 個の要素をもつB+木の高さは、最悪のケースで  \log_{ \lceil m/2 \rceil } n 程度、最良のケースで  \log_{m} n 程度になります。 通常  m  n に比べて十分小さいものとみなせるため、計算量としては O( \log n) 程度となります。

B+木の節は、最大  m 個の節と  m-1 個の「境界を示す値」が格納されています。
B+木の葉には、キーとデータが格納されます。

B+木の操作

探索

根から始めて探索キーを境目の値と比較しながら、部分木を下向きにたどっていきます。
葉に到達したとき、探索キーの値と葉に持っているキーの値が等しければ探索は成功、等しくなければ探索は失敗となります。

挿入

探索によって、葉のひとつ前の節  \alpha まで下ります。新しく作成した葉  \beta が節  \alpha に追加する余地があるならば、
 \beta をを節  \alpha の子として適切な位置に付け加えるだけです。
 \alpha がすでに  m 個の子を持っている場合は、節  \alpha を2つに分割することになります。
 \alpha を2つに分割するということは、節  \alpha の親の節から見れば、子が一つ増えたことと同様になります。そのため、節  \alpha の親の節に対しても節  \alpha と同じ処理を行います。このようにして、節の分割が親へ親へと上向きに根に向かって伝播していきます。途中で節を分割しないで挿入できれば、その節の先祖については分割は伝播しません。もし分割が根  \gamma まで伝播して、かつ根が  m 個の子をもっていた場合は、根  \gamma を節  \gamma_1 と節  \gamma_2 に分割して、新に根  \delta を割り当てて、根  \delta の子として節 \gamma_1 と節 \gamma_2 を割り当てます。
B+木の高さが増えるのは、要素の挿入によって、節の分割が根まで伝播した場合のみです。

削除

探索によって、削除の対象となる葉 L を探し出します。葉Lの親を節  \alpha とします。もし、節  \alpha から葉Lを削除した時、節  \alpha に子が  \lceil m/2 \rceil 個以上残っていれば、節  \alpha の中身を詰め替えるだけで処理は完了です。
もし、節  \alpha から子 L を削除した時に、節  \alpha に子が  \lceil m/2 \rceil-1 個しか残っていなければ、隣の節  \beta から子をもらってきます。
削除の場合は、隣の節  \beta から子をもらおうとしたときに、隣の節  \beta  \lceil m/2 \rceil 個しか子を持たない場合は、節  \beta から子をもらうと、節  \beta  \lceil m/2 \rceil-1 個しか子をもたたくなり、B+木の条件を満たさなくなります。この場合は節  \alpha と節  \beta を併合してしまいます。併合してできた節は  m 個または  m-1 個の子をもつのでB+木の条件を満たします。
 \alpha と節  \beta が併合されたということは、親から見れば子が1つなくなることを意味します。親についても同様の処理を行います。そうして節の併合が根  \gamma まで伝わり、根  \gamma がただ一つの子  \delta のみをもつようになったら、根  \gamma を削除して、節  \delta を新たに根とします。この操作のみB+木の高さが1つ小さくなります。

B+木の動作イメージ(挿入のみ)

{1, 21, 10, 7, 94, 11, 6, 96, 34, 71, 15, 38, 3, 35, 27, 29, 79, 82} 上記のキーを順番にB+木に格納したときの動作を可視化してみます。
今回は木の分割が分かりやすいように 3 階のB+木とします。
3 階のB+木のため、葉の要素は最大で  27 = 3^3 個になります。

f:id:d_tutuz:20180125001827g:plain

上のgifを見ればわかるように、途中の節に関しては必ずしもすべて使用されるわけではありません。B+木の条件2より最低でも  \lceil m/2 \rceil 個の子をもてばB+木として成立するためです。これがB+木の欠点です。最悪の場合は約半分程度の記憶領域が無駄になります。

B+木の実装

以下にB+木の実装を載せておきます。 こちらは、以下の「Javaプログラマのためのアルゴリズムとデータ構造」*1から自分の理解のために写経したものになります。

public class BTree {


    final private static int MAX_CHILD = 5;
    final private static int HALF_CHILD = ((MAX_CHILD + 1) / 2);

    /**
    * B木の節
    * */
    private abstract class Node {

        int serial;

    }

    /**
    * B木の内部節
    * */
    private class InternalNode extends Node {

        // この節が持っている子の数
        int nChilds;

        // 部分木
        Node[] child;

        // 各部分木の最小の要素=境界の値が入っている
        Integer[] low;

        /**
        * コンストラクタ:空の内部節を生成する
        * */
        private InternalNode() {
            serial = serialNumber++;
            nChilds = 0;
            child = new Node[MAX_CHILD];
            low = new Integer[MAX_CHILD];
        }

        /**
        * キーkeyをもつデータは何番目の部分木に入るかを調べる。
        * 線形探索法によって境界の値と比較を実施している。
        *
        * @param key 調べるキー
        * @return キーkeyが何番目の部分木に入るかを調べる
        * */
        private int locateSubtree(Integer key) {
            for (int i = nChilds - 1; i > 0; i--) {
                if (key.compareTo(low[i]) >= 0) {
                    return i;
                }
            }
            return 0;
        }
    }

    private class Leaf extends Node {

        Integer key;    // 葉が持っているキーの値
        Object data;    // 葉に格納するデータ

        /**
        * コンストラクタ:葉を生成する
        * */
        private Leaf(Integer key, Object data) {
            serial = serialNumber++;
            this.key = key;
            this.data = data;
        }

    }

    // B木の根
    private Node root;
    // Nodeに附番するシリアル番号
    private int serialNumber = 0;

    private Leaf currentLeaf;

    /**
    * コンストラクタ:B木を生成する
    * */
    public BTree() {
        root = null;
    }

    /**
    * B木からキーkeyを探索する。
    * キーkeyをもつ葉が見つかれば、それをcurrentLeafフィールドにセットする。
    * */
    public boolean search(Integer key) {

        currentLeaf = null;

        // 空の木であれば、即座にfalseを返す
        if (root == null) {
            return false;
        } else {
            // 根から始めて、葉にたどり着くまで内部節をたどる
            Node p = root;
            while (p instanceof InternalNode) {
                InternalNode node = (InternalNode)p;
                p = node.child[node.locateSubtree(key)];
            }

            // 与えられたキーと、葉にセットされているキーを比較する
            Leaf leaf = (Leaf)p;

            // 探索に成功
            if (key.compareTo(leaf.key) == 0) {
                currentLeaf = leaf;
                return true;
            } else {
                // 探索に失敗
                return false;
            }
        }
    }

    /**
    * 最後に成功したsearchメソッドが見つけた要素のデータを得る
    * */
    public Object getData() {
        if (currentLeaf == null) {
            return null;
        } else {
            return currentLeaf.data;
        }
    }

    /**
    * 最後に成功したsearchメソッドが見つけた要素がもつデータをセットする
    * */
    public boolean setData(Object data) {
        if (currentLeaf == null) {
            return false;
        } else {
            currentLeaf.data = data;
            return true;
        }
    }

    /**
    * InsertAuxメソッドの結果
    * ※複数のフィールドをメソッドの返り値として返却するために使用される
    *
    * */
    private static class InsertAuxResult {
        Node newNode;   // 新しい節を作った場合に、その節が入る
        Integer lowest; // 新しい節を作った場合に、newNodeが指す部分木の最小要素が入る

        private InsertAuxResult(Node newNode, Integer lowest) {
            this.newNode = newNode;
            this.lowest = lowest;
        }
    }

    /**
    * 指定した節に対して、キーkeyをもつ要素を挿入する(insertの下請け)
    *
    * @param pnode 内部節pnodeのnth番目の子に対して挿入を行う。
    *              pnodeがnullの場合は根が対象になる。
    * @param nth 内部節pnodeのnth番目の子に対して挿入を行う。
    * @param key 挿入する要素のキー
    * @param data 挿入する要素のデータ
    *
    * @return 結果を表すInsertAuxResult型のオブジェクト
    * */
    private InsertAuxResult insertAux(InternalNode pnode, int nth, Integer key, Object data) {

        // 要素の挿入の対象となる節へのリンクを変数thisNodeに入れる
        Node thisNode;

        if (pnode == null) {
            thisNode = root;
        } else {
            thisNode = pnode.child[nth];
        }

        // この葉は節である
        if (thisNode instanceof Leaf) {

            // これ以降、この節を葉leafとして参照する
            Leaf leaf = (Leaf)thisNode;

            // 既に登録済であれば、何もしないでnullを返す
            if (leaf.key.compareTo(key) == 0) {
                return null;
            } else {
                // 新たに葉newLeafを割り当てる
                Leaf newLeaf = new Leaf(key, data);

                // もし割り当てた葉newLeafのほうが葉leafよりも小さいなら、newLeafとleafの位置を入れ換える
                if (key.compareTo(leaf.key) < 0) {
                    // 元の節には、新しく割り当てた葉newLeafを入れる
                    if (pnode == null) {
                        root = newLeaf;
                    } else {
                        pnode.child[nth] = newLeaf;
                    }
                    // 新たに割り当てた葉として、leafを報告する
                    return new InsertAuxResult(leaf, leaf.key);
                } else {
                    // 新たに割り当てた葉として、newLeafを報告する
                    return new InsertAuxResult(newLeaf, key);
                }
            }

        // この節は内部節である
        } else {
            // これ以降、この節を内部節nodeとして参照する
            InternalNode node = (InternalNode)thisNode;

            // 何番目の部分木に挿入するかを決める
            int pos = node.locateSubtree(key);

            // 部分木に対して、自分自身を再帰呼び出しする
            InsertAuxResult result = insertAux(node, pos, key, data);

            // もし分割が行われていなければ、そのまま戻る
            if (result == null || result.newNode == null) {
                return result;
            }

            // 分割が行われていたので、節nodeにそれ(result.newNode)を挿入する
            if (node.nChilds < MAX_CHILD) {
                // 追加の余地があったので、適切な位置に挿入する
                for (int i = node.nChilds - 1; i > pos; i--) {
                    node.child[i+1] = node.child[i];
                    node.low[i+1] = node.low[i];
                }
                node.child[pos+1] = result.newNode;
                node.low[pos+1] = result.lowest;
                node.nChilds++;
                return new InsertAuxResult(null, null);
            } else {
                // 追加の余地がないので、節nodeを2つに分割しなければならない
                // 新しい内部節newNodeを割り当てる
                InternalNode newNode = new InternalNode();

                // 節result.newNodeがどちらの節に挿入されるかで、場合分けする
                if (pos < HALF_CHILD - 1) {
                    // 節result.newNodeは節node側に挿入される
                    // まずHALF_CHILD-1~MAX_CHILD-1番目の部分木を節nodeから節newNodeに移す
                    for (int i = HALF_CHILD-1, j = 0; i < MAX_CHILD; i++, j++) {
                        newNode.child[j] = node.child[i];
                        newNode.low[j] = node.low[i];
                    }
                    // 0~HALF_CHILD-2番目の部分木の間の適切な位置に、節result.newNodeを挿入する
                    // 節result.newNodeへと移す
                    for (int i = HALF_CHILD-2 ; i > pos; i--) {
                        node.child[i+1] = node.child[i];
                        node.low[i+1] = node.low[i];
                    }
                    node.child[pos+1] = result.newNode;
                    node.low[pos+1] = result.lowest;
                } else {
                    // 節result.newNodeは節newNodeの側に挿入される
                    // HALF_CHILD~MAX_CHILD-1番目の部分木を、節newNodeに移動する。
                    // 同時に節result.newNodeを適切な位置に挿入する
                    int j = MAX_CHILD - HALF_CHILD;
                    for (int i = MAX_CHILD-1; i >= HALF_CHILD; i--) {
                        if (i == pos) {
                            newNode.child[j] = result.newNode;
                            newNode.low[j--] = result.lowest;
                        }
                        newNode.child[j] = node.child[i];
                        newNode.low[j--] = node.low[i];
                    }
                    if (pos < HALF_CHILD) {
                        newNode.child[0] = result.newNode;
                        newNode.low[0] = result.lowest;
                    }
                }
                // 子の数nChildを更新する
                node.nChilds = HALF_CHILD;
                newNode.nChilds = (MAX_CHILD + 1) - HALF_CHILD;

                // 分割して作られた節をフィールドnewNodeに、
                // またその最小値をlowestフィールドに返す
                return new InsertAuxResult(newNode, newNode.low[0]);

            }
        }
    }

    /**
    * B木に要素を挿入する
    *
    * @param key 挿入する要素のキー
    * @param data 挿入する要素のデータ
    * */
    public boolean insert(Integer key, Object data) {

        currentLeaf = null;

        // 木が空の場合は、葉を作ってtrueを返す
        if (root == null) {
            root = new Leaf(key, data);
            return true;
        } else {
            // 木が空でない場合はinsertAuxメソッドを呼び出して、要素の挿入を行う
            InsertAuxResult result = insertAux(null, -1, key, data);

            // もし結果がnullなら、すでにキーkeyは登録されているので、そのままfalseを返す
            if (result == null) {
                return false;
            }

            // もし分割が行われたら、木の高さを1段高くする
            if (result.newNode != null) {
                InternalNode newNode = new InternalNode();
                newNode.nChilds = 2;
                newNode.child[0] = root;
                newNode.child[1] = result.newNode;
                newNode.low[1] = result.lowest;
                root = newNode;
            }
            return true;
        }
    }

    /**
    * 内部節pのx番目とx+1番目の部分木を再編成する。
    * もし、併合が必要なら、すべての要素をx番目の部分木に集めて、trueを返す
    * 併合が不要ならfalseを返す
    *
    * @param p 内部節p
    * @param x 内部節pのx番目とx+1番目の部分木を再編成する
    *
    * */
    private static boolean mergeNode(InternalNode p, int x) {
        InternalNode a = (InternalNode)p.child[x];  //x番目の部分木
        InternalNode b = (InternalNode)p.child[x+1];   //x+1番目の部分木
        b.low[0] = p.low[x+1];

        int an = a.nChilds;
        int bn = b.nChilds;

        if (an + bn <= MAX_CHILD) {
            // 部分木aとbを併合しなければならない
            // bの子をすべてaへ移動する
            for (int i = 0; i < bn; i++) {
                a.child[i+an] = b.child[i];
                b.child[i] = null;
                a.low[i+an] = b.low[i];
            }
            a.nChilds += bn;
            return true; // 併合したことを通知する
        } else {
            // 部分木aとbで、節を再分配する
            int move;  // 移動する要素の個数

            // 部分木aに分配すべき子の数を求める
            int n = (an + bn) / 2;
            if (an > n) {
                // 部分木aから部分木bへと移動する
                move = an - n;
                // bの要素を右にずらす
                for (int i = 0; i < move; i++) {
                    b.child[i] = a.child[i+n];
                    a.child[i+n] = null;
                    a.low[i] = a.low[i+n];
                }
            } else {
                // 部分木bから部分木aへと移動する
                move = n - an;
                for (int i = 0; i < move; i++) {
                    a.child[i+an] = b.child[i];
                    a.low[i+an] = b.low[i];
                }
                // bの要素を左に詰め合わせる
                for (int i = 0; i < bn - move; i++) {
                    b.child[i] = b.child[i+move];
                    b.child[i+move] = null;
                    b.low[i] = b.low[i+move];
                }
            }
            // 子の個数を更新する
            a.nChilds = n;
            b.nChilds = an + bn - n;
            // 部分木bの最小値を節pにセットする
            p.low[x+1] = b.low[0];
            return false;
        }

    }

    // deleteAuxメソッドの戻り値
    // 値の意味は、deleteAuxメソッドのコメントを参照のこと
    private enum Status {
        OK,
        OK_REMOVE,
        OK_NEED_REORG,
        NOT_FOUNDS
    }

    /**
    * 節thisNodeから、キーkeyをもつ要素を削除する(deleteの下請け)
    *
    * @oaram thisNode この節(またはその部分木)から要素を削除する
    * @param key 削除する要素のキー
    *
    * @return 以下の値を返す
    *              OK:             削除に成功。thisNodeには何も変化ない
    *              OK_REMOVE:      削除に成功。thisNodeそのものが削除された
    *              OK_NEEW_REORG:  削除に成功。thisNodeの子が少なく(HALF_CHILD以下)になったので、
    *                              再編成が必要になった
    *              NOT_FOUNDS:     削除に失敗。キーkeyをもつ子は見つからなかった
    * */
    private static Status deleteAux(Node thisNode, Integer key) {

        if (thisNode instanceof Leaf) {
            // この節は葉である
            Leaf leaf = (Leaf) thisNode;

            if (leaf.key.compareTo(key) == 0) {
                return Status.OK_REMOVE;
            } else {
                // キーが一致しなかった場合
                return Status.NOT_FOUNDS;
            }
        } else {
            // この節は内部節である
            InternalNode node = (InternalNode)thisNode;

            boolean joined = false;  // 再編成の結果、部分木が併合されたかどうか
            // どの部分木から削除するかを決める
            int pos = node.locateSubtree(key);
            // その部分木に対して、自分自身を再帰呼び出しする
            Status result = deleteAux(node.child[pos], key);
            // 部分木に何の変化もなければ、そのまま戻る
            if (result == Status.NOT_FOUNDS || result == Status.OK) {
                return result;
            }

            // 部分木posを再編成する必要があるか
            if (result == Status.OK_NEED_REORG) {
                int sub = (pos == 0) ? 0 : pos - 1;
                // 部分木subとsub+1を再編成する
                joined = mergeNode(node, sub);
                // もしsubとsub+1が併合されていたら、部分木sub+1をnodeから削除する必要がある
                if (joined) {
                    pos = sub + 1;
                }
            }

            Status myResult = Status.OK;

            // 部分木posが削除された
            if (result == Status.OK_REMOVE || joined) {
                // nodeの部分木を詰め合わせる
                for (int i = pos; i < node.nChilds - 1; i++) {
                    node.child[i] = node.child[i+1];
                    node.low[i] = node.low[i+1];
                }
                node.child[node.nChilds-1] = null; // 不要な参照を削除する
                // もし、nodeの部分木の数のHALF_CHILDより小さいなら、再編成が必要である。
                if (--node.nChilds < HALF_CHILD) {
                    myResult = Status.OK_NEED_REORG;
                }

            }
            return myResult;
        }
    }

    /**
    * B木から要素を削除する
    *
    * @param key 削除する要素のキー
    *
    * */
    public boolean delete(Integer key) {

        // currentLeafフィールドをnullにする。
        currentLeaf = null;

        // 木が空ならばfalseを返す
        if (root == null) {
            return false;
        } else {
            // 木が空でない場合
            // deleteAuxメソッドを呼び出して、キーkeyをもつ要素を削除する
            Status result = deleteAux(root, key);

            // 見つからなければfalseを返す
            if (result == Status.NOT_FOUNDS) {
                return false;
            }

            if (result == Status.OK_REMOVE) {
                // 根が削除されたので、rootにnullを代入する
                root = null;
            } else if (result == Status.OK_NEED_REORG && ((InternalNode)root).nChilds == 1) {
                // 根が再編成された結果、根の子が1つだけになったら、木の高さを1つ減らす
                root = ((InternalNode)root).child[0];
            }
            return true;
        }
    }

    /**
    * B木の内容を表す文字列を返す
    *
    * @param p この節より下の部分を表す文字列を生成して返す
    * @return 節pより下の部分を表す文字列
    * */
    private static String toStringAux(Node p) {
        // 葉が内部節かで処理を分ける
        if (p instanceof Leaf) {
            // 葉である
            Leaf l = (Leaf)p;
            return "Leaf #" + l.serial + " key=" + l.key;
        } else {
            // 内部節である
            InternalNode n = (InternalNode)p;
            String s = "Node #" + n.serial + " (" + n.nChilds + " childs): ";
            s += "#" + n.child[0].serial + " ";
            for (int i = 1; i < n.nChilds; i++) {
                s += "[" + n.low[i] + "] #" + n.child[i].serial + " ";
            }
            s += "\n";
            for (int i = 0; i < n.nChilds; i++) {
                s += toStringAux(n.child[i]) + "\n";
            }
            return s;
        }
    }

    /**
    * B木の内容を表す文字列を返す
    *
    * @return B木の内容を表す文字列
    * */
    public String toString() {
        if (root == null) {
            return "<Tree is empty.>";
        } else {
            return toStringAux(root);
        }
    }

}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BTreeTest {


    /**
    * テスト用のメインルーチン
    *
    *      ">"というプロンプトが表示されるので、コマンドを入力すると実行結果が表示される。
    *
    *      コマンド一覧(nは整数)
    *          +n          : nを挿入する
    *          -n          : nを削除する
    *          /n          : nを探索する
    *          =String     : 直前に成功した/コマンドで見つけた要素に対する値をStringにする
    *          p           : B木の内容を表示する
    *          q           : 終了する
    * @throws IOException
    *
    * */
    public static void main(String[] args) throws IOException {

        BTree tree = new BTree();

        // B木に初期データを挿入する
        int data[] = {1,100,27,45,3,135};


        for (int x : data) {
            tree.insert(x, "["+x+"]");
        }

        // コマンドを1行入力して、それを実行する
        // これをEOFになるまで繰り返す
        System.out.println(">");
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        String str = null;
        while ((str = input.readLine()) != null) {
            if (str.length() == 0) {
                // 空行は読み飛ばす
                System.out.print(">");
                continue;
            }

            // 先頭の1文字(コマンド)をcommandに入れる
            char command = str.charAt(0);

            // 引数部分をargに入れる。その際に先頭のスペースを削除する
            String arg = str.substring(1).trim();

            // コマンドによって分岐する
            if (command == 'q') {
                break;
            } else if (command == 'p') {
                System.out.println(tree);
            } else if (command == '=') {
                if (tree.setData(arg)) {
                    System.out.println("value:" + arg + " succeeded.");
                } else {
                    System.out.println("value:" + arg + " failed.");
                }
            } else if (command == '+' || command == '-' || command == '/') {
                // +, - コマンドならば、コマンドに続く数値をnumに得る
                int num = 0;
                try {
                    num = Integer.parseInt(arg);
                } catch (NumberFormatException e) {
                    System.err.println("input NOT integer. value:" + arg);
                    continue;
                }
                if (command == '+') {
                    if (tree.insert(num, "["+num+"]" )) {
                        System.out.println(num + " insert succeeded.");
                    } else {
                        System.out.println(num + " insert failed.");
                    }
                } else if (command == '-') {
                    if (tree.delete(num)) {
                        System.out.println(num + " delete succeeded.");
                    } else {
                        System.out.println(num + " delete failed.");
                    }
                } else if (command == '/') {
                    if (tree.search(num)) {
                        System.out.println(num + " found. value:" + tree.getData());
                    } else {
                        System.out.println(num + " NOT found.");
                    }
                }
            } else {
                System.out.println("command:" + command + " is NOT supported.");
            }
            System.out.print(">");
        }
    }

}

定本Javaプログラマのためのアルゴリズムとデータ構造

定本Javaプログラマのためのアルゴリズムとデータ構造

*1:近藤嘉雪著,「定本Javaプログラマのためのアルゴリズムとデータ構造」,SBクリエイティブ,2011