2/10/2009 4:52 PM

Render On Demand Scheme

So the basic idea with this system is to have two separate sets of records in the Database. The first, and canonical, set is used for editing. This set is stored in an augmented adjacency list structure. This structure makes this set of records easier to make edits to. However it is not efficient to retrieve entire trees from this structure. This is where the second set of records comes into play. This set of records is stored in the nested set modal which is very efficient for tree retrieval. When a tree is requested the request goes to this second set of records. If the requested tree is not found there, it is retrieved from the first set of records and then cached in this second set of records for future retrievals.

Proposed Scheme

The basis for this scheme is a two tiered tree representation. For editing we are using the adjacency list structure represented in tblEdges. This allows for fast and simple node manipulation. It also removes the previous problem we had with cloning nodes. We still wish to use the fast rendering speed of the nested set model so we render the adjacency list model to nested set. Since only the tree we are currently rendering needs to be re-rendered to nested set this significantly reduces the amount of work need to be done. In order to keep track of which trees have been rendered each tree is assigned two dirty bits. These bits represent if the parents have changed and if the children have changed since the node was last rendered. These bits are propagated down and up the trees that have been edited. When the tree is later rendered it is marked as clean and can then be retrieved from the nested set model.


This table contains the basic information for the nodes such as nodeID, Title and the dirty bit. The NodeID is an automatically generated number used as a universal identifier for each node. This table also contains both the dirtyParent bit and the dirtyChild bit that are explained in the next section.

Dirty Bits

When inserting an edge the node on the top end needs to have dirtyChild set to 1 and the node on the bottom needs to have dirtyParent set to 1. These updates will cause the following triggers to run on tblNodes.

update tblNodes set dirtyChild = 1   from inserted   left outer join tblEdges on inserted.dirtyChild = 1 and inserted.nodeID = tblEdges.childID   where tblNodes.nodeID = tblEdges.parentID and tblNodes.dirtyChild = 0 
update tblNodes set dirtyParent = 1   from inserted   left outer join tblEdges on inserted.dirtyParent = 1 and inserted.nodeID = tblEdges.parentID   where tblNodes.nodeID = tblEdges.childID and tblNodes.dirtyParent = 0 


this table contains the adjacency list representation of the trees. Each row in the table represents an edge in the graph representing all trees. The parentID is the node of lesser depth and the childID is the node directly below it. RightSiblingID is used to maintain an ordering of the children of a node. The RightSiblingID is the nodeID of the next node in the ordering of the children. The rights sibling mush share the same parent as the current node.

In the above picture, node 2's parent is node 1 and right sibling is node 3. Node 3's parent is node 1 and right sibling is <NULL>.


This table holds the rendered version of the Trees in nested set from ( This rendering is done using the procedure USP_updateTrees.

Home: WikiStart
What's new: Recently changed articles
You can subscribe to this wiki article using an RSS feed reader.