in reply to RFC: Tree-like applications
There are two or three more approaches to modelling trees in SQL, described by Joe Celko. There is Trees and Hierarchies in SQL. I didn't find the book worth its price due to the material being online in articles by Celko and also partially in his book SQL for Smarties (of which I only have the first or second edition).
The data structures and algorithms for the other tree implementations follow different ideas than your "child / parent" approach. The child/parent approach is good for quick inserts into the tree and good for quick updates (moving a subtree).
Another approach is to materialize the path to each node, for example in a varchar column. Then you get a column like:
1 1.1 1.2 1.2.1 ...
In such a structure, you can easily retrieve full subtrees with like comparisons or <= and > comparisons. Inserting is a bit slower and moving subtrees is mediocre.
Yet another approach is to store per node the covered range of children, min(child_value) and max(child_value) as left / right boundary. This also allows for easy inserts and easy queries for subtrees. Moving subtrees is mediocre again.
|
|---|
| Replies are listed 'Best First'. | |
|---|---|
|
Re^2: RFC: Tree-like applications
by rustic (Monk) on Jun 06, 2012 at 12:24 UTC |