0

私が解決しなければならない問題は、ファイル システム ツリーに相当するものをデータベースに格納することです (検索操作を高速化するため)。ツリーには +400.000.000 の inode が含まれており、各 inode に対していくつかのメタ情報を保存する必要があります (平均ファイル パスは 100 バイトで、メタ情報は ~50 バイトです)。

C ++プログラムから次の操作が行われ
ます 。

これまで、リレーショナル データベースのみを考慮してきました: MySQL、MariaDB、PostgresSQL (これまでテストを行っていません。まだ「情報収集」段階です)。そのような DB にツリーを格納する方法に関するドキュメントをいくつか読みました。

最初のオプション
- 隣接リスト モデル: テーブル内の各項目には、その親へのポインターが含まれます。
http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

2 番目のオプション
- すべてのディレクトリを別のテーブルに保存する -
残りのファイル用に別のテーブルを用意し、ファイルが属するディレクトリへのポインタを保持する

したがって、テーブルは次のようになります
。 

/home  
/home/test/

ファイルテーブル: 

file1
file2

私の質問:
1. リレーショナル データベースに巨大なツリーを格納するのに適した別のモデルを知っていますか? 2. NoSQL DB を検索する場合、どこから始めればよいですか?

どうもありがとう。

4

1 に答える 1

1

単一の選択でサブツリー全体を提供できる構造が最適なようです。これを実現するにはいくつかの方法があり、それぞれに利点と欠点があります。

  • 入れ子になったセットでは、表に lft と rgt の 2 つの列を追加します。ノードのサブツリーには、ノードの lft 値と rgt 値の間にある lft 値と rgt 値があります。このモデルは簡単にクエリを実行できますが、ツリーを変更するにはツリー全体の lft 値と rgt 値を書き換える必要があるため、更新にはコストがかかる可能性があります。
  • パスの列挙は、ファイルの絶対パスを列に保持します。このモデルもクエリは簡単ですが、パスの固定長のプレフィックスしかインデックス化できないという事実により、効率的に検索できるツリーの深さが制限されます。
  • クロージャー テーブルの場合、システム上のすべてのディレクトリに対して、サブツリーのどこかに含まれるファイルの ID を保持する新しいテーブルを追加します。繰り返しますが、クエリは簡単ですが、クロージャ テーブルはかなり大きくなる可能性があり、ディレクトリが移動した場合は更新する必要があります。

このスライドショーでは、これらのモデルをグラフとサンプル コードで説明しています: http://www.slideshare.net/billkarwin/models-for-hierarchical-data

于 2012-07-26T13:30:45.737 に答える