incubator-couchdb-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jim Klo <jim....@sri.com>
Subject Re: Tree like structures in CouchDB
Date Sat, 23 Feb 2013 07:56:23 GMT


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


Mime
View raw message