> 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...
smime.p7s
Description: S/MIME cryptographic signature
