Деревья теперь и в MySQL

написал драйвер для mysql и на той же страничке выложил их сравнительное тестирование.

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

в мускуле наблюдаюся странные тормоза при выборке всех предков. видимо он забывает, что у него есть индексы, которые было бы неплохо заюзать %-\

пока адаптировал DirecTree под мускул весь на мат изошёл...
1. мускул требует либо указывать для полей имена таблиц, либо брать имена таблиц в бэктики, которые не совместимы с другими БД.
2. мускул не позволяет сделать модификацию таблицы, если в запросе используется подзапрос вытягивающий данные из этой же таблицы. идиотизм какой-то...

вроде поборол, но, смотря на код, самому тошно... надо будет переписать...

функцию install под мускул пока не тестировал - остальные вроде работают нормально.

ссылка та же: http://dark-demon.jino-net.ru/directree/ тока не злоупотребляйте рефрешем ^_8

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

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

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

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

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

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