Hi Nick,
no, level and position are not identical.
The idea behind it is to use level for node to know how deep in tree
it exists, so root nodes have level=0, node with one parent have
level=1, node with three parents (A-B-C-D) have level=3, etc.. This
should allow simple move in path.. WHERE level ><...
Position will be used just for sorting. It will start in every subtree
with zero value, and will be incremented when new node is added, so it
will be possible to reorder node position in subtree, something like
this should be possible:
BEFORE:
A(0) level = 0
/ | \
B(0) C(1) D(2) level = 1
/ \
E(0) F(1) level = 2
(Note: number in brackets represents position)
AFTER (node B, C reorder):
A(0) level = 0
/ | \
C(0) B(1) D(2) level = 1
/ \
E(0) F(1) level = 2
What do you think about it? There will be probably maximum few
hundreds of levels. Does it fits for datastore?
Do i have to create index on parents property? If yes, size of this
index will probably grow nonlinear with growing amount of levels. And
i have to put also position, level and yet another two or three
properties under index. What is the maximum index size? I did found
just one information about it in documentation - `its huge`, but what
does huge exactly mean?
My hopefully last question :)
Is there somewhere some paper about deeper explanation of datastore?
It would be nice to know how it exactly works in deeper level, how are
the query counters working (i had some problem there also), etc...
Thanks a lot!
Peter.
On Jul 14, 11:47 am, "Nick Johnson (Google)" <[email protected]>
wrote:
> Hi Peter,
>
>
>
>
>
> On Mon, Jul 13, 2009 at 6:56 PM, Peter Cicman<[email protected]> wrote:
>
> > Hi Nick, hi Vince, i did come up with something like this yesterday:
>
> > class Tree(db.Expando):
> > parents = ListProperty()
> > level = IntegerProperty()
> > position = IntegerProperty()
>
> > properties:
> > parents: sorted list of all parent keys, sorting order top/down,
> > so parents[-1] gives object direct parent
> > level: nested level, for root nodes = 0, for children of root node
> > = 1, etc..
> > position: node position in current subtree, 0 on top, n on bottom
>
> Won't level and position always be identical?
>
>
>
> > Probably it will work, parent, children, descendants selection should
> > be possible. Its probably very close to solution described by Nick.
>
> > ----
>
> > But anyway, the key paths looks like so nice solution for tree
> > structure, so i'm still thinking about them. It brings up some
> > questions:
>
> Key names internally use the same sort of structure as you just
> outlined using a ListProperty. Given that you want to move your
> objects without renaming them, using parent relationships is not a
> good idea here.
>
>
>
> > - is there a possibility to use other property for path than a
> > key? probably not if i understand the implementation
>
> No, only the key works.
>
>
>
> > - moving the node with all descendants is currently be possible
> > this way: copy node, change key, save it, delete original node. the
> > question is - if the datastore is represented like a hash, why key
> > change isn't allowed? What is so difficult on this?
>
> You also need to repeat the operation for all child entities of the object.
>
> The datastore is not stored as a hash table, it's stored as a sorted
> list. Key changes aren't permitted because they're identical to a
> deletion followed by an insertion - so we expose that fact to the
> user.
>
> -Nick Johnson
>
>
>
>
>
>
>
> > - if the key change really isn't possible on datastore level,
> > can't there be some helper in datastore API for doing this (change
> > instance key / change instance keys on node + all descendants,
> > eventually also delete method, which performs descendants deletion
> > when parent gets removed)..
>
> > Thanks...
>
> > On Jul 13, 1:51 pm, Vince Stross <[email protected]> wrote:
> >> I use the following structure:
>
> >> class Tag (db.Expando):
> >> label = StringProperty()
> >> parent_ = SelfReferenceProperty(collection_name='children')
>
> >> This is a simplified for illustration purposes, but it works well
> >> enough for us because we just grab all Tag entities and build the tree
> >> in memory with a single simple function. Of course, we will never be
> >> more than 3-4 deep and always have less than 100 tags total.
>
> >> On Jul 13, 5:17 am, "Nick Johnson (Google)" <[email protected]>
> >> wrote:
>
> >> > Hi Peter,
>
> >> > On Sun, Jul 12, 2009 at 8:31 PM, Peter Cicman<[email protected]> wrote:
>
> >> > > I had spend some time today with building tree structure using
> >> > > datastore. I need a real tree, for real world, so there must be a
> >> > > possibility to move node with all descendants. There must also be a
> >> > > quick way to find all ancestors, children and descendants.
>
> >> > I'm not aware of any tree structure that fits both those requirements
> >> > - in fact, I'm fairly sure it's not possible.
>
> >> > There are two basic approaches to representing trees: Ones that
> >> > encompass the node's position in the entire tree, such as materialized
> >> > path and nested set notation, and ones that only encompass the node's
> >> > relationship to neighbouring nodes, such as adjacency lists. The
> >> > former permit easily querying all descendants, while the latter make
> >> > it easy to move entire branches. I don't think it's possible to have
> >> > both at once.
>
> >> > If moving a branch is less common than querying, and your trees are
> >> > relatively shallow (Say, less than 100 levels deep), I would recommend
> >> > using the materialized path approach: Have a ListProperty that lists
> >> > all the ancestors of the node.
>
> >> > -Nick Johnson
>
> >> > > So, datastore keys can not be used for tree like this - because key
> >> > > can not change, and i would like to prevent node copying/deletion,
> >> > > because this must be always done on node and all its descendants which
> >> > > may end up with tons of sql queries.
>
> >> > > Design i made should fit for me, but maybe there is some common
> >> > > solution for this problem... Anybody knows about some optimal
> >> > > solution? (i can not use serialization)
>
> >> > > Thanks a lot!
>
> >> > --
> >> > Nick Johnson, App Engine Developer Programs Engineer
> >> > Google Ireland Ltd. :: Registered in Dublin, Ireland, Registration
> >> > Number: 368047
>
> --
> Nick Johnson, App Engine Developer Programs Engineer
> Google Ireland Ltd. :: Registered in Dublin, Ireland, Registration
> Number: 368047
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Google App Engine" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/google-appengine?hl=en
-~----------~----~----~----~------~----~------~--~---
