建站
咨詢
售后
建站咨詢
新聞中心
隨著互聯(lián)網(wǎng)的不斷發(fā)展和數(shù)據(jù)量的不斷增加，數(shù)據(jù)庫(kù)的需求量也越來(lái)越大。但是傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)管理方式已經(jīng)不能滿足實(shí)時(shí)性、安全性、擴(kuò)展性和復(fù)雜數(shù)據(jù)的處理需求。因此，圖數(shù)據(jù)庫(kù)的出現(xiàn)成為了一個(gè)全新的數(shù)據(jù)管理方式。
圖數(shù)據(jù)庫(kù)是一種由節(jié)點(diǎn)和邊構(gòu)成的圖形結(jié)構(gòu)數(shù)據(jù)管理系統(tǒng)，它可以更加高效地處理復(fù)雜數(shù)據(jù)，并且可以克服傳統(tǒng)數(shù)據(jù)庫(kù)的缺陷，將數(shù)據(jù)管理提升到新的高度。這里我們就來(lái)探索一下圖數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)圖，以及它所帶來(lái)的新一代數(shù)據(jù)管理方式。
一、圖數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)圖
圖數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)使用圖形結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)，由“節(jié)點(diǎn)”和“邊”兩個(gè)元素構(gòu)成。其中，節(jié)點(diǎn)是數(shù)據(jù)的核心，每個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)數(shù)據(jù)實(shí)體，可以是人、物、事、概念等。邊則描述了節(jié)點(diǎn)之間的關(guān)系，用于連接不同的節(jié)點(diǎn)，從而形成一個(gè)關(guān)系網(wǎng)絡(luò)。
在圖數(shù)據(jù)庫(kù)中，每個(gè)節(jié)點(diǎn)和邊都可以有不同的屬性，這些屬性可以存儲(chǔ)各種類型的數(shù)據(jù)，如數(shù)字、字符串、日期、圖像等。這些屬性可以幫助用戶更加方便地對(duì)數(shù)據(jù)進(jìn)行查詢、分析和管理。
二、探索新一代數(shù)據(jù)管理方式
圖數(shù)據(jù)庫(kù)的出現(xiàn)打破了傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)的限制，使得數(shù)據(jù)管理的方式發(fā)生了重大變化。那么它為什么能夠成為新一代數(shù)據(jù)管理方式呢？下面是圖數(shù)據(jù)庫(kù)帶來(lái)的三個(gè)顯著優(yōu)勢(shì)：
1.更高效的數(shù)據(jù)處理能力
圖數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)圖是由節(jié)點(diǎn)和邊組成的，每個(gè)節(jié)點(diǎn)都是獨(dú)立的，可以包含完整的數(shù)據(jù)信息和屬性，這使得圖數(shù)據(jù)庫(kù)可以更快速地進(jìn)行數(shù)據(jù)的讀寫(xiě)操作和查詢過(guò)程。同時(shí)，圖數(shù)據(jù)庫(kù)還可以進(jìn)行跨邊和多方向的數(shù)據(jù)查詢，讓數(shù)據(jù)的處理變得更加高效。
2.更加精確的數(shù)據(jù)分析能力
圖數(shù)據(jù)庫(kù)可以幫助用戶更加準(zhǔn)確地分析數(shù)據(jù)，因?yàn)樗梢圆煌S度地關(guān)聯(lián)不同的節(jié)點(diǎn)和邊，從而形成更加精確的分析結(jié)果。這使得圖數(shù)據(jù)庫(kù)在社交網(wǎng)絡(luò)、金融等復(fù)雜數(shù)據(jù)領(lǐng)域的數(shù)據(jù)分析過(guò)程中更加受歡迎。
3.更高的可擴(kuò)展性和可適應(yīng)性
由于圖數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)圖是基于圖形結(jié)構(gòu)的，節(jié)點(diǎn)和邊的拓展具有天然的可擴(kuò)展性。當(dāng)需要新加節(jié)點(diǎn)或邊時(shí)，只需簡(jiǎn)單地添加或修改節(jié)點(diǎn)或邊的屬性即可。此外，圖數(shù)據(jù)庫(kù)還能夠適應(yīng)和解決傳統(tǒng)數(shù)據(jù)庫(kù)無(wú)法處理的大規(guī)模和復(fù)雜數(shù)據(jù)處理需求。
三、
圖數(shù)據(jù)庫(kù)是新一代數(shù)據(jù)管理方式的代表，它的存儲(chǔ)結(jié)構(gòu)圖和優(yōu)勢(shì)所帶來(lái)的高效性、精確性、可擴(kuò)展性和適應(yīng)性等特點(diǎn)成為了數(shù)據(jù)管理的主流趨勢(shì)。同時(shí)，隨著對(duì)大數(shù)據(jù)的需求和云計(jì)算技術(shù)的不斷發(fā)展，相信圖數(shù)據(jù)庫(kù)也將在數(shù)據(jù)架構(gòu)的演化過(guò)程中扮演更加重要的角色。
成都網(wǎng)站建設(shè)公司-創(chuàng)新互聯(lián)為您提供網(wǎng)站建設(shè)、網(wǎng)站制作、網(wǎng)頁(yè)設(shè)計(jì)及定制高端網(wǎng)站建設(shè)服務(wù)！
圖的兩種存儲(chǔ)結(jié)構(gòu)是什么
順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)
二樓說(shuō)錯(cuò)了，方向有誤。
這兩個(gè)分別叫剖面符號(hào)和斷面符號(hào)，他們剖段的方向都是縱向的，觀察的方向是指向數(shù)字的方向，從網(wǎng)頁(yè)上來(lái)看，就是L1是從左往右，而1┃則表示從右往左看。
這兩種符號(hào)的區(qū)別是斷面圖與剖面圖的區(qū)別在于：
斷面圖只畫(huà)形體被剖開(kāi)后斷面的投影，而剖面圖要畫(huà)出形體被剖開(kāi)后整個(gè)余下部分的投影如圖。
1)剖面圖是形體剖切之后剩下部分的投影，是體的投影。斷面圖是形體剖切之后斷面的投影，是面的投影。 剖面圖中包含斷面圖。
2)剖面圖用剖切位置線、投射方向線和編號(hào)來(lái)表示。斷面圖則只畫(huà)剖切位置線與編號(hào)，用編號(hào)的注寫(xiě)位置來(lái)代表投射方向。
3)剖面圖可用兩個(gè)或兩個(gè)以上的剖切平面進(jìn)行剖切，斷面圖的剖切平面通常只能是單一的。
如何用 Python 實(shí)現(xiàn)一個(gè)圖數(shù)據(jù)庫(kù)（Graph Database）？
本文章是 重寫(xiě) 500 Lines or Less 系列的其中一篇，目標(biāo)是重寫(xiě) 500 Lines or Less 系列的原有項(xiàng)目：Dagoba: an in-memory graph database。
Dagoba 是作者設(shè)計(jì)用來(lái)展示如何從零開(kāi)始自己實(shí)現(xiàn)一個(gè)圖數(shù)據(jù)庫(kù)（ Graph Database ）。該名字似乎來(lái)源于作者喜歡的一個(gè)樂(lè)隊(duì)，另一個(gè)原因是它的前綴 DAG 也正好是有向無(wú)環(huán)圖 （ Directed Acyclic Graph ） 的縮寫(xiě)。本文也沿用了該名稱。
圖是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，它將信息描述為若干獨(dú)立的節(jié)點(diǎn)（ vertex ，為了和下文的邊更加對(duì)稱，本文中稱為 node ），以及把節(jié)點(diǎn)關(guān)聯(lián)起來(lái)的邊（ edge ）。我們熟悉的鏈表以及多種樹(shù)結(jié)構(gòu)可以看作是符合特定規(guī)則的圖。圖在路徑選擇、推薦算法以及神經(jīng)網(wǎng)絡(luò)等方面都是重要的核心數(shù)據(jù)結(jié)構(gòu)。
既然圖的用途如此廣泛，一個(gè)重要的問(wèn)題就是如何存儲(chǔ)它。如果在傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)中存儲(chǔ)圖，很自然的做法就是為節(jié)點(diǎn)和邊各自創(chuàng)建一張表，并用外鍵把它們關(guān)聯(lián)起來(lái)。這樣的話，要查找某人所有的子女，就可以寫(xiě)下類似下面的查詢：
還好，不算太復(fù)雜。但是如果要查找孫輩呢？那恐怕就要使用子查詢或者 CTE(Common Table Expression) 等特殊構(gòu)造了。再往下想，曾孫輩又該怎么查詢？孫媳婦呢？
這樣我們會(huì)意識(shí)到，SQL 作為查詢語(yǔ)言，它只是對(duì)二維數(shù)據(jù)表這種結(jié)構(gòu)而設(shè)計(jì)的，用它去查詢圖的話非常笨拙，很快會(huì)變得極其復(fù)雜，也難以擴(kuò)展。針對(duì)圖而言，我們希望有一種更為自然和直觀的查詢語(yǔ)法，類似這樣：
為了高效地存儲(chǔ)和查詢圖這種數(shù)據(jù)結(jié)構(gòu)，圖數(shù)據(jù)庫(kù)（ Graph Database ）應(yīng)運(yùn)而生。因?yàn)楹蛡鹘y(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)存在極大的差異，所以它屬于新型數(shù)據(jù)庫(kù)也就是 NoSql 的一個(gè)分支（其他分支包括文檔數(shù)據(jù)庫(kù)、列數(shù)據(jù)庫(kù)等）。圖數(shù)據(jù)庫(kù)的主要代表包括 Neo4J 等。本文介紹的 Dagoba 則是具備圖數(shù)據(jù)庫(kù)核心功能、主要用于教學(xué)和演示的一個(gè)簡(jiǎn)單的圖數(shù)據(jù)庫(kù)。
原文代碼是使用 JavaScript 編寫(xiě)的，在定義調(diào)用接口時(shí)大量使用了原型（ prototype ）這種特有的語(yǔ)言構(gòu)造。對(duì)于其他主流語(yǔ)言的用戶來(lái)說(shuō)，原型的用法多少顯得有些別扭和不自然。
考慮到本系列其他數(shù)據(jù)庫(kù)示例大多是用 Python 實(shí)現(xiàn)的，本文也按照傳統(tǒng)，用 Python 重寫(xiě)了原文的代碼。同樣延續(xù)之前的慣例，為了讓讀者更好地理解程序是如何逐步完善的，我們用迭代式的方法完成程序的各個(gè)組成部分。
原文在 500lines 系列的 Github 倉(cāng)庫(kù)中只包含了實(shí)現(xiàn)代碼，并未包含測(cè)試。按照代碼注釋說(shuō)明，測(cè)試程序位于作者的另一個(gè)代碼庫(kù)中，不過(guò)和 500lines 版本的實(shí)現(xiàn)似乎略有不同。
本文實(shí)現(xiàn)的代碼參考了原作者的測(cè)試內(nèi)容，但跳過(guò)了北歐神話這個(gè)例子——我承認(rèn)確實(shí)不熟悉這些神祇之間的親緣關(guān)系，相信中文背景的讀者們多數(shù)也未必了解，雖然作者很喜歡這個(gè)例子，想了想還是不要徒增困惑吧。因此本文在編寫(xiě)測(cè)試用例時(shí)只參考了原文關(guān)于家族親屬的例子，放棄了神話相關(guān)的部分，盡管會(huì)減少一些趣味性，相信對(duì)于入門(mén)級(jí)的代碼來(lái)說(shuō)這樣也夠用了。
本文實(shí)現(xiàn)程序位于代碼庫(kù)的 dagoba 目錄下。按照本系列程序的同意規(guī)則，要想直接執(zhí)行各個(gè)已完成的步驟，讀者可以在根目錄下的 main.py 找到相應(yīng)的代碼位置，取消注釋并運(yùn)行即可。
本程序的所有步驟只需要 Python3 ，測(cè)試則使用內(nèi)置的 unittest , 不需要額外的第三方庫(kù)。原則上 Python3.6 以上版本應(yīng)該都可運(yùn)行，但我只在 Python3.8.3 環(huán)境下完整測(cè)試過(guò)。
本文實(shí)現(xiàn)的程序從最簡(jiǎn)單的案例開(kāi)始，通過(guò)每個(gè)步驟逐步擴(kuò)展，最終形成一個(gè)完整的程序。這些步驟包括：
接下來(lái)依次介紹各個(gè)步驟。
回想一下，圖數(shù)據(jù)庫(kù)就是一些點(diǎn)（ node ）和邊（ edge ）的。現(xiàn)在我們要做出的一個(gè)重大決策是如何對(duì)節(jié)點(diǎn)/邊進(jìn)行建模。對(duì)于邊來(lái)說(shuō)，必須指定它的關(guān)聯(lián)關(guān)系，也就是從哪個(gè)節(jié)點(diǎn)指向哪個(gè)節(jié)點(diǎn)。大多數(shù)情況下邊是有方向的——父子關(guān)系不指明方向可是要亂套的！
考慮到擴(kuò)展性及通用性問(wèn)題，我們可以把數(shù)據(jù)保存為字典（ dict ），這樣可以方便地添加用戶需要的任何數(shù)據(jù)。某些數(shù)據(jù)是為數(shù)據(jù)庫(kù)內(nèi)部管理而保留的，為了明確區(qū)分，可以這樣約定：以下劃線開(kāi)頭的特殊字段由數(shù)據(jù)庫(kù)內(nèi)部維護(hù)，類似于私有成員，用戶不應(yīng)該自己去修改它們。這也是 Python 社區(qū)普遍遵循的約定。
此外，節(jié)點(diǎn)和邊存在互相引用的關(guān)系。目前我們知道邊會(huì)引用到兩端的節(jié)點(diǎn)，后面還會(huì)看到，為了提高效率，節(jié)點(diǎn)也會(huì)引用到邊。如果僅僅在內(nèi)存中維護(hù)它們的關(guān)系，那么使用指針訪問(wèn)是很直觀的，但數(shù)據(jù)庫(kù)必須考慮到序列化到磁盤(pán)的問(wèn)題，這時(shí)指針就不再好用了。
為此，更好按照數(shù)據(jù)庫(kù)的一般要求，為每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)主鍵（ _id ），用主鍵來(lái)描述它們之間的關(guān)聯(lián)關(guān)系。
我們之一步要把數(shù)據(jù)庫(kù)的模型建立起來(lái)。為了測(cè)試目的，我們使用一個(gè)最簡(jiǎn)單的數(shù)據(jù)庫(kù)模型，它只包含兩個(gè)節(jié)點(diǎn)和一條邊，如下所示：
按照 TDD 的原則，首先編寫(xiě)測(cè)試：
與原文一樣，我們把數(shù)據(jù)庫(kù)管理接口命名為 Dagoba 。目前，能夠想到的最簡(jiǎn)單的測(cè)試是確認(rèn)節(jié)點(diǎn)和邊是否已經(jīng)添加到數(shù)據(jù)庫(kù)中：
assert_item 是一個(gè)輔助方法，用于檢查字典是否包含預(yù)期的字段。相信大家都能想到該如何實(shí)現(xiàn)，這里就不再列出了，讀者可參考 Github 上的完整源碼。
現(xiàn)在，測(cè)試是失敗的。用最簡(jiǎn)單的辦法實(shí)現(xiàn)數(shù)據(jù)庫(kù)：
需要注意的是，不管添加節(jié)點(diǎn)還是查詢，程序都使用了拷貝后的數(shù)據(jù)副本，而不是直接使用原始數(shù)據(jù)。為什么要這樣做？因?yàn)樽值涫强勺兊模脩艨梢栽谌魏螘r(shí)候修改其中的內(nèi)容，如果數(shù)據(jù)庫(kù)不知道數(shù)據(jù)已經(jīng)變化，就很容易發(fā)生難以追蹤的一致性問(wèn)題，最糟糕的情況下會(huì)使得數(shù)據(jù)內(nèi)容徹底混亂。
拷貝數(shù)據(jù)可以避免上述問(wèn)題，代價(jià)則是需要占用更多內(nèi)存和處理時(shí)間。對(duì)于數(shù)據(jù)庫(kù)來(lái)說(shuō)，通常查詢次數(shù)要遠(yuǎn)遠(yuǎn)多于修改，所以這個(gè)代價(jià)是可以接受的。
現(xiàn)在測(cè)試應(yīng)該正常通過(guò)了。為了讓它更加完善，我們可以再測(cè)試一些邊緣情況，看看數(shù)據(jù)庫(kù)能否正確處理異常數(shù)據(jù)，比如：
例如，如果用戶嘗試添加重復(fù)主鍵，我們預(yù)期應(yīng)拋出 ValueError 異常。因此編寫(xiě)測(cè)試如下：
為了滿足以上測(cè)試，代碼需要稍作修改。特別是按照 id 查找主鍵是個(gè)常用操作，通過(guò)遍歷的方法效率太低了，更好是能夠通過(guò)主鍵直接訪問(wèn)。因此在數(shù)據(jù)庫(kù)中再增加一個(gè)字典：
完整代碼請(qǐng)參考 Github 倉(cāng)庫(kù)。
在上個(gè)步驟，我們?cè)诔跏蓟瘮?shù)據(jù)庫(kù)時(shí)為節(jié)點(diǎn)明確指定了主鍵。按照數(shù)據(jù)庫(kù)設(shè)計(jì)的一般原則，主鍵更好是不具有業(yè)務(wù)含義的代理主鍵（ Surrogate key ），用戶不應(yīng)該關(guān)心它具體的值是什么，因此讓數(shù)據(jù)庫(kù)去管理主鍵通常是更為合理的。當(dāng)然，在部分場(chǎng)景下——比如導(dǎo)入外部數(shù)據(jù)——明確指定主鍵仍然是有用的。
為了同時(shí)支持這些要求，我們這樣約定：字段 _id 表示節(jié)點(diǎn)的主鍵，如果用戶指定了該字段，則使用用戶設(shè)置的值（當(dāng)然，用戶有責(zé)任保證它們不會(huì)重復(fù)）；否則，由數(shù)據(jù)庫(kù)自動(dòng)為它分配一個(gè)主鍵。
如果主鍵是數(shù)據(jù)庫(kù)生成的，事先無(wú)法預(yù)知它的值是什么，而邊（ edge ）必須指定它所指向的節(jié)點(diǎn)，因此必須在主鍵生成后才能添加。由于這個(gè)原因，在動(dòng)態(tài)生成主鍵的情況下，數(shù)據(jù)庫(kù)的初始化會(huì)略微復(fù)雜一些。還是先寫(xiě)一個(gè)測(cè)試：
為支持此功能，我們?cè)跀?shù)據(jù)庫(kù)中添加一個(gè)內(nèi)部字段 _next_id 用于生成主鍵，并讓 add_node 方法返回新生成的主鍵：
接下來(lái)，再確認(rèn)一下邊是否可以正常訪問(wèn)：
運(yùn)行測(cè)試，一切正常。這個(gè)步驟很輕松地完成了，不過(guò)兩個(gè)測(cè)試（ DbModelTest 和 PrimaryKeyTest ）出現(xiàn)了一些重復(fù)代碼，比如 get_item 。我們可以把這些公用代碼提取出來(lái)。由于 get_item 內(nèi)部調(diào)用了 TestCase.assertXXX 等方法，看起來(lái)應(yīng)該使用繼承，但從 TestCase 派生基類容易引起一些潛在的問(wèn)題，所以我轉(zhuǎn)而使用另一個(gè)技巧 Mixin ：
實(shí)現(xiàn)數(shù)據(jù)庫(kù)模型之后，接下來(lái)就要考慮如何查詢它了。
在設(shè)計(jì)查詢時(shí)要考慮幾個(gè)問(wèn)題。對(duì)于圖的訪問(wèn)來(lái)說(shuō)，幾乎總是由某個(gè)節(jié)點(diǎn)（或符合條件的某一類節(jié)點(diǎn)）開(kāi)始，從與它相鄰的邊跳轉(zhuǎn)到其他節(jié)點(diǎn)，依次類推。所以鏈?zhǔn)秸{(diào)用對(duì)查詢來(lái)說(shuō)是一種很自然的風(fēng)格。舉例來(lái)說(shuō)，要知道 Tom 的孫子養(yǎng)了幾只貓，可以使用類似這樣的查詢：
可以想象，以上每個(gè)方法都應(yīng)該返回符合條件的節(jié)點(diǎn)。這種實(shí)現(xiàn)是很直觀的，不過(guò)存在一個(gè)潛在的問(wèn)題：很多時(shí)候用戶只需要一小部分結(jié)果，如果它總是不計(jì)代價(jià)地給我們一個(gè)巨大的，會(huì)造成極大的浪費(fèi)。比如以下查詢：
為了避免不必要的浪費(fèi)，我們需要另外一種機(jī)制，也就是通常所稱的“懶式查詢”或“延遲查詢”。它的基本思想是，當(dāng)我們調(diào)用查詢方法時(shí)，它只是把查詢條件記錄下來(lái)，而并不立即返回結(jié)果，直到明確調(diào)用某些方法時(shí)才真正去查詢數(shù)據(jù)庫(kù)。
如果讀者比較熟悉流行的 Python ORM，比如 SqlAlchemy 或者 Django ORM 的話，會(huì)知道它們幾乎都是懶式查詢的，要調(diào)用 list(result) 或者 result 這樣的方法才能得到具體的查詢結(jié)果。
在 Dagoba 中把觸發(fā)查詢的方法定義為 run 。也就是說(shuō)，以下查詢執(zhí)行到 run 時(shí)才真正去查找數(shù)據(jù)：
和懶式查詢（ Lazy Query ）相對(duì)應(yīng)的，直接返回結(jié)果的方法一般稱作主動(dòng)查詢（ Eager Query ）。主動(dòng)查詢和懶式查詢的內(nèi)在查找邏輯基本上是相同的，區(qū)別只在于觸發(fā)機(jī)制不同。由于主動(dòng)查詢實(shí)現(xiàn)起來(lái)更加簡(jiǎn)單，出錯(cuò)也更容易排查，因此我們先從主動(dòng)查詢開(kāi)始實(shí)現(xiàn)。
還是從測(cè)試開(kāi)始。前面測(cè)試所用的簡(jiǎn)單數(shù)據(jù)庫(kù)數(shù)據(jù)太少，難以滿足查詢要求，所以這一步先來(lái)創(chuàng)建一個(gè)更復(fù)雜的數(shù)據(jù)模型：
此關(guān)系的復(fù)雜之處之一在于反向關(guān)聯(lián)：如果 A 是 B 的哥哥，那么 B 就是 A 的弟弟/妹妹，為了查詢到他們彼此之間的關(guān)系，正向關(guān)聯(lián)和反向關(guān)聯(lián)都需要存在，因此在初始化數(shù)據(jù)庫(kù)時(shí)需要定義的邊數(shù)量會(huì)很多。
當(dāng)然，父子之間也存在反向關(guān)聯(lián)的問(wèn)題，為了讓問(wèn)題稍微簡(jiǎn)化一些，我們目前只需要向下（子孫輩）查找，可以稍微減少一些關(guān)聯(lián)數(shù)量。
因此，我們定義數(shù)據(jù)模型如下。為了減少重復(fù)工作，我們通過(guò) _backward 字段定義反向關(guān)聯(lián)，而數(shù)據(jù)庫(kù)內(nèi)部為了查詢方便，需要把它維護(hù)成兩條邊：
然后，測(cè)試一個(gè)最簡(jiǎn)單的查詢，比如查找某人的所有孫輩：
這里 outcome/income 分別表示從某個(gè)節(jié)點(diǎn)出發(fā)、或到達(dá)它的節(jié)點(diǎn)。在原作者的代碼中把上述方法稱為 out/in 。當(dāng)然這樣看起來(lái)更加簡(jiǎn)潔，可惜的是 in 在 Python 中是個(gè)關(guān)鍵字，無(wú)法作為函數(shù)名。我也考慮過(guò)加個(gè)下劃線比如 out_.in_ 這種形式，但看起來(lái)也有點(diǎn)怪異，權(quán)衡之后還是使用了稍微啰嗦一點(diǎn)的名稱。
現(xiàn)在我們可以開(kāi)始定義查詢接口了。在前面已經(jīng)說(shuō)過(guò)，我們計(jì)劃分別實(shí)現(xiàn)兩種查詢，包括主動(dòng)查詢（ Eager Query ）以及延遲查詢（ Lazy Query ）。
它們的內(nèi)在查詢邏輯是相通的，看起來(lái)似乎可以使用繼承。不過(guò)遵循 YAGNI 原則，目前先不這樣做，而是只定義兩個(gè)新類，在滿足測(cè)試的基礎(chǔ)上不斷擴(kuò)展。以后我們會(huì)看到，與繼承相比，把共同的邏輯放到數(shù)據(jù)庫(kù)本身其實(shí)是更為合理的。
接下來(lái)實(shí)現(xiàn)訪問(wèn)節(jié)點(diǎn)的方法。由于 EagerQuery 調(diào)用查詢方法會(huì)立即返回結(jié)果，我們把結(jié)果記錄在 _result 內(nèi)部字段中。雖然 node 方法只返回單個(gè)結(jié)果，但考慮到其他查詢方法幾乎都是返回，為統(tǒng)一起見(jiàn)，讓它也返回，這樣可以避免同時(shí)支持與單結(jié)果的分支處理，讓代碼更加簡(jiǎn)潔、不容易出錯(cuò)。此外，如果查詢對(duì)象不存在的話，我們只返回空，并不視為一個(gè)錯(cuò)誤。
查詢輸入/輸出節(jié)點(diǎn)的方法實(shí)現(xiàn)類似這樣：
查找節(jié)點(diǎn)的核心邏輯在數(shù)據(jù)庫(kù)本身定義：
以上使用了內(nèi)部定義的一些輔助查詢方法。用類似的邏輯再定義 income ，它們的實(shí)現(xiàn)都很簡(jiǎn)單，讀者可以直接參考源碼，此處不再贅述。
在此步驟的最后，我們?cè)賹?shí)現(xiàn)一個(gè)優(yōu)化。當(dāng)多次調(diào)用查詢方法后，結(jié)果可能會(huì)返回重復(fù)的數(shù)據(jù)，很多時(shí)候這是不必要的。就像關(guān)系數(shù)據(jù)庫(kù)通常支持 unique/distinct 一樣，我們也希望 Dagoba 能夠過(guò)濾重復(fù)的數(shù)據(jù)。
假設(shè)我們要查詢某人所有孩子的祖父，顯然不管有多少孩子，他們的祖父應(yīng)該是同一個(gè)人。因此編寫(xiě)測(cè)試如下：
現(xiàn)在來(lái)實(shí)現(xiàn) unique 。我們只要按照主鍵把重復(fù)數(shù)據(jù)去掉即可：
在上個(gè)步驟，初始化數(shù)據(jù)庫(kù)指定了雙向關(guān)聯(lián)，但并未測(cè)試它們。因?yàn)槲覀冞€沒(méi)有編寫(xiě)代碼去支持它們，現(xiàn)在增加一個(gè)測(cè)試，它應(yīng)該是失敗的：
運(yùn)行測(cè)試，的確失敗了。我們看看要如何支持它?；叵胍幌拢?dāng)從邊查找節(jié)點(diǎn)時(shí)，使用的是以下方法：
這里也有一個(gè)潛在的問(wèn)題：調(diào)用 self.edges 意味著遍歷所有邊，當(dāng)數(shù)據(jù)庫(kù)內(nèi)容較多時(shí)，這是巨大的浪費(fèi)。為了提高性能，我們可以把與節(jié)點(diǎn)相關(guān)的邊記錄在節(jié)點(diǎn)本身，這樣要查找邊只要看節(jié)點(diǎn)本身即可。在初始化時(shí)定義出入邊的：
在添加邊時(shí)，我們要同時(shí)把它們對(duì)應(yīng)的關(guān)系同時(shí)更新到節(jié)點(diǎn)，此外還要維護(hù)反向關(guān)聯(lián)。這涉及對(duì)字典內(nèi)容的部分復(fù)制，先編寫(xiě)一個(gè)輔助方法：
然后，將添加邊的實(shí)現(xiàn)修改如下：
這里的代碼同時(shí)添加正向關(guān)聯(lián)和反向關(guān)聯(lián)。有的朋友可能會(huì)注意到代碼略有重復(fù)，是的，但是重復(fù)僅出現(xiàn)在該函數(shù)內(nèi)部，本著“三則重構(gòu)”的原則，暫時(shí)不去提取代碼。
實(shí)現(xiàn)之后，前面的測(cè)試就可以正常通過(guò)了。
在這個(gè)步驟中，我們來(lái)實(shí)現(xiàn)延遲查詢（ Lazy Query ）。
延遲查詢的要求是，當(dāng)調(diào)用查詢方法時(shí)并不立即執(zhí)行，而是推遲到調(diào)用特定方法，比如 run 時(shí)才執(zhí)行整個(gè)查詢，返回結(jié)果。
延遲查詢的實(shí)現(xiàn)要比主動(dòng)查詢復(fù)雜一些。為了實(shí)現(xiàn)延遲查詢，查詢方法的實(shí)現(xiàn)不能直接返回結(jié)果，而是記錄要執(zhí)行的動(dòng)作以及傳入的參數(shù)，到調(diào)用 run 時(shí)再依次執(zhí)行前面記錄下來(lái)的內(nèi)容。
如果你去看作者的實(shí)現(xiàn)，會(huì)發(fā)現(xiàn)他是用一個(gè)數(shù)據(jù)結(jié)構(gòu)記錄執(zhí)行操作和參數(shù)，此外還有一部分邏輯用來(lái)分派對(duì)每種結(jié)構(gòu)要執(zhí)行的動(dòng)作。這樣當(dāng)然是可行的，但數(shù)據(jù)處理和分派部分的實(shí)現(xiàn)會(huì)比較復(fù)雜，也容易出錯(cuò)。
本文的實(shí)現(xiàn)則選擇了另外一種不同的方法：使用 Python 的內(nèi)部函數(shù)機(jī)制，把一連串查詢變換成一組函數(shù)，每個(gè)函數(shù)取上個(gè)函數(shù)的執(zhí)行結(jié)果作為輸入，最后一個(gè)函數(shù)的輸出就是整個(gè)查詢的結(jié)果。由于內(nèi)部函數(shù)同時(shí)也是閉包，盡管每個(gè)查詢的參數(shù)形式各不相同，但是它們都可以被閉包“捕獲”而成為內(nèi)部變量，所以這些內(nèi)部函數(shù)可以采用統(tǒng)一的形式，無(wú)需再針對(duì)每種查詢?cè)O(shè)計(jì)額外的數(shù)據(jù)結(jié)構(gòu)，因而執(zhí)行過(guò)程得到了很大程度的簡(jiǎn)化。
首先還是來(lái)編寫(xiě)測(cè)試。 LazyQueryTest 和 EagerQueryTest 測(cè)試用例幾乎是完全相同的（是的，兩種查詢只在于內(nèi)部實(shí)現(xiàn)機(jī)制不同，它們的調(diào)用接口幾乎是完全一致的）。
因此我們可以把 EagerQueryTest 的測(cè)試原樣不變拷貝到 LazyQueryTest 中。當(dāng)然拷貝粘貼不是個(gè)好注意，對(duì)于比較冗長(zhǎng)而固定的初始化部分，我們可以把它提取出來(lái)作為兩個(gè)測(cè)試共享的公共函數(shù)。讀者可參考代碼中的 step04_lazy_query/tests/test_lazy_query.py 部分。
程序把查詢函數(shù)的串行執(zhí)行稱為管道（ pipeline ），用一個(gè)變量來(lái)記錄它：
然后依次實(shí)現(xiàn)各個(gè)調(diào)用接口。每種接口的實(shí)現(xiàn)都是類似的：用內(nèi)部函數(shù)執(zhí)行真正的查詢邏輯，再把這個(gè)函數(shù)添加到 pipeline 調(diào)用鏈中。比如 node 的實(shí)現(xiàn)類似下面：
其他接口的實(shí)現(xiàn)也與此類似。最后， run 函數(shù)負(fù)責(zé)執(zhí)行所有查詢，返回最終結(jié)果；
完成上述實(shí)現(xiàn)后執(zhí)行測(cè)試，確保我們的實(shí)現(xiàn)是正確的。
在前面我們說(shuō)過(guò)，延遲查詢與主動(dòng)查詢相比，更大的優(yōu)勢(shì)是對(duì)于許多查詢可以按需要訪問(wèn)，不需要每個(gè)步驟都返回完整結(jié)果，從而提高性能，節(jié)約查詢時(shí)間。比如說(shuō)，對(duì)于下面的查詢：
以上查詢的意思是從孫輩中找到一個(gè)符合條件的節(jié)點(diǎn)即可。對(duì)該查詢而言，主動(dòng)查詢會(huì)在調(diào)用 outcome(‘son’) 時(shí)就遍歷所有節(jié)點(diǎn)，哪怕最后一步只需要之一個(gè)結(jié)果。而延遲查詢?yōu)榱颂岣咝?，?yīng)在找到符合條件的結(jié)果后立即停止。
目前我們尚未實(shí)現(xiàn) take 方法。老規(guī)矩，先添加測(cè)試：
主動(dòng)查詢的 take 實(shí)現(xiàn)比較簡(jiǎn)單，我們只要從結(jié)果中返回前 n 條記錄：
延遲查詢的實(shí)現(xiàn)要復(fù)雜一些。為了避免不必要的查找，返回結(jié)果不應(yīng)該是完整的列表（ list ），而應(yīng)該是個(gè)按需返回的可迭代對(duì)象，我們用內(nèi)置函數(shù) next 來(lái)依次返回前 n 個(gè)結(jié)果：
寫(xiě)完后運(yùn)行測(cè)試，確保它們是正確的。
從外部接口看，主動(dòng)查詢和延遲查詢幾乎是完全相同的，所以用單純的數(shù)據(jù)測(cè)試很難確認(rèn)后者的效率一定比前者高，用訪問(wèn)時(shí)間來(lái)測(cè)試也并不可靠。為了測(cè)試效率，我們引入一個(gè)節(jié)點(diǎn)訪問(wèn)次數(shù)的概念，如果延遲查詢效率更高的話，那么它應(yīng)該比主動(dòng)查詢?cè)L問(wèn)節(jié)點(diǎn)的次數(shù)更少。
為此，編寫(xiě)如下測(cè)試：
我們?yōu)?Dagoba 類添加一個(gè)成員來(lái)記錄總的節(jié)點(diǎn)訪問(wèn)次數(shù)，以及兩個(gè)輔助方法，分別用于獲取和重置訪問(wèn)次數(shù)：
然后瀏覽代碼，查找修改點(diǎn)。增加計(jì)數(shù)主要在從邊查找節(jié)點(diǎn)的時(shí)候，因此修改部分如下：
此外還有 income/outcome 方法，修改都很簡(jiǎn)單，這里就不再列出。
實(shí)現(xiàn)后再次運(yùn)行測(cè)試。測(cè)試通過(guò)，表明延遲查詢確實(shí)在效率上優(yōu)于主動(dòng)查詢。
不像關(guān)系數(shù)據(jù)庫(kù)的結(jié)構(gòu)那樣固定，圖的形式可以千變?nèi)f化，查詢機(jī)制也必須足夠靈活。從原理上講，所有查詢無(wú)非是從某個(gè)節(jié)點(diǎn)出發(fā)按照特定方向搜索，因此用 node/income/outcome 這三個(gè)方法幾乎可以組合出任意所需的查詢。
但對(duì)于復(fù)雜查詢，寫(xiě)出的代碼有時(shí)會(huì)顯得較為瑣碎和冗長(zhǎng)，對(duì)于特定領(lǐng)域來(lái)說(shuō)，往往存在更為簡(jiǎn)潔的名稱，例如：母親的兄弟可簡(jiǎn)稱為舅舅。對(duì)于這些場(chǎng)景，如果能夠類似 DSL （領(lǐng)域特定語(yǔ)言）那樣允許用戶根據(jù)專業(yè)要求自行擴(kuò)展，從而簡(jiǎn)化查詢，方便閱讀，無(wú)疑會(huì)更為友好。
如果讀者去看原作者的實(shí)現(xiàn)，會(huì)發(fā)現(xiàn)他是用一種特殊語(yǔ)法 addAlias 來(lái)定義自己想要的查詢，調(diào)用方法時(shí)再進(jìn)行查詢以確定要執(zhí)行的內(nèi)容，其接口和內(nèi)部實(shí)現(xiàn)都是相當(dāng)復(fù)雜的。
而我希望有更簡(jiǎn)單的方法來(lái)實(shí)現(xiàn)這一點(diǎn)。所幸 Python 是一種高度動(dòng)態(tài)的語(yǔ)言，允許在運(yùn)行時(shí)向類中增加新的成員，因此做到這一點(diǎn)可能比預(yù)想的還要簡(jiǎn)單。
為了驗(yàn)證這一點(diǎn)，編寫(xiě)測(cè)試如下：
無(wú)需 Dagoba 的實(shí)現(xiàn)做任何改動(dòng)，測(cè)試就可以通過(guò)了！其實(shí)我們要做的就是動(dòng)態(tài)添加一個(gè)自定義的成員函數(shù)，按照 Python 對(duì)象機(jī)制的要求，成員函數(shù)的之一個(gè)成員應(yīng)該是名為 self 的參數(shù)，但這里已經(jīng)是在 UnitTest 的內(nèi)部，為了和測(cè)試類本身的 self 相區(qū)分，新函數(shù)的參數(shù)增加了一個(gè)下劃線。
此外，函數(shù)應(yīng)返回其所屬的對(duì)象，這是為了鏈?zhǔn)秸{(diào)用所要求的。我們看到，動(dòng)態(tài)語(yǔ)言的靈活性使得添加新語(yǔ)法變得非常簡(jiǎn)單。
到此，一個(gè)初具規(guī)模的圖數(shù)據(jù)庫(kù)就形成了。
和原文相比，本文還缺少一些內(nèi)容，比如如何將數(shù)據(jù)庫(kù)序列化到磁盤(pán)。不過(guò)相信讀者都看到了，我們的數(shù)據(jù)庫(kù)內(nèi)部結(jié)構(gòu)基本上是簡(jiǎn)單的原生數(shù)據(jù)結(jié)構(gòu)（列表+字典），因此序列化無(wú)論用 pickle 或是 ON 之類方法都應(yīng)該是相當(dāng)簡(jiǎn)單的。有興趣的讀者可以自行完成它們。
我們的圖數(shù)據(jù)庫(kù)實(shí)現(xiàn)為了提高查詢性能，在節(jié)點(diǎn)內(nèi)部存儲(chǔ)了邊的指針（或者說(shuō)引用）。這樣做的好處是，無(wú)論數(shù)據(jù)庫(kù)有多大，從一個(gè)節(jié)點(diǎn)到相鄰節(jié)點(diǎn)的訪問(wèn)是常數(shù)時(shí)間，因此數(shù)據(jù)訪問(wèn)的效率非常高。
但一個(gè)潛在的問(wèn)題是，如果數(shù)據(jù)庫(kù)規(guī)模非常大，已經(jīng)無(wú)法整個(gè)放在內(nèi)存中，或者出于安全性等原因要實(shí)現(xiàn)分布式訪問(wèn)的話，那么指針就無(wú)法使用了，必須要考慮其他機(jī)制來(lái)解決這個(gè)問(wèn)題。分布式數(shù)據(jù)庫(kù)無(wú)論采用何種數(shù)據(jù)模型都是一個(gè)棘手的問(wèn)題，在本文中我們沒(méi)有涉及。有興趣的讀者也可以考慮 500lines 系列中關(guān)于分布式和集群算法的其他一些文章。
本文的實(shí)現(xiàn)和系列中其他數(shù)據(jù)庫(kù)類似，采用 Python 作為實(shí)現(xiàn)語(yǔ)言，而原作者使用的是 JavaScript ，這應(yīng)該和作者的背景有關(guān)。我相信對(duì)于大多數(shù)開(kāi)發(fā)者來(lái)說(shuō)， Python 的對(duì)象機(jī)制比 JavaScript 基于原型的語(yǔ)法應(yīng)該是更容易閱讀和理解的。
圖數(shù)據(jù)庫(kù)存儲(chǔ)結(jié)構(gòu)圖的介紹就聊到這里吧，感謝你花時(shí)間閱讀本站內(nèi)容，更多關(guān)于圖數(shù)據(jù)庫(kù)存儲(chǔ)結(jié)構(gòu)圖,圖數(shù)據(jù)庫(kù)存儲(chǔ)結(jié)構(gòu)圖：探索新一代數(shù)據(jù)管理方式,圖的兩種存儲(chǔ)結(jié)構(gòu)是什么,如何用 Python 實(shí)現(xiàn)一個(gè)圖數(shù)據(jù)庫(kù)（Graph Database）？的信息別忘了在本站進(jìn)行查找喔。
創(chuàng)新互聯(lián)-老牌IDC、云計(jì)算及IT信息化服務(wù)領(lǐng)域的服務(wù)供應(yīng)商，業(yè)務(wù)涵蓋IDC（互聯(lián)網(wǎng)數(shù)據(jù)中心）服務(wù)、云計(jì)算服務(wù)、IT信息化、AI算力租賃平臺(tái)（智算云），軟件開(kāi)發(fā)，網(wǎng)站建設(shè)，咨詢熱線:028-86922220
網(wǎng)頁(yè)標(biāo)題：圖數(shù)據(jù)庫(kù)存儲(chǔ)結(jié)構(gòu)圖：探索新一代數(shù)據(jù)管理方式(圖數(shù)據(jù)庫(kù)存儲(chǔ)結(jié)構(gòu)圖)
當(dāng)前鏈接：http://www.5511xx.com/article/cdcsjcc.html
