フラクショナルカスケーディングと分数インデックス

何を解こうとしているのか

リストの並びをデータベースに保存する素朴な方法は、各行に整数の position（0,1,2,…）を持たせることです。しかしこの方式は、ある要素を 1 番と 2 番の あいだ に入れたいだけで破綻します。整数 1 と 2 の間には整数がないため、後続の要素すべての番号を振り直す（リナンバリング）か、行をロックして再計算するしかありません。1 件の挿入が O(n) 件の更新を生み、協調編集のように複数クライアントが同時に並べ替える環境では、その一括更新どうしが衝突します。

分数インデックス（fractional indexing） は、順序キーを整数ではなく 稠密な順序集合 の値として持つことでこれを解きます。稠密とは「異なる任意の2要素 a と b（a が b 未満）の間に、必ず別の要素が存在する」性質です。有理数や実数はこの性質を持つので、1 と 2 の間には 1.5、その間には 1.25…と無限に値が取れます。要素を間に挿入したいなら、両隣のキーの中間を1つ計算して新しいキーにするだけでよく、他の行には一切触れません。挿入は O(1) の書き込みになります。

なぜ整数ではなく文字列なのか

理屈の上では有理数をそのまま使えますが、実装では問題が起きます。中間を取り続けると分母が指数的に増え、浮動小数点では精度が枯渇し、可変長整数では比較コストが膨らみます。そこで実用実装は 基数 b の桁列（文字列） でキーを表し、辞書順（lexicographic）比較がそのまま順序比較になる ように設計します。これなら任意精度を桁の追加だけで確保でき、データベースの文字列インデックス（B+Tree など）にそのまま載せて高速に範囲検索・整列できます。

要点は2つです。第一に、キーを「0.（桁列）」という基数 b の小数とみなすこと。第二に、辞書順と数値順を一致させる桁揃え を守ることです。たとえば基数 10 で 5 と 25 を辞書順で比べると、先頭の 2 が 5 より小さいので 25 が前になり、これは小数 0.5 と 0.25 の数値順（0.25 が前）と一致します。つまり「小数点以下の桁列」として左詰めで比較する限り、辞書順 = 数値順が成り立ちます。実装では基数を大きく取り（base64 など）、文字集合自体を昇順に並べておけば、文字どうしのバイト比較が桁の大小比較に一致します。

中間キーの生成アルゴリズム

中心となるのは「a と b の厳密な中間にある最短の桁列を返す」関数 midpoint(a, b) です。a が b 未満であることを前提に、両端を基数 b の小数として桁ごとに比較していきます。

midpoint(a, b):   # a, b は小数点以下の桁列、a < b（辞書順）
  i = 0
  # 共通する先頭桁はそのままコピーする
  while a[i] == b[i]:        # b 側が尽きたら b は無限に 0 が続くとみなす
    append a[i] to result
    i++
  # 食い違う最初の桁を見る
  da = digit(a, i)           # a が尽きたら 0
  db = digit(b, i)
  if db - da >= 2:
    # 桁の間に隙間があるので、その中央の1桁で確定
    append floor((da + db) / 2) to result
    return result
  else:
    # 隣接桁（差が1）。a 側の桁を採用し、a の続きと最大桁の中間へ降りる
    append da to result
    return result + midpoint(rest_of(a, i+1), "")  # b 側は最大桁の上限とみなす

ポイントは食い違った桁の差です。差が 2 以上なら、その2桁の 中央の1桁 を置くだけで a より大きく b より小さい値が確定し、桁を伸ばさずに済みます。差が 1 しかない（隣接している）ときは、その桁では間に入れないので a 側の桁を採り、1桁深く降りて さらに中間を探します。再帰の各段で必ず探索範囲が a 寄りに狭まり、いずれ差 2 以上の隙間か桁の尽きに到達して停止します。生成されるキーは平均してごく短く、最悪でも入力キー長 + 数桁に収まります。

協調編集での全順序化

単独クライアントなら midpoint だけで足りますが、同時挿入 が入ると話が変わります。2 つのクライアントが同じ隙間（同じ a と b の間）にそれぞれ要素を入れると、両者が まったく同じ中間キー を計算してしまい、キーが衝突します。順序キーは要素を一意に整列させる責務を負うので、衝突は順序の不定（どちらが先か決まらない）を招きます。

解決は、分数キーの 末尾に一意なサイトID（クライアントIDやアクター識別子）を連結 して全順序（total order）にすることです。比較は「分数部を先に比べ、等しければサイトIDで決定的に破る」。これにより同一隙間への並行挿入でも、全レプリカが同じ規則で同じ順序に収束します。これは CRDT のリスト型（RGA や LSEQ 系）が内部で用いるのと同じ発想で、分数インデックスは「位置を表す不変な識別子」をキー1本で表現する軽量な実装手段になります。

実装上の落とし穴

分数インデックスは挿入が局所的で速い反面、キー長が単調に伸びうる 弱点があります。最悪のパターンは「常に同じ要素の直後（または直前）に挿入し続ける」ケースで、毎回 1 桁ずつ深く降りるため、キー長が挿入回数に比例して伸びます。長くなったキーは索引の肥大とソートコスト増を招くため、実務では一定長を超えたら オフピークにバックグラウンドで全キーをリバランス（振り直し） する運用を併用します。

まとめ