std::variantでB+木のノードを表現し、分割アルゴリズムを実装する

Pagerによってファイルを固定長ページの並びとして扱えるようになったので、次はそのページに乗せるB-treeの本体を実装します。ただしページとの対応付けは次の段階に回し、今回はまずヒープ上のノードだけで完結する、B-treeのアルゴリズム部分——挿入・検索・ノード分割——を実装しました。

JavaのTreeMapは赤黒木、つまり二分木で高さはO(log2 n)です。B-treeはこれを一般化し、1ノードが多数のキーと多数の子を持つ「幅が広く浅い木」にします。永続化後（後続の記事で扱います）は1ノード=1ページ=1回のディスク読み取りになるため、木の高さを最小化することが読み取り回数の最小化に直結します。LMDBやBoltDBと同様、本プロジェクトでも値をリーフにだけ持つB+木を採用しました。内部ノードが値を持たない分小さく保てるため、1ページあたりの子ノード数（fan-out）を稼ぎやすくなります。

std::variantによるノード表現

// src/btree.cpp（BTreeのprivateなネスト型）
struct BTree::Node {
    struct Leaf {
        std::vector<std::string> keys;
        std::vector<std::string> values; // values[i] corresponds to keys[i]
    };

    struct Internal {
        std::vector<std::string> keys; // separator keys; size == children.size() - 1
        std::vector<std::unique_ptr<Node>> children;
    };

    std::variant<Leaf, Internal> body;
};

リーフか内部ノードかを表現する方法として、仮想関数を持つ基底クラス+派生クラスの構成、あるいはis_leafという真偽値フラグ+複数の並行配列という構成も検討しましたが、std::variantを選びました。std::get_if/std::visitによって「両方のケースを網羅していないとコンパイルが通らない」形でアクセスできる上、ノードごとの仮想関数テーブルを持つ必要もありません。

内部ノードの不変条件は「keys[i]はchildren[i+1]から辿れる最小のキー」です。B+木では値をリーフだけが持つため、内部ノードの分離キーと完全一致するキーはリーフ側にも重複して存在します（後述の分割アルゴリズムで生まれる差分です）。

min_degree（CLRSの「最小次数」）

ノードの容量を表す用語には「order」がよく使われますが、文献や実装によって「最大の子の数」を指すこともあれば「最大のキー数」を指すこともあり、定義がまちまちです。そこで本実装では、CLRS（『アルゴリズムイントロダクション』）の**最小次数（minimum degree）t**を採用しました。「ルート以外のノードはt-1個以上2t-1個以下のキーを持つ」という一意な定義です。

// include/kvstore/btree.hpp（抜粋）
class BTree {
public:
    static constexpr std::size_t kDefaultMinDegree = 128;

    explicit BTree(std::size_t min_degree = kDefaultMinDegree);
    ...
    void insert(std::string key, std::string value);
    [[nodiscard]] std::expected<std::string, BTreeError> search(const std::string& key) const;
    [[nodiscard]] std::size_t size() const noexcept;
};

min_degreeをコンストラクタ引数にしたのは、テストで木を簡単に多段化するためです。デフォルトの128だと分割を起こすだけで数百件の挿入が要りますが、min_degree = 2（最大キー数3）にすればほんの数件の挿入でリーフ分割・ルート分割まで再現できます。

挿入とノード分割：CLRS方式ではなく「実務エンジン方式」を採用

B-treeの挿入でノードが溢れた（オーバーフローした）ときの対処には、大きく2つの流儀があります。

  • CLRSの先行分割方式：ルートから子へ降りていく途中、満杯のノードに出会うたびに先んじて分割してから先に進む。上向きの後処理が要らず単純ですが、実際には不要な分割まで起こしてしまうことがあります。
  • 実務エンジン方式（今回採用）：まず挿入してしまい、オーバーフローしたノードだけを後から分割し、分離キーを親へ伝播させる。LMDBやBoltDBなどの実装はこちらです。

擬似コードで書くと、挿入処理insert_intoの骨子は次のようになります（実際にはC++の戻り値はstd::optional<SplitResult>で表現しています）。

insert_into(node, key, value):
    if node is Leaf:
        位置を二分探索で見つけ、既存キーなら上書き（アップサート）、
        なければ挿入。
        オーバーフロー（2t件を超えた）なら split_leaf() の結果を返す。
    else:
        子を選んで再帰的にinsert_intoを呼ぶ。
        子が分割されていたら、その分離キー/右ノードを自分に挿入し、
        自分自身がオーバーフローしたらsplit_internal()の結果を返す。

リーフの分割と内部ノードの分割には明確な違いがあります。リーフの分割では、右半分の先頭キーを分離キーとして親に持ち上げますが、そのキー自体は右リーフにもそのまま残ります（値を持つのはリーフだけなので、実体を消してはいけません）。一方内部ノードの分割では、中央のキーは親に持ち上げた後、両側から完全に取り除かれます——値を伴わない、単なる道しるべだからです。この非対称性こそが「B-treeとB+木の分割の違い」そのもので、実装して初めて腑に落ちる部分でした。

木全体がオーバーフローした場合（ルート自身が分割された場合）は、新しいルートを1つ作り、古いルートと新しい右ノードをその子にします。これによって木は1段高くなります。削除を扱わない今回のスコープでは、オーバーフロー（上限超過）だけを見ればよく、CLRSが要求するような「下限を下回らないか」のチェックは一切不要でした。

備考：匿名名前空間の自由関数からprivateなネスト型にアクセスできない

分割ロジックをstd::variantの中身を直接触る自由関数として匿名名前空間に書いたところ、コンパイルエラーになりました。

error: 'struct kvstore::BTree::Node' is private within this context

NodeはBTreeのprivateなネスト型で、Node自体を.cppファイル内で定義すること自体は許されるものの（前方宣言済みのメンバを完成させているだけなので）、BTreeのメンバでもfriendでもない自由関数からその型名を名指しすることはアクセス制御違反になります。対処として、分割ロジックと再帰挿入処理をBTreeのprivate staticメンバ関数に変更しました。BTree自身のメンバであれば、ネスト型Nodeとその内部のLeaf/Internal（Node内ではpublic）に自然にアクセスできます。「privateなネスト型を扱うヘルパーは、自由関数ではなくその型を所有するクラスのメンバにする」という、C++のアクセス制御を意識していないと踏みがちな落とし穴でした。

テスト

tests/btree_test.cppでは、空の木への検索・単純な往復・アップサート、そしてmin_degree = 2という小さい値を使ったリーフ分割・複数段にわたる分割（ルート分割を含む）、さらに挿入順序への非依存性を確認するため昇順・降順の両方で数十件を挿入するテストを書いています。min_degreeを小さくできる設計にしたことで、大量データを用意しなくても木の分割・多段化を確定的に再現できました。

参考リンク