couchdb-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Andrey Kuprianov <andrey.koupria...@gmail.com>
Subject Re: Tree like structures in CouchDB
Date Fri, 22 Feb 2013 07:07:53 GMT
@Elisiano: having references to children is redundant. You can simply build
a view to get children by immediate parents.

@Jim: you are right. I've never seen a thread deeper than 20-30 levels. And
I actually feel like I'm exaggerating here. :)


On Fri, Feb 22, 2013 at 3:04 PM, Elisiano Petrini <elisiano@gmail.com>wrote:

> Hi All,
>     please forgive me if I'm missing/overlooking something here, I'm not
> a couchdb expert.
>
> It all depends on the needs of the project but usually one would want to
> trasverse the tree from the root node down to its children.
> In every implementation of trees that I've seen (and done) so far, it's
> always the parent node knowing which are its children and not the other
> way around.
>
> In this particular case (having a structure of messages) I would still
> have a list of direct children in the parent but also have a reference
> to the parent in a child node in order to easily trasverse the tree in
> both directions.
>
> Having only the reference to the parent, how would you effectively
> reconstruct the tree? Reading all the documents and then reconstruct the
> structure? (or am I missing something here?).
>
> Cheers, Elisiano
>
> On Fri, 2013-02-22 at 19:09 +1300, Michael Heuberger wrote:
> > andrey, svilen, many thanks again.
> >
> > agreed, storing immediate children in a document is a bad idea. i think
> > i go for storing only an immediate parent id to get an infinite tree
> depth.
> >
> > thanks for your inspirations guys
> >
> > cheers
> > michael
> >
> > On 22/02/13 18:49, Andrey Kuprianov wrote:
> > > PS - storing only an immediate parent id would be the solution for an
> > > infinite tree depth.
> > >
> > >
> > > On Fri, Feb 22, 2013 at 1:48 PM, Andrey Kuprianov <
> > > andrey.kouprianov@gmail.com> wrote:
> > >
> > >> Storing immediate children in a parent is a bad idea in a sense that
> you
> > >> will never be able to traverse your tree back to the root, given a
> child
> > >> node.
> > >>
> > >> Storing all in one doc - you will run out of space before you know it.
> > >> Documents have a finite length and the larger the document, the
> slower it
> > >> will get to serialize and unserialize it.
> > >>
> > >> Storing just an immediate parent in children might result in a costly
> > >> multiple read operations, if you want to get root of the tree given an
> > >> arbitrary child.
> > >>
> > >> Therefore the only feasible solution is to store references to the
> parent
> > >> chain - i.e. ancestors - starting from an immediate parent and ending
> with
> > >> a tree root.
> > >>
> > >>
> > >> Here's a simple calculation for ancestors approach:
> > >>
> > >> Suppose the maximum document size is 1MB. A uuid is 32 characters in
> > >> length + taking into account commas and brackets, then the depth of
> your
> > >> tree (I am not taking content into account) could be roughly:
> > >>
> > >> ((32 + 1)*n  + 2 - 1) = 1024 * 1024  ==> n = 31775 levels
> > >>
> > >> However, max document size is configurable from the settings (as of
> > >> CouchDB 1.2) and could easily be up to 4GB, giving you over 130mil of
> > >> levels. Should be enough... :)
> > >>
> > >>
> > >>
> > >> On Fri, Feb 22, 2013 at 1:14 PM, Michael Heuberger <
> > >> michael.heuberger@binarykitchen.com> wrote:
> > >>
> > >>> thanks andrey and svil
> > >>>
> > >>> depth is infinite. in theory a message can have million replies
> forth and
> > >>> back. similar like a very long email thread.
> > >>>
> > >>> i think storing ancestors ą la andrey would be too much hassle but
> works
> > >>> well for few levels.
> > >>>
> > >>> svil, what did you mean with dicts and with keeping all children in
> one
> > >>> doc? can you tell me more?
> > >>>
> > >>> thanks,
> > >>> michael
> > >>>
> > >>>
> > >>> On 22/02/13 17:27, svilen wrote:
> > >>>
> > >>>> my rough guess:
> > >>>>
> > >>>> if it's finite depth, then all in one doc:
> > >>>> - list of (item or (list of ...))
> > >>>> - or same with dicts
> > >>>>
> > >>>> else, one doc per message keeping just link-to-parent,
> > >>>> or multiple links-to-grand...grand-parents and/or root.
> > >>>> similar to the strategies in SQL - nested etc.
> > >>>> keeping all chidlren of same node in one doc is also possible..
> > >>>>
> > >>>> in any case either traversal or storing or both will be
> > >>>> difficult.
> > >>>>
> > >>>> ciao
> > >>>> svil
> > >>>>
> > >>>> On Fri, 22 Feb 2013 17:13:01 +1300
> > >>>> Michael Heuberger <michael.heuberger@**binarykitchen.com<
> michael.heuberger@binarykitchen.com>>
> > >>>> wrote:
> > >>>>
> > >>>>   Hello guys
> > >>>>> I'd like to store messages in a tree like structure. Whenever
you
> > >>>>> reply to a message, then the original message becomes the parent
> > >>>>> message.
> > >>>>>
> > >>>>> How would you implement something like this in CouchDB? Just
> curious
> > >>>>> and need a little guidance + advice here.
> > >>>>>
> > >>>>> Thanks,
> > >>>>> Michael
> > >>>>>
> > >>>>> --
> > >>>>>
> > >>>>> Binary Kitchen
> > >>>>> Michael Heuberger
> > >>>>> 4c Dunbar Road
> > >>>>> Mt Eden
> > >>>>> Auckland 1024
> > >>>>> (New Zealand)
> > >>>>>
> > >>>>> Mobile (text only) ...  +64 21 261 89 81
> > >>>>> Email ................  michael@binarykitchen.com
> > >>>>> Website ..............  http://www.binarykitchen.com
> > >>>>>
> > >>>>>
> > >>> --
> > >>>
> > >>> Binary Kitchen
> > >>> Michael Heuberger
> > >>> 4c Dunbar Road
> > >>> Mt Eden
> > >>> Auckland 1024
> > >>> (New Zealand)
> > >>>
> > >>> Mobile (text only) ...  +64 21 261 89 81
> > >>> Email ................  michael@binarykitchen.com
> > >>> Website ..............  http://www.binarykitchen.com
> > >>>
> > >>>
> >
>
>
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message