Re^2: Trees in SQL, adjacency lists and sorting.

Replies are listed 'Best First'.
Re^3: Trees in SQL, adjacency lists and sorting. by suaveant (Parson) on Jan 05, 2006 at 21:50 UTC
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)	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^3: Trees in SQL, adjacency lists and sorting.
by suaveant (Parson) on Jan 05, 2006 at 21:50 UTC

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]

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

you can get all immediate children with stuff like

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

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

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)

[reply]
[d/l]
[select]