Fractional Indexing: 정렬된 리스트의 순서를 한 row만 바꿔 관리하기

순서가 있는 리스트를 다루는 앱이라면 한 번쯤 부딪히는 문제가 있다. 칸반 보드의 카드, 할 일 목록, 문서 에디터의 블록 — 사용자가 항목을 드래그해 순서를 바꿀 때 그 순서를 DB에 어떻게 저장할 것인가? 가장 먼저 떠오르는 정수 position은 의외로 금방 무너진다. fractional indexing은 이 문제를 "순서 변경 = 한 row UPDATE"로 바꿔주는 기법이다.

정수 position의 한계

가장 단순한 방법은 각 항목에 정수 순번을 부여하는 것이다.

[
  { id: "a", position: 0 },
  { id: "b", position: 1 },
  { id: "c", position: 2 },
];

문제는 삽입이다. b와 c 사이에 새 항목을 넣으려면 c 이후 모든 항목의 position을 한 칸씩 밀어야 한다.

UPDATE items SET position = position + 1 WHERE position >= 2;
INSERT INTO items (id, position) VALUES ('x', 2);

항목이 수천 개라면 드래그 한 번이 수천 row의 UPDATE가 된다. 실시간 협업 앱이라면 그 변경분이 전부 네트워크로 브로드캐스트된다. 순서 하나 바꿨을 뿐인데 비용이 리스트 전체에 비례한다.

핵심 아이디어: 사이에 값을 만든다

fractional indexing의 발상은 단순하다. 정수 대신, 두 이웃 사이에 항상 새 값을 끼워넣을 수 있는 키를 쓴다. 항목을 옮길 때는 그 항목의 키 하나만 바꾸면 되고 나머지는 건드리지 않는다.

가장 직관적인 형태는 실수다. 0과 1 사이는 0.5, 0과 0.5 사이는 0.25.

function midpoint(a: number, b: number): number {
  return (a + b) / 2;
}
 
midpoint(0, 1); // 0.5
midpoint(0, 0.5); // 0.25

삽입은 O(1)이고 다른 항목 갱신은 0이다. 하지만 실수에는 치명적인 약점이 있다.

실수가 안 되는 이유: 정밀도 고갈

같은 자리에 계속 삽입하면 간격이 절반씩 줄어든다. 0.5, 0.25, 0.125. IEEE 754 double은 가수가 약 52비트라, 같은 위치에 50번쯤 삽입하면 두 키가 같은 값으로 뭉개져버린다.

let lo = 0;
let hi = 1;
for (let i = 0; i < 60; i++) {
  const mid = (lo + hi) / 2;
  if (mid === lo || mid === hi) {
    console.log(`${i}번째 삽입에서 고갈 — 더 이상 사이를 못 만든다`);
    break;
  }
  hi = mid; // 계속 앞쪽에 삽입
}

mid === lo가 되는 순간 "사이"가 사라진다. 부동소수점으로는 임의의 깊이 삽입을 버틸 수 없다.

문자열 기반 fractional index

그래서 실무에서는 임의 정밀도를 갖는 문자열을 키로 쓴다. 핵심 성질은 하나다. "사전식(lexicographical) 정렬에서 a < b인 두 문자열 사이에 들어가는 문자열을 항상 만들 수 있다." 문자열은 길이를 늘려 정밀도를 무한히 확장할 수 있어 고갈되지 않는다.

a~z만 쓴다고 하면 직관은 이렇다.

• "a"와 "c" 사이 → 가운데 글자 "b"
• "a"와 "b" 사이 → 인접하니 한 자리 더: "an" (a보다 크고 b보다 작다)
• "a"와 "an" 사이 → "ag"

사이에 들어갈 글자가 있으면 그 글자를 쓰고, 인접하면 작은 쪽 뒤에 중간 글자를 덧붙인다. 개념을 코드로 옮기면(간략화 버전):

const DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz";
 
// a < b 인 두 키 사이의 키를 만든다 (경계 처리 생략한 개념용)
function between(a: string, b: string): string {
  let prefix = "";
  let i = 0;
  while (true) {
    const ca = i < a.length ? a[i] : null;
    const cb = i < b.length ? b[i] : null;
    if (ca !== null && ca === cb) {
      prefix += ca; // 공통 접두사는 그대로 이어붙인다
      i++;
      continue;
    }
    const lo = ca ? DIGITS.indexOf(ca) : -1;
    const hi = cb ? DIGITS.indexOf(cb) : DIGITS.length;
    const mid = Math.floor((lo + hi) / 2);
    if (mid > lo) return prefix + DIGITS[mid]; // 사이에 글자가 있다
    prefix += ca ?? DIGITS[0]; // 인접 → 작은 쪽을 따라 한 자리 더 내려간다
    i++;
  }
}
 
between("a", "c"); // "b"

DB에는 이 키를 문자열 컬럼으로 저장하고 ORDER BY sort_key 하면 끝이다.

맨 앞·맨 뒤 삽입

리스트 양 끝 삽입을 위해 보통 경계를 null로 표현해 between이 한쪽을 비워 받게 한다.

between(null, first); // 맨 앞에 삽입 → first 보다 작은 키
between(last, null); // 맨 뒤에 삽입 → last 보다 큰 키
between(null, null); // 빈 리스트의 첫 항목

이게 잘 알려진 npm 패키지 fractional-indexing(Figma의 구현에서 출발)의 generateKeyBetween(a, b) 시그니처다. 직접 구현하기보다 검증된 라이브러리를 쓰는 편이 안전하다.

import { generateKeyBetween } from "fractional-indexing";
 
const first = generateKeyBetween(null, null); // "a0"
const second = generateKeyBetween(first, null); // "a1"
const mid = generateKeyBetween(first, second); // "a0V"
 
// 항목을 b와 c 사이로 옮길 때
const moved = generateKeyBetween(bKey, cKey);
// → 그 항목 한 row 만 UPDATE

동시 삽입과 충돌

분산·협업 환경에선 한 가지를 더 생각해야 한다. 두 클라이언트가 같은 두 항목 사이에 동시에 삽입하면, 둘 다 같은 입력으로 between을 계산해 같은 키를 만들 수 있다. 키가 같으면 정렬 순서가 비결정적이 된다.

흔한 대응은 다음과 같다.

• 타이브레이커: 키가 같을 때 항목 id 같은 보조 기준으로 순서를 확정한다. ORDER BY sort_key, id.
• jitter: 생성한 키 끝에 약간의 무작위 글자를 붙여 충돌 확률을 낮춘다(Figma가 쓰는 방식).
• CRDT: 더 강한 수렴 보장이 필요하면 LSEQ, Logoot 같은 시퀀스 CRDT로 간다. fractional indexing은 이들의 단순화된 사촌으로 볼 수 있다.

키 길이는 자라난다

같은 위치에 반복 삽입하면 키 문자열이 점점 길어진다("a0" → "a0V" → "a0VV"). 보통은 무해하지만, 한 지점만 수만 번 파고들면 키가 길어져 저장·비교 비용이 늘어난다. 신경 쓰인다면 가끔 전체를 재정렬(rebalance)해 키를 다시 짧고 촘촘한 값으로 재배치한다. 자주 할 일은 아니다.

언제 쓰나

• 드래그 정렬이 잦은 리스트: 칸반 카드, 에디터 블록, 플레이리스트.
• 순서 변경이 한 row UPDATE로 끝나야 할 때(대량 재계산 회피).
• 실시간 협업에서 순서 변경을 작은 단위로 동기화해야 할 때.

반대로 순서가 거의 안 바뀌거나 항목이 몇 개 안 된다면, 정수 position에 가끔 재정렬을 더하는 쪽이 더 단순하고 충분하다.

정리

fractional indexing은 "정수 인덱스" 대신 "사이에 항상 더 끼울 수 있는 키"로 순서를 표현하는 기법이다. 실수의 정밀도 고갈을 문자열로 우회하고, 순서 변경을 O(1) UPDATE로 만든다. 협업 환경의 동시 삽입은 타이브레이커나 jitter로 다루면 된다. 대부분의 경우 fractional-indexing 패키지를 그대로 쓰는 것으로 충분하다.