Как найти все узлы в поддереве в рекурсивном SQL-запросе?
У меня есть таблица, которая определяет отношения между дочерними и родительскими узлами:
CREATE TABLE node ( ' pseudo code alert
id INTEGER PRIMARY KEY,
parentID INTEGER, ' should be a valid id.
)
Если parentID всегда указывает на действительный существующий узел, тогда это, естественно, определит древовидную структуру.
Если parentID - это NULL, то мы можем предположить, что этот узел является корневым.
Как бы я:
- Найти все узлы, которые являются потомками данного узла?
- Найти все узлы под данным узлом на определенной глубине?
Я хотел бы сделать каждый из них как один SQL (я ожидаю, что он обязательно будет рекурсивным) или как два взаимно рекурсивных запроса.
Я делаю это в контексте ODBC, поэтому я не могу полагаться на какие-либо особенности производителя.
Редактировать
- Таблицы еще не написаны, поэтому добавление дополнительных столбцов / таблиц вполне приемлемо.
- Дерево потенциально будет обновляться и добавляться довольно часто; Вспомогательные структуры данных / таблицы / столбцы возможны, но их необходимо поддерживать в актуальном состоянии. Если у вас есть какие-нибудь волшебные книги, к которым вы можете обратиться с подобными вопросами, я хотел бы знать.
Большое спасибо.
Ответы 3
If you have any magic books you reach for for this kind of query, I'd like to know.
Celko's Деревья и иерархии в SQL для умников
Эта ссылка предоставляет учебное пособие как по модели списка смежности (как описано в вопросе), так и по модели вложенного набора. Он написан как часть документации для MySQL.
Что не обсуждается в этой статье, так это время вставки / удаления и стоимость обслуживания двух подходов. Например:
- динамически растущее дерево с использованием модели вложенного набора, по-видимому, требует некоторого обслуживания для поддержания вложенности (например, перенумерация всех левых и правых номеров наборов)
- удаление узла в модели списка смежности потребует обновлений по крайней мере в одной другой строке.
Похоже, что Oracle плохо обращалась со ссылками на веб-сайты MySQL, возможно ли как-нибудь найти руководство сейчас?
Сохраните весь «путь» от идентификатора корневого узла в отдельном столбце, обязательно используя разделители в начале и в конце. Например. скажем, 1 является родительским элементом для 5, который является родительским для 17, а ваш символ-разделитель - тире, вы должны сохранить значение -1-5-17- в столбце пути.
Теперь, чтобы найти всех потомков 5, вы можете просто выбрать записи, в которых путь включает -5-
Разделители на концах необходимы, поэтому вам не нужно беспокоиться об идентификаторах, которые находятся в крайнем левом или правом конце поля, когда вы используете LIKE.
Что касается вашей проблемы с глубиной, если вы добавите в свою таблицу столбец глубины, указывающий текущую глубину вложенности, это также станет легко. Вы просматриваете глубину своего начального узла, а затем добавляете к нему x, где x - это количество уровней глубины, на которых вы хотите искать, и вы отфильтровываете записи с большей глубиной, чем это.
Как бы это было обновлено? В вашем примере, если вы заменили 5 на 50, вам нужно было бы изменить строку пути для каждого потомка 5. Правильно ли я понял?
Да, но поскольку вы можете легко найти всех иждивенцев из 5, и вы можете выполнить простую замену строки -5- на -50-, это все еще работает. Это не кажется «изящным», но это относится к большинству оптимизаций.
Некоторые методы были рассмотрены ранее в этой статье: SQL - как хранить иерархии и перемещаться по ним