Fractional indexing

データに任意の順序を持たせるためのアルゴリズムのひとつ

データを並び替えたいときに単一のレコードを更新するだけですませることができる

OTの代わりに、Figmaはデータベース上で再配置を実装するために頻繁に使用されるテクニックを採用しています。各オブジェクトには実数としてのインデックスが割り当てられ、ツリー内の要素の子要素の順序は、すべての子要素をインデックスで並べ替えることで決定されます。2つのオブジェクトの間に挿入するには、新しいオブジェクトのインデックスを、両側のオブジェクトのインデックスの平均値に設定するだけです。64ビット浮動小数点数ではなく任意精度分数を使用することで、多数の編集後も精度が不足するのを防ぎます。

当社の実装では、すべてのインデックスは0から1（0と1を除く）の間の分数です。排他的な範囲であることが重要です。これにより、既存のインデックスの前後でインデックスを生成するために、それぞれ0または1で平均化できます。各インデックスは文字列として格納され、精度を維持するために文字列操作で平均化を行います。コンパクトさを重視し、小数部の先頭の「0」を省略し、0–9の数字ではなくASCIIの全範囲（ベース95）を使用しています。

メリット:

理解しやすく実装が簡単

オブジェクトの並べ替えは単一の値を編集するだけで済む

デメリット:

インデックスの長さが時間とともに増加する可能性

複数のクライアントから新しい要素をマージすると、要素が交錯する可能性がある

同一のインデックス間の平均化は機能しない

事例

ここで例に出ているJavaScriptライブラリはBase62（62文字種）で表現している。Base62だと並び替えを繰り返すとそれなりに桁数が増えることがわかる

Ruby gem

Railsと統合するためのgemで、モデルクラスにヘルパーメソッドを追加してくれる

Fractional indexingのアルゴリズム本体はこのgemに含まれる

Order keyはInteger PartとFractional Partから構成される

Integer Partはその後に続くFractional Partの桁数を表す

これにより、文字列の長さに依存せずに意図した並びを実現できるとのこと

デフォルトはBase62だが、あとからエンコード方法を変えるのは大変なので始めからBase94を使っておくとよさそうな気がする