圖數據庫vs關係數據庫時空複雜

Question

圖和關係數據庫橫向的時間複雜度是多少？

Answer 1

O（N）for both？

圖形DB在其核心有一個表格（https://stackoverflow.com/a/2968931/623735）。 RDB在處理表格方面已經發展得非常高效。因此，具有持久存儲的大多數大型GDB使用RDB來存儲節點表。 GDB只是將所有常規數據錶行的id堆棧到一個「節點」表（爲了有效索引而分組和排序）中。 GDB的神奇之處在於用於行走/探索圖形的高效算法。

所以我不認爲GDB真的在兩個表（遍歷）上進行連接，就像RDBMS對同一類數據上的同一種查詢所做的那樣。一個GDB只是從一個節點（節點表中的行）走到另一個節點（以鏈表的方式）。一旦找到您查詢的節點，就會對節點屬性表執行一次「遍歷」以檢索您查詢的信息（名稱，排名，序列號;）。

Answer 2

也許你會發現這篇文章「Efficient graph management based on bitmap indices」有幫助。在第4部分稱爲實驗結果中，作者測試了mysql，圖數據庫DEX和Neo4j以及列存儲MonetDB中的相同查詢（包括查詢1和2中的遍歷）。

對於某個遍歷操作，DEX（圖形數據庫）和mysql之間的區別是120秒（DEX）和12小時執行（mysql）次。

您還可以閱讀位圖存儲的有趣方法。

Answer 3

更快，計算機或代數？

關係模型是思考有關數據的方式，一種方式代表數據到用戶。它說沒有什麼關於實現。詢問關係數據庫的時間複雜度就像詢問時間複雜度爲f(x)。

沒有SQL DBMS我已經使用元組的線性數組來存儲數據。他們都使用某種樹：B-樹，B +樹。一棵樹是一張圖。 Ergo，物理圖形數據庫聲稱的優勢是基於，好吧，如果你問我什麼都沒有。

SQL DBMS在過去幾年中增加了對所謂遞歸查詢的支持。這些查詢的有效執行沒有理論上的問題，我已經看到它完成了。但是查詢優化器必須支持它才能正常工作，如果開源項目在這方面有一些工作要做，我不會感到驚訝。

在選擇你的武器，不要問關於「關係數據庫」，但關於具體的實現遞歸查詢處理的支持，

小心假對稱的，雖然。 「圖表數據庫」中缺少一個相當長的列表。例如，關係模型基於代數，這是SQL基於（大部分，鬆散地）的內容。圖論缺乏這樣的代數，因此也是一種很好的操作語言。強制執行和交易也有類似的情況。

Answer 4

圖數據庫的一個（也許是）關鍵點是不必爲遍歷做任何連接。