【图数据库内核】邻接的代价模型：边表 JOIN、CSR 与原生指针为何不是同一件事

第 01 篇把生态位钉在「拓扑一等公民」。本篇只回答一个更窄的问题：同一张逻辑图，落成边表、CSR、原生指针链或 block 内联时，一次 hop 与 \(k\) 跳扩张分别在付什么账？ 不粘贴未跑的延迟数字；不宣称某一引擎「永远更快」。

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

篇目	核心内容
第 1 篇 · 图引擎全景	生态位与五条坐标系
第 2 篇 · 邻接的代价模型	四种布局的统一代价语言
第 3–4 篇 · Record / Block	把本篇「指针 / 内联」落到文件格式

版本锚定：布局对照以第 01 篇所引 Neo4j Operations Manual Store formats（current）为工业锚点；代价推导为方法模型。CSR / 边表讨论不绑定单一开源版本号。

一、先固定「一次 hop」指什么

在属性图里，一次 hop 指：从已知节点集合 \(S\)，按方向与关系类型（可选属性谓词）取出邻居集合 \(N(S)\)。

记号：

• \(|V|\)、|E|$：点、边规模。
• \(d(v)\)：点 \(v\) 的度数（出度或入度，按方向计）。
• \(\bar{d}\)：平均度；\(d_{\max}\)：最大度。
• \(k\)：路径长度（变长路径上界）。

渐近下界：写出 \(N(v)\) 至少要碰触 \(\Theta(d(v))\) 条边信息——任何布局都逃不掉。差异在常数、局部性、更新代价，以及优化器是否低估 \(d(v)\)。

幂律图上 \(\bar{d}\) 很小而 \(d_{\max}\) 极大：平均路径的代价叙事会被少数超节点支配。这是后文「大 O 相同、事故不同」的根源。

二、四种布局，同一逻辑图

假设逻辑模式：节点带标签与属性；有向关系带类型与属性。下面四种是工程上最常对照的物理落点。

2.1 边表 + 二级索引（关系库默认路径）

典型 DDL 心智（示意，非某一产品 DDL）：

-- 示意：边表 + 按起点的二级索引
CREATE TABLE edge (
  src   BIGINT NOT NULL,
  dst   BIGINT NOT NULL,
  typ   INT    NOT NULL,
  -- 关系属性列以实际 schema 为准
  PRIMARY KEY (src, typ, dst)  -- 或单独 edge_id
);
CREATE INDEX edge_src_typ ON edge (src, typ);

一次 hop（从 \(v\) 出发、类型 \(t\)）：

1. 用 (src, typ) 索引定位到叶页范围；
2. 扫描该范围内所有 (v, t, *)；
3. 若还要节点属性，再回表或 JOIN node。

代价直觉：

[ {}(v,t) C{} + C_{}|E(v,t)| + C_{}|N(v,t)| ]

其中 \(C_{\mathrm{idx}}\) 含 B-Tree 下降；\(C_{\mathrm{scan}}\) 受叶页是否顺序、是否缓存命中支配。多跳时每层重复「索引探测 + 可能回表」；\(k\) 跳若扇出被低估，优化器可能选出 nested loop 多层展开——计划树每个算子局部合理，乘积不合理。

优点：事务、备份、SQL 生态、部分索引与约束现成。
坑：多跳把「点的局部性」拆成「多次索引探测」；递归 CTE 语义正确不等于 I/O 局部。

2.2 CSR / 压缩邻接（只读分析友好）

Compressed Sparse Row 一类布局：

• off[0..|V|]：每个点的邻接在数组中的起止；
• adj[]：邻居 id（可另存 type[] / 边属性列式旁路）。

一次 hop：读 off[v]、off[v+1]，切片 adj——顺序内存/顺序页，极适合批量 BFS、PageRank 式扫描。

[ {}(v) C{} + C_{}d(v) ]

优点：只读分析吞吐量高；实现简单。
坑：插入/删除边常常触发数组搬移或双重缓冲；属性图的「边属性、双向、多类型」要额外结构，很快不再是教科书 CSR。生产图库很少把可变属性图做成单一全局 CSR，但 block/dense 内部的树或数组切片会借用同一「顺序扫邻居」直觉。

2.3 原生指针链（Neo4j record 系心智）

经典 record 叙事（第 3 篇钉字段；此处只留代价位）：

• 节点记录持有指向某条关系记录的指针（及 property 指针）；
• 关系记录持有两端节点、类型、以及同节点上前驱/后继关系指针，形成每点一条（或按组）关系链；
• 属性另链。

一次 hop：读节点 → 跟到首条关系 → 沿链过滤类型/方向 → 取对端节点（属性再另追）。

[ {}(v,t) C{} + {e (v)} (C{} + {e} + {e}C_{}) ]

关键点：链上每条关系都可能是一次随机页访问（缓存未命中时）。类型过滤不能跳过「不属于 \(t\) 的链节点」的读取——除非存在按类型拆链或 group（record 系的 relationship group / dense 机制正是为此）。

优点：单点起步、局部更新不必重写全局数组；与事务日志、记录级空间回收同一套 id 分配故事。
坑：度数升上去后，链式追逐把「\(\Theta(d)\) 边信息」放大成「\(\Theta(d)\) 次可能随机 I/O」；\(d_{\max}\) 节点成为系统病灶。

2.4 Block 内联 + 动态 / dense 溢出（Neo4j block 心智）

第 01 篇已钉手册事实：节点主块 128 B（block.x1.db，offset \(=128\times\mathrm{nodeId}\)），内含节点侧与关系侧各 64 B；装得下则同块内联标签、属性与少量关系；溢出进动态 store；关系过多进 dense 多根 B+ 树（按类型与方向）。

代价分层：

手册主张 block 用共置降低 pointer chasing、减少服务查询所需页数——这是布局目标，不是本站实测。本篇把它收成模型：\(\mathrm{Cost}_{\mathrm{block}}\) 在小度数区逼近 CSR 切片常数，在 dense 区逼近「按类型的有序检索」，两端都刻意逃离「无类型过滤的长链逐条随机读」。

三、统一比较：\(k\) 跳扩张

设每层平均有效扇出为 \(f\)（已含类型过滤后的平均出度）。无优化、无共享前缀时，访问的边数级为：

[ |E_{}| _{i=0}^{k-1} |S|f^{i} ]

工程判断（非 benchmark）：

1. 若工作负载是深度多跳、点查驱动、度数中低，原生内联/指针布局的局部性故事才站得住。
2. 若工作负载是全图扫描式分析，CSR / 列式邻接往往更直接——许多团队用「OLTP 图库 + 导出分析」而不是逼 OLTP store 跑 PageRank。
3. 若工作负载是少跳 + 强过滤（先用属性索引缩到很小 \(|S|\)），边表路径经常「够用」——争论应落在 \(k\)、\(f\)、\(d_{\max}\)，而不是品牌。

四、超节点：把平均值故事撕开

设 \(d(v^\star)=d_{\max}\gg \bar{d}\)。

• 边表：edge_src_typ 上 \(v^\star\) 的叶页范围可以很长，但仍是顺序叶扫；痛苦在输出基数与上层算子。
• 指针链：同一范围变成长链随机读；dense/group 出现之前，这是经典事故形态。
• CSR：扫很长一段 adj——顺序，但单点 BFS 层会爆内存与下游。
• block dense：按类型进树，避免「为了找类型 \(t\) 而走过所有类型」；并不消灭「类型 \(t\) 本身有亿级边」的输出爆炸。

排障含义（第 15 篇展开）：先问「是不是某个点/某种类型的扇出」，再问「是不是计划选错」。代价模型若只用 \(\bar{d}\)，两种问题都会被平均掉。

五、更新代价：分析布局与 OLTP 布局的分叉

选型时把「读 hop」和「写边」拆开：很多「图需求」其实是偶发多跳查询 + 频繁点属性更新——此时边表或混合架构可能更合理。反之，边高频写入且查询是多跳模式匹配，才更接近原生图引擎的舒适区。

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

1. 图数据模型：Angles & Gutierrez（ACM CSUR 2008）等把「图接口」从关系模型旁路出来——本篇关心的是旁路之后存储不变量是否也旁路。
2. 稀疏图表示：CSR/CSC 来自科学计算与图分析传统；Graph 系统论文常把「邻接是否顺序存放」当作吞吐一等变量。
3. 原生图工程争论：工业界长期存在「多跳是否必须原生」——A 侧强调指针/内联局部性；B 侧强调 SQL 引擎 + 良好索引/物化路径。本系列立场：用本节代价表把争论落到 \(k\)、\(f\)、\(d_{\max}\)、更新频率四个旋钮上，拒绝无工作负载的快慢宣言。
4. 开放问题：幂律下的代价模型如何进入优化器（第 10 篇）；block 在开源/企业能力边界上如何标注（产品事实，随版本变）。

七、回指五条坐标系

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

九、小结

1. 大 O 不够：四种布局读邻居都是 \(\Theta(d)\) 边信息；差在探测次数、顺序性、类型过滤是否避免无效读、以及更新是否打爆结构。
2. 幂律决定事故形态：\(\bar{d}\) 叙事掩盖 \(d_{\max}\)；超节点在链、叶扫、dense 树上的表现不同，但都会炸下游基数。
3. 选型旋钮：\(k\)、\(f\)、\(d_{\max}\)、边更新频率——先填这四个，再谈原生图或 CTE。
4. 下一篇：把 record 系节点/关系/属性记录的指针场钉到可核对的字段叙事上，让「链」从隐喻变成布局。

→ 系列目录 · 上一篇：全景 · 下一篇：Record 系布局