私は、C++ 用のグラフベース (またはキー値) データベース ライブラリの設計の準備段階にいます。これは、多くの人がhttp://neo4j.org/などのプロジェクトに似ていることがわかります。
これは設計の非常に初期の段階であるため、私の要件は単純で洗練されておらず、(認めますが)おそらくまだかなり素朴です。
- 有向非巡回グラフ
- 根が少なく葉が多い木のような構造
- ブランチには他のブランチへの参照が含まれる場合があります
- しかし、サイクルはありません
- グラフはキーと値のペアで表されます。ほとんどの場合、キーと値は単純な型 (整数) ですが、一部は文字列などのより複雑な型を参照する場合があります。
- クエリ
- 通常、単純なクエリではエッジが返されます。つまり、このルートから始まるエッジは、(キー / 値 / キーと値のタプル) に対応しますか?
- キーの文字列を使用したクエリ (キー、キー、キー、値)
- アクセスパターンとパフォーマンス
- 高速ルックアップを強調する必要があります
- エッジの追加
- ただし、グラフからのエッジ/ノードの削除はありません。つまり、グラフは大きくなりますが、縮小することはありません。
- キャッシュの使用に合わせてメモリ レイアウトを最適化するために、グラフで最適化が実行される場合があります。
- グラフのサイズは約 1 MB ～ 2 GB で、ほとんどの場合、プライマリ メモリに収まるはずです。
これらの大まかな要件を課題として考えると、主な懸念事項は次のとおりです。
- メモリ ストレージ: レイアウト、割り当て
- たとえば、固定サイズのブロックのプールですか?
- クラスタリングアルゴリズムによるメモリ割り当て?
- 高速クエリ
- 動的再編成
- エッジ/ノードの追加を処理する方法は?
- 最適化のための更新 (例: メモリ レイアウトの改善)
- 同時アクセス
- たとえば、最適化スレッドによるメモリ レイアウトの変更を処理しますか?
私は仕事をするための良い出発点を探しているので、既存の仕事への参照を喜んで受け取ります. 最も重要なのは、私が考えていなくて、何を考えるべきか?