一个分数索引库，提供分数索引和重分布算法。
用来实现排序索引的无状态的排序和插入，也就是元素的排序和插入只需修改当前元素的 index，不需修改其他元素的 index。
所谓分数索引 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: 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: string | null, count: number = 1): string[]生成指定索引前的索引，生成的若干索引一定排在目标索引前。
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 的核心是一个局部重平衡算法：
-
确定区间与 O(1) 快速检测：
- 如果
target传入的是区间端点{ startIndex, endIndex }，则以此边界开始检测。 - 如果
target传入的是{ items }列表，则会自动提取items中最小和最大 index 作为startIndex和endIndex，并将其作为重平衡的中间区间（如果数组为空则直接返回不重平衡）。 - 检测
startIndex和endIndex的长度。如果它们的长度均未超过设定的最大长度（maxIndexLength，默认为12），则说明当前区间依然健康，直接返回。
- 如果
-
向外寻找健康锚点：如果长度超标，算法会分别向左（向前）和向右（向后）检索数据库，以每批
5个元素的大小批量拉取（即批量调用getPrevIndexes和getNextIndexes），直到在左侧 and 右侧各找到一个长度在健康范围内的索引作为“健康锚点”（leftAnchor和rightAnchor）。 -
圈定全量重排区间：
- 若
target传入的是区间端点，则调用getRangeIndexes获取两个健康锚点之间的所有条目。 - 若
target传入的是{ items }列表，则跳过getRangeIndexes调用，直接以items作为中间区间，降低数据库查询开销。
- 若
-
重新均匀分布：利用
getIndexesBetween(leftAnchor, rightAnchor, N)为合并后（左扩展 + 中间段 + 右扩展）的$N$ 个条目重新生成一批均匀分布且非常短的索引。 -
批量更新：将生成的新索引通过
setIndexes批量写回数据库，同时本地缓存的数据索引也会随之更新。 -
并发控制与返回结果：内部内置了全局排他锁，防止多个异步重平衡任务并发。若开启了
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: { prevIndex?: string; nextIndex?: string },
items: { index: string; id: any }[],
): { items: { index: string; id: any }[] }方便的实现文档插入排序时的分数索引更新
export function changeIndexesByReverse(
items: { index: string; id: any }[],
): { items: { index: string; id: any }[] }方便的实现文档反转排序时的分数索引更新
