13

データストアにBigTableを使用するGoogleAppEngine用のアプリケーションを開発しています。

ストーリーを共同で書くためのアプリケーションです。とてもシンプルな趣味のプロジェクトで、楽しみのために取り組んでいます。これはオープンソースであり、ここで見ることができます：http ://story.multifarce.com/

アイデアは、誰でも段落を書くことができ、それを他の2人が検証する必要があるということです。ストーリーは任意の段落で分岐できるため、ストーリーの別のバージョンを別の方向に続けることができます。

次のツリー構造を想像してみてください。

すべての数字は段落になります。すべてのユニークなストーリーラインのすべての段落を選択できるようにしたいと思います。基本的に、それらのユニークなストーリーラインは（2、7、2）です。（2、7、6、5）; （2、7、6、11）および（2、5、9、4）。ノード「2」が2回表示されることを無視して、ウィキペディアからツリー構造図を取得しました。

また、提案されたソリューションの図を作成しました：https ://docs.google.com/drawings/edit?id=1fdUISIjGVBvIKMSCjtE4xFNZxiE08AoqvJSLQbxN6pc&hl=en

構造を設定するには、書き込みと読み取りの両方でパフォーマンスが効率的ですが、最も重要なのはどのようにすればよいですか？

4

2 に答える 2

16

データベースでツリーを表現するよく知られた方法がいくつかあります。それぞれに長所と短所があります。最も一般的なものを次に示します。

  • 各ノードがその親の ID を格納する隣接リスト。
  • Keyur が説明する戦略であるMaterialized path 。これは、App Engine のエンティティ グループ (親エンティティなど) で使用されるアプローチでもあります。それは多かれ少なかれ、更新で説明していることでもあります。
  • ネストされたセット。各ノードには「左」と「右」の ID があり、すべての子ノードがその範囲に含まれます。
  • ルート ID で拡張された隣接リスト。

これらにはそれぞれ独自の長所と短所があります。隣接リストは単純で、更新が安価ですが、サブツリーを取得するには複数のクエリが必要です (親ノードごとに 1 つ)。拡張された隣接リストを使用すると、すべてのレコードにルート ノードの ID を格納することで、ツリー全体を取得できます。

具体化されたパスは実装が簡単で、更新が安価で、任意のサブツリーのクエリを許可しますが、深いツリーのオーバーヘッドが増加します。

ネストされたセットは実装が難しく、挿入を行うたびに平均して半分のノードを更新する必要があります。マテリアライズド パスが持つキーの長さの問題を増加させることなく、任意のサブツリーをクエリできます。

ただし、あなたの特定のケースでは、実際にはツリー構造はまったく必要ないようです。各ストーリーは、オリジナルから分岐している可能性がありますが、独立しています。私が提案するのは、その段落のキーのリストを含む「ストーリー」モデルを持つことです（たとえば、Pythonではdb.ListProperty（db.Key））。ストーリーをレンダリングするには、ストーリーをフェッチしてから、すべての段落に対してバッチ フェッチを実行します。ストーリーを分岐するには、ストーリー エントリを複製するだけです。段落への参照は変更しません。

于 2010-07-20T09:05:30.230 に答える
0

私が考えることができる1つの解決策は、ノードへのパスがそのノードのキーでもあるということです。したがって、ノード 11 のキーは「2/7/6/11」です。パス内のすべてのキー (「2/7/6/11」、「2/7/6」、「2/7」、「2」) の単純なキー検索によって、パスをたどることができます。

于 2010-07-19T18:54:07.127 に答える