背景
listat(idx) 当前无法便宜地取第 idx 个直接子项——两后端的子项名单都是「\n 分隔的线性名单」,取第 idx 项须 split 全表,O(n):
- redis / store 后端(
Backend<S>):memindex 存 index body [4B count LE][name1\n…\n nameN](xvalue_index.rs::encode_index_raw)。
- fs 后端(
FsKVSpace):子项顺序存 __order__ 文本文件 name1\n…\n nameN\n(fs/kvspace.rs::read_order/write_order)。
count 已 O(1),但 select(idx) 仍 O(n)。且 map 目录读时还要 sort_by(cmp_coord),listat 无法直接命中。
结论(见设计讨论):在「整体读写的 blob」语境里,B+树/skiplist 的局部更新价值兑现不了(插一个子项 body 整体重写),select 反而不如 offset 索引数组 的 O(1)。故采用 offset 索引数组。
方案:offset 索引数组
名单载体(index body 与 fs __order__)统一改为:
[4B count LE][ (count+1) × 4B offset LE ][ names blob ]
offset[i] = names blob 内第 i 个名的起始字节偏移
offset[count] = names blob 总字节(末名右边界)
listlen = 读 count,O(1)
listat(idx) = 切 names[offset[idx]..offset[idx+1]],O(1),无 split、无全量物化
insert/delete = body 整体重写(与现状同量级,offset 表 O(count) 重建,无额外结构维护)
map 坐标序:map 目录存储即按坐标 row-major 升序(add_child 时二分插入维持有序),使 listat 对 map 也 O(1)、读路径零排序。非 map 目录保持插入序(追加)。
ext_index:extpath 段照旧置于名单首段(EXT_INDEX_HEAD 前缀),纳入 offset 表第 0 项;count 仍只计 children。
trait / ffi
- KVSpace trait 新增 O(1) 原语:
list_len(dir, expand_ext, resolve) -> i32、list_at(dir, idx, expand_ext, resolve) -> Option<String>,直接解 body/order,不再全量 list()。
ffi.rs 的 kvspaceListLen/kvspaceListAt 改调这两个原语(caller-owned buffer 语义已落地,库侧零状态不变)。
list() 仍保留(全量遍历 body,一次产出)。
验证范围(本 issue)
- 先在 redis 与 fs 两后端验证;shm(kvspace-c)不在本次改动,frontend ABI 不变,应保持通过。
- durable 自身
tests/ + kvlang tutorial 以 fs:// 与 redis:// 全量回归,输出逐字节不变。
关联
背景
listat(idx)当前无法便宜地取第 idx 个直接子项——两后端的子项名单都是「\n分隔的线性名单」,取第 idx 项须 split 全表,O(n):Backend<S>):memindex 存 index body[4B count LE][name1\n…\n nameN](xvalue_index.rs::encode_index_raw)。FsKVSpace):子项顺序存__order__文本文件name1\n…\n nameN\n(fs/kvspace.rs::read_order/write_order)。count 已 O(1),但 select(idx) 仍 O(n)。且 map 目录读时还要
sort_by(cmp_coord),listat 无法直接命中。结论(见设计讨论):在「整体读写的 blob」语境里,B+树/skiplist 的局部更新价值兑现不了(插一个子项 body 整体重写),select 反而不如 offset 索引数组 的 O(1)。故采用 offset 索引数组。
方案:offset 索引数组
名单载体(index body 与 fs
__order__)统一改为:listlen= 读 count,O(1)listat(idx)= 切names[offset[idx]..offset[idx+1]],O(1),无 split、无全量物化insert/delete= body 整体重写(与现状同量级,offset 表 O(count) 重建,无额外结构维护)map 坐标序:map 目录存储即按坐标 row-major 升序(
add_child时二分插入维持有序),使 listat 对 map 也 O(1)、读路径零排序。非 map 目录保持插入序(追加)。ext_index:extpath 段照旧置于名单首段(
EXT_INDEX_HEAD前缀),纳入 offset 表第 0 项;count 仍只计 children。trait / ffi
list_len(dir, expand_ext, resolve) -> i32、list_at(dir, idx, expand_ext, resolve) -> Option<String>,直接解 body/order,不再全量list()。ffi.rs的kvspaceListLen/kvspaceListAt改调这两个原语(caller-owned buffer 语义已落地,库侧零状态不变)。list()仍保留(全量遍历 body,一次产出)。验证范围(本 issue)
tests/+ kvlang tutorial 以fs://与redis://全量回归,输出逐字节不变。关联