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.

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.