定義
リストやツリーで項目の順序を頻繁に変えるのに、複数人が同時に編集しても順序が壊れないようにしたいときに使う方式だ。項目ごとに整数番号(0,1,2…)ではなくソートされる文字列キーを付け、「B の次に入れて」のように隣を基準に挿入する。
正確には、Fractional indexing(分数索引)はコレクションの項目ごとに lexicographic sort(文字列を辞書順で比較)可能な文字列キー(position と呼ぶ)を付与し、挿入・移動の意図を「index n 番目」ではなく**隣の anchor id(after/before — どの項目の前/後に入れるか指す基準点)**で表現する順序モデルだ。中間挿入時に既存項目のキーを変えず、二つのキーの間に新しいキーだけを生成する。
なぜ必要か
整数 index で順序を付けるとこんな問題が生じる。(1) 中間に一つ挿入するたびに後ろの項目番号を全部付け直す必要があり(renumber)、(2) 二人が同時に「同じ 3 番の位置に挿入」すると衝突し、(3) すでに消された項目を基準にした遅れた編集(stale patch — 古くて有効でない変更要求)が失敗する。
協業 todo リスト・文書ブロックの兄弟順序・カンバンカードのように、順序変更が頻繁で複数クライアントが同時(concurrent)に触れるデータは、整数の代わりに fractional key + 「隣基準」の意図 + tie-break(同点処理ルール)でこの三つの問題を避ける選択を実務でよくする。
動作原理
- 保存層: 各 sibling に
position: string(例"a0","a0V")。 - 意図層: patch
{ after: "block-a", block: newBlock }。 - ソート:
compare(position)lexicographic; 同率なら(clientId, opId)tie-break。 - 挿入:
generateKeyBetween(prev, next)— 二つの key の間の文字列を生成。 - Rebalance: key の長さが大きくなったら、同じ順序を保ったまま短い key で再割り当てする。
| 問題 | integer index | fractional + anchor |
|---|---|---|
| 中間 insert | O(n) renumber | O(1) new key |
| concurrent insert | index collision | tie-break |
| stale anchor | throw | fallback chain / tail |
実務適用
Subtree を別の parent へ promote/move するとき nested position をそのまま reuse すると新しい sibling set で sort が壊れうる — 新しい bounds の間に position を再割り当てする必要がある。offline replay で anchor が削除されていれば fallbackAfter[] chain で代替 anchor を探すか tail append する。
トレードオフ
- key 文字列の長さが時間とともに増加する → 定期的な rebalance が必要。
- human-readable な order number は保存しない — UI の ordinal は render time に derive。
- full CRDT より軽いが、server/client の merge ポリシー・tie-break 契約が必要。
使ってはいけない場合
- 順序がほとんど変わらず単一 writer の小さな設定配列 — integer index で十分。
- position key だけで anchor fallback なしに offline を許可する — stale patch 失敗率が急増する。
よくある間違い
- patch に index、storage に position を混用 — 意図と SoT の不一致。
- sort-on-read everywhere — 性能・一貫性の問題。
- promote 時に position reuse — sibling sort corruption。
- tie-break なしで position だけ — concurrent insert が非決定的。
関連概念
- optimistic-outbox-rebase — concurrent patch の収束
- inverted-index-full-text-search — 別種の「index」(検索)との混同に注意