技术栈:聊聊图数据库中的 index-free adjacency
图数据库在处理互相关联的数据时，比传统的关系型数据库高效得多。这主要得益于它们在数据存储方式和查询执行机制上的深度优化，特别是其中的一个关键特性：无索引邻接（index-free adjacency）。
本文首先分析在关系型数据库中进行数据遍历时的复杂度，然后解释图数据库是如何利用“无索引邻接”这一特性，更高效地完成数据遍历操作的。
关系型数据库
以一个社交应用为例，用户之间可以互相关注。下面是该应用简化后的数据库模型：
在这个示意性的数据模型中，Users 表用于存储用户的基本信息，Followers 表用于记录用户之间的单向“关注”关系。为了加快对 Followers 表的查询速度，系统还为其建立了索引（图中的黄色部分）。
现在，假设我们想判断是否可以从某个“源用户”（Source User）出发，在最多“N”步之内找到某个“目标用户”（Target User）
我们该如何用 SQL 来实现这个查询呢？
由于 SQL 是一种声明式编程语言，主要用于查询关系型数据库中的数据，因此在实现类似图遍历这种需要逐步推进的算法时，我们通常还需要借助某种命令式编程语言。幸运的是，大多数数据库系统本身都原生支持结构化编程，可以用来编写函数或存储过程。
无论你使用哪种具体的数据库或编程语言，实现这个遍历逻辑的代码结构基本上都会类似于下面这段代码：
bool CanReachTarget(int[] sourceIds, int targetId, HashSet<int> visitedIds, int steps)
{
if (steps == 0)
returnfalse;
int[] followersIds = ExecuteQuery<int[]>(
"SELECT Follower_ID FROM Followers WHERE User_ID in ({0});",
sourceIds
);
if (followersIds.Contains(targetId))
{
returntrue;
}
else
{
visitedIds.AddRange(sourceIds);
sourceIds = followersIds.Except(visitedIds).ToArray();
return CanReachTarget(sourceIds, targetId, visitedIds, steps - 1);
}
}
在递归的每一层，函数都会获取当前层级下所有的关注者 ID，检查目标用户的 ID 是否出现在其中：如果找到了目标 ID，就立即返回 true；如果没有找到，就继续递归进入下一层，并记录下已经访问过的用户，避免重复遍历。
如果在递归过程中“可用的步数”耗尽，仍然没有找到目标 ID，说明无法在限定步数内到达目标用户，此时函数将返回 false。
我们现在用上图中的示例来运行这个算法：从 “Willian Johnson”（ID = 2）出发，尝试在最多 3 步内到达 “Mary Miller”（ID = 5）。
# | sourceIds | targetId | visitedIds | steps | followersIds | contains? |
1 | [2] | 5 | [ ] | 3 | [1, 4] | false |
2 | [1, 4] | 5 | [2] | 2 | [1, 2, 3, 4, 5] | true |
可以看到，“Mary Miller” 在第二层就被找到了，因此函数会在此处返回 true。
接下来，我们来分析这个算法的时间复杂度。你可能已经意识到，它实际上是在执行一个广度优先搜索（BFS），并将大部分的查询工作交给了数据库引擎来处理。BFS 本身的操作复杂度是 O(V + E)，其中：
- V 是从数据库中获取关注者信息的用户数量，
- E 是这些用户的关注者总数（即所有边的数量）。
对于每个用户，如果我们使用了 B-Tree 索引来查找其关注者，那么查询的代价是 O(log(n))，其中 n 是 Followers 表的总记录数。因此，整个算法的时间复杂度为：
O(V * log(n) + E)。
如果没有使用索引，情况就会变得更糟。我们需要对整个 Followers 表进行全表扫描来查找每个用户的关注者，那么最坏情况下的时间复杂度就会达到：
O(V * n + E)。
图数据库
正如本文开头所提到的，图数据库通过无索引邻接（index-free adjacency）这一特性，实现了更加高效的数据遍历。下图展示了前一张图中的数据在图数据库中的组织方式：
在图数据库中，节点之间不依赖全局索引来查找相邻节点，而是每个节点都直接引用它的邻接节点。虽然“无索引邻接”这个名字来源于“节点关系缺乏全局索引”，但你可以理解为：每个节点实际上都维护了一个指向其相邻节点的“小型索引”，因此遍历操作的代价非常低。
为了充分利用这种结构，图数据库原生支持遍历类查询，能够在数据库查询引擎内部直接执行上面提到的 BFS 算法。BFS 的操作部分依然是 O(V + E)，但不同的是：获取某个用户的关注者其操作代价会降为 O(1)，也就是常数时间复杂度，因为这些关注者在图中是直接连接在该用户节点上的。
你可能会想：那一开始如何定位查询的起始节点？难道不还是需要用到全局索引吗？
这个问题提得非常好。确实如此，为了高效地找到遍历的起点节点，仍然需要进行一次索引查找。如果我们使用的是 B-Tree 索引，这个查找操作的时间复杂度就是 O(log(n))，其中 n 是节点总数。
因此，整个查询的时间复杂度为：
O(V + E + log(n))。
相比关系型数据库，这个复杂度要好很多，尤其是当用户数量（n）很大时，图数据库的效率优势会更加明显。
为了简化分析，本文有意忽略了许多影响数据库性能的重要因素，例如文件系统缓存、数据存储的稀疏性、内存需求、数据库结构设计和查询优化等。
需要强调的是，不存在一种在所有场景下都能表现优秀的“万能数据库”。面对不同类型的问题，选择合适的数据库往往能带来更好的解决效果，当然，这也可能会增加额外的运维成本。