Page 425 - 《软件学报》2025年第5期

张志国 等: PLTree: 一个高性能持久化内存学习索引 2325

均存储在 PM 中, 元数据则存储在 DRAM 中负责维护叶节点和溢出缓存中键的指纹信息, 加速索引的查找. 内部
节点和叶节点存储了线性模型的信息. 在内部节点中 PLTree 消除了局部搜索, 因此可以通过模型定位指向下一层
子节点的槽位的准确位置. 叶节点中, 模型以数据块为粒度预测键值对存储的位置.

槽位 32 B
内部节点 M
minkey slope size leaf lock me v levelnum child
叶节点 8 B 4 B 4 B 1 bit 7 bits 6 B 1 B 2 B 6 B
M
元数据 内部节点 M 32 B
… … …
溢出缓存 模型 minkey slope size unused
DRAM 指针 M … M 8 B 4 B 4 B 16 B
叶节点头部信息
PM 指针
M … … … M minkey slope size flag fptr pre next1 next2
… …
数据块 block 256 B
… … …
H kv kv …
… …
PM 15 个 16 B
键值对
DRAM …
图 1 索引结构

2.1 内部节点
如图 1 所示, 内部节点存储在 PM 中. 其结构主要由两部分构成: 头部模型 M 和槽位数组. 内部节点模型根据
键预测子节点对应槽位的位置, 头部模型包括以下内容: 最小键 minkey (8 B)、单精度浮点数 slope (4 B) 表示模型
的斜率, 以及 size (4 B) 表示槽位数组的大小, 也代表节点的分支数量.
为了减少 PM 访问, 每个槽位都存储了其指向的子节点的模型信息. 因此, 在搜索过程中, 除了访问根节点需
要获取节点头部的模型信息外, 在向下搜索时无需访问子节点的头部信息, 通过模型准确定位, 每次只需访问内部
节点的一个槽位. 内部节点结构设计考虑了缓存友好性, 将头部模型和每个槽位大小统一设置为 32 B, 并确保内
部节点数据结构按 256 B 对齐. 根节点的大小最大限制为 256 B, 因此每个内部节点的访问只会读取 1 个 PM 块
(256 B), 且每次访问的数据范围不会超过一个缓存行 (64 B). 在当前的 AMD64 和 Intel® 64 架构中, 指针的有效位
为 48 位, 因此在槽位中只使用 6 B 存储指针信息. 其中 child (6 B) 为子节点的指针. 每个槽位中的 leaf (1 bit) 表示
所指向的节点是否为叶节点, 若 leaf 为 0, 则 child 指向内部节点, 并且槽位中的 minkey、slope 和 size 字段为所指
向的内部节点线性模型的参数. 当 leaf 为 1 时, child 指向叶节点, 此时 minkey、slope 和 size 字段是所指向的叶节
点中线性模型参数. 此外, 字段 me、v、levelnum 和 lock 只有在子节点为叶节点时有效, me (6 B) 为指向 DRAM
中元数据数组的指针, v (1 B) 存储所指向叶节点的版本信息, 用于系统崩溃后的索引恢复, levelnum (2 B) 存储了
所指向叶节点中所有溢出缓存的总层数, lock (7 bits) 为节点扩展时的叶节点锁.

2.2 叶节点
叶节点的结构如图 1 所示, 叶节点之间通过指针组成双向链表, 以支持范围查找和索引的恢复. 叶节点由头部
信息和数据块 (block) 数组两部分组成: (1) 头部信息存储了叶节点的模型参数信息, 包括斜率 slope、叶节点最小
键 minkey 和数据块数组的长度 size. 此外, 头部信息还包括一个指向前一兄弟叶节点的指针 pre; 两个备选兄弟节
点指针 (next1, next2) 用于指向下一个叶节点; 字段 flag 用于切换两个备选兄弟节点指针, 实现无日志叶节点修改;
字段 fptr 为指向父节点槽位的指针, 用于恢复时的一致性检查. (2) 数据块数组地址按 256 B 对齐. 其中各个 block
之间的键保持有序, 而 block 内部的键无需有序排列. 每个 block 的大小为 256 B, 其中头部 H (16 B) 中存储了指
向溢出缓存的指针, 当 block 不存在溢出数据时, 此指针为空. 剩余空间可以存储最多 15 个 16 B 的键值对, 键值对
由 8 B 的键和 8 B 的数据组成. 叶节点中数据的加载采用了 NVM 感知的数据放置策略 [24] , 即采用以 block 为粒度
的线性模型预测 block 的位置, 并将键值对以无序方式写入其中. 叶节点模型预测粒度设置为 256 B 的好处是可以