图数据库存储引擎深度实战：从免索引邻接、点边切分分区到 Cypher/GQL 执行计划的工程全解

图数据库存储引擎深度实战：从免索引邻接、点边切分分区到 Cypher/GQL 执行计划的工程全解

关系型数据库把世界切成一张张二维表，查询时用 Join 把碎片重新拼回去。而现实世界里，社交关注、资金流向、服务调用依赖、供应链级件清单——这些数据的本质是关系本身。当一条查询从"三表 Join"变成"六跳好友的好友的好友"时，关系库的代价是灾难性的：每一跳都是一次 Index Nested Loop Join，代价随深度指数爆炸。

图数据库的价值就在于把"关系"从需要计算的东西，变成可以直接物理寻址的东西。这篇文章拆开图数据库的三层核心：存储布局、分布式分区、执行计划，并给出可落地的工程判断。

一、免索引邻接：把指针写进磁盘

图数据库最关键的存储决策叫 Index-Free Adjacency（免索引邻接）。在关系库里，follows 表存 (src_id, dst_id)，要找 A 的关注者必须走 B+ 树索引，O(log N) 一次，多跳就是多次。而在原生图存储里，每个节点记录里直接保存它的邻接边在文件中的物理偏移量，遍历一条边是一次 O(1) 的数组寻址加一次顺序读。

一个典型的定长存储布局长这样：

Node Record (fixlen 15B):
  [ in_use:1b | next_rel_id:35b | next_prop_id:36b | label:4B ]

Relationship Record (fixlen 34B):
  [ in_use:1b | first_node:35b | second_node:35b | rel_type:4B
    | first_prev_rel_id:35b | first_next_rel_id:35b
    | second_prev_rel_id:35b | second_next_rel_id:35b
    | next_prop_id:36b ]

注意 Relationship Record 里有四个指针字段：以 first_node 视角的 prev/next，以及以 second_node 视角的 prev/next。这不是冗余，而是把邻接表做成了双向链表，从而支持 O(1) 的正向与反向遍历。这是图数据库能在毫秒级回答"谁关注了我"和"我关注了谁"两个方向问题的物理基础。

用 Rust 描述这个游标，核心就是一个偏移量追逐：

// 简化的邻接游标：沿 first_next_rel_id 链前进
struct RelCursor<'a> {
    store: &'a RelStore,
    cur: RelId,          // 35 位物理记录号
    dir: Direction,
}

impl<'a> Iterator for RelCursor<'a> {
    type Item = (NodeId, RelId);
    fn next(&mut self) -> Option<Self::Item> {
        if self.cur == NULL_REL { return None; }
        // 定长记录 → 直接 offset 计算，无索引查找
        let rec = self.store.read_at(self.cur)?;
        let (peer, next) = match self.dir {
            Direction::Out => (rec.second_node, rec.first_next_rel_id),
            Direction::In  => (rec.first_node,  rec.second_next_rel_id),
        };
        self.cur = next;
        Some((peer, self.cur))
    }
}

工程含义：定长记录意味着 offset = id * RECORD_SIZE，不需要任何间接层。代价是每条边无论带不带属性都占 34 字节，且删除后产生空洞——所以需要 .id 文件的空闲链表（freelist）复用。这个设计的另一个后果是：图数据库的节点/边 ID 是物理地址，不是逻辑键。业务主键必须自己建索引映射到内部 ID，而 ID 复用会导致悬空引用，这也是为什么生产级图库普遍把 ID 空间做成单调递增不复用（Neo4j 4.x 之后废弃了 ID 复用）。

二、属性存储：定长骨架 + 变长溢出

节点和边的属性不能塞进定长记录，否则 schema 就锁死了。常见做法是属性链（property chain）：定长记录里存 next_prop_id，属性本身存在独立的 Property Store，每个属性记录也是一个链表节点。

Property Record:
  [ in_use:4b | type:4b | key_id:24b | payload:8B(内联或指针) | next_prop:36b ]

关键优化是 payload 内联：long/double/boolean/短字符串（≤7 字节）直接塞进 8 字节 payload，避免一次额外的随机 I/O。长字符串、数组、地理坐标则溢出到 Dynamic Store，payload 存指针。这个策略与 PostgreSQL 的 TOAST、MongoDB 的 inline document 是同一个思想：让热字段留在主记录里，代价是记录变宽、缓存命中率下降。

这里有个反直觉的调优点：如果图查询 90% 只关心 2 个属性，那么"把属性全打散到链表"比"列式存放"更慢，因为每次要顺着链表读 20 个属性记录才能拿到想要的 2 个。工业界（如 TigerGraph、Neo4j 的 property block 演进）的方向是把高频属性提升为节点内的定长列，把链表退化为冷属性的溢出区。

三、分布式分区：边切分 vs 点切分

单机装不下大图时必须分区，而图分区比 KV 分区难得多，因为边把两个分区绑在了一起。

边切分（Edge-Cut）：点分配给某个分区，跨越分区的边被"切开"，两端各存一份。Neo4j Fabric 早期、JanusGraph 默认策略属此类。遍历跨分区边要走网络 RPC。

点切分（Vertex-Cut）：边分配给某个分区，被切开的是点——一个超级节点会被复制到多个分区。PowerGraph、现代的 PowerLyra 采用此策略。

判断标准非常明确，看图是否符合幂律分布（power-law）：

# 用度数分布判断切分策略
import collections

def recommend_cut(degree_seq):
    d = sorted(degree_seq, reverse=True)
    total = sum(d)
    top1 = d[0] / total
    top01 = sum(d[:max(1, len(d)//1000)]) / total
    if top01 > 0.20:
        # 极少数点占了 20%+ 的边 → 边切分会产生巨型热点
        return "vertex-cut + 度数感知哈希"
    return "edge-cut + 社区发现分区"

社交网络、Web 链接图几乎一定是幂律：1% 的节点占 30% 以上的边。此时边切分下那 1% 的超级节点会成为单点热点（所有跨分区遍历都要打过去），而点切分把它们的边摊到所有分区，代价是点副本的一致性维护。

实践中更常用的是 HDRF（High Degree Replicated First） 这类流式贪心分区器：对每条边 (u, v)，把边放到"已持有 u 或 v 副本最多、且当前负载最轻"的分区，并优先复制度数高的点。它的核心打分函数是：

score(p) = (u∈p ? 1 + (1 - deg(u)/(deg(u)+deg(v))) : 0)
         + (v∈p ? 1 + (1 - deg(v)/(deg(u)+deg(v))) : 0)
C(p) = score(p) + λ * (max_load - load(p)) / (max_load - min_load + ε)
选 argmax C(p)，λ 平衡局部性与负载均衡

这个算法的巨大优势是单次流式扫描、O(1) 内存、可增量接入新边，不需要 METIS 那种全图离线重分区。代价是分区质量比离线 METIS 略差（边切比通常高 10~20%），但换来的是在线可用性。

四、Cypher 与 GQL：声明式图查询如何变成执行计划

Cypher 的模式匹配语法本质是图同态搜索的声明式描述：

// 找出 A 的三跳内、买过同一商品、且未被风控标记的用户
MATCH (a:User {id: $uid})-[:FOLLOWS*1..3]->(b:User)
      -[:PURCHASED]->(p:Product)<-[:PURCHASED]-(c:User)
WHERE NOT (c)-[:RISK_FLAGGED]->()
  AND c <> a
RETURN c.id, count(p) AS common
ORDER BY common DESC
LIMIT 20

优化器把它编译成一棵算子树。理解执行计划是图库调优的第一生产力：

+--------------------------+----------------+
| Operator                 | Est. Rows      |
+--------------------------+----------------+
| +ProduceResults          |             20 |
| +Top(20, common DESC)    |             20 |
| +EagerAggregation        |           8.4k |
| +AntiConditionalApply    |           42k  |
| |\+Optional(risk)        |           42k  |
| +Filter(c <> a)          |           42k  |
| +Expand(Into) (b)-[PURCHASED]->(p)        |
| +VarLengthExpand(Pruning, 1..3)           |
| +NodeIndexSeek(a:User(id)) |            1 |
+--------------------------+----------------+

三个必须认识的关键算子：

1. NodeIndexSeek：入口锚点。一定要让查询从一个有索引的选择性锚点开始，否则会退化成全图扫描 AllNodesScan——这是图库里最贵的操作，没有之一。
2. VarLengthExpand(Pruning)：变长跳变。Pruning 变体在"只要终点不要路径"时启用，只维护去重的终点集合，内存从 O(路径数) 降到 O(节点数)。路径数在稠密图上是指数级的，这个差异可能是 100MB 和 100GB 的区别。
3. Apply / ConditionalApply：图查询里的"嵌套循环"。Apply 表示对左子树每一行执行一次右子树。看到 Apply 且左子树行数巨大时，就要考虑能否改写成 Expand(Into) 或用半连接（semi-join）提前剪枝。

基数估计是图优化器最难的部分。关系库假设列独立，图库里这个假设错得更离谱——"FOLLOWS 关系的选择率"和"当前节点的度数"强相关。主流做法是为每种 (label, rel_type, label) 三元组维护直方图 + 平均度，用 (A→B 边数 / A 节点数) 作为度估计，多跳时连乘。一旦估计偏 10 倍，Join 顺序就会错得离谱，因此生产上常备的手法是：

// 用基数提示强制枚举顺序，绕开估计失准
MATCH (a:User {id: $uid})-[:FOLLOWS]->(b)-[:PURCHASED]->(p)
USING INDEX a:User(id)
USING JOIN ON b          // 强制在 b 上做 hash join 而非逐点展开
RETURN p

2024 年 ISO 发布了 GQL（Graph Query Language） 标准（ISO/IEC 39075），它把 Cypher 作为主要输入，同时纳入了 SQL/PGQ（在 SQL 里写图模式匹配）。这意味着图查询正在从"各家方言"走向标准化，Oracle、SQL Server 已经支持 SQL/PGQ。选型时的现实建议是：如果图查询只是分析场景的补充，优先用 SQL/PGQ 或图计算库；只有需要低延迟多跳在线遍历时，才上原生图库。

五、生产落地的五个硬经验

1. 可控跳数优先于变长跳数。 *1..3 在小图上很快，在亿级图上会瞬间吃满内存。生产服务应把跳数上限硬编码到查询模板里，并对 *n..m 做拦截。
2. 为超级节点做特殊建模。 一个百万粉丝的大 V 节点，展开一次就是百万条边。常见做法是"关系分桶"：把 FOLLOWS 按时间或 hash 拆成 FOLLOWS_2024Q1 等多个类型，或引入中间聚合节点打散扇出。
3. 别把图数据库当主存储。 属性值仍应回源到 KV 或关系库，图库只存拓扑 + 少量过滤属性。这能把存储成本降一个数量级，也让图库的内存 cache 命中率大幅提升。
4. 写放大来自指针维护。 插入一条边要更新 4 个指针字段 + 2 个节点记录，在机械盘上是 6 次随机写。批量导入务必走离线 bulk loader（先排序再顺序写），不要走在线事务路径。
5. PageCache 命中率决定一切。 图遍历的随机性意味着 cache 命中率就是吞吐。经验法则是热子图（20% 的点边）必须完全驻留内存，否则 P99 会抖动到秒级。

结语

图数据库的本质不是"另一种查询语言"，而是一次存储布局上的取舍：牺牲了通用性和写入效率，换取了关系遍历的 O(1) 物理寻址。理解这一点，才能做出正确的判断——什么时候该上图数据库，什么时候一个带递归 CTE 的 PostgreSQL 就够了，什么时候干脆上 Spark GraphX 做离线全图计算。

真正值得投入的，是把"关系"作为一等公民建模的能力：当你的业务问题从"有多少用户买了 A"变成"哪些用户经由哪些路径影响了这批人"时，图已经不是可选项，而是唯一合理的答案。