コラム: Key-Value ストアのデータ構造選択

mini_db は内部で std::map<std::string, std::string> を使っています。なぜハッシュマップ (std::unordered_map) ではないのか? どの選択がどんなトレードオフを伴うのか? を整理します。

1. 候補の比較

データ構造	平均 find	最悪 find	メモリ局所性	順序保持	C++98
std::map (赤黒木)	$O(\log N)$	$O(\log N)$	△ ノードごとに散る	◎ キー昇順	◎
std::unordered_map (ハッシュ)	$O(1)$	$O(N)$ (衝突悪化時)	○ バケット連続	✕	△ (C++11+)
自前ハッシュテーブル	$O(1)$	設計次第	設計次第	✕	◎
ソート済み配列 + 二分探索	$O(\log N)$	$O(\log N)$	◎ 連続メモリ	◎	◎

mini_db では std::map を選ぶ実用的な理由が複数あります。

2. mini_db で std::map を選ぶ理由

C++98 で素直に使える

ここでは C++98 で書く前提なので、std::unordered_map (C++11 以降) は使えません。-std=c++98 でビルドする限り、選択肢にすら載らない。

最悪計算量が安定している

std::map は $O(\log N)$ が 最悪 ケースでも保証されます。std::unordered_map は平均 $O(1)$ ですが、悪意あるキー (ハッシュ衝突を誘発する文字列) を投げ込まれた瞬間に $O(N)$ に劣化し、リンクリスト走査と化します。ネットワーク越しに任意の文字列を受け付ける mini_db では、この最悪値の方が重要です。

「順序を持つ」のは地味に効く

std::map はキー昇順で走査できます。save() の出力ファイルが 常に決定的な順序 で並ぶのは、

• diff を取りやすい (save 結果を diff で比較できる)
• バックアップ間の差分が見やすい
• テストが安定する (順序ハッシュへの依存が無い)

という地味で大きな恩恵があります。実際 test.sh でも <key> <value>\n の出現を素直に grep で確認できるのは、出力が安定しているからです。

規模感が小さい

mini_db のスコープでは、エントリ数はせいぜい数千〜数万。$\log_2 (10^5) \approx 17$ の比較で済む木の深さなので、ハッシュ表との実速差はほぼ計測不能です。

3. ハッシュ表に切り替えたくなる場面

高頻度の point lookup が支配的

レイテンシ要件が μs オーダー、書き込みより参照が圧倒的に多い、というワークロードならハッシュ表が有利です。Redis / Memcached がハッシュ表ベースなのはこれが理由。

キー数が極端に多い (10^7 以上)

赤黒木の比較回数 ($\log N$) はそのまま「キャッシュミスを伴うランダムアクセス回数」になります。100 万件を超えるあたりから、ハッシュ表のキャッシュ局所性差が効いてきます。

範囲スキャンが要らない

GET しかしないなら順序情報は無駄。std::map の木構造は捨てて、配列ベースのハッシュ表にする方がメモリも使いません。

逆に「キー範囲スキャン (SCAN A:* )」「ソート済み出力」が要るなら、ハッシュ表だと別途インデックスを持つことになり、結局ツリーが必要になります。

4. もし C++11 以降で書き直すなら

std::unordered_map<std::string, std::string> を使うとして、それでも気をつけるポイント:

カスタムハッシュ関数 : 攻撃者からの予測可能なハッシュ衝突攻撃を避けるため、文字列ハッシュにランダム seed を混ぜる (hash_random_seed を起動時に決める)。

reserve() で初期バケット数を指定 : 初期容量を見積もって reserve(N) するだけで、初期 rehash の連鎖を抑えられる。

max_load_factor : デフォルトは 1.0 が多いが、衝突を更に減らしたければ 0.5 などに下げる (メモリと引き換え)。

5. もう一段先: ストレージとの一体化

mini_db のメモリ常駐モデルでは「物理メモリより大きい」KVS は作れません。本気でやるなら:

• LevelDB / RocksDB — LSM-Tree。書き込みが大量に来るワークロードに強い。
• LMDB — メモリマップ型 B+ Tree。読み取りが速く、コードベースが小さい。
• SQLite — 万能。テーブル 1 個に (key TEXT PRIMARY KEY, value BLOB) を作るだけで KVS 化できる。

これらを使うと「永続化戦略」「索引」「クラッシュリカバリ」がまるごと組み込みになり、自前で書く部分は薄いラッパーで済みます。

まとめ

• C++98 縛り・最悪計算量保証・出力順序の安定性 — どれを取っても std::map が mini_db には素直。
• ハッシュ表は平均高速だが、ネットワーク経由の任意キーを受け付ける用途では最悪値の脆さが残る。
• データ規模・参照パターン・順序要件の 3 点で再評価し、必要なら std::unordered_map や既製品 (SQLite/LMDB) に乗り換える。