Tree/Other
Материал из PhpWiki.
Деревья в базах данных => Другие способы
Другие способы представления деревьев в базах данных
Содержание
- Номер строки и уровень вложенности
- Смотрите так же
Деревья в базах данных => Другие способы => Строка и уровень
Номер строки и уровень вложенности
Maxik
Суть в следующем: Каждая вершина дерева как бы находится в двухмерной системе координат. Координата X - это глубна в дереве. Координата Y - это строка в дереве. Мне кажется это удобнее и нагляднее чем вложенные множества.
Представьте обычную школьную систему координат. Теперь мы хотим описать дерево. При том обычное двухмерное, типа форума. Каждое сообщение этого форума имеет две определяющие величины. Удаленность от начала форума сверху, и удаленность от края. Пример:
сообщение 1.1 сообщение 2.1 --сообщение 3.2 --сообщение 4.2 сообщение 5.1 --сообщение 6.2 --сообщение 7.2 --сообщение 8.2 ----сообщение 9.3 ----сообщение 10.3 ----сообщение 11.3 --сообщение 12.2 --сообщение 13.2 сообщение 14.2
~SelenIT
Основной плюс использования двух координат вижу в удобстве и быстроте построения дерева при выводе.
su1d
как в такой системе выбрать всех потомков узла Х?
~SelenIT
Уровень вложенности больше, чем у данного элемента, номер в интервале между номером данного элемента и номером ближайшего элемента с не большим, чем у данного элементата, уровнем вложенности.
su1d
Слишком много JOIN'ов потребуется (2-3 как минимум). БД просто грохнется на больших объёмах. Сравни с выборкой BETWEEN x AND y для Вложенных Множеств или Вложенных Интервалов.
popoff 1. Узнать координаты узла Х (Nx - номер строки, Lx - уровень) - поиск по первичному ключу.
2. Узнать номер "ближайшего элемента с не большим, чем у данного элементата, уровнем вложенности". Ближайшего снизу. Это, я так понимаю, поиск с примерно таким по смыслу условием:
SELECT min(N) AS Ny FROM t_tree WHERE N>Nx AND L<=Lx
Фактически это тот же самый BETWEEN x AND y, только здесь под условие попадает не только все потомки, но и значительная часть дерева, которая находится внизу (если говорить о номерах строк) слева (если говорить об уровнях, расположенных слева направо). На практике СУБД ~MySQL этот запрос очень часто будет выполнять линейным поиском по всей таблице, без использования индексов, потому что эта часть дерева - слишком большая часть дерева и поэтому линейный поиск по всей таблице - это быстрее, чем поиск с использованием индексов.
3. Собственно выбираем список всех потомков. Снова "N BETWEEN Nx AND Ny".
Результаты сравнения - налицо. Во вложенных множествах - один "BETWEEN", а здесь - два.
Смотрите так же (о том, когда используются индексы): How MySQL Optimizes WHERE Clauses http://dev.mysql.com/doc/mysql/en/where-optimizations.html How MySQL Optimizes WHERE Clauses
su1d
Как в такой системе выбрать всех предков узла Х?
~SelenIT
Группировка по разности уровней вложенности текущего элемента и заданного, разность положительна, выбрать элементы с наибольшим номером, меньшим номера данного, сортировка по разности.
popoff
Если немножко оптимизировать и перевести с русского на SQL, получится примерно следующее:
SELECT max(N) AS N, L-Lx AS d_level FROM t_tree WHERE L<Lx AND N<Nx GROUP BY d_level ORDER BY L
И что мы видим? Тот же самый "BETWEEN", что и во вложенных интервалах. Только здесь еще добавилась группировка и использование функции min().
Этот запрос "проще, удобнее и быстрее"?
su1d
Как в такой системе выбрать всех непосредственных детей узла Х?
~SelenIT
Все то же самое, что и для поиска всех потомков, но уровень вложенности строго на единицу больше уровня вложенности заданного элементата.
Но можно делать это средствами php при самом выводе, благо массив получается уже упорядоченным. Такой метод может быть хорош как дополнение к известным методам именно для быстрого вывода.
su1d
Не самое лучшее решение: таскать от БД-сервера к БД-клиенту миллионы записей для того, чтобы вывести 20 из них.