Hi Nick, i just found my model will not work efficiently. The problem is not not position update, there will be max few tens of nodes in subtree, so i just have to update them, and even if enough big distance between positions will be chosen, lets say 10000, i can just do simple checks between two nodes, (e.g. average value from positions which are around) and change the position in my node, this will mean few selects with 2 entries, and one update.
Eg: B, C, D are sub nodes of A pB (position of B) = 1 000 000, because it was the first node created under B pC = 1 010 000 pD = 1 020 000 nov - reoder to get D, B, C will with some few queries and checks result with: pB = 1 000 000 (unchanged) pC = 1 010 000 (unchanged) pA = (1 000 000 - 0) / 2 = 500 000 (position updated) [0 is there because A is the first node] This will give me a possibility for quick changed in position. Of course there may be a conflict if i would like to `move` node between two nodes (Left, Right) and when pR - pL = 0 (difference between two possitions). This may lead to update of position of multiple nodes, but probably only one 2 nodes will be updated. But for this, there may be cron checking difference between positions, and... But i'm not expecting hundreds of positional moves anyway... The problem is somewhere else - lies in parents[] property. If there will be a move on lets say second level, and moved node have 5 000 descendants, parents property of all descendants must be updated, this will probably not be fast enough, or on other words, it will be very expensive. Hmm, i need something better here... But, anyway thanks for your help! Peter. Of course, there might be a conflict when the On Jul 15, 3:17 pm, "Nick Johnson (Google)" <[email protected]> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
