今天，我們需要討論一個(gè)很簡(jiǎn)單但是也很容易被忽略的問(wèn)題，我們要通過(guò)模擬現(xiàn)實(shí)世界中的情形，通過(guò)理論和實(shí)驗(yàn)的方式分析不同的圖模型在neo4j中的構(gòu)建及其性能。
這里我們通過(guò)旅客坐火車(chē)這個(gè)很簡(jiǎn)單的例子，來(lái)建立人與人之間的關(guān)系，最終目的是能夠?qū)ふ页鋈我庵付ǖ?個(gè)人之間的關(guān)系（換言之就是尋找這兩個(gè)人之間的最短路徑）
我們采用了2種不同的方式來(lái)建立模型：
模型1:建立2類(lèi)節(jié)點(diǎn)：人節(jié)點(diǎn)、車(chē)節(jié)點(diǎn)，1類(lèi)關(guān)系：人坐車(chē)關(guān)系，當(dāng)某個(gè)人乘坐了某趟車(chē)，那么他們之間就建立了人坐車(chē)的關(guān)系。
模型2:建立1類(lèi)節(jié)點(diǎn)：人節(jié)點(diǎn)，1類(lèi)關(guān)系：人與人之間的關(guān)系，當(dāng)一個(gè)人與另一個(gè)人之間存在乘坐同一趟車(chē)的情形時(shí)，那么這2個(gè)人直接就存在一個(gè)關(guān)系。
我們首先來(lái)進(jìn)行實(shí)驗(yàn)分析，我會(huì)通過(guò)不同規(guī)模的數(shù)據(jù)集來(lái)分析：
一、采用403個(gè)人，4趟車(chē)，其中每一百人共同乘坐一趟車(chē)，另外3個(gè)人是用來(lái)建立連接的，具體可以直接參考數(shù)據(jù)（附后），當(dāng)采用模型1時(shí)來(lái)分析數(shù)據(jù)時(shí)：
當(dāng)采用模型2時(shí)：
可以看出，模型1和模型2尋找最短路徑的時(shí)間分別為680ms和616ms
二、采用4003個(gè)人，4趟車(chē)，其中每一千人共同乘坐一趟車(chē)，另外3個(gè)人是用來(lái)建立連接的，當(dāng)采用模型1來(lái)進(jìn)行分析時(shí)：
當(dāng)采用模型2時(shí)：
可以看出，模型1和模型2尋找最短路徑的時(shí)間分別為748ms和4505ms，相差大約6倍。
三、采用20003個(gè)人，4趟車(chē)，其中每五千人共同乘坐一趟車(chē)，另外3個(gè)人是用來(lái)建立連接的，當(dāng)采用模型1來(lái)進(jìn)行分析時(shí)：
當(dāng)采用模型2時(shí)：
可以看出，模型1和模型2尋找最短路徑的時(shí)間分別為1343ms和67948ms，相差大約50倍。
四、采用40003個(gè)人，4趟車(chē)，其中每一萬(wàn)人共同乘坐一趟車(chē)，另外3個(gè)人是用來(lái)建立連接的，當(dāng)采用模型1來(lái)進(jìn)行分析時(shí)：
當(dāng)采用模型2時(shí)：
可以看出，模型1和模型2尋找最短路徑的時(shí)間分別為1503ms和296162ms，相差大約197倍。
通過(guò)以上的實(shí)驗(yàn)可以看出來(lái)，當(dāng)數(shù)據(jù)量不大的時(shí)候，2種模型的查找時(shí)間相差不大，當(dāng)節(jié)點(diǎn)和關(guān)系量上升時(shí)，2種模型的查找時(shí)間相差非常巨大。
下面我們從理論上分析下這個(gè)問(wèn)題：
根據(jù)neo4j的文檔介紹，neo4j采用的是雙向廣度優(yōu)先搜索算法來(lái)進(jìn)行最短路徑問(wèn)題的處理，其算法的復(fù)雜度為O(V+E)，其中V代表圖的頂點(diǎn)數(shù)，E代表圖的邊數(shù)。
對(duì)于第一種情形，模型1導(dǎo)入 407個(gè)結(jié)點(diǎn)，406個(gè)關(guān)系，模型2導(dǎo)入 403個(gè)結(jié)點(diǎn)，20402個(gè)關(guān)系，2者相差不大
對(duì)于第二種情形，模型1導(dǎo)入4007個(gè)結(jié)點(diǎn)，4006個(gè)關(guān)系，模型2導(dǎo)入4003個(gè)結(jié)點(diǎn)，2004002個(gè)關(guān)系，可以看到模型2的關(guān)系數(shù)量上升比較快
對(duì)于第三種情形，模型1導(dǎo)入20007個(gè)結(jié)點(diǎn)，20006個(gè)關(guān)系，模型2導(dǎo)入20003個(gè)結(jié)點(diǎn)，50020002個(gè)關(guān)系，關(guān)系差不多達(dá)到5000多萬(wàn)個(gè)
對(duì)于最后一種情形，模型1導(dǎo)入40007個(gè)結(jié)點(diǎn)，40006個(gè)關(guān)系，模型2導(dǎo)入40003個(gè)結(jié)點(diǎn)，200040002個(gè)關(guān)系，關(guān)系差不多達(dá)到2億多個(gè)
這里理論分析出來(lái)的結(jié)果和實(shí)驗(yàn)的結(jié)果基本符合，通過(guò)這樣的分析和實(shí)驗(yàn)可以看出，當(dāng)節(jié)點(diǎn)數(shù)量基本固定的情況下，盡量減少模型中的關(guān)系數(shù)量，對(duì)提高搜索的效率有很大的幫助。
附（數(shù)據(jù)）：
鏈接:https://pan.baidu.com/s/1AxmymxTgWPuYRN99DBRzLA 密碼:smwx
