Keith Devens .com

Trees in SQL

It turns out there's another way to store hierarchical data in SQL that I didn't know existed. Basically, rather than storing the "parent" for each record (with the root having a NULL parent), it turns out you can store a tree by storing "left" and "right" values for each element of the tree, where left and right are numbers that would be assigned by a preorder traversal of the tree.

Via Simon, check out this article from SitePoint.com by Gijs Van Tulder: Storing Hierarchical Data in a Database, and via a comment on Simon's blog, check out database guru Joe Celko's explanation of the same thing.

The first article has more of a tutorial flavor, and has nice diagrams, but Celko's article goes a little more in depth. Also, Gijs only used a binary tree in his example, so I wasn't sure if it'd work for more-than-binary trees, but Celko's example shows that it can.

The only downside to this technique is that it's more of a pain to insert new rows or delete existing ones, but the benefits seem to outweigh the downsides, especially for large or heavily nested recordsets. This is really a great technique, and I'm glad that it's now in my repetoire. I didn't realize this was possible. Thanks for finding this, Simon

Permalink | 3 Comments | Tags: Programming | id 3988

02:21 (utc-4)
edited: 06:16 (utc-4)