January 28, 2003
Implementing a tree in SQL
Recently on the agile databases mailing list someone raised the spectre of implementing a hierarchy in a relational database. Someone then almost reflexively talked about Joe Celkos set based approach to implementing a hierarchy.
Now I like a parent-child table but I like to think I am open to new ideas. But this one does rather hurt my brain. I can see how easy it is to traverse an existing tree, but it looks very hard to populate the left and right values. As far as I can tell each time you add or remove a node from the tree you have to recalculate the left right values for each node in the tree. Which looks rather hard to me.
Still, I am going to do my best to get to the bottom of it and try and implement it in one of my databases.
Posted by Andy Todd at January 28, 2003 05:21 PM
http://www.sitepoint.com/article/1105 goes deeper into this. http://dbforums.com/t319623.html discusses details.
Celko also mentions some math tricks somewhere so you can sort of leave large gaps between the left/rigth values, like 100, so there is some space to insert nodes without having to renumber all higher values. He likes you to pay for the details.
I've looked for an OS class doing this but it does not seem to be available.