indexless | Fractional Indexing

一个分数索引库，提供分数索引和重分布算法。

用来实现排序索引的无状态的排序和插入，也就是元素的排序和插入只需修改当前元素的 index，不需修改其他元素的 index。

什么是分数索引 Fractional Indexing

所谓分数索引 Fractional Indexing 是用在给数据手动排序时，取代传统数字值来控制位置的算法。传统的数字排序，每当进行重新排序、插入等操作时，不仅仅要改变被操作数据的 index 值，还需要修改前后数据的 index 值。

例如在下面的例子中，插入 D 到列表最前端，除了需要给 D 设置 index 值，还需要修改 D 之后每一个元素 index 值。

A:1     + D:1
B:2  ->   A:2
C:3       B:3
          C:4

这样的操作成本在大数据量时肯定无法接受，还有一种方法是 Gap Buffer，也就是每个 index 直接留足间隔空间，这样操作时就可以利用好间隔，而无需改动其他元素。但这样有其他问题，比如空间一定会被耗尽，届时就需要复杂的重新分布（rebalance）操作。

A:1000   + D:500
B:2000 ->  A:1000
C:3000     B:2000
           D:3000

分数索引就是更好地利用间隙，并且可以自动处理重分布操作的索引算法。本质上它是把索引像分数一样的值,如 1.1 1.2 1.3 等等，在 2 个数之间可以无限插入更小精度的小数。当然实际上由于存储数据类型的限制，不可能做到无限精度，所以实际上使用的是字符串和文本编码特性来实现。

A:zA     D: zAa
B:zB  -> A: zA
C:zC     B: zB
         C: zC

通过字符串的特性，可以做到每次插入都只用修改操作的元素 index 不用修改其他元素 index，其代价是 index 是字符串类型，并且长度随着操作会不断增长。如果场景简单、操作数量不会太多就可以完全不用考虑 index 过长的问题，毕竟是用存储空间换时间和易用性。

如果数据的量级很大、操作频繁、对 index 长度有要求的场景，也可以通过 重分布（rebalance） 算法来控制 index 的长度。

相比同样需要重分布（rebalance）的 Gap Buffer 方式，分数索引的优势在于分数索引的重分布是可选的、非强制的，而 Gap Buffer 则是需要立即执行的，否则排序就不对了，分数索引的重分布只是为了缩短索引长度，可以延迟执行，或者定期后台执行。

安装

npm i indexless

import { getIndexesBetween, getIndexesPrev, getIndexesNext, smartRebalance } from "indexless"

核心功能

getIndexesBetween(prev, next, count)

getIndexesBetween(prev: string | null, next: string | null, count: number = 1):string[]

生成指定范围内的若干索引值，每个索引值都介于 prev 和 next 之间，并且排在 prev 之后、next 之前，按顺序排列。

• 如果 prev 为 null，next !== null 从 next 向前生成 count 个分数索引
• 如果 prev !== null，next === null 从 prev 向后生成 count 个分数索引
• 如果 prev === null，next === null，则表示根据 count 长度从「默认起始位置」开始生成 count 个分数索引

getIndexesPrev(target, count)

getIndexesPrev(target: string | null, count: number = 1): string[]

生成指定索引前的索引，生成的若干索引一定排在目标索引前。

getIndexesNext(target, count)

getIndexesNext(target: string | null, count: number = 1): string[]

生成指定索引后的索引，生成的若干索引一定排在目标索引后。

重分布

当你在列表的同一位置频繁地进行插入或移动操作时，分数索引的长度会随着精度的增加而不断增长（例如从 a0 演变为 a0VVVVV...）。过长的索引不仅会增加存储开销，也会降低排序和比对的性能。

indexless 提供了智能的重分布（Rebalance）算法 smartRebalance，帮助你控制索引的长度。由于分数索引的有序性仅依赖于字符的字典序，因此它的重分布是可选且非强制的。你可以选择在每次数据变更后异步/后台执行重分布，以保证索引长度维持在一个健康的范围内，而不必担心阻塞用户主流程。

export async function smartRebalance(
    target:
        | {
              /** 本次操作新生成的 indexes 中最小的那个（最左端） */
              startIndex: string
              /** 本次操作新生成的 indexes 中最大的那个（最右端） */
              endIndex: string
          }
        | {
              /** 本次操作涉及的全部条目（直接作为中间段，不调用 getRangeIndexes） */
              items: { index: string; id?: any }[]
          },
    options: {
        /** 返回两个 index 之间的所有条目，按 index 字典序从小到大升序排序（含端点）。当 target 传入的是 items 时可选。 */
        getRangeIndexes?: (startIndex: string, endIndex: string) => Promise<{ index: string; id?: any }[]>
        /** 根据指定 index，按字典序升序返回此 index 前 count 个条目 */
        getPrevIndexes: (index: string, count?: number) => Promise<{ index: string; id?: any }[]>
        /** 根据指定 index，按字典序升序返回此 index 后 count 个条目 */
        getNextIndexes: (index: string, count?: number) => Promise<{ index: string; id?: any }[]>
        /** 批量更新分数索引的回调函数 */
        setIndexes: (reqs: ({ index: string; newIndex: string } | { id: any; newIndex: string })[]) => Promise<any>
        /** 触发重平衡的 index 最大长度阈值，默认值为 12 */
        maxIndexLength?: number
        /** 最大向外扩展查询次数，防止单次重平衡消耗过多数据库 IO，默认值为 10（单侧最多扩展 50 个元素） */
        maxExpansionCount?: number
        /** 是否返回被重平衡的索引列表 */
        returnChangedItems?: boolean
    },
): Promise<IRebalanceResult>

export interface IRebalanceResult {
    /** 是否触发了重平衡 */
    rebalanced: boolean
    /** 数据操作函数的调用次数统计，便于监控数据库 IO */
    callCounts: {
        getPrevIndexes: number
        getNextIndexes: number
        getRangeIndexes: number
        setIndexes: number
    }
    /** 重排更新的索引条目数量 */
    changedCount: number
    /** 改变的索引列表，包含 id 与新生成的 index（当 returnChangedItems 为 true 时返回） */
    changedItems?: {
        id: any
        index: string
    }[]
}

工作原理

smartRebalance 的核心是一个局部重平衡算法：

1. 确定区间与 O(1) 快速检测：
   • 如果 target 传入的是区间端点 { startIndex, endIndex }，则以此边界开始检测。
   • 如果 target 传入的是 { items } 列表，则会自动提取 items 中最小和最大 index 作为 startIndex 和 endIndex，并将其作为重平衡的中间区间（如果数组为空则直接返回不重平衡）。
   • 检测 startIndex 和 endIndex 的长度。如果它们的长度均未超过设定的最大长度（maxIndexLength，默认为 12），则说明当前区间依然健康，直接返回。
2. 向外寻找健康锚点：如果长度超标，算法会分别向左（向前）和向右（向后）检索数据库，以每批 5 个元素的大小批量拉取（即批量调用 getPrevIndexes 和 getNextIndexes），直到在左侧 and 右侧各找到一个长度在健康范围内的索引作为“健康锚点”（leftAnchor 和 rightAnchor）。
3. 圈定全量重排区间：
   • 若 target 传入的是区间端点，则调用 getRangeIndexes 获取两个健康锚点之间的所有条目。
   • 若 target 传入的是 { items } 列表，则跳过 getRangeIndexes 调用，直接以 items 作为中间区间，降低数据库查询开销。
4. 重新均匀分布：利用 getIndexesBetween(leftAnchor, rightAnchor, N) 为合并后（左扩展 + 中间段 + 右扩展）的 $N$ 个条目重新生成一批均匀分布且非常短的索引。
5. 批量更新：将生成的新索引通过 setIndexes 批量写回数据库，同时本地缓存的数据索引也会随之更新。
6. 并发控制与返回结果：内部内置了全局排他锁，防止多个异步重平衡任务并发。若开启了 returnChangedItems，结果中还会包含被更新的条目和对应的新 index。

使用示例与最佳实践

下面是一个配合模拟数据库（或实际 ORM / 数据库）的具体使用示例：

import { getIndexesBetween, smartRebalance } from "indexless"

// 插入或移动条目的函数
async function handleInsertTask(prevIndex: string | null, nextIndex: string | null, name: string) {
    // 生成新分数索引
    const [newIndex] = getIndexesBetween(prevIndex, nextIndex)

    // 插入新任务到数据库
    const newTask: Task = { id: Date.now().toString(), name, index: newIndex }
    tasks.push(newTask)
    tasks.sort((a, b) => (a.index < b.index ? -1 : 1))

    // 关键：在操作完成后，后台异步执行 smartRebalance。
    smartRebalance(
        {
            startIndex: newIndex,
            endIndex: newIndex,
        },
        rebalanceOptions,
    )
        .then((result) => {
            if (result.rebalanced) {
                console.log(`[Rebalance] 重平衡触发成功，重排了 ${result.changedCount} 个元素`)
            }
        })
        .catch((err) => {
            console.error("[Rebalance] 重平衡失败:", err)
        })

    return newTask
}

工具方法

changeIndexesByInsert(target, items)

changeIndexesByInsert(
    target: { prevIndex?: string; nextIndex?: string },
    items: { index: string; id: any }[],
): { items: { index: string; id: any }[] }

方便的实现文档插入排序时的分数索引更新

changeIndexesByReverse(items)

export function changeIndexesByReverse(
    items: { index: string; id: any }[],
): { items: { index: string; id: any }[] }

方便的实现文档反转排序时的分数索引更新

参考

• Realtime Editing of Ordered Sequences
• Implementing Fractional Indexing
• crdt-fractional-indexing