图数据库，第2版

第 6 章 图形数据库内部 图形数据库内部结构

本作品已使用人工智能进行翻译。欢迎您提供反馈和意见：[e-mail]

在本章中，我们将深入探讨图形数据库的实现，展示图形数据库与其他存储和查询复杂、结构多变、连接密集数据的方式有何不同。虽然即使在图形数据库中也不存在单一的通用架构模式，但本章将介绍图形数据库中最常见的架构模式和组件。

出于几个原因，我们在本章中使用 Neo4j 图形数据库来说明讨论内容。Neo4j 是一个具有原生处理能力和原生图存储能力的图数据库（有关原生图处理和存储的讨论，请参见第 1 章）。除了是撰写本文时最常用的图数据库之外，它还具有开源的透明优势，便于喜欢冒险的读者深入研究并检查代码。最后，这也是作者所熟悉的数据库。

本地图形处理

在本书中，我们已经多次讨论过属性图模型。现在，你应该已经熟悉了它的概念：节点通过命名关系和有向关系连接起来，节点和关系都是属性的容器。虽然在不同的图数据库实现中，该模型本身是相当一致的，但在数据库引擎的主内存中，有许多编码和表示图的方法。在众多不同的引擎架构中，如果图数据库表现出一种称为无索引邻接（index-free adjacency）的属性 ，我们就认为它具有本地处理能力。

利用无索引邻接的数据库引擎是指每个节点对其相邻节点保持直接引用。因此，每个节点都是附近其他节点的微索引，这比使用全局索引要便宜得多。这意味着查询时间与图表的总大小无关，而是与搜索的图表数量成正比。

相反，非本地图形数据库引擎则使用（全局）索引将节点连接起来，如图 6-1 所示。这些索引为每次遍历增加了一层间接性，从而产生了更高的计算成本。支持本地图处理的人认为，无索引邻接对于快速、高效的图遍历至关重要。

备注

要理解本机图形处理为何比基于重索引的图形高效得多，请考虑以下几点。根据实现方式的不同，索引查找的算法复杂度为O(log n)，而查找直接关系的算法复杂度为O(1)。要遍历一个包含m 个步骤的 Network+，索引方法的成本为O(m log n)，与使用无索引邻接关系的实现方法的成本O(m)相比，相形见绌。

图 6-1. 非本地图形处理引擎使用索引在节点间遍历

图 6-1展示了图处理的非本地方法是如何工作的。要找到爱丽丝的朋友，我们首先要执行索引查找，成本为O（log n）。这对于偶尔或浅层查找来说也许是可以接受的，但当我们反转遍历方向时，成本很快就会变得很高。如果我们不想查找爱丽丝的朋友，而是想找出谁是爱丽丝的朋友，那么我们就必须执行多次索引查找，每个可能是爱丽丝朋友的节点都要查找一次。这样一来，成本就更高了。查找爱丽丝的朋友是O(log n)，而查找谁是爱丽丝的朋友则是O(m log n)。

无索引邻接带来低成本 "连接"

通过无索引邻接，双向连接可以有效地预先计算并作为关系存储在数据库中。相反，如果使用索引来模拟记录之间的连接，数据库中就不会存储实际的关系。由此产生了两个问题：

首先，使用全局索引查找在算法上通常要比遍历物理关系昂贵得多。索引的时间成本通常为O(log(n))，而至少在 Neo4j 中，遍历关系的时间成本为O(1)。从理论上讲，即使n 值不大，对数成本也会比恒定时间成本高出许多倍。在实践中，由于图形及其全局索引会争夺缓存和 I/O 等资源（例如，当索引和图形数据之间发生页面争用时），性能甚至会更差。 ...