incubator-couchdb-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Michael Heuberger <michael.heuber...@binarykitchen.com>
Subject Re: Tree like structures in CouchDB
Date Sun, 24 Feb 2013 00:43:55 GMT
Very good argumentation Jim. As an Ex CS major coming from the SQL world 
I can't agree more with you.

This classic tree traversal is not optimal for CouchDB.

On 23/02/13 20:56, Jim Klo wrote:
>
>
>> This might be useful. The implementation in the article is SQL, but I 
>> think
>> the algorithm is probably relevant.
>>
>> http://www.sitepoint.com/hierarchical-data-database-2/
>
> This is the classic tree traversal taught to most 1st year CS majors..
>
> The largest problem with this specific algorithm and CouchDB, is that 
> it requires indexing of the nodes serially in traversal order. Adding 
> a node is pretty intense. In SQL notice what has to be done:
>
> |	UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
>
> 	UPDATE tree SET lft=lft+2 WHERE lft>5;|
> |	INSERT INTO tree SET lft=6, rgt=7, title='Strawberry';|
> For you noSQL types.... that's updating every node to the 'right' of 
> the inserted node, imagining that the tree is indexed depth first, 
> left to right.  So in the best case you update at least the depth of 
> the right most node. The worst case is inserting left most child to 
> root, causing all nodes to be updated.
>
> For CouchDB, that means updating lots of docs... and then reindexing 
> all views for the updated docs... for big trees this is potentially a 
> costly algorithm.
>
> Solutions that are insert only work best... there was a technique 
> discussed last year that was similar to this, but used floating point 
> numbers to in lieu if integers for insertion between nodes... that 
> might be an acceptable alternative than having to renumber... but at 
> some point you start running into the float precision problems just 
> recently discussed on this list...
>

-- 

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