couchdb-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Elisiano Petrini <elisi...@gmail.com>
Subject Re: Tree like structures in CouchDB
Date Fri, 22 Feb 2013 07:10:38 GMT
Hi Kim,
    I don't think using this kind of documents' ids is a viable
solution: what if there is more that one message in response to another
(ie:several people answering to the same message)?

On Fri, 2013-02-22 at 07:00 +0000, Jim Klo wrote:
> In theory you mention infinite depth, but is that realistic?
> 
> A simple way is to make ID's a composite serial and chain them together. 
> 
> 1 : orig message
> 1-2 : reply to 1
> 1-2-5 : reply to 2
> 1-3 : reply to 1
> 1-3-4 : reply to 
>  
> The keys will then sort in order, such that can build the tree DFS and use range queries
to get just segments. 
> 
> You can obviously do some creative things in compression - using different number bases
to handle deep trees. 
> 
> 
> 
> On Feb 21, 2013, at 10:10 PM, "Michael Heuberger" <michael.heuberger@binarykitchen.com>
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
> > 
> > -- 
> > 
> > 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
View raw message