Nested Intervals provide a means of managing hierarchical data in a relational database by keying nodes in the tree using rational numbers.
The Nested Interval Behavior is an implementation of the encoding scheme presented in "Using Rational Numbers to Key Nested Sets"; Dan Hazel 19 June 2008. (http://arxiv.org/PS_cache/arxiv/pdf/0806/0806.3115v1.pdf)
The key of a node is calculated from the key of the parent node in such a way that places every descendant of a node before the next sibling of the node.
A key feature of the encoding is a significantly reduced requirement for re-indexing of nodes; addition or deletion of a last child node requires no re-indexing, and deletion of any other node only requires re-indexing of sibling sub-trees.
Nested Interval encoding also provides inherent support for multiple trees.
Requirements ¶
Built and tested with Yii 1.1.8; should work with Yii 1.1.x
Usage ¶
Attach the behavior to a model in the normal way. Your DB table will need four integer columns to support the behavior - the names default to "nv", "dv", "snv", and "sdv", but can be configured.
There are many methods to add data (these are used in place of CActiveRecord::save()), named scopes and getters to access data, methods to get information about a node, move nodes within the hierarchy, and delete nodes.
A few examples; please see the documentation for details of the API; you can also take a look at the Unit Tests (in the download) for examples.
$node->children()->findAll(); // return all the children of $node
$node->firstChild()->find(); // return the first child of $node
These could also be written as:
$node->children; // return all the children of $node
$node->firstChild; // return the first child of $node
Add a new node (there are many methods that allow the node to be added exactly where needed)
$node = new MyModel();
// set attributes here
$node->appendTo($target); // append $node to (add as last child of) $target
Find out some information about a node (there are many methods that give information about nodes)
$node->isChildOf($target); // find out if one node is the child of another
Move a node (there are many methods to move a node to exactly the right place)
$node->moveAfter($target); // move $node (and its descendants) to be the next sibling of $target
There are two extensions already
There are two extensions alredy implementing the same tree storage method:
http://www.yiiframework.com/extension/nestedset/ (old one with some bugs and now abandoned)
http://www.yiiframework.com/extension/nestedsetbehavior (new one that's maintained and is unit-tested)
Re: There are two extensions already
@samdark
Incorrect.
While the extensions mentioned also manage DB hierarchical data they do so using a different tree storage method; they implement nested sets using left and right keys for node indexing. Consequently any operation results in the whole tree to the right of the node being operated on being re-indexed with the associated database thrash; for example adding a node requires all nodes with a higher left and right keys being moved up to make room for the new node.
This extension encodes node keys using Nested Intervals - hence the name. Here nodes are indexed using a numerator and denominator created from the parent node key (each node stores both its and next sibling values to make computation easier). The keys of all descendants of a node lie between the parent node key and the parent's next sibling node key. As a result operations on a sub-tree only require re-indexing of that sub-tree at worst, and adding or deleting a last child node does not require any re-indexing at all. The result is far less database thrash and associated performance benefits.
To understand the difference between nested set and nested interval node key encoding please read Dan Hazel's paper referenced above.
@Yeti so what 's the benefit using this extension ! if i choose this what's the best use case(scenario )!
you say this is another way to realize the nestedset mode , now i using the nestedsetbehavior , if i want to implement the comment functionality which is better , please give some best use cases for using this extension!
is this better than nestedsetbehavior , more efficient ? or in some scenario this is better than the traditional left/right value way?
@yiqing95
As stated in the main text and reply to samdark, the benefit of nested interval node key encoding is significantly less re-indexing, reduced database thrash, and associated performance benefits.
Please see section 1 of the paper by Dan Hazel referenced which explains why this is the case.
@Yeti ok i see , thanks for replying . why not create a topic for talking about this extension
the functionality of this extension is a little much, you should give more example of usage examples , better to create a topic to discuss . and want to know is it possible to have the same api interface as nestedsetbehavior (make both to implement the same interface and thus we can switch to another transparently without changing our client class ) i know such thing is need a lot efforts , but still want to see such an extension come out ! after all they implements the same nestedset model!
and want to know that do this extension have the single root , multiply root concepts.(surely, after i read the doc i got it)
another question :
when the tree is too large , too deep or to wide , how to control the amount of the getDescendants() method returning . for example if i want to rend a comment tree but want to control the tree width and the tree depth , what ' s your advise ?
thanks for this great extension !
and bug report:
private function addNode($parent=null,$n=0,$validate=true,$attributes=null) { $owner = $this->getOwner(); if (!$owner->getIsNewRecord()) throw new NestedIntervalException(Yii::t(__CLASS__.__CLASS__,'Cannot add node; it is not a new node(node Primary Key: {nodePK})', array('{nodePK}'=>print_r($owner->getPrimaryKey())))); if ($target && get_class($target)!==get_class($owner)) throw new NestedIntervalException(Yii::t(__CLASS__.__CLASS__,'Cannot add node; owner and target are different classes (owner: {owner}, target: {target})', array('{owner}'=>get_class($owner), '{target}'=>get_class($target)))); .....in the addNode function there is an undefined variable -------》 $target
@yiqing95
Thanks for spotting the bug - my mistake - packaged the wrong file (dohhh)
Multiple Trees: as per the main text, Nested Intervals support multiple trees. If you just want one tree just add one root only.
Limiting width and depth: This not supported in this release.
I am trying to figure out if the encoding supports depth or if another column will be needed.
Width I hadn't considered, but the node encoding should make this very easy to implement.
Awesome work, Friend
This is awesome work. Thank you very much for sharing this.
I read the document you cited in your article. You managed to understand it? Impressive! I was lost when those equations went to Mars...
Very nice documentation. And the code is very clean and easy to understand.
I was about to use the Modified Preorder Tree Traversal to implement a registry for parameters and users preferences when I discovered your extension. It will do the trick very nicely.
Again, thank you for sharing.
Louis
Multiple Trees
Hi there,
Fantastic work. I am trying to store separate trees for each user. It's working now. However the nv,dv,snv,sdv for the first root are 1,1,2,1. But the other roots have different values for nv, snv. Is this ok? It seems to be working but I would not like these numbers to climb as more users are added with their new trees.
Is it possible to keep starting at 1,1,2,1? Is the current way (above) a problem?
Thanks,
Marco.
Re: Multiple Trees
Hi Marco,
This is how Nested Intervals work.
The dv and sdv for roots is always 1
nv and snv for the first root will be 1,2
for the second root they will be 2,3, for the third, 3,4, for the forth, 4,5 ----, for the nth root they will be n, n+1.
The key principal of Nested Intervals is that the (nv/dv) of all descendant nodes of a node lie between (nv/dv) and (snv/sdv) of the node.
If size of integers is a problem then NestedSets is another solution. The values stay smaller but tree operations can take longer as every node in the tree needs re-indexing; with NestedIntervals there is less re-indexing of the tree.
Which is best depends on what you are doing.
Hope this helps.
Integer Size
Do you think other encoding schemes might solve the integer size problem? Currently, using unsigned INTs for nv,dv,snv,sdv I can achieve a max tree depth of about 30.
I've been reading about matrix encoding. I know this plug-in does not support that, but I'm curious if you think this encoding will solve the integer problem.
I want the efficiency of nested intervals with none of the disadvantages. :D a dream
Tree depth
To suppliment my last comment, a tree that only contains a chain of approximately 50 nodes (i.e. depth 50) will produce integers larger than an unsigned BIG INT can hold.
@Yeti is this a bug?
NestedInterval::model()->root()->find('xxx');
i notice in your test file :
public function testFindNthRoot() { $n = rand(1,NI_TREES); $root = NestedInterval::model()->root($n)->find(); $this->assertTrue($root->getIsRoot()); $this->assertEquals($n,$root->getPosition()); } /** * Test finding the root node of a node */ public function testFindRoot() { $node = $this->loadNode(1,NI_LEVELS); $root = $node->root()->find(); $this->assertTrue($root->getIsRoot()); $this->assertTrue($root->isAncestorOf($node)); }but didn't test NestedInterval::model()->root()->find(); if used as this it will throw exception .
in your code :
public function root($n=0) { .. else { $k = $owner->{$this->nv}.' * '.$db->quoteColumnName("$alias.".$this->dv).' * '.$db->quoteColumnName("$alias.".$this->sdv).' / '.$owner->{$this->dv}.' - '.$db->quoteColumnName("$alias.".$this->nv).' * '.$db->quoteColumnName("$alias.".$this->sdv); $condition = "$k>0 AND $k<1"; } $condition .=' AND '.$db->quoteColumnName("$alias.".$this->dv).'=1'; $owner->getDbCriteria()->mergeWith(compact('condition')); return $owner; }i think should better use if($owner->getIsNewRecord()) to check before directly using the " $owner->{$this->nv} "
Found a couple of bugs
I've been working on incorporating the nested intervals extension into a project I've been working on. The behavior pretty much works as it should, however I believe that I've uncovered a couple of bugs.
The issues:
Function move() does not use NI key column name aliases
In the function move(), the return which generates four CDbExpression objects is not using the object properties $this->nv, $this->dv, $this->sdv, $this->sdv for the nv, dv, snv, and sdv column names in the SQL fragments it is generating. Instead it is hardcoding "nv", "dv", "snv", and "sdv" into the SQL, which will fail if the table schema is using different names for these respective columns.
Unable to delete root nodes
Calling deleteNode() on a node which is a root node fails with an exception: "Cannot get node's parent quadruple; node is a root note". This exception is thrown because deleteNode() makes a call to mockParent(), which makes a call to parentQuadruple(), which actually throws the exception. parentQuadruple() is acting logically, I would think, since it's logically impossible to have a parent for a root element. Therefore, I would suggest that the logic in mockParent() be changed to detect whether or not the node that it is acting on is a root node, and if it is a root node then the "parent" is the node itself.
If you have any questions, please ask in the forum instead.
Signup or Login in order to comment.