1.7.2　Neo4j底層存儲結構

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

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

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

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

節點和關系在Neo4j中的示意圖如圖1-18所示。

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

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

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

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

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

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

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+secondPrevRelId+secondNextRelId+nextPropId。

●　inUse，nextPropId：作用同上。

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

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

●　relType：關系的類型。

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

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

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

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

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

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