読み書き・空間増幅(RUM 予想)のトレードオフ

RUM 予想とは何か

データベースのストレージ構造を選ぶとき、「どれが一番速いか」という問いには答えがありません。速さの種類が複数あり、それらは互いに引き合うからです。この引き合いを1枚の地図にまとめたのが **RUM 予想（RUM Conjecture）**です。2016 年に Athanassoulis らが提唱したもので、アクセス手法（access method）が払う基本オーバーヘッドを3つに分類します。

• R（Read overhead）: 求めるデータ1件を読むために、実際にアクセスする必要があるデータ量。論理1件の読み取りで何バイト・何ページ・何ファイルを触るか。
• U（Update overhead）: 論理的な1更新を反映するために、実際にストレージへ加える書き込み量と移動量。
• M（Memory／space overhead）: 元データに対して構造が消費する追加の空間。インデックス・冗長コピー・古い版・予約された空きなど。

RUM 予想の主張は次の一文に集約されます。「R・U・M の3つすべてを同時に最小化するアクセス手法は作れない。一つを良くすると、残りの少なくとも一つが悪化する。」三角形の3頂点に R・U・M を置き、どの構造もこの三角形の内側の1点に対応すると考えるのが、この枠組みの肝です。

なぜ三すくみになるのか（原理）

3つが独立に動かない理由は、読み取りを速くする仕掛けは必ず空間か更新コストで買うという物理にあります。

1. 読み取りを速くしたい（R を下げる） なら、目的データへ最短で到達できる索引・整列・冗長コピーを増やす。これは追加の空間（M を上げる）を要し、その索引や整列をデータ更新のたびに維持する手間（U を上げる）も生む。
2. 更新を速くしたい（U を下げる） なら、更新を「その場で書き換える」のをやめ、末尾に追記して後で整理する。すると同じキーの版が複数残り、空間が膨らみ（M を上げる）、読むときに版を横断する必要が出る（R を上げる）。
3. 空間を切り詰めたい（M を下げる） なら、冗長な索引や古い版を持たず、データを高密度に詰める。すると目的データの絞り込みに使える手掛かりが減って読み取りが重くなり（R を上げる）、高密度ゆえに更新時の再配置コストも増える（U を上げる）。

つまり「速い読み取りには手掛かり（=空間か更新作業）が要る」「追記で更新を軽くすると掃除の借金が空間と読み取りに回る」という、保存則のような構造が背景にあります。

三角形の頂点に近い極端な構造

各頂点を極端に追い求めた理論上の構造を見ると、トレードオフが直感的になります。

現実のエンジンは、この3頂点のどれか1つに振り切らず、三角形の内部のどこかへ意図的に配置されています。設計とは、どの頂点を犠牲にするかの選択です。

実在のストレージ構造を地図に置く

代表的な構造が RUM 三角形のどこに位置するかを整理します。点読み取り（単一キー検索）の挙動を基準にしています。

B+Tree と LSM-Tree は三角形のほぼ対角に位置するのが要点です。B+Tree は読み取りを根から葉への1経路に固定して R を小さく保つ代わりに、更新を in-place で行うため U を払います。LSM-Tree は更新を追記に変えて U を均す代わりに、版が複数ファイルへ散らばって R が増え、古い版とトゥームストーンが残って M が膨らみます。この対比は B+Tree の内部構造を更新方式の側から見直すと一段はっきりします。

設計レバーは「犠牲にする頂点を選ぶ手段」

RUM の価値は、最適化テクニックを「どの頂点の借金を、どの頂点へ付け替えるか」として読み解けることにあります。

• ブルームフィルタ: わずかな空間（M を少し上げる）を払って、存在しないキーへの無駄なファイル読み取りを排除し R を下げる。M↑ で R↓ という付け替え。詳しくはブルームフィルタ。
• フェンスポインタ／スパース索引: ソート済みファイルにキーとオフセットの粗い対応表を持たせ（M を少し上げ）、目的位置へ直接ジャンプして R を下げる。
• コンパクション戦略: LSM のコンパクション戦略は、まさに R・U・M のどこへ重みを置くかのダイヤルそのものです。Leveled は統合を頻繁に行って R と M を抑える代わりに U（書き込み増幅）を払い、Size-Tiered は統合を遅らせて U を抑える代わりに R・M を払います。
• 負荷率（load factor）チューニング: ハッシュ索引で空きを多く確保すれば衝突が減って R↓・U↓ になるが、その分 M↑。空間を読み書きへ両替している。

これらに共通するのは、RUM 三角形の外側へは出られないという前提です。どのレバーも、ある頂点のコストを別の頂点へ移すだけで、3頂点の合計的な「楽さ」を一方的に増やすことはできません。

# B+Tree 系: その場で消す（U を払い、M・R は増やさない）
delete(K):
  leaf = traverse_from_root(K)   # R 相当のコスト
  remove_entry(leaf, K)          # ページ書き戻し = U
  if underflow(leaf): merge_or_rebalance(leaf)  # 追加の U

# LSM 系: 消さずにトゥームストーンを追記（U を軽くし、M・R へ付け替え）
delete(K):
  append(memtable, tombstone(K))  # 1 追記 = 小さな U
  # 実体の K はまだ古い SSTable に残る   → M が増える
  # 読むときトゥームストーンに当たるまで横断 → R が増える
  # 借金はコンパクション時にまとめて返済される（その時 U を払う）

RUM をどう使うか（限界も含めて）

RUM は厳密な数学的定理ではなく **予想（conjecture）**です。任意の構造の R・U・M に普遍的な下限を与える証明ではなく、「3つを同時に底まで下げる手法は知られておらず、設計上ほぼ常にトレードオフが現れる」という強い経験則として使うのが正しい姿勢です。実務では次のように働かせます。

1. ワークロードの偏りを R/U/M のどれが支配するかへ翻訳する。 読み取り主体の OLTP なら R を守る（B+Tree 寄り）、書き込み洪水なら U を守る（LSM 寄り）、コスト最優先のアーカイブなら M を守る、という対応づけ。
2. 「速くする」提案を必ず付け替えとして疑う。 ある索引を足して読み取りを速くする話には、必ず U と M の請求書が付いています。請求先を確認しないチューニングは別の頂点を悪化させます。
3. ハイブリッドは三角形の内部移動。 多くの現代エンジンは LSM に B+Tree 的な索引やキャッシュを足すなどして三角形の中心寄りに置きますが、これは魔法ではなく中庸を選んだという宣言です。

まとめ