Организация деревьев в реляционных базах данных

сага об изобретении велосипеда: http://php.ru/forum/viewtopic.php?t=5303
и вот к чему это в итоге привело: http://dark-demon.jino-net.ru/directree/

не буду особо распространяться относительно подробностей реализации разных алгоритмов огранизации деревьев (при необходимости вы легко найдёте их в гугле), только приведу их краткий список:
1. таблица смежности - каждый узел хранит ссылку на родителя. фиг выберешь поддерево одним запросом. как следствие - тормоза при больших вложениях, особенно, если sql-сервер стоит на отдельной машине.
2. материализованный путь - каждый узел хранит ссылки на предков в строковой переменной. поиск по подстроке - забудьте о скорости и глубоких деревьях.
3. вложенные множества - все узлы выстроены в линию и каждый узел хранит свой номер и номер последнего потомка. очень большой плюс - естественное упорядочивание дерева. очень серьёзный минус - необходимость перелопачивать половину базы данных при изменениях.
4. таблица смежностей + кэш связей. в кэше хранятся все линки предок-потомок. большая избыточность при глубоких деревьях.

мною реализован последний вариант в виде библиотеки, которую легко подключить к уже существующей таблице смежностей. база данных пока поддержиается только sqlite, но драйвера для других баз пишутся элементарно (для прикидки - драйвер sqlite занимает около полусотни строчек кода).

особенность реализации: добавление листа не увеличивает размер кэш таблицы, но вот трансформация листа во внутренний узел (добавление хотябы одного ребёнка) увеличивает размер кэш-таблицы пропорционально глубине этого узла. все выборки идут одним запросом, модификации затрагивают сравнительно небольшое число строк. для удобного составления запросов - есть набор хелперов, позволяющих не вникать в тонкости работы кэша.

сия штука замечательно подходит в случае сравнительно неглубоких деревьев с большим числом листьев. например, для обычного линейного форума с произвольной иерархией разделов.