Google Appengine Datastoreの階層最適化

Question

次のようなモデルを使用して、データストアに階層データを保存しています：

class ToolCategories(db.Model):  
   name = db.StringProperty()  
   parentKey = db.SelfReferenceProperty(collection_name="parent_category")  
   ...  
   ...  

次のような形式で、階層を保持しているすべてのカテゴリ名を印刷したい：

--Information Gathering  
----OS Fingerprinting  
----DNS  
------dnstool  
----Port Scanning   
------windows  
--------nmap  
----DNS3  
----wireless sniffers  
------Windows  
--------Kismet  

上記を行うには、後方参照機能を使用して単純な再帰を使用しました。

class GetAllCategories (webapp.RequestHandler) :


        def RecurseList(self, object, breaks) :
                output = breaks + object.name + "</br>"
                for cat in object.parent_category:
                        output = output + self.RecurseList(cat, breaks + "--")

                return output



        def get (self) :
                output = ""
                allCategories = ToolCategories.all().filter(' parentKey = ', None)
                for category in allCategories :
                        output = output + self.RecurseList(category, "--")

                self.response.out.write(output)

App Engineプログラミングは非常に新しいため（コードの記述を開始してから3日以内）、これがデータストアアクセスの観点から最適な方法で目的のジョブを実行するかどうかはわかりません。

これが最良の方法ですか？そうでない場合は何ですか？

Answer 1

非常に合理的なアプローチがあります！私の主な注意点は、GAEとはほとんど関係なく、Pythonと多くの関係があることです。 + または + = 。むしろ、文字列の断片のリストを作成し（ append または extend またはリスト内包表記＆amp; cを使用）、完了したらそれを結合して最終的な文字列にします ''。join（thelist）などの結果。最近のPythonバージョンは、 + または + = ループの本質的に O（N squared）のパフォーマンスを最適化するために努力していますが、最終的には「途中で文字列のリストを作成し、最後にそれらを ''。join することをお勧めします！

Answer 2

アプローチの主な欠点は、「隣接リスト」を使用しているためです。ツリーを表す方法では、ツリーの各ブランチに対して1つのデータストアクエリを実行する必要があります。データストアクエリはかなり高価です（それぞれ約160ミリ秒）。したがって、特にツリーが大きい場合、ツリーの構築はかなり高価になる可能性があります）。

別のアプローチがあります。これは、本質的にエンティティグループを表すためにデータストアが採用するアプローチです。親キーを単に保存する代わりに、ListPropertyを使用して祖先のリスト全体を保存します。

class ToolCategories(db.Model):
  name = db.StringProperty()
  parents = db.ListProperty(db.Key)

その後、ツリーを構築するために、1つのクエリですべてを取得できます：

q = ToolCategories.all().filter('parents =', root_key)