B+木をページに永続化する——ノードをバイト列にシリアライズしてPagerに載せる

B+木の挿入・検索・分割アルゴリズムをヒープ上のノードで実装し、Pagerによって4096バイト固定長のページを読み書きできるようになりました。今回はこの2つを組み合わせ、B+木のノードを実際にページへ永続化します。ここまでの実装が揃ったことで、プロセスを終了して再度起動してもキーが読み出せる、実際にディスクへ永続化されたキーバリューストアが動くようになりました。

ポインタからPageIdへ

オンメモリ版のB+木では、内部ノードは子をstd::unique_ptr<Node>で保持していました。永続化版では子はもうヒープ上のオブジェクトではなくページ上のバイト列なので、ポインタの代わりに**PageId**で子を指します。「木を降りる」という操作は「ポインタを辿る」から「Pager::read_pageでページを読み、その場でデシリアライズする」に変わります。

// src/btree.cpp（永続化版のNode）
struct BTree::Node {
    struct Leaf {
        std::vector<std::string> keys;
        std::vector<std::string> values;
    };

    struct Internal {
        std::vector<std::string> keys;
        std::vector<PageId> children;  // かつてはstd::unique_ptr<Node>だった
    };

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

この変更により、BTree自体はもう木をメモリ上に保持し続けません。バッファプール（キャッシュ）はまだ実装しない方針のため、insert/searchの呼び出しのたびにルートから必要なページだけをその場で読み直し、呼び出しが終わればヒープ上のNodeは破棄します。

メタページと固定長バイトレイアウト

ページ0は特別に「メタページ」として扱い、ルートページ番号や木の容量を記録します。マルチバイト整数はすべて、C++の構造体を直接memcpyするのではなく、リトルエンディアンで1フィールドずつ明示的に書き込みます。構造体のパディングやコンパイラ依存のレイアウトに頼らない、SQLiteのファイルフォーマット仕様などと同じ考え方です。

メタページ（PageId{0}固定）
offset   size  field
0        8     magic ("KVSTREE1")
8        4     format version (u32) = 1
16       8     root_page_id (u64)
24       8     min_degree (u64)
32       8     key_count (u64)

ノードページ（0以外の全ページ）
offset   size  field
0        1     node_type (u8): 0=leaf, 1=internal
8        4     key_count (u32)
16       ...   payload（キー・値・子ページ番号を長さ接頭辞付きで並べたもの）

// src/btree.cpp（書き込みヘルパー、抜粋）
void put_u64(std::span<std::byte> buf, std::size_t offset, std::uint64_t value) {
    for (std::size_t i = 0; i < 8; ++i) {
        buf[offset + i] = static_cast<std::byte>((value >> (8 * i)) & 0xFF);
    }
}

ノードのシリアライズは、常にノード全体をその場で作り直す方式にしました。既存ページの一部だけを差分更新する（SQLiteやPostgreSQLのような、オフセット配列で可変長セルを指す「スロット化ページ」）方式も検討しましたが、その方式の利点は「ページ全体を毎回デシリアライズせずに済む」点にあります。今回はどのみちinsert/searchのたびにページ全体をヒープのNodeへ読み込んでから操作しているため、その利点がまだ活きません。バッファプールを導入する段階で改めて検討する対象として見送りました。

ページサイズからmin_degreeを逆算する

オンメモリ版ではmin_degree（最大キー数2t-1を決める値）は自由なパラメータでしたが、永続化する以上、「1ノードが1ページに収まる」という制約から逆算する必要があります。リーフはキーと値の両方を持つため、内部ノードより明らかに大きくなります。キーの上限を64バイト、値の上限を256バイトという保守的な前提を置くと、1エントリあたり最大4(key_len) + 64 + 4(value_len) + 256 = 328バイトです。ヘッダー16バイトを引いた(4096 - 16) / 328 ≈ 12件が1ページに入るエントリ数の上限になるので、2t - 1 <= 12からmin_degree = 6をデフォルト値としました。同じキー数の内部ノードは16 + 11*(4+64) + 12*8 = 860バイトほどで、明らかにリーフの方がボトルネックです。実際のエンジンの多くも、値を持つリーフの方が容量の制約になります。

ただしこれはあくまで前提であって強制ではありません。想定を超えて大きな値を挿入した場合は、シリアライズ時にページサイズを超えないかその場でチェックし、超えていればBTreeError::node_too_largeを返すようにしています。

// src/btree.cpp（抜粋）
auto put_bytes = [&](const std::string& s) {
    if (offset + 4 + s.size() > Page::kSize) {
        return false;
    }
    put_u32(buf, offset, static_cast<std::uint32_t>(s.size()));
    offset += 4;
    std::memcpy(buf.data() + offset, s.data(), s.size());
    offset += s.size();
    return true;
};
// ... put_bytesがfalseを返したら node_too_large

書き込みの順序と、今回あえて対処しなかったこと

ノード分割時は「新しく確保した右ノードを書く→（分割で縮んだ）元のノードを書く→親を更新する→メタページのルート番号を最後に進める」という順序を守っています。これにより、途中でクラッシュしても「まだどこからも参照されていない新規ページ」がゴミとして残るだけで、メタページが指すルートは常にクラッシュ前の有効な状態を指し続けます。

ただしこれは万能ではありません。既存のページを上書きする変更（分割を伴わない挿入）についてはこの限りではなく、書き込み途中のクラッシュはそのページを破損させ得ます。BoltDBのように既存ページも含めて毎回新しいページへ書き直すコピーオンライトを採用すれば解決しますが、それは実質的にクラッシュリカバリの設計を先取りすることになるため、今回は見送りました。WAL（Write-Ahead Log）によるクラッシュリカバリは、次のセグメントで正面から扱う予定です。

備考：deleteされたコピーコンストラクタが暗黙のムーブも道連れにする

BTreeはPager（ムーブのみ許可）を値として持つため、コピー禁止・ムーブ許可にする必要があります。最初、次のように書きました。

BTree(const BTree&) = delete;
BTree& operator=(const BTree&) = delete;
// ムーブは書かない。Pagerのムーブが正しいのでコンパイラ生成に任せればよいはず

ところがこれはビルドエラーになりました。BTree::open()の中でreturn tree;のようにstd::expected<BTree, BTreeError>へBTreeを戻そうとすると、「BTreeから変換できない」というエラーになります。

原因はC++の特殊メンバ関数の生成規則にありました。コピーコンストラクタを= deleteであってもユーザー宣言すると、それだけで暗黙のムーブコンストラクタ・ムーブ代入演算子の生成が抑制されます。ムーブが存在しないクラスは、return tree;のような場面でコピーへフォールバックしようとし、そのコピーコンストラクタがdeleteされているためエラーになる、という流れです。「delete宣言もユーザー宣言の一種」という規則は知識として知っていても、実際にビルドが壊れて初めて体で理解できた落とし穴でした。対処は単純で、ムーブコンストラクタ/代入演算子を明示的に= defaultしておくだけです。

BTree(BTree&&) noexcept = default;
BTree& operator=(BTree&&) noexcept = default;
BTree(const BTree&) = delete;
BTree& operator=(const BTree&) = delete;

テストと動作確認

tests/btree_test.cppでは、オンメモリ版から引き継いだテスト（往復・アップサート・分割・挿入順序への非依存性）に加え、永続化ならではのケースを追加しました。木を構築したBTreeをスコープの外に出して破棄し、同じパスを再度openし直してすべてのキーとサイズが復元されることを確認するテスト、ページ0の先頭バイトを不正な値にしたファイルをopenするとinvalid_meta_pageになることを確認するテスト、そして1ページに収まりきらない巨大な値を挿入するとnode_too_largeが返り、直前まで格納していたデータには影響がないことを確認するテストです。

AddressSanitizer/UndefinedBehaviorSanitizerを有効にしたビルドでも全テストを実行し、手書きのバイトシリアライズ・デシリアライズ処理に境界外アクセスや未定義動作がないことを確認しています。

参考リンク

SQLite File Format —— 構造体のmemcpyではなく明示的なバイトオフセット表としてファイル形式を定義する実例です
BoltDB (bbolt) source —— ページ単位のB+木とコピーオンライトの実装を参照する際のリファレンスです