Well.. obviously you have a large unique field for the string....

I did the following... I had a unique varchar(255) that held the tree string and used 2 digit base 36 ids... obviously you could extend the character set, but I figured 1296 children per leaf was enough. If you only need binary then one char is fine, 0-1 or something... you could probably encode something, but that may make queries difficult... obviously with 2 char codes you can only get 127 levels in a tree with a 255 char field.

I used a couple of self written functions to turn the codes to and from numbers:

sub de36 {
  my($a,$b) = (uc substr($_[0],-2,1),uc substr($_[0],-1,1));
  $CHARS{$a}*36+$CHARS{$b};
}

sub en36 {
  $CHARS[$_[0]/36].$CHARS[$_[0]%36];
}
[download]

To insert I would would first grab the max id within the group I wanted, something like

SELECT MAX(thread) FROM messages WHERE thread LIKE "${parent}__"
[download]

matching those threads that were in the same parent....

you can get all immediate children with stuff like

SELECT * FROM messages WHERE thread LIKE "${parent}__"
[download]

and you can get a history with something like

SELECT * FROM messages WHERE thread = LEFT("$thread",LENGTH($thread))
[download]

sorting is, in this case, super easy.

I am using MySQL syntax but it should be clear enough...

You'll have to work out how to make it binary yourself, if you need it... not terribly difficult, select and compare, then add accordingly... table locking could probably help, too. :)

                - Ant
                - Some of my best work - (1 2 3)

So, '10th grade optics' would be 'A1.1.1B1.1'. We use a delimitor between items, so we aren't restricted to subsets that each have a unique character in them, allowing for wider branching. (depth is still a problem when dealing with fixed line lengths)

The problem is, it's fine for humans to understand, but a little messy to sort on in SQL. You can get around this by adding another delimiter between facets, and ending every notation w/ a null heirarchy: ';A1.1.1.;B1.1.'. We can then get all items relating to 10th grade physics w/ LIKE '%;A1.1.%;B1.1.%', without fear of getting 'A1.10AB1.1', and still getting items that may have even more facets, eg a movie for 10th grade physics ';A1.1;B1.1;C1'

The only requirement is that you keep each of the facets in order. (what order doesn't matter, so long as you're consistent)

If you'd like a more complex example: