#moonbit-multiindex

一张记录表,N 个二级索引。用稳定 ID 定位记录,按任意索引 O(1)/O(log n) 查找。

• 唯一索引 —— 一个键对应至多一条记录(冲突在变更前上报,不静默覆盖);
• 非唯一索引 —— 一个键对应多条记录;
• 有序索引 —— 按键有序,支持范围查询。

#它解决什么问题

BiMap 是「两个互为逆的唯一索引」的特例。本项目把它泛化成 N 个彼此独立的索引。

#安装

moon new hello-multiindex
cd hello-multiindex
moon add aurasuisui/multiindex@0.3.0

import { "aurasuisui/multiindex" }

pkgtype(kind: "executable")   // 本页的程序放在模块根包;`moon run .` 需要一个可执行包

#快速开始

完整可运行版本见 cmd/leaderboard(独立模块,import 已发布的包); 签名以 docs/SPEC.md 为准(唯一真源)。

struct Player {
  id : Int32
  name : String
  team : Int32
  score : Int32
}

fn main {
  let t : @multiindex.Table[Int32, Player] = @multiindex.Table::new()
  t.register_unique("id", fn(p) { p.id }).unwrap()
  t.register_non_unique("team", fn(p) { p.team }).unwrap()
  t.register_non_unique_ordered("score", fn(p) { p.score }).unwrap()

  let roster : Array[Player] = [
    { id: 7, name: "Alice", team: 1, score: 120 },
    { id: 9, name: "Bob", team: 1, score: 95 },
    { id: 11, name: "Carol", team: 2, score: 150 },
  ]
  match t.insert_many(roster) {
    Ok(ids) => println("inserted \{ids.length()} records, len = \{t.len()}")
    Err(rejected) => println("refused \{rejected.record.name}: \{rejected.conflict}")
  }

  let (_, alice) = t.get_by("id", 7).unwrap()
  println("id=7 -> \{alice.name}")

  for (_, p) in t.iter_by("team", 1) {
    println("team=1 -> \{p.name}")
  }
  for (_, p) in t.range_by("score", 100, 130) {
    println("score in [100, 130] -> \{p.name}")
  }
  for (_, p) in t.iter_desc_by("score") {
    println("\{p.name}: \{p.score}")
  }
}

inserted 3 records, len = 3
id=7 -> Alice
team=1 -> Alice
team=1 -> Bob
score in [100, 130] -> Alice
Carol: 150
Alice: 120
Bob: 95

#运行示例

cd cmd/leaderboard
moon run .

#API(与 docs/SPEC.md 同源)

#限制(已知边界)

• RowId 不可持久化:跨进程 / 跨版本不保证稳定;to_json / from_json 只保记录与插入序,不序列化索引, 载入后要重新 register_*、重新取句柄。跨表引用要自己带上表标识(见上文)。
• from_json 没有行数上限:读多大就解析多大;超大文件请自行分批,避免一次性内存峰值。
• 约束擦除(异构枚举)不做:K 必须满足方法所需的 Hash + Eq + Compare,不能在注册时擦成闭包 —— 否则擦除后无法继续逐步校验 I3 / I4 / I5 / I7(理由见 docs/SPEC.md §11)。
• 可变记录契约(读写两侧):值类型随便改;V 内含 Array / Ref 时,get / get_by / iter* / range_* 返回的记录与表内 共享容器,这些容器视为只读。insert / update / modify 存进去的 V 也与调用方共享容器:插入后再改自己手里的对象, 同样会写脏索引。改被索引字段必须走 update / modify;否则旧键命中 / 新键漏查,verify_invariants 会报 I4 / I7。 恢复三步:unregister_index → 用 update / remove 拆开重复投影 → 重新 register_*(见 docs/SPEC.md §3.7)。
• 脏表的残余边界:上述修复只针对被操作的那条记录;其他脏条目仍由 verify_invariants 指出。脏表上 insert 的唯一性预检也可能被绕过(干净表没有这个问题)——verify 一报错就按恢复路径重建索引。

#与生态中已有项目的关系

• 不重复 Milky2018/slotmap:slotmap 提供稳定键与槽复用(无索引投影、无唯一性、无按键查找); 本库的记录身份机制与它同源,核心价值在多索引。
• 不重复 kesmeey/IndexMap / wqbcs/moon_collections / Hhsqoo/moon-collections: 它们是有序哈希表(单索引、保留插入序);本库是多路查找结构。
• 不依赖 aurasuisui/bimap 或 aurasuisui/indexmap:同作者作品,思路延续,代码独立。

分支:main 是里程碑视图(每个阶段一个提交),dev 保留完整的逐节点开发历史。

#文档

• 文档枢纽/全量地图:docs/README.md
• API 唯一真源:docs/SPEC.md
• 立项设计稿(为什么这么设计):docs/DEVPLAN.md
• 开发圣经:CONTRIBUTING.md

#Gotchas(实测得来,不是设想)

• range_by 是双闭区间 [lo, hi](跟随 core 的 SortedMap::range);要半开请用 range_half_open_by。lo > hi 是合法的空区间,返回空迭代器而不是报错。
• index_names() 的"升序"是 MoonBit 的 String 序(shortlex:先比长度): ["aa", "b"] 会排成 ["b", "aa"]。多索引同时冲突时,报出的也是名称升序的第一个 (与注册顺序无关)。
• 两类"失败"必须分开看(SPEC §7.1):可预期的运行时条件(唯一冲突 / 陈旧句柄 / 键查不到) 返回 Err / None / 空迭代器,绝不 panic;而未知索引名、在哈希索引上做有序查询 是调用方 bug,一律 abort —— "空结果"只应表示"查得到,但没有"。
• 查询按值返回记录:值类型是独立副本,V 内含 Array / Ref 时与表内共享容器(见「限制」与 docs/SPEC.md §3.7),要改被索引字段请走 update / modify。所以索引赢在选择性,不在"扫得多": iter_by 在大桶上不比线性扫描快(两边都要走完所有匹配项,索引还多付拷贝),range_by 在 宽区间上同理。真正的优势是点查与选择性遍历(实测表与交叉点见 bench/README.md)。
• remove 是 O(len + I + Σ log 桶):order 数组按插入序原地压缩,所以删除耗时随表长线性 增长 —— 实测比 insert 贵 k=1 约 56×、k=8 约 6×(k 越大 insert 自身越贵,比值随之收窄)。 要 O(1) 删除就得放弃插入序稳定性,那是另一个取舍(见 SPEC §6);原始数字见 bench/README.md。
• JSON 不携带索引:from_json 返回的表注册表为空,载入后需自己 register_* 回填 (§3.1 的"对非空表注册即回填"会顺势把索引建好,不需要第二个机制)。
• 冲突不会让调用方丢数据:insert / insert_many / update / modify 失败时,记录随 Err 归还;但 modify 的闭包若已就地修改共享容器,返回的已是改后记录,无法回滚(见 docs/SPEC.md §3.7)。
• clear() 保留索引注册:清空的是记录与索引条目,不是"架构";清空后插入仍会被索引。

#致谢与来源

1. 代际 RowId(ABA 防护) —— 主蓝本的 Slab 槽位复用不带代际号,陈旧下标会静默命中复用该槽的新元素。
2. 范围查询 —— 主蓝本的 ordered 索引只暴露点查与全量遍历,没有 range;本库提供 range_by(双闭)/ range_half_open_by(半开)/ iter_asc_by / iter_desc_by,且范围查询保持惰性(一次只物化一个桶)。
3. 绝不 panic、且冲突时归还记录 —— 主蓝本 insert 冲突直接 panic,modify_by_* 冲突时更是先删旧键再 panic,留下脏索引;本库只有 Result,且 Rejected[K,V] 把记录原样还给调用方。
4. 代际号溢出即退役槽位 —— 所有 Rust 参考实现都选择静默回绕(bevy 文档明写 "generations can (and do) wrap or alias");本库让陈旧句柄永不复活。
5. 运行时注册索引(闭包投影)—— 主蓝本依赖 derive 宏;MoonBit 无等价机制,故采用运行时注册,代价是索引名运行时校验,收益是可动态增删/枚举索引。
6. 插入序语义 —— 主蓝本按槽位序遍历;本库额外维护 order。
7. 公开 verify_invariants() —— 主蓝本没有一致性自检 API;本库返回 Result[Unit, String], 首个违反点带上"哪条不变量 + 哪个槽位/键",而不是只说 false。
8. 整批原子 insert_many —— 主蓝本 FromIterator 是 first-wins(静默的胜出规则);本库 预检批内互相冲突,任一条冲突则整批零变更,并用 DuplicateInBatch 指明是批次里哪个成员。
9. 诊断与序列化 —— index_stats(桶数/最长桶/平均桶长)与 JSON 往返({"records": [...]}) 在主蓝本中都没有。

#License