Optimierung der Hierarchie im Google Appengine-Datenspeicher

Question

Ich habe hierarchische Daten im Datenspeicher gespeichert und verwende ein Modell, das wie folgt aussieht:

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

Ich möchte alle Kategorienamen unter Beibehaltung der Hierarchie ausdrucken, z. B. in einer Form wie dieser:

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

Um dies zu erreichen, habe ich eine einfache Rekursion mit Hilfe der Rückverweisungsfunktion verwendet:

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)

Da ich sehr neu in der App-Engine-Programmierung bin (kaum 3 Tage, seit ich mit dem Schreiben von Code begonnen habe), bin ich nicht sicher, ob dies der optimierte Weg vom Standpunkt des Datenspeicherzugriffs aus ist, um die gewünschte Aufgabe zu erledigen.

Ist dies der beste Weg? Wenn nicht, was dann?

Answer 1

Der Hauptnachteil Ihres Ansatzes besteht darin, dass Sie aufgrund der Verwendung der "Adjazenzliste" für die Darstellung von Bäumen eine Datenspeicherabfrage für jeden Zweig des Baums durchführen müssen. Datenspeicherabfragen sind ziemlich teuer (ca. 160 ms pro Abfrage), so dass die Erstellung des Baums, insbesondere wenn er groß ist, ziemlich teuer sein kann.)

Es gibt noch einen anderen Ansatz, der im Wesentlichen dem des Datenspeichers zur Darstellung von Entitätsgruppen entspricht: Anstatt nur den übergeordneten Schlüssel zu speichern, speichern Sie die gesamte Liste der Vorfahren mit einer ListProperty:

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

Um den Baum zu konstruieren, können Sie dann das Ganze in einer einzigen Abfrage abrufen:

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

Answer 2

Sie haben einen sehr vernünftigen Ansatz! Mein Hauptvorbehalt wäre einer, der wenig mit GAE und viel mit Python zu tun hat: nicht eine Kette aus Teilen mit + ou += . Stattdessen erstellen Sie eine Liste von String-Stücken (mit append ou extend oder List Comprehensions &c), und wenn Sie fertig sind, fügen Sie sie zusammen, um das endgültige String-Ergebnis mit ''.join(thelist) oder dergleichen. Auch wenn sich die neueren Python-Versionen sehr bemühen, die intrinsische O(N squared) Leistung der + ou += Schleifen, ist es letztlich immer besser, wenn Sie unterwegs Listen von Strings erstellen und ''.join Sie werden erst ganz zum Schluss auftauchen!