FalkorDB 的边存储原理：为什么查邻居是 O(degree)？

很多人第一次看到 FalkorDB 的架构时，会有一个疑问：

它不用传统 adjacency list（邻接链表），而是用 sparse matrix（稀疏矩阵）维护边，那它到底怎么高效找到某个节点的所有边？

进一步还会问：

如果邻居节点已经连续存储了，为什么查询复杂度仍然是O(degree)，而不是O(1)？

一、传统图数据库如何存边

传统图数据库（如 Neo4j）通常使用：

adjacency list（邻接表）

例如：

A -> B A -> C A -> D

内部更像：

A: edge1 -> edge2 -> edge3

即：

• 每个节点维护自己的边链表

• 查某节点所有边：

• 直接遍历链表即可

因此复杂度：

O(degree)

其中：

degree = 边数量

例如：

• out_degree出边数量

• in_degree入边数量

二、FalkorDB 完全不同：Sparse Matrix

FalkorDB 的核心设计不是 adjacency list。

它基于：

• Sparse Matrix
• GraphBLAS

维护整个图。

例如：

A(id=0) -> B(id=1)

内部表示：

M[0,1] = edge_id

意思：

source=0 target=1

存在一条边。

三、每种 Edge Type 一个矩阵

例如：

(:User)-[:FRIEND]->(:User) (:User)-[:LIKES]->(:Post)

FalkorDB 会维护：

FRIEND matrix LIKES matrix

这样 traversal 时：

不需要扫描整个图。

四、多重边（Multi-edge）如何维护

FalkorDB 支持：

A -[:CALL]-> B A -[:CALL]-> B A -[:CALL]-> B

因此矩阵格子不能只是：

M[0,1] = 1

而更像：

M[0,1] = [3,8,15]

即：

edge ids

本质接近：

• sparse tensor
• compressed adjacency structure

五、如何高效找边？

很多人会误以为：

0 0 0 1 0 0 1 1 0

意味着：

必须扫描整行才能找到 1。

实际上完全不是。

因为：

Sparse Matrix 根本不存 0

六、Sparse Matrix 真正存什么？

例如：

[0,0,0,1,0,0,1,1,0]

真实存储更像：

[3,6,7]

意思：

index 3 有边 index 6 有边 index 7 有边

0 完全不存在。

因此：

查节点 A 的邻居：

neighbors(A) = [3,6,7]

直接返回即可。

七、CSR / CSC：工业级稀疏矩阵结构

真实实现通常是：

• CSR（Compressed Sparse Row）
• CSC（Compressed Sparse Column）

例如：

矩阵：

A: 0 0 0 1 0 0 1 1 B: 1 0 0 0 0 0 0 0 C: 0 1 0 0 1 0 0 0

CSR 可能存成：

indices = [3,6,7,0,1,4] row_ptr = [0,3,4,6]

解释：

• A 的数据在indices[0:3]
• B 的数据在indices[3:4]
• C 的数据在indices[4:6]

于是：

查 A 的所有边：

indices[0:3]

即可得到：

[3,6,7]

八、为什么复杂度仍然是 O(degree)？

这是最容易误解的地方。

很多人会问：

既然[3,6,7]已经是连续内存， 直接 memcpy 不就是 O(1)？

答案：

定位数组是 O(1)

但：

遍历数组仍然是 O(k)

其中：

k = degree

九、算法复杂度到底算什么？

例如：

MATCH (a)-[e]->() RETURN e

数据库不是只返回：

数组指针

而是必须：

• 遍历每条边
• 解码 edge object
• 构造结果集
• 返回客户端

因此：

for edge in neighbors: emit(edge)

必须执行：

degree 次

所以整体复杂度：

O(degree)

十、Output-sensitive Complexity

这是一个经典概念：

输出本身大小也算复杂度

例如：

如果：

A 有 100 万条边

即使：

找到数组起点

只需要：

O(1)

但：

返回 100 万条边：

不可能：

O(1)

因为：

你至少得“看一眼”每个元素。

十一、FalkorDB 为什么仍然快？

因为：

[3,6,7]

是：

• 连续内存
• cache-friendly
• SIMD-friendly

CPU 可以：

• prefetch
• vector load
• branch prediction

而传统 adjacency list：

edge1 -> edge2 -> edge3

属于：

pointer chasing

会导致：

• cache miss
• memory stall
• branch miss

因此：

FalkorDB 在：

• 高 fan-out traversal
• 多跳 pattern matching
• 图分析
• GraphRAG

场景中优势明显。

十二、Neo4j vs FalkorDB 本质区别

Neo4j 更像：

节点 + 边链表

适合：

• OLTP
• 单跳查询
• 高频边更新

FalkorDB 更像：

图计算引擎

适合：

• 多跳 traversal
• pattern matching
• 图分析
• 向量化计算

例如：

(A)-[:F]->(B)-[:F]->(C)

Neo4j：

pointer traversal

FalkorDB：

matrix multiply

即：

F × F

这是它最大的架构差异。

十三、最终总结

FalkorDB 的核心思想：

不存“空” 只存“存在的边”

因此：

0 0 0 1 0 0 1

实际变成：

[3,6]

查询某节点所有边：

• 定位邻接数据：

• O(1)

• 返回所有边：

• O(degree)

其中：

degree = 当前节点边数量

而不是：

整个图的边数量

这就是 Sparse Matrix 图数据库的核心性能模型。

十四、边分类型 vs 单一类型，是否影响查询速度？

一个常见疑问：

既然定位边是 O(1)，返回边是 O(degree)， 那把边归为一种类型还是多种类型，是否影响查询速度？

答案：取决于查询是否指定 edge type。

查询指定 edge type 时

例如：

MATCH (a)-[:FRIEND]->(b) RETURN b

FalkorDB 只扫描FRIEND矩阵。

如果把所有边都归为一种类型（如:REL），则矩阵包含所有边，degree 更大。

分多种类型 = 每个矩阵更小 = 遍历更少 =更快。

查询不指定 edge type 时

例如：

MATCH (a)-[]->(b) RETURN b

FalkorDB 需要合并多个矩阵的结果。

此时：

• 总遍历量相同（都是总 degree）
• 多类型有少量合并开销
• 单类型直接遍历一个矩阵

差异极小，近似无影响。

总结

实际建模建议：

分类型是更好的实践。 大多数实际查询都会指定关系类型，分类型能显著减少需要遍历的边数量。