Neo4jの検索クエリの時間複雑度はどのくらいですか？

Question

私は、Neo4jデータベースのデータとして500万の製品と100,000の売り手を持っています。売り手は、すべての製品ポートフォリオの中にいくつかの共通の製品を持っています。これらの製品と売り手はノードであり、それらの間の関係はNeo4jデータベースのエッジです。

Neo4jデータベースの各売り手のすべての商品を検索するための検索クエリの複雑さはどのくらいですか？

Answer 1

特定の売り手（または売り手、一度に複数の人を見上げる場合）を探す必要がある場合、関係を横断する複雑さは、特定の売り手（すべての売り手ではない）によって販売される商品に比例しますそれをkと呼ぶ）、したがってO（k）。

売り手ノードを索引で検索します（特定のラベル/プロパティー索引のルーゼン索引ルックアップ、これはO（log（n））とみなされます）。ここでnはその項目の数です特定のインデックス）、次に関連するすべての関係（：Sells？）を、それらの売り手によって販売された製品ノードにトラバースし、次に売り手ごとの製品を収集する。

トラバーサルはグラフの関連部分を歩くだけなので、クエリが1つの売り手とその100個の商品についてクエリであった場合、それらがグラフ内の唯一のノードであるか、 5百万の製品と1 lakhの売り手の提案されたグラフ。

最初の売り手のルックアップにインデックスを使用していない場合は、代わりにすべての売り手ノードでラベルスキャンを実行するため複雑さが変わるため、クエリに比例します売り手ノードの数。

これは、できるだけインデックスを作成し、開始ノードにインデックスルックアップを使用することが不可欠な理由です。

EDIT：

で成長することは、クエリ（販売された製品の数が多いを与えられた）の中で最も高価な部分ではないかもしれないが、私は、Luceneを介して、少し上の...索引参照を明らかに索引付けされたノードの数（その1つの特定のラベル/プロパティー索引の場合）。しかし、ルーシンインデックスルックアップの複雑さを説明するためには、おそらくより緊密な方法があります。この種のルックアップは、ほとんどのデータベースでは、Neo4jやグラフDBに固有のものではないので、グラフのDBパフォーマンスを考える上でインデックスのルックアップは非常に重要ではないと考えています。