1.7.1　免索引鄰接

Neo4j具有一個很重要的、用來保證關(guān)系查詢速度的特性，即免索引鄰接屬性，數(shù)據(jù)庫中的每個節(jié)點(diǎn)都會維護(hù)與它相鄰節(jié)點(diǎn)的引用。因此相當(dāng)于每個節(jié)點(diǎn)都具有與它相鄰節(jié)點(diǎn)的微索引，這比使用全局索引的代價(jià)要小得多。這就意味著查詢時間和圖的整體規(guī)模無關(guān)，只與它附近節(jié)點(diǎn)的數(shù)量成正比。在關(guān)系數(shù)據(jù)庫中使用全局索引連接各個節(jié)點(diǎn)，這些索引對每個遍歷都會增加一個中間層，因此會導(dǎo)致非常大的計(jì)算成本。而免索引鄰接為圖數(shù)據(jù)庫提供了快速、高效的圖遍歷能力。

對比圖1-16和圖1-17，可以明顯地看出關(guān)系數(shù)據(jù)庫與Neo4j在查找關(guān)系時的區(qū)別。

圖1-16　關(guān)系數(shù)據(jù)庫中關(guān)系查詢示意圖

圖1-17　Neo4j中關(guān)系查詢示意圖

圖1-16展示了在關(guān)系數(shù)據(jù)庫中的查詢方式。要查找Alice所購買的東西，首先要執(zhí)行關(guān)系表的索引查詢，時間成本為O(log(n))，n為索引表的長度。這對于偶爾的淺層次查詢是可以接受的，但是當(dāng)查詢的層次變深或者是執(zhí)行反向查詢時代價(jià)將會變得不可接受了。如果要查詢某件商品被哪些人購買了（推薦引擎中常用的一個場景），將不得不使用暴力方法來遍歷整個索引，時間復(fù)雜度則將增長到O(n)。除非我們再建立一個從商品到用戶的索引表，但是該方法將會占用許多額外空間，并且使索引變得難以維護(hù)。

如果我們再考慮一個更復(fù)雜的場景，Alice購買過的商品被哪些人購買過（推薦引擎中查找有共同愛好的人），找到Alice購買過的商品的時間成本為O(log(n))，找到每個商品被哪些人購買的時間成本為O(n)，假如Alice購買過m（m遠(yuǎn)小于n）個商品，那么總的時間復(fù)雜度即為O(mnlog(n))。即使再建立一個方向索引表，時間復(fù)雜度也為O(mn)。

圖1-17展示了在同樣的場景下Neo4j的查詢方式。使用免索引近鄰機(jī)制，每個節(jié)點(diǎn)都有直接或間接指向其相鄰節(jié)點(diǎn)的指針。要查找Alice購買過的東西，只需要在Alice的關(guān)系鏈表中遍歷，每次的遍歷成本僅為O(1)。要查找一個商品被哪些人購買了，只要跟隨指向該商品的關(guān)系來源即可，每次的遍歷成本也是O(1)。更復(fù)雜的，要查找Alice購買過的東西被哪些人購買過，時間復(fù)雜度也僅為O(m)，其中m遠(yuǎn)小于n。這相較于RDBMS的時間復(fù)雜度來說還是占有絕對的優(yōu)勢。

免索引鄰接針對RDBMS中的關(guān)系查詢的兩個缺點(diǎn)做了改進(jìn)：

（1）免索引鄰接使用遍歷物理關(guān)系的方法查找，比起全局索引來說代價(jià)要小得多。查詢一個索引一般的時間復(fù)雜度為O(log(n))，而遍歷物理關(guān)系的時間復(fù)雜度僅為O(1)，至少對于Neo4j的存儲結(jié)構(gòu)來說是如此。

（2）當(dāng)索引建立之后在試圖反向遍歷時，建立的索引就起不到作用了。我們有兩個選擇：對每個反向遍歷的場景創(chuàng)建反向查找索引，或者使用原索引進(jìn)行暴力搜索，而暴力搜索的時間復(fù)雜度為O(n)。這種代價(jià)相對于很多需要實(shí)時操作的場景來說是不可接受的。

利用免索引鄰接機(jī)制，在圖數(shù)據(jù)庫上進(jìn)行關(guān)系查詢效率非常高，這種高效是建立在圖數(shù)據(jù)庫注重關(guān)系的架構(gòu)設(shè)計(jì)之上的。