1.7.1　免索引邻接

Neo4j具有一个很重要的、用来保证关系查询速度的特性，即免索引邻接属性，数据库中的每个节点都会维护与它相邻节点的引用。因此相当于每个节点都具有与它相邻节点的微索引，这比使用全局索引的代价要小得多。这就意味着查询时间和图的整体规模无关，只与它附近节点的数量成正比。在关系数据库中使用全局索引连接各个节点，这些索引对每个遍历都会增加一个中间层，因此会导致非常大的计算成本。而免索引邻接为图数据库提供了快速、高效的图遍历能力。

对比图1-16和图1-17，可以明显地看出关系数据库与Neo4j在查找关系时的区别。

图1-16　关系数据库中关系查询示意图

图1-17　Neo4j中关系查询示意图

图1-16展示了在关系数据库中的查询方式。要查找Alice所购买的东西，首先要执行关系表的索引查询，时间成本为O(log(n))，n为索引表的长度。这对于偶尔的浅层次查询是可以接受的，但是当查询的层次变深或者是执行反向查询时代价将会变得不可接受了。如果要查询某件商品被哪些人购买了（推荐引擎中常用的一个场景），将不得不使用暴力方法来遍历整个索引，时间复杂度则将增长到O(n)。除非我们再建立一个从商品到用户的索引表，但是该方法将会占用许多额外空间，并且使索引变得难以维护。

如果我们再考虑一个更复杂的场景，Alice购买过的商品被哪些人购买过（推荐引擎中查找有共同爱好的人），找到Alice购买过的商品的时间成本为O(log(n))，找到每个商品被哪些人购买的时间成本为O(n)，假如Alice购买过m（m远小于n）个商品，那么总的时间复杂度即为O(mnlog(n))。即使再建立一个方向索引表，时间复杂度也为O(mn)。

图1-17展示了在同样的场景下Neo4j的查询方式。使用免索引近邻机制，每个节点都有直接或间接指向其相邻节点的指针。要查找Alice购买过的东西，只需要在Alice的关系链表中遍历，每次的遍历成本仅为O(1)。要查找一个商品被哪些人购买了，只要跟随指向该商品的关系来源即可，每次的遍历成本也是O(1)。更复杂的，要查找Alice购买过的东西被哪些人购买过，时间复杂度也仅为O(m)，其中m远小于n。这相较于RDBMS的时间复杂度来说还是占有绝对的优势。

免索引邻接针对RDBMS中的关系查询的两个缺点做了改进：

（1）免索引邻接使用遍历物理关系的方法查找，比起全局索引来说代价要小得多。查询一个索引一般的时间复杂度为O(log(n))，而遍历物理关系的时间复杂度仅为O(1)，至少对于Neo4j的存储结构来说是如此。

（2）当索引建立之后在试图反向遍历时，建立的索引就起不到作用了。我们有两个选择：对每个反向遍历的场景创建反向查找索引，或者使用原索引进行暴力搜索，而暴力搜索的时间复杂度为O(n)。这种代价相对于很多需要实时操作的场景来说是不可接受的。

利用免索引邻接机制，在图数据库上进行关系查询效率非常高，这种高效是建立在图数据库注重关系的架构设计之上的。