Как выбрать всех родителей узла в иерархической таблице MySQL?

Question

У меня есть таблица MySQL, которая представляет данные для компонента графического интерфейса дерева, вот структура моей таблицы:

treeTable ( 
  id INT NOT NULL PRIMARY KEY, 
  parentId INT, 
  name VARCHAR(255) 
);

parentId является внешним ссылочным ключом.

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

Например, предположим, что моя таблица заполнилась этими данными:

1, null, 'root'
2, 1   , 'level_1'
3, 2   , 'level_2'

Теперь я хочу получить все родительские узлы узла 3 (узлы 1 и 2) и вернуть набор результатов, который содержит все записи дерева. Кто-нибудь может мне помочь, пожалуйста?

Answer 1

Хороший вопрос. В Oracle вы бы использовали что-то вроде CONNECT BY .

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

Answer 2

MySQL не поддерживает табличные функции 18.2.1. Сохраненный обычный синтаксис (это то, что вам нужно, чтобы иметь возможность возвращать произвольный набор результатов).

Без них у вас есть три варианта:

1. разверните древовидный запрос до фиксированной максимальной глубины и ограничьте разрешенную вложенность в вашей иерархии,
2. Использование цикла для записи данных во временную таблицу и введение некоторого соглашения для возврата результатов вызывающей стороне. Вам нужно будет подумать о повторном входе, или,
3. Предварительный расчет результатов путем включения всех предков каждого компонента в таблицу поддержки (как показано) и ведения ее с помощью триггеров на treeTable. Таким образом, хранимая процедура возвращает строки в parentTable, отфильтрованные соответствующим образом. Вам необходимо создать составной первичный ключ и, возможно, индексы для эффективного доступа.

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

parentTable (
    id INT NOT NULL,
    parentId INT NOT NULL
); 

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

Answer 3

Есть также материализованные пути , о которых стоит подумать.Довольно простая концепция, которая действительно независима от базы данных.Намного проще управлять вставками и т. Д., В отличие от вложенных наборов, вам не нужно знать, что у вас левый / правый узлы и т. Д., Прежде чем вставлять.

Answer 4

Смотрите здесь в разделе «Получение одного пути».Но лучше использовать подход вложенный набор , с деревом будет намного проще работать.Также я рекомендую прочитать презентацию « Деревья в базе данных - Расширенные структуры данных ».

Answer 5

Было схожее обсуждение с этим, которое могло бы помочь в решении этой проблемы.

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