Lexorank
並び替え機能付きリストで、個々の要素に割り振られるランキング情報を扱うアルゴリズム
仕組み
ランク情報として辞書順キーを使う
3つのパートから構成されるランク値を持つ
Bucket
リバランシング時に順序関係を壊さないようにするための値
FixedKey
基本的なランクとして使用される固定長キー
VariableKey
FixedKey 枯渇時に割り当てられる可変長キー
並べ替え
GreenHopperと同様に、前後のアイテムの間にある値のキーに更新する
リバランシング（再インデックス）
更新処理中のどの時点を見てもランキング順序が壊れないようにできる
Bucket が最大値でないとき
ランキングの最下位要素から処理
Bucket の値を辞書順で+1して、FixedKey (, VariableKey) にbalancedなキーを割り当てていく
Bucketが最大値のとき
ランキングの最上位要素から処理
Bucket の値を辞書順の最小値に戻して、FixedKey (, VariableKey) にbalancedなキーを割り当てていく
周辺情報
Lexorank の TypeScript 実装
Bucket のデフォルトは 0~2 の三種類 （変更可）
キーは36進の値
JIRAのチームが開発し、チケットの並び替えに使っているらしい リスト状に並べられた要素を任意の順序で並べ替えするために、個々の要素に「順序関係を示す情報」をいい感じに割り振るアルゴリズムの一つ
資料
1. Sequential integer index な ランキング
優先度の高い（低い）順に整数値を割り当てていく
最もシンプルな実装方法
整数の順序関係を用いる
並べ替えの変更コストが高いのが問題
2. GreenHopper (integer) なランキング
並べ替えのコストを解消している
ランキング値が枯渇する点が問題
リバランシング（ランキング値の振り直し）が必要になる
リバランシングでは処理中のランキングが壊れる点が問題
3. GreenHopper (float) なランキング
integerに比べランキング値は枯渇しづらくなるが、いつか枯渇する点は変わらない
浮動小数点数は小数そのものではないため
2.と同様にリバランシングの問題を持つ
4. Lexorank
リバランシング問題を解消する仕組みとして導入
1. Basic ranking
Sequential Integer index なランキングを紹介
データが多いと並べ替えの変更コストによるパフォーマンス問題につながる
2. GreenHopper Ranking
Green Hopper (integer) を例として紹介
再インデックス時にロックが必要
3. Lexorank
再インデックス中でも順序が保持されたデータを取得できると紹介
既存のランキングシステムと、それぞれの問題点を紹介
1. Integer方式
sequential integer index なランキングを紹介
順序変更時の修正範囲が大きい (O(N))
2. GreenHopper方式
例は integer
ランクの枯渇・リバランス時のシステム停止
3. Linked List方式
ランク変更コストはあまり重くない
クエリしようとするとフルスキャンになる
それらを解決するものとして Lexorank を紹介
キーの説明がわかりやすい
リバランスのタイミングの話・実装など、応用めな話が詳しく書いてある