AgensGraph-Btree VS Neo4j-IndexFree

Question

データを効率的に処理するため、Neo4jは「インデックスフリーの隣接関係」の方法でグラフデータを検索します。しかし、私はAgensGraphがPostgreSQLの "Btree"の方法をクエリに使用していることを知っています

"Index-free adjacency"と比較してPostgreSQLの "Btree"を使う利点は何ですか？

Answer 1

私が理解しているように、「インデックスフリーの隣接関係」は、Neo4jが一定時間O（1）でノードの隣接要素を得ることができることを意味します。

AgensGraphは特にどのように動作するのかわかりませんが、要素を取得するBTreeではO（ログn）です。

Answer 2

Neo4jは、固定サイズの配列を使用して、ノードとリレーションシップに関する情報を格納します。構造が提供する利点の1つは、IDの乗算と要素の固定サイズを計算することによって、内部IDを持つファイル内のノードまたは関係の場所を見つけることができることです。だから、Neo4jはBtree構造（RDBMSで一般的です）を必要とせず、Neo4jはグラフデータに対して「インデックスフリーの隣接関係」を提供すると主張しています。

逆に、AgensGraphは、頂点（ノード）またはエッジ（関係）を見つけるために使用します。 Neo4jのO（1）と比較してO（log n）なので、AgensGraphのアプローチはNeo4jほど速くないと感じるかもしれません。

理論上、これは真です。しかし実際には、考慮すべき点がいくつかあります。まず、RDBMSではログのベースが非常に大きくなります。したがって、Btree（log n）の高さは非常に小さく（ほとんどの場合< = 3）、Btreeの内部ページはほとんどメモリにキャッシュされます。

さらに重要なのは、グラフのトラバーサルを処理するときに実際のディスクI/Oが必要であると考えると、実際にはそれほど単純ではありません。

AgensGraphでは、クエリが頂点（IDがv1）に隣接するエッジを検出すると、Btreeを検索し、Btreeのループアップですべての隣接エッジのIDを取得し、 Btree。 Btreeのリーフエントリにはエッジがクラスタリングされているため、隣接するエッジを高速に取得できます。サーバ側の隣接する辺があるにもかかわらず、AgensGraphはBtreeの参照を1つ必要とします。しかし、Neo4jでは、関係を固定サイズの配列の異なるページに格納することができます。隣接関係は、二重リンクリストを使用してリンクされます。したがって、ファイル全体に散らばっていると、より多くのランダムI/Oが必要になります。

実際、AgensGraphはNeo4jより高速であり、Btreeもこれらの同時アクセス用に最適化されているため、マルチクライアントセッションでも更新が効率的です。