【图数据库内核】Neo4j record 系布局：节点、关系链、属性链与 dense group

第 02 篇把「原生指针链」写成代价位。本篇把隐喻落成可核对的固定记录：Community 默认的 aligned（以及弃用路径上的 standard）仍走 record-storage-engine 这套链表式布局。Enterprise 推荐的 block 故意减少 pointer chasing——但对照对象必须先讲清楚。

本文是「图数据库内核」系列第 3 篇（共 16 篇）。→ 系列目录

篇目	核心内容
第 2 篇 · 邻接代价	四种布局的统一代价语言
第 3 篇 · Record 系布局	固定记录字段、sparse/dense 链、一次 hop
第 4 篇 · Block format	128 B 主块与 dense 树（对照本篇）

版本锚定：源码 neo4j/neo4j 标签 5.26.0，模块 community/record-storage-engine，包 org.neo4j.kernel.impl.store.format.standard。产品身份见 Operations Manual Store formats：aligned → record-aligned-1.1；standard / high_limit 自 5.23 弃用。pageAligned=true 时逻辑记录仍是下列 RECORD_SIZE，页内对齐策略由 BaseOneByteHeaderRecordFormat 处理——本篇讲逻辑字段与指针语义，不展开页填充字节账。

一、record 系在产品地图上的位置

Operations Manual（current）把图数据存盘格式分成两类叙事：

SHOW DATABASES YIELD name, store 若看到 record-aligned-1.1，读路径就是本章。system 库在手册示例中亦可为 aligned——以环境为准。

设计母题（与官方 KB Understanding Neo4j’s data on disk 一致，B 级运维叙事；字段尺寸以下方 5.26 源码为准）：无全局 schema 宽表 → 定长记录 + id 即偏移 → 用指针把节点、关系、属性串成链表。Schema-less 的代价不是「没有类型」，而是局部性交给指针与 page cache。

二、定长记录：四种 RECORD_SIZE

standard 格式下（aligned 共用同一套 format 类，构造时传入 pageAligned）源码钉死的逻辑记录长度：

文件名在库目录里仍是经典的 neostore.nodestore.db、neostore.relationshipstore.db、neostore.propertystore.db、neostore.relationshipgroupstore.db 一族（KB 与运维文档口径；具体文件集合随版本可能附加 token / 动态 store）。

id 位宽（StandardFormatSettings，与手册 aligned/standard 实体上限一致）：

high_limit 放大若干指针宽度（本篇不展开字段打包）；block 的上限表见第 01 / 04 篇——不要把 block 的「关系无上界」套到 record 系上。

三、节点记录：15 字节里的两个入口

NodeRecordFormat 注释给出布局口诀：

in_use(byte) + next_rel_id(int) + next_prop_id(int) + labels(5) + extra(byte)  = 15 B

语义拆解：

1. in_use 与高位修饰位挤在首字节：nextRel / nextProp 的高位靠 header 位扩展（longFromIntAndMod），从而在 4 B 槽里塞进超过 32 位的 id。
2. nextRel：sparse 时指向关系链上的第一条关系记录；dense 时指向 relationship group 链（见第五节）。NodeRecord.toString 把二者分别标成 rel= / group=。
3. nextProp：指向该节点属性链的第一条 PropertyRecord；无属性则为 NO_NEXT_PROPERTY。
4. labels（5 B）：内联标签字段；装不下时走动态 label 记录（dynamicLabelRecords / heavy 路径）。标签不是每跳都要扫的边，而是节点上的集合——与关系类型过滤是两条路。
5. extra：最低位为 dense。RecordNodeCursor.relationshipsReferenceWithDenseMarker 会在 dense 时给引用打标，让后续 cursor 走 group 路径而非普通 rel 链。

flowchart LR
  N["NodeRecord<br/>15 B"] -->|"nextProp"| P["PropertyRecord 链"]
  N -->|"nextRel · sparse"| R["RelationshipRecord 链"]
  N -->|"nextRel · dense"| G["RelationshipGroupRecord 链"]
  G -->|"firstOut / firstIn / firstLoop"| R2["按类型拆开的 Rel 链"]

工程直觉：节点记录本身极小——15 B 只买两个「入口指针」加标签摘要。真正的图体积在关系 store 与属性 store。

四、关系记录：一条边，两条链上的节点

RelationshipRecordFormat.RECORD_SIZE = 34。注释中的字段骨架：

in_use / 高位修饰
+ first_node + second_node + type
+ first_prev_rel + first_next_rel
+ second_prev_rel + second_next_rel
+ next_prop
+ first-in-chain 标记字节

读路径上的不变量：

因此每条关系记录同时挂在两个节点的邻接结构里（loop 边则两侧指向同一节点）。KB 的概括仍准确：Each Relationship references its start and end node. It also references the previous and next relationship record for the start and end node respectively.

4.1 Sparse 节点：一条（逻辑）链扫过去

当 NodeRecord.dense == false：

Node.nextRel → Rel₀ ⇄ Rel₁ ⇄ Rel₂ ⇄ …

（实现上是双向链；上图略去 prev。）Expand 某类型 \(t\) 时，cursor 不能数学上跳过类型不等于 \(t\) 的链节点——必须读到该 RelationshipRecord 才能看 type 字段。这就是第 02 篇 \(\mathrm{Cost}_{\mathrm{ptr}}\) 里「非匹配边仍付 \(C_{\mathrm{rel}}\)」的物理来源。

链上记录的 id 不必空间连续：定长 store 里 id → id * RECORD_SIZE 偏移，逻辑相邻 ≠ 页内相邻。冷缓存时，度数 \(d\) 的 expand 可以变成接近 \(d\) 次随机页访问。

4.2 一次 hop 的最小指针剧本（sparse）

目标：从节点 \(v\) 取出类型 \(t\)、方向出边的对端。

1. 读 NodeStore[v] → 得 nextRel、确认非 dense。
2. rel = nextRel；当 rel != NO_NEXT：
   • 读 RelationshipStore[rel]；
   • 若类型/方向匹配，产出对端节点 id（及可选 nextProp）；
   • rel = getNextRel(v)（在 \(v\) 为 first 或 second 侧时选对应 next 字段）。
3. 若还要节点属性：另从对端 Node.nextProp 走属性链（与关系链正交）。

没有「边表二级索引叶页顺序扫」——除非你在 Cypher 层先用属性/标签索引缩小起点（第 7、10 篇）。

五、Dense：relationship group 把链按类型拆开

5.1 阈值

GraphDatabaseSettings.dense_node_threshold（配置名 db.relationship_grouping_threshold）默认 50：节点关系数达到阈值后按 dense 处理。源码描述原文：“Relationship count threshold for considering a node to be dense.”

官方开发者博文与社区答疑补充工程事实（B 级）：转为 dense 通常不随度数回落而逆转；关系链锁等并发优化也挂在 group 抽象上（第 11 篇再写锁）。本篇只钉存储形状。

5.2 Group 记录：25 字节

RelationshipGroupRecordFormat 注释：

[type + inUse + highbits, next, firstOut, firstIn, firstLoop, owningNode] = 25 B

一句话：一个 group = 某个 owning node 上、某一个 relationship type 的三条链头（出、入、自环），group 之间再串成 next 链。

Node (dense)
  └─ Group(type=A) → Group(type=B) → Group(type=C) → …
         │ firstOut / firstIn / firstLoop
         └─ Rel ⇄ Rel ⇄ …   （仅该 type + 该方向）

引入 group 的原始动机（历史提交 Splits relationship chains by type and direction 的说明）：按类型/方向过滤时，不必再加载无关类型的关系记录；链首还可承载计数，使按类型方向的度数查询走 \(O(1)\) 路径。这正是第 02 篇把「dense」从「更慢」改写成「有时更快」的条件——过滤类型时少读无效边；类型本身边数仍是 \(\Theta(d_{v,t})\)。

RecordNodeCursor：非 dense 时直接 relationshipCursor.init；dense 时 groupCursor.init(entityReference(), getNextRel(), …)，再按 RelationshipSelection 选类型与方向。

六、属性记录：41 字节 payload 链

PropertyRecordFormat：

RECORD_SIZE = 1 + 4 + 4 + 32 = 41

• 1 B：next/prev 高位等；
• 4 B next + 4 B prev：属性记录双向链；
• 32 B payload：划成四个 8 B PropertyBlock。

KB（B 级）对 payload 的填充规则仍是读属性时的实用心智：key+type 约占 3.5 B；小标量可与 key 同块；大 long/double 占整块；长字符串/数组指向 propertystore.db.strings / .arrays 的 128 B 动态记录；短串/短数组可内联进剩余 block。

节点与关系各自有一条属性链（Node.nextProp / Relationship.nextProp）。因此：

[ () + () + () ]

block 格式把「属性与节点/关系共置」写成优化目标（手册原文）——对照意义在第 4 篇：record 系里属性几乎总是另一次指针追逐。

七、aligned vs standard vs high_limit（record 家族内）

对阅读内核的人：aligned 与 standard 的指针故事相同；差别在页对齐与产品默认，不在「是否还有 nextRel 链」。把时间花在 sparse→dense 分叉上，比纠结 aligned 多出来的填充字节更值。

八、和代价模型对齐的三句收束

1. Sparse expand：读 1 个 Node + 链上每条 Rel（含类型不匹配者）+ 可选属性链；随机性来自 id 散列到页。
2. Dense + 类型过滤：读 Node + 扫描/定位 Group 链至目标 type + 只扫该方向 Rel 链；无效类型的 Rel 记录可跳过。
3. Dense 也不消灭超节点：某一 [:FOLLOWS] 若本身挂千万条边，group 只是把爆炸关进「正确的房间」——输出基数与下游算子仍会炸（第 9–10、15 篇）。

九、学术与工程谱系（短）

1. 定长记录 + 指针：与早期图数据库「native」叙事同源——把邻接写成一等磁盘结构，而不是边表行。Angles & Gutierrez（CSUR 2008）停在模型层；record store 是工业落点。
2. 按类型拆链（group）：是对「单链扫类型」的工程反驳——承认幂律与多类型并存时，类型成为一等过滤键（提交说明与后续关系链锁博文同一谱系）。
3. 开放争论：record 链表 vs block 内联——兼容性与工具链 vs 局部性。Neo4j 产品答案是 EE 推向 block，但 Community 与存量 record-aligned-* 使本章长期有效。
4. 未写：page cache 计量（第 5 篇）、写入时如何改链与升 dense（第 6 篇）、block 文件布局（第 4 篇）。

十、来源与实验台账（本篇）

十一、小结

1. record 系 = 定长记录 + 多条链表：节点 15 B 只持入口；关系 34 B 同时串进两端邻接；属性 41 B 另链；dense 时插入 25 B group 按类型分桶。
2. 一次 hop：sparse 扫整链；dense 先找 group 再扫类型链——类型过滤的收益来自少读，不来自魔法压缩度数。
3. 对照 block 的理由：本篇每一跳「Node → Rel → Prop」的指针次数，就是第 4 篇内联要消掉的对象。
4. 下一篇：block.x1.db 128 B 主块、动态 store 与 dense B+ 树如何改写上述剧本。

→ 系列目录 · 上一篇：邻接代价 · 下一篇：Block format