On Tue, Jul 14, 2009 at 8:35 PM, Peter Cicman<[email protected]> wrote: > > 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:
Ah. The distinction wasn't clear initially. Given that 'position' in your example appears to apply to all nodes of a given depth, how will you efficiently calculate and update this? Inserting a new leftmost leaf node would require renumbering every other node's position. > > 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? Yes, though a 'few hundred' is getting to the point where the ListProperty of ancestors will take a significant amount of time to update. > > 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? You only have to index the properties if you want to execute queries against them that use more than one property and involve an inequality or a sort order. See the indexing documentation for more details. The indexing is limited by index entries per entity, not size - and the limit is in the low thousands. > > > 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... Reading the Bigtable paper would be a good start. -Nick Johnson > > 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 > > > -- 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 -~----------~----~----~----~------~----~------~--~---
