Re: Adding history/versioning to a Nested Set model (is it possible?)

First, get a copy of my TREES & HIERARCHIES IN SQL so you will have some code to work with.

In this model, the structure is kept in a table like this: Tree (lft, rgt, node) where the node is a reference to the Nodes table and (lft, rgt) is an integer pair. It is very small, and if you leave an appropriate fill factor on the data pages, updates are very fast. Think about how much fits on a 5K data page, with three 4-byte integers. .

You could do snapshots of the whole tree with a timestamp. Or add a timestamp column and keep it all in one table. This will let you do a COMPLETE re-structuring every time -- probably not likely in the real world.

If the table is growing, then we can put wide gaps in the (lft, rgt) and keep adding nodes to the tree as long as we can preserve the "between-ness" property of new nodes. This means you have to give up the algebraic property (i.e sub-tree size rooted at this node = (rgt - lft +1) /2 for all nodes); but do you need it?

My experience with applications that use Nested Set model, you handle ~1,000 nodes per thread in a newsgroup forum where trees grow in a predictable fashion (i.e. add leaf nodes to an existing structure).

Talk to me off-line. Received on Sun Nov 01 2009 - 04:32:11 CET