1.6 Neo4j的體系結構

本節將從數據庫的底層設計揭開Neo4j數據庫的神秘面紗，了解Neo4j為了實現圖的存儲所采用什么樣的體系結構，揭秘為什么圖數據庫基于復雜聯系的查詢相比關系型數據庫要更快。

Neo4j最初的設計動機是為了更好地描述實體之間的聯系。現實生活中，每個實體都與周圍的其他實體有著千絲萬縷的關系，這些關系里存在著大量的潛在信息。但是傳統的關系型數據庫更加注重刻畫實體內部的屬性，實體與實體之間的關系主要通過外鍵來實現。因此，在查詢一個實體的關系時需要join操作，特別是深層次的關系查詢需要大量的join操作，而join操作通常又非常耗時。隨著現實世界中關系數據的急劇增加，導致關系型數據庫已經逐漸地難以承載查詢海量數據深層次關系需要大量數據庫表操作帶來的運算復雜性，Neo4j在這樣的情況下應運而生。

1.6.1 免索引鄰接

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

對比圖1-14和圖1-15，可以明顯地看出關系型數據庫與Neo4j在查找關系時的區別。

圖1-14 RDBMS中關系查詢示意圖

圖1-15 Neo4j中關系查詢示意圖

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

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

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

免索引鄰接針對RDBMS中的關系查詢的兩個缺點做了改進：

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

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

利用免索引鄰接機制，在圖數據庫上進行關系查詢效率非常高，這種高效是建立在圖數據庫注重關系的架構設計之上的。

1.6.2 Neo4j底層存儲結構

免索引鄰接是圖數據庫實現高效遍歷的關鍵，那么免索引鄰接的實現機制就是Neo4j底層存儲結構設計的關鍵。能夠支持高效的、本地化的圖存儲以及支持任意圖算法的快速遍歷，是使用圖數據庫的重要原因。本節將深入地探索Neo4j的底層存儲結構。

從宏觀角度來說，Neo4j中僅僅只有兩種數據類型：

（1）節點（Node）：節點類似于E-R圖中的實體（Entity）。每一個實體可以有零個或多個屬性（Property），這些屬性以key-value對的形式存在。屬性沒有特殊的類別要求，同時每個節點還具有相應的標簽（Label），用來區分不同類型的節點。

（2）關系（Relationship）：關系也類似于E-R圖中的關系（Relationship）。一個關系有起始節點和終止節點。另外，與節點一樣，關系也能夠有自己的屬性和標簽。

節點和關系在Neo4j中如圖1-16所示。

圖1-16 Neo4j基本存儲結構示意圖

節點和關系分別采用固定長度存儲，圖1-17為Neo4j節點和關系存儲文件的物理結構。

圖1-17 Neo4j節點和關系存儲文件的物理結構

節點存儲文件用來存儲節點的記錄，文件名為neostore.nodestore.db。節點記錄的長度為固定大小，如圖中所示，每個節點記錄的長度為9字節。格式為：Node:inUse+nextRelId+nextPropId。

● inUse:1表示該節點被正常使用，0表示該節點被刪除。

● nextRelId：該節點的下一個關系ID。

● nextPropId：該節點的下一個屬性ID。

我們可以將neostore.nodestore.db中存儲的記錄看作是如下方式：

    Node[0, used=true, rel=9, prop=-1]
    Node[1, used=true, rel=1, prop=0]
    Node[2, used=true, rel=2, prop=2]
    Node[3, used=true, rel=2, prop=4]
    Node[4, used=true, rel=4, prop=6]
    Node[5, used=true, rel=5, prop=8]
    Node[6, used=true, rel=5, prop=10]
    Node[7, used=true, rel=7, prop=12]
    Node[8, used=true, rel=8, prop=14]
    Node[9, used=true, rel=8, prop=16]
    Node[10, used=true, rel=10, prop=18]
    Node[11, used=true, rel=11, prop=20]

Node[12, used=true, rel=11, prop=22]采用固定字節長度的記錄可以快速地查詢到存儲文件中的節點。如果有一個ID為100的節點，我們知道該記錄在存儲文件中的第900字節。基于這種查詢方式，數據庫可以直接計算一個記錄的位置，其成本僅為O(1)，而不是執行成本為O(log(n))的搜索。

關系存儲文件用來存儲關系的記錄，文件名為neostore.relationshipstore.db。像節點的存儲一樣，關系存儲區的記錄大小也是固定的。格式為：Relationship:inUse+firstNode+secondNode+relType+firstPrevRelId+firstNextRelId+secondPrevRel Id+secondNextRelId+nextPropId。

● inUse, nextPropId：作用同上。

● firstNode：當前關系的起始節點。

● secondNode：當前關系的終止節點。

● relType：關系的類型。

● firstPrevRelId & firstNextRelId：起始節點的前一個和后一個關系的ID。

● secondPrevRelId & secondNextRelId：終止節點的前一個和后一個關系ID。

同樣的，“neostore.relationshipstore.db”中存儲的記錄也可以看作是如下的方式：

    Relationship[0, used=true, source=1, target=0, type=0, sPrev=1, sNext=-
    1, tPrev=3, tNext=-1, prop=1]
    Relationship[1, used=true, source=2, target=1, type=1, sPrev=2, sNext=-1, tPrev=-
    1, tNext=0, prop=3]
    Relationship[2, used=true, source=3, target=2, type=2, sPrev=-1, sNext=-1, tPrev=-
    1, tNext=1, prop=5]
    Relationship[3, used=true, source=4, target=0, type=0, sPrev=4, sNext=-
    1, tPrev=6, tNext=0, prop=7]
    Relationship[4, used=true, source=5, target=4, type=1, sPrev=5, sNext=-1, tPrev=-
    1, tNext=3, prop=9]
    Relationship[5, used=true, source=6, target=5, type=2, sPrev=-1, sNext=-1, tPrev=-
    1, tNext=4, prop=11]
    Relationship[6, used=true, source=7, target=0, type=0, sPrev=7, sNext=-
    1, tPrev=9, tNext=3, prop=13]
    Relationship[7, used=true, source=8, target=7, type=1, sPrev=8, sNext=-1, tPrev=-
    1, tNext=6, prop=15]
    Relationship[8, used=true, source=9, target=8, type=2, sPrev=-1, sNext=-1, tPrev=-
    1, tNext=7, prop=17]
    Relationship[9, used=true, source=10, target=0, type=0, sPrev=10, sNext=-1, tPrev=-
    1, tNext=6, prop=19]
    Relationship[10, used=true, source=11, target=10, type=1, sPrev=11, sNext=-
    1, tPrev=-1, tNext=9, prop=21]
    Relationship[11, used=true, source=12, target=11, type=2, sPrev=-1, sNext=-
    1, tPrev=-1, tNext=10, prop=23]

Neo4j中有一個．id文件用來保持對未使用記錄的跟蹤，用來回收未使用的記錄占用的空間。節點和關系的存儲文件只關心圖的基本存儲結構而不是屬性數據。這兩種記錄都使用固定大小的記錄，以便存儲文件內的任何記錄都可以根據ID快速地計算出來。這些都是強調Neo4j高性能遍歷的關鍵設計決策。節點記錄和關系記錄都是相當輕量級的：只由幾個指向聯系和屬性列表的指針構成。

圖1-18是Neo4j中的其他常見的基本存儲類型，需要注意的是屬性的存儲，屬性記錄的物理存儲放置在neostore.propertystore.db文件中。與節點和關系的存儲記錄一樣，屬性的存儲記錄也是固定長度。每個屬性記錄包含4個屬性塊和屬性鏈中下一個屬性的ID。屬性鏈是單向鏈表，而關系鏈是雙向鏈表。一個屬性記錄中可以包含任何Java虛擬機（JVM）支持的基本數據類型、字符串、基于基本類型的數組以及屬性索引文件（neostore.propertystore.db.index）。屬性索引文件主要用于存儲屬性的名稱，屬性索引的值部分存儲的是指向動態內存的記錄或者內聯值，短字符串和短數組會直接內聯在屬性存儲記錄中。當長度超過屬性記錄中的propBlock長度限制之后，會單獨存儲在其他的動態存儲文件中。

圖1-18 Neo4j其他常見的物理結構

Neo4j中有兩種動態存儲：動態字符串存儲（neostore.propertystore.db.strings）和動態數組存儲（neostore.propertystore.db.arrays）。動態存儲記錄是可以擴展的，如果一個屬性長到一條動態存儲記錄仍然無法完全容納時，可以申請多個動態存儲記錄邏輯上進行連接。

1.6.3 Neo4j的遍歷方式

我們可以看到磁盤上各種存儲文件存在交互。每個節點記錄都包含一個指向該節點的第一個屬性的指針和聯系鏈中第一個聯系的指針。要讀取一個節點的屬性，從指向第一個屬性的指針開始，遍歷整個單向鏈表結構。要找到一個節點的關系，從指向的第一個關系開始，遍歷整個雙向鏈表，直到找到了感興趣的關系。一旦找到了感興趣關系的記錄，我們就可以與使用和查找節點屬性一樣的方法查找關系的屬性（如果該關系存在屬性）。我們也可以很方便地獲取起始節點和結束節點的ID，利用節點ID乘以節點記錄的大小（9字節）就可以立即算出每個節點在節點存儲文件中的具體位置，所需的復雜度僅為O(1)。

圖1-19就是節點、關系、屬性在Neo4j中的物理表現方式。圖中直接看起來可能不是那么直觀，可以想象關系是屬于兩個節點的，但是一個關系也不應該在記錄中出現兩次，這樣會造成內存的浪費。因此兩個雙向鏈表之間會有指針，一個是起始節點可見的列表關系，另一個是結束節點可見的列表關系。每一個列表都是雙向鏈表，因此我們可以在任何一個方向上進行快速遍歷和高效地插入和刪除。

圖1-19 在Neo4j中的物理存儲方式

下面通過一個例子來講解Neo4j遍歷關系和節點的詳細過程。假如在Neo4j中存儲了A、B、C、D、E 5個節點和R1、R2、R3、R4、R5、R6、R7 7個關系，它們之間的關系如圖1-20所示。

圖1-20 Neo4j中的一個關系結構示意圖

假如要遍歷圖中節點B的所有關系，只需要向NODEB-NEXT方向遍歷，直到指向NULL為止，可以從圖1-21中看出節點B的所有關系為R1、R3、R4、R5。

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

通過固定大小的存儲記錄和指針ID，只要跟隨指針就可以簡單地實現遍歷并且高速執行。要遍歷一個節點到另一個節點的特定關系，在Neo4j中只需要遍歷幾個指針，然后執行一些低成本的ID計算即可，這相較于全局索引的時間復雜度要低很多，這就是Neo4j實現高效遍歷的秘密。

● 從一個給定節點定位關系鏈中第一個關系的位置，可以通過計算它在關系存儲的偏移量來獲得。跟獲得節點存儲位置的方法一樣，使用關系ID乘以關系記錄的固定大小即可找到關系在存儲文件中的正確位置。

● 在關系記錄中，搜索第二個字段可以找到第二個節點的ID。用節點記錄大小乘以節點ID可以得到節點在存儲中的正確位置。

1.6.4 Neo4j的存儲優化

Neo4j支持存儲優化（壓縮和內聯存儲屬性值），對于某些短字符的屬性可以直接存儲在屬性文件中（neostore.propertystore.db）。在實際操作中，像郵政編碼、電話號碼這樣的短字符串屬性就可以直接內聯到屬性存儲文件，而不是單獨地放在另一個動態存儲區，這樣將大幅減少I/O操作并且增大吞吐量，因為只有一個文件需要訪問。

除了可以內聯屬性值，Neo4j還可以對屬性名稱的空間嚴格維護，例如在社交網絡中，有可能會有多個節點存在first_name和last_name這樣的屬性。如果將每個屬性都逐字寫入到磁盤上就會造成浪費。因此，替代方案是屬性名稱都通過屬性索引文件從屬性存儲中間接引用。屬性索引允許所有具有相同名稱的屬性共享單個記錄，因而Neo4j可以節省相當大的空間和I/O開銷。

即使現在的磁盤訪問速度已經很快了，但是CPU訪問磁盤仍然比CPU直接訪問高速緩存要慢得多。因此，Neo4j也采用了緩存策略，保證那些經常訪問的數據可以快速地被多次重復訪問。Neo4j高速緩存的頁面置換算法是基于最不經常使用的頁置換（LFU, Least Frequently Used）緩存策略，根據頁的常用程度進行微調。也就是說即使有些頁面近期沒有使用過，但是因為以前的使用頻率很高，那么在短期之內它也是不會被淘汰的。該策略保證了緩存資源在統計學上的最優配置。