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