Table of Contents

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)——持久化机制与恢复协议