1.7.3　Neo4j的遍歷方式

Neo4j每個(gè)節(jié)點(diǎn)記錄都包含一個(gè)指向該節(jié)點(diǎn)的第一個(gè)屬性的指針和聯(lián)系鏈中第一個(gè)聯(lián)系的指針。要讀取一個(gè)節(jié)點(diǎn)的屬性，從指向第一個(gè)屬性的指針開始，遍歷整個(gè)單向鏈表結(jié)構(gòu)。要找到一個(gè)節(jié)點(diǎn)的關(guān)系，從指向的第一個(gè)關(guān)系開始，遍歷整個(gè)雙向鏈表，直到找到了感興趣的關(guān)系。一旦找到了感興趣關(guān)系的記錄，我們就可以與使用和查找節(jié)點(diǎn)屬性一樣的方法查找關(guān)系的屬性（如果該關(guān)系存在屬性）。我們也可以很方便地獲取起始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)的ID，利用節(jié)點(diǎn)ID乘以節(jié)點(diǎn)記錄的大小（9字節(jié)），就可以立即算出每個(gè)節(jié)點(diǎn)在節(jié)點(diǎn)存儲(chǔ)文件中的具體位置，所需的復(fù)雜度僅為O(1)。

圖1-21所示就是節(jié)點(diǎn)、關(guān)系、屬性在Neo4j中的物理表現(xiàn)方式。圖中直接看起來可能不是那么直觀，可以想象關(guān)系是屬于兩個(gè)節(jié)點(diǎn)的，但是一個(gè)關(guān)系也不應(yīng)該在記錄中出現(xiàn)兩次，這樣會(huì)造成內(nèi)存的浪費(fèi)。因此兩個(gè)雙向鏈表之間會(huì)有指針，一個(gè)是起始節(jié)點(diǎn)可見的列表關(guān)系，另一個(gè)是結(jié)束節(jié)點(diǎn)可見的列表關(guān)系。每一個(gè)列表都是雙向鏈表，因此我們可以在任何一個(gè)方向上進(jìn)行快速遍歷和高效地插入和刪除。

圖1-21　在Neo4j中的物理存儲(chǔ)方式

下面通過一個(gè)例子來講解Neo4j遍歷關(guān)系和節(jié)點(diǎn)的詳細(xì)過程。假如在Neo4j中存儲(chǔ)了A、B、C、D、E 5個(gè)節(jié)點(diǎn)和R1、R2、R3、R4、R5、R6、R7 7個(gè)關(guān)系，它們之間的關(guān)系如圖1-22所示。

圖1-22　Neo4j中的一個(gè)關(guān)系結(jié)構(gòu)示意圖

假如要遍歷圖中節(jié)點(diǎn)B的所有關(guān)系，只需要向NODEB-NEXT方向遍歷，直到指向NULL為止，可以從圖1-23中看出節(jié)點(diǎn)B的所有關(guān)系為R1、R3、R4、R5。

圖1-23　Neo4j中的圖遍歷方式

通過固定大小的存儲(chǔ)記錄和指針I(yè)D，只要跟隨指針就可以簡(jiǎn)單地實(shí)現(xiàn)遍歷并且高速執(zhí)行。要遍歷一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的特定關(guān)系，在Neo4j中只需要遍歷幾個(gè)指針，然后執(zhí)行一些低成本的ID計(jì)算即可，這相較于全局索引的時(shí)間復(fù)雜度要低很多，這就是Neo4j實(shí)現(xiàn)高效遍歷的秘密。

●　從一個(gè)給定節(jié)點(diǎn)定位關(guān)系鏈中第一個(gè)關(guān)系的位置，可以通過計(jì)算它在關(guān)系存儲(chǔ)的偏移量來獲得。跟獲得節(jié)點(diǎn)存儲(chǔ)位置的方法一樣，使用關(guān)系ID乘以關(guān)系記錄的固定大小，即可找到關(guān)系在存儲(chǔ)文件中的正確位置。

●　在關(guān)系記錄中，搜索第二個(gè)字段可以找到第二個(gè)節(jié)點(diǎn)的ID。用節(jié)點(diǎn)記錄大小乘以節(jié)點(diǎn)ID可以得到節(jié)點(diǎn)在存儲(chǔ)中的正確位置。