グラフベースの（キー/値）データベースのパフォーマンス指向設計

Question

私は、C++のグラフベース（またはキー値）データベースライブラリの設計段階にあります。 http://neo4j.org/となります。これは設計の非常に初期の段階なので

、私の要件は、（私は認める）おそらくまだかなりナイーブ未精製、シンプルであり、：

• Aは非巡回グラフ
  • TREE-を監督しましたいくつかのルーツと多くの葉
  • 分岐構造のような他の支店への参照
  • しかし、無サイクル
  が含まれていてもよいです
  • グラフは、大部分のキーと値の単純なタイプ（整数）であるキーと値のペアで表されるが、一部はそのような文字列
• クエリなど、より複雑な型を指すことができる
  • 単純なクエリは、通常、エッジを返します。私。このルートから始まるエッジは（キー/値/キー値タプル）に対応しますか？キーの文字列を使用して
  • クエリ（キー、キー、キー、値）
• アクセスパターンとパフォーマンス
  • 高速検索がエッジ
  • の
  • 追加を強調すべきである。しかしグラフからエッジ/ノードを削除しないでください。私。グラフは大きくなりますが、縮むことはありません。
  • 最適化は、キャッシュ使用のためのメモリ・レイアウトを最適化するために、グラフ上で実行されてもよい
  • グラフのサイズは、約1メガバイトのオーダーである2 - GBとすべき主記憶
  に大部分のフィット感
課題としてこれらのラフな要件を考えると

、あなたの主な関心事はに関して何でしょう：

• メモリストレージ：レイアウト、割り当て
  • など。固定サイズブロ​​ックのプール？
  • クラスタリングアルゴリズムによるメモリ割り当てですか？
• 高速クエリ
• ダイナミック再編エッジ/ノードの追加を処理する方法
  • ？
  • 最適化のための更新（例えば、メモリレイアウトを改善する）
• 同時アクセス
  • 例えば最適化スレッドによるメモリレイアウトの変更の処理？

私はので、私は既存の作業への参照を受信するよりも幸せだし、仕事をする、そこから良い出発点を探しています。 最も重要なこと：何をする必要があります私はそれについて考えているについて考えていますか？あなたが参照のために興味があるかもしれない

Answer 1

高速なキー/値データベースを使用すると、高速エッジがを挿入する必要がある場合、これは重い要件ですhttp://www.corpit.ru/mjt/tinycdb.html

Answer 2

TinyCDB しかし、無サイクル

です。新しい辺がサイクルを導入しないことを確認することは、最悪の場合のO（v + e）である（vは頂点の数であり、eは辺の数である）。おそらくエッジの同時挿入も除外されます。この要件をオプションにすることを検討してください。

もう1つのオプションは、2つの挿入操作を区別することです。CheapInsertとExpensiveInsertです。各頂点に「ランク」の整数を付け、より低い頂点から高いランクの頂点までの安価なエッジの挿入を許可します。高価な挿入物にはこの制約はなく、必要に応じてランクを自動的に書き換えます。クライアントは、（低から高のルールが壊れていない限り）任意の頂点のランクを検査して変更することができます。こうすることで、高価な挿入を避けるためにグラフの特定のプロパティを利用することで、独自の挿入戦略を実装することができます。