Index 使用指南——点查 Hash / 有序 BTree / SkipList
给谁看:需要索引(点查/范围/前缀批量删)的 KV 组合开发者 回答什么:HashIndex vs BTreeIndex vs SkipListIndex 怎么选 / Settings 全参数 / KeyResolver 闭环 / 持久化两形态 / 恢复 本篇只讲机制——帧字节布局见源码;性能数字见
perf/structures-perf-baseline.md定位:Structures/ 6 子族之一,派生数据(与 Ring=真相源 组合为 KV)
0. 一句话总纲
索引 = 派生数据 + KeyResolver 闭环判等 + 自建主存储(PersistenceKind 可关)。
- 写编排正序:先
ring.Write得地址 →index.Insert指向;反序 = 索引指向不存在数据。 - 两族持久化均为自建主存储(内置后台 dump + 帧恢复),区别在帧策略—— Hash 走链 + N 版轮替,Sorted 固定锚点覆写。不配也安全,走全量重放 fail-safe。
- 两族不设公共基类——选族即选消费形态:有序遍历/range scan 选比较族,极省内存点查选探测族。
1. 定位
1.1 派生数据
索引是派生数据(可重建,存在性 = 优化非正确性)——索引丢失不损数据,只损恢复速度。 Ring 是数据真相源(record 流),索引是派生数据(可重建)。写编排正序:先真相源写、再索引插; 反向 = 索引指向不存在的数据。读两段合口径:先经索引发现地址,之后永久直达取值(跳过 hash)。
1.2 地址一等公民
16B LogicalAddress 是唯一的取值句柄——先经索引发现地址,之后永久直达取值(跳过 hash);
判等/哈希只比较地址本身。地址即句柄:ring.GetValue(addr) 永久零税,无需会话/索引保护。
1.3 三选一决策树
需要有序遍历 / range scan / 前缀批量删?
├─ 否 → HashIndex(点查为主,内存最省,tag-only 桶不物化 key)
└─ 是 → 写并发模式与记录尺寸?
├─ 高写并发 + 小记录 → SkipListIndex(无分裂重排,CAS 塔链)
└─ 读重 / 大记录 / 紧凑内存 → BTreeIndex(B+树扁平节点缓存全 L3 常驻)
└─ 需字节字典序(RocksDB/LMDB 同款范围通用序)→ ByteOrderBTreeIndex
| 选项 | 优势 | 注意 |
|---|---|---|
| HashIndex | tag-only 桶不物化 key,内存最省 | 构造必注入 KeyResolver(判等闭环);无有序遍历 |
| BTreeIndex | B+树扁平节点缓存全 L3 常驻(100k 条 ≈ 2.2MB) | 内部操作闸读写全互斥;游标仅 Forward |
| SkipListIndex | 无分裂重排(高写并发小记录最优) | arena 驻留节点(100k 条 ≈ 6.5MB);游标仅 Forward |
| ByteOrderBTreeIndex | 字节字典序范围通用序 | sealed 子类,比较器固定非可注入 |
3. 构造与生命周期
3.1 [RingKey] 源生成器
开放泛型(HashIndex<TKey>/BTreeIndex<TKey>/SkipListIndex<TKey>)的构造是 protected internal——
消费面只经 [RingKey] 生成的封闭薄类(编译期封闭 + CreateAsync 工厂)。内置 long 已声明(KernLab.Tier.Runtime
程序集),HashOfLong/BTreeOfLong/SkipListOfLong 开箱即用;自定义 Key 在消费程序集加一行:
[assembly: RingKey(typeof(OrderId))] // 产出 RingOfOrderId / HashOfOrderId / BTreeOfOrderId / SkipListOfOrderId
3.2 CreateAsync 工厂(三索引)
using var fs = TierFs.New("memory:");
await using var ring = await RingOfLong.CreateAsync(ringSettings, fs);
await using var hash = await HashOfLong.CreateAsync(fs, hashSettings, ring); // KeyResolver=ring(判等闭环必注入)
await using var btree = await BTreeOfLong.CreateAsync(fs, btreeSettings, ring); // KeyResolver=ring(恢复重放需要)
await using var skipl = await SkipListOfLong.CreateAsync(fs, skipListSettings, ring); // KeyResolver=ring(恢复重放需要)
- CreateAsync = 构造 + Initialize + WaitForReadyAsync(一步就绪——
LifecycleBase编排)。 - HashIndex:
KeyResolver构造期必注入(tag 命中后回读真 key 校验——判等闭环硬依赖, null 抛ArgumentNullException:"探测族判等闭环强依赖 IKeyResolver")。 - SortedIndex:
KeyResolver可选注入——判等不需要(key 物化条目内),恢复重放需要; 有重放窗口而无 resolver 者,恢复核心 fail-fast:"比较族重放窗口需要 IKeyResolver"。 ByteOrderBTreeIndex<TKey>是BTreeIndex<TKey>的 sealed 子类,内置KeyByteOrderComparer<TKey>(字节字典序——RocksDB/LMDB 同款范围扫描通用序,非可注入,类型语义即排序语义)。
3.3 KeyResolver 闭环
| 族 | 判等机制 | KeyResolver 角色 |
|---|---|---|
| HashIndex | tag 命中后回读真 key 比对(FASTER 判等闭环) | 构造期必注入——tag 只是加速器,冲突会假阳性 |
| BTreeIndex | key 物化条目内,比较即路由 | 可选——恢复重放需要(拉流自建节点) |
| SkipListIndex | key 物化条目内,比较即路由 | 可选——恢复重放需要(拉流自建节点) |
IKeyResolver<TKey> 三方法:
TryGetKey(addr, out key)——按地址读单条 key(false = 读不到/无效地址/record 无效)。GetFlushedWatermark()——真相源已落盘水位 W(主存储 dump 的 footer 锚点)。ScanAsync(begin, end, ct)——范围扫描吐(Key, Address, IsTombstone)三元组(墓碑感知重放)。
3.4 写读 KV 编排
// 写编排(正序两步写——先真相源得地址,再索引插指向)
static LogicalAddress KvPut(RingOfLong ring, IIndex<long> index, long key, ReadOnlySpan<byte> value)
{
var addr = ring.Write(key, value); // ① 真相源先写,得地址
index.Insert(key, addr, LogicalAddress.Empty); // ② 索引后插(指向该地址)
return addr;
}
// 读编排(两段合口径——索引命中得地址,真相源按址取值)
static bool KvTryGet(RingOfLong ring, IIndex<long> index, long key, Span<byte> buf, out int len)
{
len = 0;
var addr = index.Find(key); // ① 索引命中得地址
if (addr == LogicalAddress.Empty) return false;
len = ring.GetValue(addr, buf); // ② 真相源按址取值
return true;
}
// 批量读(EnterScope——一批一进出,零逐查 epoch 进出开销 ~10ns/op)
using var scope = index.EnterScope();
Span<long> addrs = stackalloc long[64];
index.FindBatch(keys, addrs); // 批量点查(同一轮 epoch 内完成)
for (int i = 0; i < keys.Length; i++)
if (addrs[i] != LogicalAddress.Empty)
ring.GetValue(addrs[i], buf);
终态读形态(批量最快):
index.EnterScope()一批一进出 +IndexScope.Find+Ring.GetValueSpan(零拷贝切片——仅同步栈内合法;跨 await 必须走拷贝 API)。
8. 反模式
| # | 反模式 | 后果 / 正解 |
|---|---|---|
| 1 | 写编排反序:先 index.Insert 再 ring.Write |
索引指向不存在的数据——必须先真相源写再索引插 |
| 2 | 增长后检查索引阈值 | 增长必须在插入之前检查(增长时刻表内条目必可经 KeyResolver 解析) |
| 3 | 跨实例组合 DeleteOnClose=true |
跨重启组合必须 DeleteOnClose=false(否则索引重建时真相源被清) |
| 4 | 绕过 KeyResolver 判等 | Hash tag 冲突静默错误——tag 只是加速器,命中后必读回真 key 校验 |
| 5 | 为 Sorted 手搭 checkpoint 引擎/存储 | 内置自建主存储(CheckpointFrame)——无需自搭 |
| 6 | BTree/SkipList 游标传 Backward | 叶链/层 0 链单向——NotSupportedException;倒序经 TryGetMax/TryGetFloor 组合 |
| 7 | SortedIndex 重放窗口不注入 KeyResolver | 恢复核心 fail-fast——构造期须注入(判等不需要,重放需要) |
| 8 | 给地址直达读加会话/索引 | 地址即句柄——ring.GetValue(addr) 永久零税(ring.md) |
| 9 | 零拷贝 span 跨 await | GetValueSpan 返回值仅同步栈内合法——跨 await 走拷贝 API(TryGetValue/GetValue) |
| 10 | 绕过 [RingKey] 直接继承开放泛型 |
封闭薄类是唯一消费面(外部直接 new = CS0122) |
| 11 | dump 前未落盘真相源 | W = 已落盘水位——调用 CheckpointFrame 前须先 ring.FlushUntil(Tail) |
9. 想深入?指路
| 想懂什么 | 去哪 |
|---|---|
| 总览(七种结构速查 + KV 组合三步上手) | structures.md |
| Ring 真相源(写读/水位/截断/快照/内容自愈读) | ring.md |
| Log WAL(组提交与回放/单写者) | log.md |
| meta 统一协议(opaque 搭车/块格式/锚点 W) | meta.md |
| Session 协调协议(写/读/检查点三 op、悬挂裁决) | session.md |
| 引擎使用(读写/水位/恢复/Compact) | storage-engine.md |
| 镜像/快照(WholeMirror/StreamSnapshot 基线形态) | mirror.md / snapshot.md |
| 版本链元数据(跨重启单值状态) | versioned-metadata.md |
| 性能基线(点查/写/恢复/并发扩展) | perf/structures-perf-baseline.md |
| 帧格式/主存储机制/恢复细节 | 源码注释(Structures/ProbingIndex/ + Structures/SortedIndex/) |
机制级细节(帧字节布局、dump 协议内部状态机、环防御阈值 MaxDescentPath、
槽稳定读双读比对协议、arena 驻留节点偏移契约)按需从源码与设计稿查阅——
使用面不需要这些细节;能力全集以类型 XML 注释为准。
分册导航:index.md | [index-api.md](API 与工厂) | index-persistence.md | Index(Hash/BTree/SkipList)——Settings / API 详表 / 注入工厂 | Index(Hash/BTree/SkipList)——持久化机制与恢复协议