Skip to content

memindex 子项名单改 offset 索引数组:listat(idx) O(1)(先 redis/fs 验证) #18

Description

@miaobyte

背景

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\nfs/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) -> i32list_at(dir, idx, expand_ext, resolve) -> Option<String>,直接解 body/order,不再全量 list()
  • ffi.rskvspaceListLen/kvspaceListAt 改调这两个原语(caller-owned buffer 语义已落地,库侧零状态不变)。
  • list() 仍保留(全量遍历 body,一次产出)。

验证范围(本 issue)

  • 先在 redisfs 两后端验证;shm(kvspace-c)不在本次改动,frontend ABI 不变,应保持通过。
  • durable 自身 tests/ + kvlang tutorial 以 fs://redis:// 全量回归,输出逐字节不变。

关联

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions