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
|