walk ndb directory structure

Question

Since Google App Engine NDB has a directory structure, what is the best way to walk this structure to perform a depth-first traversal of each entity. I would like the entities to be traversed in this order using ndb and the Python programming language.

            1
          / | \
         2  8  9
        / \     \
       3   7    10
     / | \      / \
    4  5  6    11 12

Answer 1

ndb doesn't have a directory structure. You can create a tree structure using ancestor keys, however it would be a fixed tree, you can't move elements around, and parents don't have to exist. In addition there may be many roots. A tree built this way will also be limited by write speed because all elements will belong to a single entity group. Which has its positive and negatives depending on what you are doing.

If you structured a tree like this there is no mechanism to get immediate children, so you would have to perform and ancestor query, and order by key which would essentially give you a depth first list of entities that you could loop over. You could store additional properties in the objects that would allow you to limit the query depth.

See kindless ancestor queries - https://developers.google.com/appengine/docs/python/datastore/queries#Python_Kindless_ancestor_queries . If all nodes are the same Kind then you can do a basic ancestor query for the node Kind.

You can get the immediate parent key of any entity (assuming the entity exists you can get the parent).

I implements tree's in a CMS, however I doesn't use ancestor keys. Each parent stores the immediate childrens keys (and names) so you can walk the tree explicitly and move nodes around.