Tree structures in a nosql database?

There are a number of well known ways to represent trees in databases; each of them have their pros and cons. Here are the most common: Adjacency list where each node stores the ID of its parent Materialized path which is the strategy Keyur describes. This is also the approach used by entity groups (eg, parent entities) in App Engine.It's also more or less what you're describing in your update Nested sets where each node has 'left' and 'right' IDs, such that all child nodes are contained in that range Adjacency lists agumented with a root ID Each of these has its own advantages and disadvantages.

Adjacency lists are simple, and cheap to update, but require multiple queries to retrieve a subtree (one for each parent node). Augmented adjacency lists make it possible to retrieve an entire tree by storing the ID of the root node in every record Materialized paths are easy to implement and cheap to update, and permit querying arbitrary subtrees, but impose increasing overhead for deep trees Nested sets are tougher to implement, and require updating, on average, half the nodes each time you make an insertion. They allow you to query arbitrary subtrees, without the increasing key length issue materialized path has In your specific case, though, it seems like you don't actually need a tree structure at all: each story, branched off an original though it may be, stands alone.

What I would suggest is having a 'Story' model, which contains a list of keys of its paragraphs (Eg, in Python a db. ListProperty(db. Key)).

To render a story, you fetch the Story, then do a batch fetch for all the Paragraphs. To branch a story, simply duplicate the story entry - leaving the references to Paragraphs unchanged.

There are a number of well known ways to represent trees in databases; each of them have their pros and cons. Here are the most common: Adjacency list, where each node stores the ID of its parent. Materialized path, which is the strategy Keyur describes.

This is also the approach used by entity groups (eg, parent entities) in App Engine. It's also more or less what you're describing in your update. Nested sets, where each node has 'left' and 'right' IDs, such that all child nodes are contained in that range.

Adjacency lists agumented with a root ID. Each of these has its own advantages and disadvantages. Adjacency lists are simple, and cheap to update, but require multiple queries to retrieve a subtree (one for each parent node).

Augmented adjacency lists make it possible to retrieve an entire tree by storing the ID of the root node in every record. Materialized paths are easy to implement and cheap to update, and permit querying arbitrary subtrees, but impose increasing overhead for deep trees. Nested sets are tougher to implement, and require updating, on average, half the nodes each time you make an insertion.

They allow you to query arbitrary subtrees, without the increasing key length issue materialized path has. In your specific case, though, it seems like you don't actually need a tree structure at all: each story, branched off an original though it may be, stands alone. What I would suggest is having a 'Story' model, which contains a list of keys of its paragraphs (Eg, in Python a db.

ListProperty(db. Key)). To render a story, you fetch the Story, then do a batch fetch for all the Paragraphs.To branch a story, simply duplicate the story entry - leaving the references to Paragraphs unchanged.

Yup, I already chose not to use adjacency lists (too high read cost) or nested sets (too high write cost). Your solution sounds good. I guess I was afraid to keep a list of 200 keys on one entity, but that shouldn't be a problem, I guess.

I actually already went ahead and implemented my solution and it works fine too with no performance issues, so I'll probably use it for a while and see if it makes more sense to go over to your solution. – Blixt Jul 20 '10 at 12:53 Thanx for the explaination, it is very helpful. – RAHUL PRASAD May 9 at 11:34.

One solution I can think about is - the path to the node is also the key of that node. So the key of node 11 is "2/7/6/11". You can traverse the path by a simple key lookup of all keys in the path - "2/7/6/11", "2/7/6", "2/7", "2.

Good point. The only downside I see is that once you've got 200 nodes, that key will be very long. I don't know if it would be an issue, though.

– Blixt Jul 19 '10 at 19:02.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.