Binary trees in database with interval halving

gistfile1.txt

For binary trees I've found a variant of nested sets.

The idea is to let
- the root node be represented by the interval [0, 1], 
- the two children of the root node be represented by the intervals [0, 1/2] and [1/2, 1] respectively, 
- the grandchild nodes by [0, 1/4], [1/4, 1/2], [1/2, 3/4] and [3/4, 1].

Then it's easy to find:
- the left and right children (one or both),
- all descendents of a node,
- all ancestors of a node,
- all nodes where you only go left (or right) from a given node.

Very nice!

With the more commonly used design for Nested Sets, it's not necessary to use both left and right; you can just use BETWEEN like I showed.

Note that your design can't use indexes as effectively, both because of the division expressions, and because you use both left and right in inequality comparisons. It will get the right answer, but it won't perform well if the dataset gets large.

I found this variant when helping another developer who wanted to fetch the left-left-left-... and right-right-right-... paths from a node. He was satisfied with just a loop construct, but I wanted to look for a solution where I can find all nodes in a single select.

Now I realise that it can be done also with "normal" nested sets, but it's not as obvious. And "normal" nested sets has a weakness that you have to update a lot of nodes when inserting a new node. You don't have to do that with my solution.

The difficulties caused by the division expressions can be avoided by multiplying all fractions with a power of two. Instead of letting the root node be identified with [0, 1], it can be identified with for example [0, 256]. The next level will then be [0, 128] and [128, 256]. And so on. You will then get inequalities like child.left >= root.left and child.right <= root.right that can use an index.