|
Text Based Nested Set Implementation |
Trever Shick was kind enough to send in an alternate implementation of an SQL Nested Set.
I read your nested set implementation tutorial and it was an interesting approach.
I have an alternate method that adds a single column (text) to do the same thing. The benefit is
updates and deletions do not require all of the nodes to be udpated.
root
|- Child 1
| |- child 1.1
| |- child 1.2
|- Child 2
| |- child 2.1
| |- child 2.2
ID | Parent | Path | Data
---------------------------------------
1 | 0 | /0/ | Root
2 | 1 | /0/1/ | Child 1
3 | 2 | /0/1/2/ | Child 1.1
4 | 2 | /0/1/2/ | Child 1.2
5 | 1 | /0/1/ | Child 2
6 | 5 | /0/1/5/ | Child 2.1
7 | 5 | /0/1/5/ | Child 2.2
Obviously this is a text column and some don't like text columns, but unless you have very deeply
nested sets, the size of the text column won't be too large. I've not found this to be a performance
problem. The added benefit of reading the path like value is nice too; not necessary, but nice.
Selecting the subtree from one node becomes:
SELECT * FROM tree_table WHERE PATH = '/0/1/2/';
Selecting a subtree of child 1 and 2 now becomes:
'SELECT * FROM tree_table WHERE PATH LIKE '/0/1/_%';
Moving a node requires you update the nodes path and then the children's node path
if child one moves under child 2, then:
-- move the child, then update the paths
update tree_table set parent = 5 WHERE id = 2;
uppate tree_table p INNER JOIN tree_table c ON c.parent = p.id SET c.path = concat(p.path,
p.id,'/');
--verify the move
select * from tree_table where path = '/0/1/5/;
(returns Child 1, Child 2.1 and Child 2.2)
select * from mytree where path LIKE '/0/1/5/%';
(returns Child 1, Child 2.1 ,Child 2.2, Child 1.1 and Child 1.2)
No bounds to check or recalculate and the only recalculation (of paths) can be done with a single
SQL for the entire tree.
Anyhow, i use this in a project where geographic regions are specified and it works well. In that
implementation i use an abbreviation instead of the ids for the path. Which allows them to do
searches like select geographic where geo_code like '%/sw/%' (sw=Southwest) and pull all regions in
the southwest region....
Anyhoo, just thought you'd like to see an alternate implementation.
Trever