【图数据库内核】写入路径：建边、升 dense、逻辑删除与 ID 复用

第 03–05 篇把读路径钉在布局与 page cache 上。写路径改的是同一套结构：挂链、升 dense、弄脏页、把删除变成可复用的 id。本篇回答：一条关系如何写进 store、空间何时还给 OS、以及「删了又建」为何会让第 05 篇的随机 fault 变本加厉。 锁与隔离的细账留给第 11 篇。

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

篇目	核心内容
第 3–5 篇 · 布局与 cache	读路径坐标系
第 6 篇 · 写入路径	建边 / dense / 删除 / ID 复用
第 7 篇 · 索引与约束	写路径上的另一类维护

版本锚定：Operations Manual（2026.07 / current）Space reuse、Concurrent data access（dense 定义与写锁边界）。源码：neo4j/neo4j 5.26.0 org.neo4j.internal.recordstorage.RelationshipCreator / RelationshipModifier；GraphDatabaseSettings.dense_node_threshold（db.relationship_grouping_threshold，默认 50）。Block 大值碎片复用行为见手册 Space reuse（2026.01 引入说明）。

一、写事务在改什么

一次成功提交的写，至少碰三层：

flowchart LR
  Cypher["CREATE / DELETE"] --> Tx["Transaction state"]
  Tx --> Cmd["Record commands"]
  Cmd --> Store["Store files via page cache"]
  Cmd --> Log["Transaction log"]
  Cmd --> Ids[".id free-list / high id"]

读路径看到的「指针链 / 主块」是这些命令的稳态投影。下面按 record 系建边（源码可钉）讲主干，再对照 block 与 空间复用。

二、创建关系：sparse 挂链

RelationshipModifier.modifyRelationships 在拿锁之后调用 RelationshipCreator.relationshipCreate（5.26.0）。单条创建的骨架：

1. 对两端节点各调用 convertNodeToDenseIfNecessary（见第三节）。
2. 分配/写入一条 RelationshipRecord（id、type、两端、属性）。
3. connectSparse 或 dense 连接：把新边挂进两端邻接结构。

2.1 Sparse：插到链头

connectSparse 的核心动作（读源码语义，非伪代码臆造）：

• 若节点尚无关系：新边成为 Node.nextRel，度数相关字段从 1 起。
• 若已有链头 firstRel：把新边的 next 指向旧链头，旧链头的 prev（该侧）指向新边，并更新「是否链首」标记；链首上的 prev 槽位还承载度数计数（创建时 newCount = firstPrev + 1 一类逻辑）。

结果：高频写入下，新边偏向成为逻辑链头。若 id 分配也偏向高水位递增，短时间窗口内「新边 id ≈ 相邻」——这是第 05 篇「热写后热读可能同页」的来源。一旦大量删除后复用旧 id（第四节），这种时间局部性会被打碎。

2.2 两端各挂一次

每条有向边在 first/second 两侧各改一套 prev/next（第 03 篇）。因此「加一条边」的写放大下界是：

[ (1)  + (1)  ]

外加可选属性记录与索引维护（第 7 篇）。不是「插入边表一行」的单点更新。

三、升 dense：单向改造

3.1 阈值与不可逆

配置：db.relationship_grouping_threshold / dense_node_threshold，默认 50。

手册 Concurrent data access（A 级）：

• 节点若在任意时刻达到过阈值关系数，即视为 dense；即使后来边变少，仍视为 dense。
• 从未超过阈值者视为 sparse。
• 另有「按关系类型接近约 50 条（还受关系属性体积影响）可视为该类型 dense」的叙述——与 block 的类型级落点（第 04 篇）及并发结构一致；record 系源码里整点 Node.dense 比特仍由 RelationshipCreator 在总度数达阈值时翻转。

3.2 convertNodeToDenseNode 做什么

当 convertNodeToDenseIfNecessary 发现非 dense 且 relCount >= denseNodeThreshold：

1. node.setDense(true)，nextRel 先清空为无关系哨兵。
2. 遍历原 sparse 整链，把已有关系按类型/方向重新挂到 relationship group 结构上（connectDense 路径）。
3. 之后新边走 connectRelationshipToDenseNode → 取/建对应 type 的 group → 插入该方向链。

这是一次读改写放大：升 dense 的事务可能重写该点历史上所有关系记录的链接字段。阈值不是「读路径开关」而已，而是写路径上的结构迁移点。

RelationshipModifier 在加锁阶段若预判「当前度数 + 本事务新建数 ≥ 阈值」，会提前按即将 dense 的路径取锁（checkAndLockRelationshipsIfNodeIsGoingToBeDense）——细节第 11 篇；本篇记住：逼近阈值的写入比稳态 sparse 追加更贵、锁更重。

3.3 并发语义（预告）

手册：创建/删除关系时，不对 dense 节点在事务中持排他节点锁的同一套严格模式；用共享锁防止删点、用度数相关共享锁与标签变更同步。Dense 把度数放进更适合并发的结构，从而在几乎所有关系修改上避开排他节点锁。Sparse 的主要争用往往就是度数/链头更新。这解释了为何超节点写入「有时反而更能并」——代价是已经付过升 dense 的结构税，且读路径变成 group/树（第 03–04 篇）。

四、Block 写入：填主块、溢动态、进 dense 树

Block 没有公开到与 RelationshipCreator 同级的 Community 源码叙事时，以手册布局约束推导写动作（第 04 篇 A 级事实）：

相对 record：升「类型级 dense」更接近「该类型从 xd 溢出到树」，而不是必须先把整点翻成单一 dense 比特再拆 group——但运维文档里的「dense / sparse 节点」并发语义仍然适用。动态记录「随增删变尺寸并可能重定位」意味着写路径会主动搬数据以换取装填率；这是读缓存友好与写放大之间的显式交换。

2026.01+（手册 Space reuse）：big_values 在找不到足够大的连续空闲 id 时，可将大值拆成多段较小记录以强制复用空间，牺牲部分共置；碎片容忍度随未用空间比例动态上升（未用 \(<5\%\) 时偏不碎片化）。写负载若「分配尺寸单调变大」，旧行为曾使文件无效膨胀；新策略把第 05 篇的局部性与空间复用再拧紧一档——有环境再测，正文不报倍数。

五、ID 分配与逻辑删除

5.1 分配：高水位或复用

IdGenerator.nextId 语义（id-generator 模块文档/接口）：返回值要么是此前最高已分配 + 1，要么是已删除且可再分配的 id。Store 文件按 id 定址（record：id * RECORD_SIZE；block x1：id * 128）——复用 id 即复用文件洞，而不是把文件截断。

5.2 删除：标删，不还给 OS

手册 Space reuse 核心不变量：

1. 逻辑删除：相关记录标为 deleted，占用空间不立即退回操作系统。
2. 删除同样写 transaction log 命令；大批 DETACH DELETE 会撑大事务内存状态与日志（手册警告），日志随后按保留策略修剪，但 store 文件不因删除缩小。
3. 可复用 id 记在对应 .id 文件（例：neostore.nodestore.db.id 或 block.x1.db.id）。
4. 提交删除时 id 先在内存缓冲，并跟踪与未完成事务的重叠；重叠结束才真正可复用。缓冲在 checkpoint 时刷入 .id；恢复与集群靠事务命令推断 .id 变更，保证与 store 一致。
5. 禁止手工删 .id 或直接改 store；收缩靠官方工具路径。

5.3 复用如何反咬读局部性

删除后若持续创建，分配器优先吃 free-list → 新点/新边获得旧 id → 文件体积可稳住，但：

• 逻辑上「刚创建的边」在文件里可能落在古老、远离当前高水位的页；
• sparse 链头插入仍按指针链接，时间局部性 ≠ 空间局部性；
• page cache 工作集从「尾部热带」变成「全文件洒点」——第 05 篇随机指针颠簸的经典诱因之一。

运维上「删光再灌」若只看磁盘用量下降，会误判；看 store 是否稀疏 + hit_ratio 才对齐机制。

5.4 真要还给文件系统时

手册路径：neo4j-admin database copy 做碎片整理式拷贝（示例含 --compact-node-store），生成新库；集群需按文档重 seed。Copy 跳过未使用记录，高水位可回到紧凑区间。这是离线/运维动作，不是在线 DELETE 的副作用。

手册示例叙事（数字为文档演示，非本站实测）：删除大量节点并 checkpoint 后，store size 与 ID Allocation 高水位可仍停在删除前量级；copy 之后新库高水位归零量级、体积回到紧凑值。

六、写放大清单（排障入口）

七、与系列坐标系闭合

八、争论与开放问题

1. 逻辑删除 vs 立即压实：A 侧要提交吞吐与崩溃简单性；B 侧要磁盘与扫描局部性。Neo4j 选 A，把压实交给 copy/运维窗口。
2. 阈值 50：过低则过早付 group/树税；过高则长链随机读与锁争用并存。手册默认与源码默认一致；调参需同时看读延迟与升 dense 尖峰。
3. 开放问题：block 动态重定位与 Muninn 驱逐的交互频率；多库共享 page cache 时写脏页干扰；id 复用策略是否应对「扫描友好」提供可选模式——未在本站证实前不写进结论。

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

十、小结

1. 建边 = 分配 Rel + 改两端邻接（sparse 插链头或 dense 入 group/树）；逼近阈值会触发整链重挂的升 dense。
2. 删除 = 标删 + 记入 .id，不还给 OS；空间靠后续创建复用，或靠 database copy 压实。
3. 复用稳定体积，却可能毁掉时间局部性——写路径直接塑造第 05 篇的 fault 形状。
4. 第一部分（01–06）收束：模型 → 代价 → record → block → cache → 写。下一篇进入索引：标签/类型/属性索引如何改变「从哪里开始走」。

→ 系列目录 · 上一篇：Page cache · 下一篇：索引与约束