incubator-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:35:42 GMT
Ah OK, I get the point now, you put something unique to the node in the
ID (in this case a sequential number).

But still, see the concern in my previous mail.
This approach works if the client has the logic to re-try (with an
incremented sequence number) in case of collisions.

Cheers, Elisano

On Fri, 2013-02-22 at 07:26 +0000, Jim Klo wrote:
> 
> Sent from my iPhone
> 
> On Feb 21, 2013, at 11:11 PM, "Elisiano Petrini" <elisiano@gmail.com> wrote:
> 
> > 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)?
> > 
> 
> Nope. Works fine. It only has issues with deep trees as the id gets quite large. I'm
not sure how big an ID can actually be, but consider if you could use utf-8 chars to pack
the ID, it's pretty big, and it should still sort. 
> 
> I started with this:
> 
> >> 1 : orig message
> >> 1-2 : reply to 1
> >> 1-2-5 : reply to 2
> >> 1-3 : reply to 1
> >> 1-3-4 : reply to 
> 
> 
> But if later more replies come in:
> 
> 1-2-6 : another reply to 2
> 1-3-7 : another reply to 4
> 
> CouchDB will sort those:
> 
> >> 1 : orig message
> >> 1-2 : reply to 1
> >> 1-2-5 : reply to 2
> 1-2-6 : another reply to 2
> >> 1-3 : reply to 1
> >> 1-3-4 : reply to 3
> 1-3-7 : another reply to 4
> 
> And that would be without any view!
> 
> - Jim
> 
> > 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