背景
memindex(p·,kind=index)承载目录成员名单。durable#18 已把它改成 offset 索引数组 [4B count][(count+1)×4B offset][names blob],listat/listlen 达到 O(1),但仍有两处不足:
- 非 map 目录名单按插入序存、无序 → 成员存在性只能 O(N) 线扫;
- redis 后端每次增删整块 GET+SET 重写。
durable#14 曾提议 redis 改原生 ZSET,但 ZSET 是后端专属结构,破坏「三后端同一 blob」契约,且 cmp_coord(整数坐标元组 row-major 序)无法干净编码进单一 f64 score。本 issue 用一个三后端通用、更简单的方案统一收口。
方案:定宽排序矩阵,几何塞进 kindexpr
memindex(kind=index)统一改为:
- head:
kindexpr = [N,M]index,复用 XValueHead 的 [dims] 段承载几何——N=成员数,M=行宽(当前全体成员 UTF-8 字节最大长度)。
- body:
N × M 字节。每行 = 成员名 UTF-8 + NUL 补齐到 M(UTF-8 永不含 0x00,NUL 补齐/终止安全)。
- 排序:全表按
cmp_coord 排序。cmp_coord 三档天然覆盖三种容器——数组 [0][1]… / map 坐标段 → row-major 数值序(顺带修掉「按字节把 [10] 排到 [2] 前」的错误);object 字符串键 → 落字符串兜底档 = 字典序。无需按容器 kind 分派比较器。
适用范围:index / object / stringkeymap 三种容器的 memindex(三者 memindex 均在 p·、kind=index;容器逻辑 shape 存在 p 值的头里,与 memindex 的 [N,M] 互不冲突)。
extindex = 矩阵 + 尾挂 ext_path(同一套,不割裂)
extindex(写时复制叠加层,运行时用作栈帧根)同样并入本矩阵:其本地 childs 是普通成员名,未来常是带自身 memindex 的容器、需要 listat / 有序能力,不降级为无序 hash。布局 = 矩阵 +1(+1 为 ext_path):
extindex body = [ ext_path 变长字节 ] + [ N×M 矩阵(childs,cmp_coord 有序) ]
head = [N,M]extindex # N=childs 数,M=childs 最大 UTF-8 宽
矩阵起点 off = body_len − N*M # body_len 在 head 唯一确定,无需额外长度字段
- ext_path 置 body 头部(offset 0):帧生命周期内 ext_path 一次写定、childs 才 churn,头部固定 → 矩阵起点稳定、增删只重建尾部矩阵、ext_path 字节不被矩阵重建触碰(shm 可原地);亦延续「ext_path 为 0 号元素」的既有心智模型。ext_path 通常远长于 M(如
/lib/main·add/),故作变长段、不占 M 宽的行。
- decode:ext_path =
body[..off];childs = 尾部 N×M 矩阵行 body[off..](有序,listat/listlen/二分与普通 index 完全一致),off = body_len − N*M。
list(expand_ext=true):本地矩阵 + base(ext_path 指向的 /lib/<func>/ 常规 index 矩阵)双侧有序归并、本地遮蔽 base、去重。
- 栈帧局部 churn 增量 O(N) 重建可接受——帧局部数量小而有界(参数 nr + 返回 nw + 少量
._litN),换来结构统一 + 全树有序能力。
复杂度
| 操作 |
复杂度 |
说明 |
| listlen |
O(1) |
读 head dims[0]=N,不碰 body |
| listat(idx) |
O(1) |
body[idx*M .. idx*M+M] 去 NUL |
| 成员存在 / 定位 |
O(log N) |
cmp_coord 二分 |
| 顺序遍历 |
O(N) |
顺读 |
| insert / del |
O(M·N) |
整块重建 |
设计取舍(已定):
- 丢弃 object 插入序,object 成员按名排序。
- stringmap 键长由生成侧(agent prompt)约束在合理范围,接受定宽 padding。M 是本目录最大长度,坐标 / 定长数组目录 padding≈0;只有「一个超长键 + 一堆短键」才浪费,这类目录通常小。
redis 线传收益
- listlen:GETRANGE 只取 head 前几字节。
- listat(idx):GETRANGE 单行 M 字节,O(1) 线传,不拉整块。
- 二分:每探一次 GETRANGE 一行,O(M·log N) 线传即可判存在性。
为什么不上树(取舍确认)
要同时做到「增量插入 O(log N) + 可位置无关序列化进 blob」,rank-augmented B-tree/skiplist、ART、succinct rank/select 等均需 blob 内分页 / 空闲空间管理或整块静态重建,复杂度高、逼近被明确排除的磁盘 B+ 树。目录「查多改少」前提下,本方案在 get / listat / 简单性 / 三后端一致性上全胜,代价仅 insert 的 O(n) 重建——取舍划算。
契约与分解
本 issue 为跨后端契约与总纲:shm / fs / durable(redis) 三后端必须实现同一 blob 布局与语义,listat / listlen / 顺序逐字节一致。存储侧 redis/shm 直接存该 blob,fs 于 get 时按 readdir 重建同格式 blob。
关联:supersedes array2d/kvspace-durable#18(offset 索引数组);取代 array2d/kvspace-durable#14 的 redis ZSET 方向(改用本统一 blob)。
背景
memindex(
p·,kind=index)承载目录成员名单。durable#18 已把它改成 offset 索引数组[4B count][(count+1)×4B offset][names blob],listat/listlen 达到 O(1),但仍有两处不足:durable#14 曾提议 redis 改原生 ZSET,但 ZSET 是后端专属结构,破坏「三后端同一 blob」契约,且
cmp_coord(整数坐标元组 row-major 序)无法干净编码进单一 f64 score。本 issue 用一个三后端通用、更简单的方案统一收口。方案:定宽排序矩阵,几何塞进 kindexpr
memindex(kind=index)统一改为:
kindexpr = [N,M]index,复用 XValueHead 的[dims]段承载几何——N=成员数,M=行宽(当前全体成员 UTF-8 字节最大长度)。N × M字节。每行 = 成员名 UTF-8 + NUL 补齐到 M(UTF-8 永不含0x00,NUL 补齐/终止安全)。cmp_coord排序。cmp_coord 三档天然覆盖三种容器——数组[0][1]…/ map 坐标段 → row-major 数值序(顺带修掉「按字节把[10]排到[2]前」的错误);object 字符串键 → 落字符串兜底档 = 字典序。无需按容器 kind 分派比较器。适用范围:
index/object/stringkeymap三种容器的 memindex(三者 memindex 均在p·、kind=index;容器逻辑 shape 存在p值的头里,与 memindex 的[N,M]互不冲突)。extindex = 矩阵 + 尾挂 ext_path(同一套,不割裂)
extindex(写时复制叠加层,运行时用作栈帧根)同样并入本矩阵:其本地 childs 是普通成员名,未来常是带自身 memindex 的容器、需要 listat / 有序能力,不降级为无序 hash。布局 = 矩阵 +1(+1 为 ext_path):
/lib/main·add/),故作变长段、不占 M 宽的行。body[..off];childs = 尾部N×M矩阵行body[off..](有序,listat/listlen/二分与普通 index 完全一致),off = body_len − N*M。list(expand_ext=true):本地矩阵 + base(ext_path 指向的/lib/<func>/常规 index 矩阵)双侧有序归并、本地遮蔽 base、去重。._litN),换来结构统一 + 全树有序能力。复杂度
dims[0]=N,不碰 bodybody[idx*M .. idx*M+M]去 NUL设计取舍(已定):
redis 线传收益
为什么不上树(取舍确认)
要同时做到「增量插入 O(log N) + 可位置无关序列化进 blob」,rank-augmented B-tree/skiplist、ART、succinct rank/select 等均需 blob 内分页 / 空闲空间管理或整块静态重建,复杂度高、逼近被明确排除的磁盘 B+ 树。目录「查多改少」前提下,本方案在 get / listat / 简单性 / 三后端一致性上全胜,代价仅 insert 的 O(n) 重建——取舍划算。
契约与分解
本 issue 为跨后端契约与总纲:shm / fs / durable(redis) 三后端必须实现同一 blob 布局与语义,listat / listlen / 顺序逐字节一致。存储侧 redis/shm 直接存该 blob,fs 于 get 时按 readdir 重建同格式 blob。
关联:supersedes
array2d/kvspace-durable#18(offset 索引数组);取代array2d/kvspace-durable#14的 redis ZSET 方向(改用本统一 blob)。