Entity tree

This is an API module to help putting entities in a tree hierarchy. (Actually. DAG. I want to support multiple parents). We encode trees by enumerating each children of a parent, encode them with UTF-8 (I just use it as an algorithm) and then writing them down as an encoding of the materialized path. As UTF-8 as a binary stream sorts the same as the numbers encoded this works well. UTF-8 can encode at most 2**31 so that's the most children each parent can have.

MySQL indexing restricts us of somewhat to a max depth of 255 (or less) but that's not serious.

In PostgreSQL you want to use a c_locale character field ( I think ) and in MySQL, use VARBINARY.

See this presentation for a through explanation.

Currently, the only implemented operation is the "find the new number for a newly inserted element" because the rest of the operations are trivial and work well on the UTF-8 encoded materialized path and so just requires UTF-8 string manipulation:

1. get a list of parents. If the encoding is ABCDE, then the parents are A, AB, ABC, ABCD.
2. Find a subtree. The children of ABC can be found by LIKE 'ABC%'
3. Move subtrees. To move the children of ABC under PQ just preg_replace('^ABC', 'PQ', $encoding);
4. Show a tree in tree order, just ORDER BY encoding. That's the point of the encoding after all.

Downloads