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 из них.

Реклама