很多人第一次看到 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）
多类型有少量合并开销
单类型直接遍历一个矩阵

差异极小，近似无影响。

总结

场景	单类型 vs 多类型	影响
查询指定 edge type	多类型更快	只扫描对应矩阵，degree 更小
查询不指定 edge type	几乎无差别	总 degree 相同，多类型有少量合并开销

实际建模建议：

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

标签： CSR

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