C++プログラマへの道 #14

このブログ記事では、C++におけるB(+)木について紹介します。

B木

前回の記事では、RBTについて説明しました。RBTはBSTのバランスを保ち、その高さに応じて時間計算量が $log_2(n)$ でスケーリングします。しかし、そもそも各ノードに1つのキーと2つの子ノードしか持てないようにする必要はあるでしょうか。デック（deque）のように、連続したメモリ領域に複数のキーを格納し、断片化したメモリを活用することもできるはずです。また、2つ以上の子ノードを持つことで、木の高さを低く抑え、探索時間を短縮することができます。B木は、このような木を操作中に自動的にバランスをとるメカニズムで実装する試みです。

B木の各ノードは、昇順に並んだキーをn個持ち、さらにその範囲に対応するn+1個の子ノードを持ちます。以下は、キー数の上限が4で、キーの最小数が2に設定されたB木の例です。ルートノードは特別なケースで、最小数より少ないキーを持つことが許されます。要素を検索するときには、まずルートノードのキーを調べます。各比較によって、ノード内のキーが見つかるか、または次の探索範囲が特定されます。このプロセスはキーが見つかるまで繰り返され、時間計算量は $O(log(n))$ (または $O(log_5(n))$ )となります。

class BTreeNode {
public:
    int *keys;
    int minimum;
    BTreeNode **children;
    int n;
    bool isLeaf;
 
    BTreeNode(int minimum, bool isLeaf): maximum(minimum), isLeaf(isLeaf) {
        // Allocate memory
        keys = new int[2 * minimum - 1];
        children = new BTreeNode *[2 * minimum];
        n = 0;
    };
 
    ~BTreeNode() {
        // Delete child nodes recursively
        if (!isLeaf) {
            for (int i = 0; i <= n; ++i) {
                delete children[i];
            }
        }
        delete[] keys;
        delete[] children;
    };
 
    // Search within node
    BTreeNode* search(int k) {
        // Find the first key greater than or equal to k
        int i = 0;
        while (i < n && k > keys[i]) {
            i++;
        }
 
        // If the found key is equal to k, return this node
        if (i < n && keys[i] == k) {
            return this;
        }
 
        // If the key is not found here and this is a leaf node
        if (isLeaf) {
            return nullptr;
        }
 
        // Go to the appropriate child
        return children[i]->search(k);
    };
};
 
class BTree {
public:
    BTreeNode *root;
    int minimum;
 
    BTree(int minimum): minimum(minimum) {
        root = nullptr;
    };
 
    ~BTree() {
        delete root;
    };
 
    // Function to search a key in this tree
    BTreeNode* search(int k) {
        return (root == nullptr) ? nullptr : root->search(k);
    };
};

上は、int型のデータを扱うB木の実装です。各ノードは、キーのリスト、子ノードへのポインタリスト、子ノードの最小数、現在のキー数、そしてそのノードが葉であるかどうかのフラグを持ちます。検索関数はノード内で実装されており、ノード内のキーを検索するか、探索を継続する適切な子ノードを特定します。木の検索関数は、指定されたキーを見つけるためにルートノードの検索関数を呼び出します。

挿入

B木での挿入は、木のバランスを保つために慎重に行う必要があります。ルートに要素を挿入する場合、キーが最大数に達するまでは単純にソート順にノードに追加していきます。もし満杯のルートノードに新しいキーを挿入する必要がある場合、そのノードを半分に分割し、B木で許される最小数のキーを持つ左右の子ノードを作成します。このノードは既にソートされているため、この処理はB木のルールを侵すことなく行えます。

キーは常に適切なリーフノードに格納され、満杯ノードを中央で分割するこの仕組みは、他のノードにも適用できます。親ノードに新たなキーを挿入するスペースがある場合、中央のキーを親に追加し、そのキーによって生成された範囲を代表するようにノードを2つの子ノードに分割します。このアルゴリズムは再帰的に適用可能であり、B木のバランスを保つことができます。

void BTreeNode::splitChild(int i, BTreeNode *child) {
    // Making sibling
    BTreeNode *sibling = new BTreeNode(child->minimum, child->isLeaf);
    sibling->n = minimum - 1;
 
    // Transfering keys from child to sibling
    for (int j = 0; j < minimum - 1; j++) {
        sibling->keys[j] = child->keys[j + minimum];
    }
 
    // Transfering children from child to sibling
    if (!child->isLeaf) {
        for (int j = 0; j < minimum; j++) {
            sibling->children[j] = child->children[j + minimum];
        }
    }
 
    child->n = minimum - 1;
 
    // Making room for new child, sibling
    for (int j = n; j >= i + 1; j--) {
        children[j + 1] = children[j];
    }
 
    children[i + 1] = sibling;
 
    // making room for new key from child
    for (int j = n - 1; j >= i; j--) {
        keys[j + 1] = keys[j];
    }
 
    keys[i] = child->keys[minimum - 1];
    n = n + 1;
};
 
void BTreeNode::insertNonFull(int k) {
    int i = n - 1;  // Initialize index of rightmost element
 
    if (isLeaf) {
        // Insert the new key into this leaf node
        while (i >= 0 && keys[i] > k) {
            keys[i + 1] = keys[i];
            i--;
        }
        keys[i + 1] = k;
        n = n + 1;
    } else {
        // Find the child that will have the new key
        while (i >= 0 && keys[i] > k) {
            i--;
        }
 
        // Check if the found child is full
        if (children[i + 1]->n == 2 * minimum - 1) {
            splitChild(i + 1, children[i + 1]);
 
            if (keys[i + 1] < k) {
                i++;
            }
        }
        children[i + 1]->insertNonFull(k);
    }
};
 
int BTree::insert(int k) {
    if (root == nullptr) {
        root = new BTreeNode(minimum, true);
        root->keys[0] = k;
        root->n = 1;
        return 1;
    }
    
    if (root->n == 2 * minimum - 1) {
        BTreeNode *newRoot = new BTreeNode(minimum, false);
        newRoot->children[0] = root;
        newRoot->splitChild(0, root);
 
        int i = 0;
        if (newRoot->keys[0] < k) {
            i++;
        }
        newRoot->children[i]->insertNonFull(k);
 
        root = newRoot;
        return 1;
    }
 
    root->insertNonFull(k);
    return 1;
};

上記のコードは、B木ノードとB木の挿入の実装を示しています。splitChild関数は、分割されて兄弟ノードに転送されたキーを削除する必要はありません。右に新しい兄弟が常に作成されるため、nを調整することで、その後のキーを木が無視するようにしています。insertNonFull関数は、必要に応じてsplitChildを呼び出して非満杯ノードへのキーの挿入を再帰的に行います。insert関数は、splitChildとinsertNonFullの両方を使用して挿入を実行し、ルートノードが満杯の場合には新しいルートノードを作成する特別なケースを処理します。このアルゴリズムでは木の各レベルを一度だけ通過し、各レベルでの操作は格納されているキーの数に依存しないため、挿入の時間計算量は $O(\log(n))$ となります。

削除

B木からキーを削除するのは、木をたどりながらキーを見つけてノードから削除するだけで、ルールに違反しない場合もあります。しかし、削除はさまざまな違反を引き起こす可能性があります。最初のケースは、削除対象のリーフノードが既に最小数のキーしか持っていない場合です。この場合、右または左の兄弟から右端または左端のキーを取得し、それを親ノードのセパレーターと置き換え、削除が行われたノードにセパレーターを配置することができます。この置換により、最小キー数違反を修正しつつB木の特性が保持されます。

しかし、上記の解決策は兄弟ノードが最小キー数以上のキーを持っている場合に限られます。2つ目のケースは、兄弟ノードも最小キー数しか持っていない場合です。この場合、削除対象のノードとその兄弟、そしてそれらの間の親セパレーターを1つの子ノードとして統合することで対応できます。親ノードがこれにより最小キー数を下回る場合でも、兄弟から借りるか、再帰的にノードを統合することで違反を解消できます。

中間ノードからの削除も別の問題を引き起こし、子ノードのセパレーターを削除することになります。この違反を修正するために、子ノードから右端または左端のキーを借り、それを新しいセパレーターとして設定する必要があります。借用による最小キー数違反が発生する場合には、先述の兄弟からの借用や統合の方法で修正できます。残念ながら、削除のコード実装はこの記事の範囲外です。実装を試みたい方へのヒントとして、BTreeNodeクラス内にborrowやmergeのようなメンバー関数を追加し、実装を簡単にすることをお勧めします。挿入と同様に、このアルゴリズムは木の各レベルを一度だけ通過し、各レベルでの操作は格納されているキーの数に依存しないため、削除の時間計算量も $O(\log(n))$ となります。

B+木

B木はデータベースを含む多くのシナリオで非常に効果的に機能しますが、範囲ベースのクエリには制約があります。データベースをクエリする際には、一度に複数のキーを取得する必要があることが多々あります。例えば、このブログで1ページあたり10件の記事をクエリする際に、ノード内のキーの最大数が4である場合、親ノードや祖父母ノード、リーフノード間を行き来するのはコストがかかります。

この問題を解決するために、B+木では親ノード内のすべてのキーをリーフノードに複製し、各リーフノードに隣接するノードへのポインタを追加してリンクリストを作成します。これにより、 10件の記事をクエリする際には、リーフノードのリンクリストを通過するだけで済むため、範囲ベースのクエリにおいて非常に効率的に値を取得できます。範囲が広がるにつれて、クエリがよりスムーズになることで、重複や追加のポインタを導入するコスト以上のメリットが得られるようになります。

データベースインデックス

B+木はデータベースにおけるもう一つのメリット、インデックスを用いたクエリの高速化を提供します。インデックスでは、各レコードにポインタを添付し、クエリ時にすべてのレコードを個別に調査しなくても済むようにします。 B木の場合、木内のすべてのレベルにレコードへのポインタが含まれます。データベースが小さくメモリに収まる場合には問題ありませんが、一部のノードがアクセス速度が遅いストレージに移動するにつれて、クエリで予測不可能な遅延が発生する可能性があります。範囲ベースのクエリが行われる場合、この問題が顕著になります。

しかし、B+木では、すべての中間ノードは検索のためだけに存在し、レコードへのポインタは持たず、リーフノードにのみポインタが含まれます。この構成により中間ノードが非常に軽量（通常データ全体のわずか1%）になり、メモリに収まる可能性が高くなります。その結果、データベースがスケールするにつれてクエリの遅延が低くなるため、 B+ 木はデータベースに適したデータ構造とされます。

結論

本記事では、B木がキャッシュヒット率を上げ、木の高さと計算時間を削減する方法について解説しました。 B木は、挿入や削除のたびにポインタを更新したり木の再構成を行う必要がないため、特にデータベースやファイルシステムといったさまざまなアプリケーションで人気のあるキー構造です。また、B+木と、データベースインデックスとして好まれる理由についても説明しました。挑戦として、B木を使用して C++ で連想コンテナを実装してみるのも良いでしょう。

リソース

Nasser, H. 2021. B-tree vs B+ tree in Database Systems. YouTube.
Spanning Tree. 2024. Understanding B-Trees: The key Structure Behind Modern Databases. YouTube.