> 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...