Storing Composite Patterns (Hierarchical Data) in Database

Question

What are 'best-practices' for saving Composite patterns in a Relational Database?

We have been using Modified Preorder Tree Traversal. This is very quick to build the whole tree, but very slow to insert or delete new nodes (all left and right values need to be adjusted). Also querying the children of a node is not easy and very slow.

Another thing we noticed is that you really have to make sure the tree doesn't get messy. You need transaction locks, otherwise the left and right values can get corrupt, and fixing a corrupt left right tree is not an easy job.

It does work very good however, the Modified Preorder Tree Traversal, but I was wondering if there are better alternatives.

Answer 1

While finding all descendents of a row with MPTT is fast, finding all children can be slow. However you should be able to fix that by adding a parent_id field to your table that records (yes, redundantly) the parent of the row. Then the search becomes:

SELECT *
FROM tbl
WHERE parent_id = z

Yes, parent_id contains redundant information, potentially denormalizing your table -- but since any insert/update/delete already requires global changes, keeping parent_id up-to-date isn't much extra to pay. You could alternatively use a level field that records the vertical level of the row, although that is in fact more likely to change under certain types of transformations (e.g. moving a subtree to a different point in the tree).

The plain old link-to-parent representation (i.e. just having parent_id and no left_pos or right_pos), is of course faster for insert/update-heavy workloads, but the only queries it can answer efficiently are "Find the parent of X" and "Find the children of X." Most workloads involve much more reading than writing, so usually MPTT is faster overall -- but perhaps in your case you need to consider moving ("back") to link-to-parent?

Answer 2

The best way to store hierakial data in a database I have heard is to use a string attribute where the content is the list of parents separated by, say colons.

Answer 3

These are the two main models:

1. The Adjacency List Model
2. The Nested Set Model

Both can do the same thing, but there are a few little differences.

The Adjacency List Model makes it easy to alter trees, but it also makes it harder to retrieve them.

The Nested Set Model makes it very easy to retrieve an entire branch/tree. This model also inherently stores the order of nodes. The sql commands to alter the tree is a bit more difficult to grasp than from the other model.

As I explained you before: your application needs The Nested Set Model. Come by my desk if you feel it is too complicated. I'll explain it all over again.