LexoRank で実現する単語帳の並び替え機能 - 並び替え可能なデータ構造

はじめに

私が開発している子供向け学習アプリケーション「Enplayn」では、ユーザーが自分の単語帳を作成・管理できる機能を提供しています。
https://enplayn.com

単語帳機能をリリースした後、学習順序をユーザー自身がコントロールできるように「単語を自由に並び替えたい」と考えるようになりました。Enplayn は私自身の学習も兼ねているので、せっかくなら効率的でスケーラブルな並び替え機能の実装に挑戦してみることにしました。

本記事では、この並び替え機能を実装する際に選択した LexoRank という技術と、その実装の詳細について紹介します。
https://x.com/doba_shuzaburo/status/1992168663127040311?s=20

並び替え可能なデータ構造の比較

並び替え機能を実装するにあたり、まずはどのようなデータ構造で順序を保存するか検討しました。

主な手法の比較

方式	UPDATE 数	精度問題	同時編集耐性	実装難易度	スケーラビリティ
連番	多い	なし	低	★☆☆☆☆	△
間隔	少ない	なし	中	★★☆☆☆	△
小数点	少ない	あり	中	★★☆☆☆	△
配列	少ない	なし	低	★★★☆☆	△
LexoRank	少ない	なし	高	★★★☆☆	◎

1. 連番方式

順番 のカラムに 1, 2, 3 ... と連番を振る最もシンプルな方式です。

Fruits テーブル

id	name	order
1	Apple	2
2	Banana	1
3	Cherry	3

order カラムでソートすることで順序を復元できるためとても扱いやすいですが、大量の UPDATE が発生します。 たとえば Cherry を先頭に移動する場合、Apple と Banana の order も更新しなければなりません。

メリット:

• 実装が簡単で理解しやすい
• ソートクエリが高速
• 1 つのテーブルで完結する

デメリット:

• 並び替え時に大量の UPDATE が必要（例: 100 件中の先頭に挿入すると 99 件更新）
• トランザクション処理が重い

2. 間隔方式

100, 200, 300 ... のように間隔を空けて番号を振る方式です。

Fruits テーブル

id	name	order
1	Apple	1500000
2	Banana	1000000
3	Cherry	2000000

連番方式と比べて、間に挿入できる余地があるため、UPDATE 数を減らせます。 Cherry を先頭に移動する場合、Apple と Banana の order は更新せず、Cherry のみ 500000 に更新すれば良くなります。
ただし、並び替えを繰り返すと間隔が埋まってしまい、重複が発生するため、リナンバリングのプログラムを頻繁に実行する必要があります。

メリット:

• 挿入時の UPDATE が減る（間に挿入できる場合）
• 1 つのテーブルで完結する

デメリット:

• 間隔が埋まることでリナンバリングを頻繁に実行する必要がある
• 最適な間隔の決定が難しい

3. Decimal 方式（小数点利用）

1.0, 2.0, 3.0 として、間に 1.5 のように挿入する方式です。

Fruits テーブル

id	name	order
1	Apple	2.0
2	Banana	1.0
3	Cherry	3.0

間隔方式に似ていて、間に挿入できる余地があるため、UPDATE 数を減らせます。 おなじみ Cherry を先頭に移動する場合、Apple と Banana の order は更新せず、Cherry のみ 0.5 に更新すれば良くなります。
ただし、並び替えを繰り返すと、浮動小数点の精度問題により同じ値が発生するリスクがあります。 たとえば 1.0 と 1.0000000000001 の間に挿入し続けると、最終的に同じ値になってしまう可能性があります。
DB 側で DECIMAL / NUMERIC 型を使えば精度問題はある程度回避できますが、 実装や運用で一貫して取り扱う必要があり、やや注意が必要です。

メリット:

• 挿入が柔軟
• UPDATE 数が少ない
• 1 つのテーブルで完結する

デメリット:

• 浮動小数点の精度問題
• 深くネストすると桁あふれのリスク

4. 配列方式

レコードの順番を配列として保存する方法です。
順番テーブルを別で持ち、次のような構造にします。

Fruits テーブル

id	name
1	Apple
2	Banana
3	Cherry

FruitsOrder テーブル

id	order_array
1	2, 1, 3

配列のインデックスで順序を管理するため、並び替え時の UPDATE 数は最小限に抑えられます。 ただし、配列全体を更新する必要があるため、同時編集に弱く、複数ユーザーが同時に並び替えを行うと競合が発生しやすくなります。
また順番を取得する際に JOIN が必要になるため、クエリが複雑化します。

メリット:

• 挿入時に更新するレコード数は 1 件で済む
• 配列全体を 1 レコードとして扱えるため、テーブル構成はシンプル
• 実装が比較的簡単

デメリット:

• 同時編集に弱い
• JOIN が必要でクエリが複雑化

5. LexoRank 方式

文字列ベースのランキングシステムです。

Fruits テーブル

id	name	rank
1	Apple	"0
2	Banana	"0
3	Cherry	"0

LexoRank では、文字列の辞書順でソートすることで順序を管理します。 間隔方式などに似ていて、間の値を挿入することで UPDATE 数を減らせます。
Cherry を先頭に移動する場合、Apple と Banana の rank は更新せず、Cherry のみ 0|hzzzzj: というような算出された値に更新すれば良くなります。

メリット:

• 文字列なので精度問題がない
• 挿入時の更新が 1 件のみ
• ライブラリが充実（npm: lexorank）
• スケーラブル（理論上ほぼ無限に挿入可能）
• 1 つのテーブルで完結する

デメリット:

• 文字列長が増加する可能性（リバランスが必要）
• 実装がやや複雑
• ライブラリへの依存

LexoRank を採用した理由

Enplayn では以下の理由で LexoRank を選択しました。

1. 更新効率: 並び替え時に 1 件の UPDATE のみで済む
2. 精度の信頼性: 文字列ベースで浮動小数点の問題がない
3. 実績: Atlassian Jira で採用されている
4. ライブラリ: npm に lexorank パッケージが存在し、導入が容易
5. スケーラビリティ: 単語帳の単語数が増えても対応可能
6. 自身の学習: 新しい技術を学ぶ良い機会になる

LexoRank の基本概念

LexoRank は、文字列で順序を表現します。例えば "0|hzzzzz:" のような文字列を使います。

import { LexoRank } from 'lexorank';

// 基本的な使い方
const min = LexoRank.min();     // 例: "0|000000:"
const max = LexoRank.max();     // 例: "0|zzzzzz:"
const middle = LexoRank.middle(); // 例: "0|hzzzzz:"

// 2つのランクの間に挿入
const rank1 = LexoRank.parse("0|000000:");
const rank2 = LexoRank.parse("0|hzzzzz:");
const between = rank1.between(rank2);

// 次/前のランクを生成
const next = rank1.genNext();
const prev = rank2.genPrev();

文字列の辞書順でソートすることで、常に正しい順序を保つことができます。

実装の詳細

Enplayn では並び替え後の前後の単語の ID を受け取り、新しいランク値を計算して保存する API を作成しました。
以下のようなケースを実装しています。

• ケース 1: 末尾への追加（前後の単語の ID なし）
• ケース 2: 特定単語の後に追加（前の単語 ID のみあり）
• ケース 3: 特定単語の前に追加（後の単語 ID のみあり）
• ケース 4: 2 つの単語の間に挿入（前後の単語 ID 両方あり）

例: ケース 4（2 つの単語の間に挿入）

async calculate(
        wordBookId: WordBookId,
        beforeWordIdOptional: Optional<WordBookWordId>,
        afterWordIdOptional: Optional<WordBookWordId>
): Promise<WordBookWordRank> {
  ...
  
  // ケース 4: 2 つの単語の間に追加
  if (beforeWordIdOptional.isPresent() && afterWordIdOptional.isPresent()) {
    // 前の単語の情報を取得
    const beforeWord = await this.wordBookWordRepository.findByIdAndWordBookId(
      beforeWordIdOptional.get(),
      wordBookId
    );
    // 後の単語の情報を取得
    const afterWord = await this.wordBookWordRepository.findByIdAndWordBookId(
      afterWordIdOptional.get(),
      wordBookId
    );
  
    // 前後の単語のランク値を取得
    const beforeWordRank = beforeWord.getRank();
    const afterWordRank = afterWord.getRank();
  
    if (beforeWordRank.isPresent() && afterWordRank.isPresent()) {
      return new WordBookWordRank(
        LexoRank.parse(beforeWordRank.get().getValue())
          .between(LexoRank.parse(afterWordRank.get().getValue()))
          .toString()
      );
    } else {
      // どちらかの単語のランク値が存在しない場合
      // （本来は起こりにくいが、念のためリバランスしてから再計算する）
      await this.wordBookWordRankRebalanceDomainService.execute(wordBookId);
      return this.calculate(wordBookId, beforeWordIdOptional, afterWordIdOptional);
    }
  }
  
  ...
}

このように、2 つの単語のランク値を取得し、その間の値を between() メソッドで計算します。どちらかの単語がランク値を持っていない場合は、リバランス処理（後述）を実行してから再計算します。

リバランスの実装

LexoRank には文字列長が増加するという問題があります。頻繁に並び替えを繰り返すと、"0|hzzzzz:" → "0|hzzzzj:0000000000i" のように文字列が長くなっていきます。

そこで、定期的にランク値を均等に再配分する「リバランス」処理が必要になります。

リバランスの実行条件

以下のいずれかに該当する場合、リバランスを実行します：

1. rank が NULL の単語がある
2. rank の文字列長が 20 文字以上の単語がある（20 文字という閾値は、インデックスサイズとランクの余裕度のバランスを見て、暫定的に決めています）

中央優先二分割法アルゴリズム

リバランス時は、LexoRank.min() と LexoRank.max() の間に単語を均等に配置します。

この際、中央優先二分割法を使うことで、より均等な分布を実現しています。

public calculateEvenlyDistributedRanks(count: number): string[] {
  const L = LexoRank.min();
  const R = LexoRank.max();
  const ranks: string[] = new Array(count);

  type Range = { l: LexoRank; r: LexoRank; li: number; ri: number };
  const stack: Range[] = [{ l: L, r: R, li: 0, ri: count - 1 }];

  while (stack.length > 0) {
    const { l, r, li, ri } = stack.pop()!;
    if (li > ri) continue;

    const mi = Math.floor((li + ri) / 2);
    const mid = l.between(r);
    ranks[mi] = mid.toString();

    if (li <= mi - 1) {
      stack.push({ l, r: mid, li, ri: mi - 1 });
    }
    if (mi + 1 <= ri) {
      stack.push({ l: mid, r, li: mi + 1, ri });
    }
  }
  return ranks;
}

アルゴリズムの動作イメージ

5 個の単語を均等配置する例：

Step 1: 中央 (index=2) に middle() を配置
[_, _, middle, _, _]

Step 2: 左半分 [0,1] の中央 (index=0)
[rank0, _, middle, _, _]

Step 3: 右半分の中央 (index=3)
[rank0, _, middle, rank3, _]

Step 4: 残りを埋める
[rank0, rank1, middle, rank3, rank4]

この方法により、単純に順番に割り当てるよりも均等な分布が得られます。

バッチ処理によるリバランス実行

リバランスは、Cron ジョブから定期的に呼び出されるバッチ処理として実装しています。

API 仕様

• リバランス対象の検出: rank が NULL または 20 文字以上の単語を持つ単語帳

エラーハンドリング

1 つの単語帳のリバランスが失敗しても、他の単語帳の処理は継続されます。

レスポンス例:

{
  "total_processed": 5,
  "success_count": 4,
  "failure_count": 1,
  "failed_word_book_ids": ["123"]
}

失敗した単語帳の ID を返すことで、後から手動で対処することも可能です。

フロントエンド実装（dnd-kit）

ドラッグ & ドロップの UI には、@dnd-kit/core と @dnd-kit/sortable を使用しています。

ライブラリのセットアップ

import {
  DndContext,
  closestCenter,
} from '@dnd-kit/core';
import {
  arrayMove,
  SortableContext,
  verticalListSortingStrategy,
} from '@dnd-kit/sortable';

ドラッグ終了時のハンドリング

const handleDragEnd = async (event: DragEndEvent) => {
  const { active, over } = event;
  if (!over || active.id === over.id) return;

  const oldIndex = localWords.findIndex((w) => w.id === active.id);
  const newIndex = localWords.findIndex((w) => w.id === over.id);

  // オプティミスティックUI更新
  const newWords = arrayMove(localWords, oldIndex, newIndex);
  setLocalWords(newWords);

  // before_word_id / after_word_id を計算
  let beforeWordId: string | null = null;
  let afterWordId: string | null = null;

  if (newIndex > 0) {
    beforeWordId = newWords[newIndex - 1].id;
  }
  if (newIndex < newWords.length - 1) {
    afterWordId = newWords[newIndex + 1].id;
  }

  // API呼び出し
  try {
    await csrfFetch(
      `/api/word-books/${wordBookId}/words/${active.id}/ranks`,
      {
        method: 'PATCH',
        body: JSON.stringify({ before_word_id: beforeWordId, after_word_id: afterWordId }),
      },
      csrfToken
    );
    onRefresh();
  } catch (error) {
    setLocalWords(words); // エラー時は元に戻す
    toast.error('並び替えに失敗しました');
  }
};

オプティミスティック UI の重要性

ユーザー体験を向上させるため、API の応答を待たずに即座に UI を更新する「オプティミスティック UI」を実装しています。

API 呼び出しが失敗した場合のみ、元の状態に戻す仕組みです。

API 設計

並び替え API は、移動先の前後の単語 ID を受け取るシンプルなものになっています。

エンドポイント仕様

• エンドポイント: PATCH /api/word-books/{id}/words/{word_id}/ranks
• リクエストボディ:

  {
    before_word_id?: string | null,
    after_word_id?: string | null
  }
  

使用例

// 先頭に移動
{ before_word_id: null, after_word_id: "1" }

// 末尾に移動
{ before_word_id: "10", after_word_id: null }

// 単語 5 と 6 の間に挿入
{ before_word_id: "5", after_word_id: "6" }

この設計により、フロントエンドから柔軟に並び替えを指示できます。

まとめ

LexoRank を採用したことで、効率的な並び替え機能を実装することができたと考えています。
また内部でのデータの持ち方やアルゴリズムの設計など、多くの学びがありました。
特に、LexoRank によって「1 件の UPDATE で並び替えを成立させつつ、リバランスで安全に保つ」というパターンは、他のアプリケーションでもそのまま流用できると感じています。
本記事が並び替え機能を検討している方の参考になったら幸いです。
今後も楽しみながら色々な機能を追加していけたらと思います。