Vertices テーブルと Edges テーブルを作成することを検討しましたが、メモリ内にグラフを作成し、サブグラフをトラバースするには、多数のルックアップが必要ですか? 過度のデータベース読み取りを避けたいです。グラフを永続化する他の方法はありますか?
補足: Neo4j については聞いたことがありますが、私の質問は、標準データベースでグラフを概念的に表現する方法です。ただし、mongodb のようないくつかの NoSQL ソリューションにはオープンです。
質問する
31241 次
4 に答える
0
ここでの他の投稿には同意しません。制限付きの特別なクラスのグラフがある場合は、より特殊な設計でうまくいくことがよくあります (たとえば、頂点ごとのエッジの数を制限する、一方向のみをトラバースする必要があるなど)。
ただし、任意のグラフを保存する場合、リレーショナル データベースは、ほぼすべての状況で適切に機能する、非常に優れた一連のトレードオフを実現します。さらに、データのニーズは時間の経過とともに変化する傾向があり、リレーショナル データベースを使用すると、データ表現を変更することなく、ストレージとルックアップを簡単に変更できます。
設計を確認してみましょう。
- 頂点用の 1 つのテーブル (id、データ)
- エッジ用の 1 つのテーブル (startId、endId、data)
最初に、保存するデータに比例するため、ストレージが効率的であることを観察します。10 個の頂点と 10 個のエッジがある場合、20 個の情報を格納します。
では、ルックアップを見てみましょう。頂点 ID にインデックスがあると仮定すると、少なくとも必要なデータを検索できますlog(n)(インデックスによってはより良いかもしれません)。
- 与えられたノードから出るエッジを教えてください
- 与えられたノードに入るエッジを教えてください
- エッジが与えられた場合、それが発生したノードまたは入力したノードを教えてください
必要な基本的なクエリはこれですべてです。
ここで、各頂点から出るエッジのリストを格納する「グラフ データベース」があるとします。これにより、各頂点が可変サイズになります。トラバースが少し楽になります。しかし、反対方向に移動したい場合はどうすればよいでしょうか。これで、各頂点に入るエッジのリストも保存できました。これで、その情報のコピーが 2 つになりました。データベース (または開発者) は、それらが同期されないようにするために多くの作業を行う必要があります。
O(log(n)) 対 O(1)
リレーショナル データベース インデックスは、通常、データを並べ替えられた形式で格納するか、他の人が指摘したように、ハッシュ テーブルを使用することもできます。sorted に固執している場合でも、非常にうまく機能します。
最初に、ビッグオーはパフォーマンスではなくスケーラビリティを測定することに注意してください。ハッシュは、小さなデータ セットの多くのループよりも遅くなる可能性があります。O(1)二分探索には優れていlog2ますが、かなり良いです。30 ステップで 10 億件のレコードを検索できます。さらに、キャッシュと分岐予測に適しています。
于 2022-02-23T00:00:43.673 に答える