from codeproject Auther: Daniel Parnell
I don’t know how many times I’ve had to deal with tree structures implemented like this. I know I made this same mistake when I was starting out with databases. On the surface it looks like the way to do it, but there are several much better ways to do it. The problem with this approach is that traversing the tree is a very expensive operation. If the tree is only 2 or 3 levels deep this may not be a problem, but as soon as the tree starts to get deep it does not scale well (I remember getting yelled at by a DBA for doing this ).
One of the easiest ways to implement a tree structure that is easy to traverse is to use a structure as follows:
create table my_tree (
id int IDENTITY(1,1) NOT NULL,
path VARCHAR(200) not null,
title nvarchar(200) not null
)
We make a trade off between disk space and access speed. This would allow us to easily store a tree with 50 levels or more (make the path column longer to allow deeper trees).
| id | path | title |
| 1 | / | this is the root |
| 2 | /1 | this is the first item under the root |
| 3 | /1 | another item under the root |
| 4 | /1/2 | an item under the first item under the root |
| 5 | /1/2/4 | a deeper item |
To get the whole tree you can then do the following:
select * from my_tree order by path+'/'+cast(id as varchar)
The expression in the order by could be eliminated if the path were updated to contain the full path to the node rather than the path to the parent. To do this nicely we would need to pre-allocate the node ID or use some other method for identifying the nodes that does not relate to the ID column.
To get a sub-tree:
select * from my_tree where path like '/1/2/%' order by path+'/'+cast(id as varchar)
Similarly deleting a sub-tree becomes:
delete from my_tree where path like '/1/2/%'
Moving items around in the tree becomes a little more complicated.
update my_tree set path='/1/3/'+substring(path, 6, 1000) where path like '/1/2/%'
There are a couple of even more efficient ways of implementing trees, but they are a lot more complicated to implement. See here an example
In SQlite3, there should be some modification like this:
update my_tree set path='/1/3/'|| substr(path, 6) where path like '/1/2/%'