質問
ディレクトリ階層/ツリーをKey-Valueデータベース(私の場合はMongoDBですが、いずれか)に保存するためのクリーンで効率的な方法は何ですか?
たとえば、ツリー構造
- Cars
+ Audi
+ BMW
- M5
+ Ford
- Color
+ Red
- Apple
- Cherry
+ Purple
- Funny
現在使用しているメソッド。各オブジェクトはその親にリンクしています
{
dir: "red"
parent-dir: "color"
}
これにより、ツリーのあらゆる側面の挿入と並べ替えが非常に効率的/高速になります(たとえば、赤とそのすべての子をCarsディレクトリに移動する場合)。
しかし、このメソッドは、特定のディレクトリのすべてのサブディレクトリとその子を再帰的に使用したい場合に役に立ちます。解析を効率化するために、たとえば次のような構造を持つことができます
{
dir: "red"
children: "audi, bmw, ford"
}
{
dir: "bmw"
children: "m5"
}
しかし、ツリーを変更したい場合は、オブジェクト全体をタッチして変更する必要があります。
KVストアにディレクトリ構造を保存する他の方法はありますか?
解決
現在使用しているメソッドは、隣接リストモデルと呼ばれます。
(リレーショナル)データベースに階層データを保存する別のモデルは、ネストセットモデルです。 SQLデータベースでの実装はよく知られています。また、修正された先行予約ツリートラバーサルアルゴリズムに関するこの記事も参照してください。
非常に簡単な方法:オブジェクトごとにパスを保存できます-NOSQLデータベースのツリーを照会するのは簡単です:
{ path: "Color", ... }
{ path: "Color.Red", ... }
{ path: "Color.Red.Apple", ... }
{ path: "Color.Red.Cherry", ... }
ノードが削除または名前変更される場合、一部のパスを更新する必要があります。しかし、一般的に、この方法は有望に見えます。セパレータとして特殊文字を予約する必要があります。ストレージスペースのオーバーヘッドはごくわずかです。
編集:このメソッドはマテリアライズドパス
他のヒント
NOSQLの経験はあまりないので、これは決定的な答えではありませんが、次のようにアプローチします。
私はおそらくあなたが持っている最初のアプローチを使用します:
{
dir: 'dir_name',
parent_dir: 'parent_dir_name'
}
次に、map-reduceを設定して、ディレクトリの子をすばやく照会します。 MongoDBのmap-reduce機能はまだ開発ブランチでのみ利用可能であり、私はまだそれを使用していませんが、CouchDB(および、MongoDBで少し変更を加えた場合)では次のようなことができます:
map:
function(doc) {
emit( doc.parent_dir, doc.dir );
}
reduce:
function(key, values) {
return( values );
}
各親ディレクトリのサブディレクトリのリストが表示されます。
データ項目のIDにヒープを保存することをお勧めします。 これが最良の計画だと思います。大量のものが必要な場合、ヒープ要素は別のヒープへのインデックスになります。
eg
{" id:xxx"、" id:yyy"、" sub-heap-id:zzz" ....}
これが明確でない場合は、コメントを投稿してください。家に帰ったら詳細を説明します。
インデックスを作成してください!