C++によるB+ツリーの実装方法：挿入・分割・走査を徹底解説

B+ツリーは、1つのノードが2つ以上の子を持つことができる点で、二分探索木を一般化したデータ構造です。自己平衡化を行う木構造の一種であり、ソート済みのデータを保持しながら、対数時間（O(log n)）での逐次アクセス、検索、挿入、削除を可能にします。

B+ツリーは、各ノードがキーのみを保持するB木と捉えることもできます。さらに、最下層にリンクされた葉ノードからなるレベルを追加した構造になっています。この特徴により、範囲検索や順次アクセスが効率的に行えるため、データベースやファイルシステムで広く採用されています。

アルゴリズム

以下は、B+ツリーにノードを挿入する際の基本的な流れです。

Begin
    ノードを木に挿入する関数 insert()：
    x を根ノードとして初期化する。
    もし x が葉ノードで、かつ空きがある場合は、a を x に挿入する。
    そうでなく x が葉でない場合：
        次に辿るべき x の子を見つける。
        子が満杯でなければ、x をその子へ移動させる。
        子が満杯の場合は、それを分割し、x を子の2つの部分のいずれかに向ける。
        a が子の中央キーより小さければ第1部分を、大きければ第2部分を選択する。
End

サンプルコード

以下は、C++でB+ツリー（次数6）を実装した例です。ノードの生成、木の走査、子ノードの分割、要素の挿入といった一連の処理を含んでいます。

#include<iostream>
using namespace std;
struct BplusTree {
    int *d;
    BplusTree **child_ptr;
    bool l;   // 葉ノードかどうかを示すフラグ
    int n;    // 現在保持しているキーの数
}*r = NULL, *np = NULL, *x = NULL;

// ノードを生成する関数
BplusTree* init() {
    int i;
    np = new BplusTree;
    np->d = new int[6];          // 次数6
    np->child_ptr = new BplusTree *[7];
    np->l = true;
    np->n = 0;
    for (i = 0; i < 7; i++) {
        np->child_ptr[i] = NULL;
    }
    return np;
}

// 木を走査して全キーを表示する関数
void traverse(BplusTree *p) {
    cout<<endl;
    int i;
    for (i = 0; i < p->n; i++) {
        if (p->l == false) {
            traverse(p->child_ptr[i]);
        }
        cout << " " << p->d[i];
    }
    if (p->l == false) {
        traverse(p->child_ptr[i]);
    }
    cout<<endl;
}

// 配列を昇順にソートする関数
void sort(int *p, int n) {
    int i, j, t;
    for (i = 0; i < n; i++) {
        for (j = i; j <= n; j++) {
            if (p[i] >p[j]) {
                t = p[i];
                p[i] = p[j];
                p[j] = t;
            }
        }
    }
}

// 満杯の子ノードを分割する関数
int split_child(BplusTree *x, int i) {
    int j, mid;
    BplusTree *np1, *np3, *y;
    np3 = init();
    np3->l = true;
    if (i == -1) {
        mid = x->d[2];
        x->d[2] = 0;
        x->n--;
        np1 = init();
        np1->l = false;
        x->l = true;
        for (j = 3; j < 6; j++) {
            np3->d[j - 3] = x->d[j];
            np3->child_ptr[j - 3] = x->child_ptr[j];
            np3->n++;
            x->d[j] = 0;
            x->n--;
        }
        for (j = 0; j < 6; j++) {
            x->child_ptr[j] = NULL;
        }
        np1->d[0] = mid;
        np1->child_ptr[np1->n] = x;
        np1->child_ptr[np1->n + 1] = np3;
        np1->n++;
        r = np1;
    } else {
        y = x->child_ptr[i];
        mid = y->d[2];
        y->d[2] = 0;
        y->n--;
        for (j = 3; j <6 ; j++) {
            np3->d[j - 3] = y->d[j];
            np3->n++;
            y->d[j] = 0;
            y->n--;
        }
        x->child_ptr[i + 1] = y;
        x->child_ptr[i + 1] = np3;
    }
    return mid;
}

// 要素を挿入する関数
void insert(int a) {
    int i, t;
    x = r;
    if (x == NULL) {
        r = init();
        x = r;
    } else {
        if (x->l== true && x->n == 6) {
            t = split_child(x, -1);
            x = r;
            for (i = 0; i < (x->n); i++) {
                if ((a >x->d[i]) && (a < x->d[i + 1])) {
                    i++;
                    break;
                } else if (a < x->d[0]) {
                    break;
                } else {
                    continue;
                }
            }
            x = x->child_ptr[i];
        } else {
            while (x->l == false) {
                for (i = 0; i < (x->n); i++) {
                    if ((a >x->d[i]) && (a < x->d[i + 1])) {
                        i++;
                        break;
                    } else if (a < x->d[0]) {
                        break;
                    } else {
                        continue;
                    }
                }
                if ((x->child_ptr[i])->n == 6) {
                    t = split_child(x, i);
                    x->d[x->n] = t;
                    x->n++;
                    continue;
                } else {
                    x = x->child_ptr[i];
                }
            }
        }
    }
    x->d[x->n] = a;
    sort(x->d, x->n);
    x->n++;
}

int main() {
    int i, n, t;
    cout<<"挿入する要素の個数を入力してください\n";
    cin>>n;
    for(i = 0; i < n; i++) {
        cout<<"要素を入力してください\n";
        cin>>t;
        insert(t);
    }
    cout<<"構築されたB+ツリーの走査結果\n";
    traverse(r);
}

出力結果

enter the no of elements to be inserted
10
enter the element
10
enter the element
20
enter the element
30
enter the element
40
enter the element
50
enter the element
60
enter the element
70
enter the element
80
enter the element
90
enter the element
100
traversal of constructed B tree
10 20
30
40 50
60
70 80 90 100

解説

この実装では、各ノードが最大6個のキーを保持できる「次数6」のB+ツリーを構築しています。主なポイントは以下の通りです。

• init()： 新しいノードを生成し、キー配列・子ポインタ配列・葉フラグなどを初期化します。
• split_child()： ノードが満杯（キー6個）になったときに中央のキーを親に押し上げ、ノードを2つに分割します。根ノードが分割される場合は新しい根が作られます。
• insert()： 根から適切な葉ノードまで降りていき、途中で満杯のノードに遭遇したら分割を行いながら挿入位置を決定します。葉に到達したら値を追加しソートします。
• traverse()： 再帰的に木をたどり、すべてのキーを順番に出力します。

10個の要素（10〜100）を挿入した結果、木が適切に平衡化され、ソート済みの状態で走査できていることが確認できます。このようにB+ツリーは、大量のデータに対しても高速な検索・挿入・削除を実現できる強力なデータ構造です。