Можно ли запросить таблицу древовидной структуры в MySQL одним запросом, на любую глубину? - PullRequest
Новая
       24

Можно ли запросить таблицу древовидной структуры в MySQL одним запросом, на любую глубину?

58 голосов
/ 04 октября 2008

Я думаю, что ответ - нет, но я бы хотел, чтобы кто-нибудь знал, как сканировать древовидную структуру на любую глубину в SQL (MySQL), но с помощью одного запроса

Точнее говоря, учитывая древовидную таблицу (id, data, data, parent_id) и одну строку в таблице, можно ли получить всех потомков (дочерний / внучатый / и т. Д.) Или по этому вопросу все предки (родитель / дедушка / бабушка и т. д.), не зная, как далеко или вверх он пойдет, используя один запрос?

Или использование какой-то рекурсии требует, где я продолжаю опрашивать глубже, пока не появятся новые результаты?

В частности, я использую Ruby и Rails, но я предполагаю, что это не очень актуально.

Ответы [ 9 ]

38 голосов
/ 04 октября 2008

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

Деревья и иерархии Джо Селко в SQL для умников

Рабочий пример (на PHP) приведен здесь

http://www.sitepoint.com/article/hierarchical-data-database/2/

23 голосов
/ 04 октября 2008

Вот несколько ресурсов:

По сути, вам нужно сделать какой-то курсор в хранимой процедуре или запросить или построить таблицу смежности. Я бы избегал рекурсии вне БД: в зависимости от того, насколько глубоко ваше дерево, оно может быть очень медленным / отрывочным.

3 голосов
/ 05 марта 2012

Ответ Даниэля Бердсли вовсе не так уж плох, когда основные вопросы, которые вы задаете: «Кто все мои дети» и «Каковы все мои родители».

В ответ Алексу Вайнштейну этот метод фактически приводит к меньшему количеству обновлений узлов в родительском движении, чем в методе Celko. В методике Celko, если узел уровня 2 в дальнем левом углу перемещается в узел ниже уровня 1 в крайнем правом углу, то почти все узлы в дереве нуждаются в обновлении, а не просто в дочерних узлах.

Однако я бы сказал, что Даниэль, возможно, хранит путь к корню в неправильном направлении.

Я бы сохранил их так, чтобы запрос был 

SELECT FROM table WHERE ancestors LIKE "1,2,6%"

Это означает, что mysql может использовать индекс для столбца «предки», что он не сможет сделать с ведущим%.

2 голосов
/ 08 декабря 2008

Техника Селко (вложенные множества) довольно хороша. Я также использовал таблицу смежности с полями «предок», «потомок» и «расстояние» (например, прямые дети / родители имеют расстояние 1, внуки / бабушки и дедушки имеют расстояние 2 и т. Д.).

Это необходимо сохранить, но это довольно просто сделать для вставок: вы используете транзакцию, затем помещаете прямую ссылку (parent, child, distance = 1) в таблицу, а затем INSERT игнорируете выбор существующих родительских и дочерних элементов: добавление расстояний (я могу подтянуть SQL, когда у меня есть возможность), которое хочет индекс для каждого из 3 полей для производительности. Там, где этот подход уродлив, касается удалений ... вы должны пометить все элементы, которые были затронуты, а затем перестроить их. Но преимуществом этого является то, что он может обрабатывать произвольные ациклические графы, тогда как модель вложенного множества может выполнять только прямые иерархии (например, каждый элемент, кроме корня, имеет одного и только одного родителя).

2 голосов
/ 04 октября 2008

Я сталкивался с этой проблемой раньше, и у меня была одна дурацкая идея. Вы можете хранить поле в каждой записи, которая является объединенной строкой идентификаторов ее прямых предков вплоть до корня.

Представьте, что у вас есть такие записи (отступы подразумевают иерархию, а числа - id, предки.

  • 1, "1"
    • 2, "2,1"
      • 5, "5,2,1"
      • 6, «6,2,1»
        • 7, "7,6,2,1"
        • 11, "11,6,2,1"
    • 3, "3,1"
      • 8, "8,3,1"
      • 9, "9,3,1"
      • 10, "10,3,1"

Затем выберите потомков id: 6 , просто сделайте это 

SELECT FROM table WHERE ancestors LIKE "%6,2,1"

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

1 голос
/ 13 января 2015

Я использовал процедуру «With Emulator», описанную в https://stackoverflow.com/questions/27013093/recursive-query-emulation-in-mysql (предоставлено https://stackoverflow.com/users/1726419/yossico).. До сих пор я получал очень хорошие результаты (с точки зрения производительности), но у меня нет Обилие данных или большое количество потомков для поиска через / для.

1 голос
/ 10 октября 2012

Это определенно можно сделать, и это не так уж сложно для SQL. Я ответил на этот вопрос и предоставил рабочий пример с использованием процедурного кода mysql здесь:

MySQL: как найти листья в определенном узле

Стенд: Если вы удовлетворены, отметьте один из ответов как принятый.

1 голос
/ 04 октября 2008

SQL не является языком Turing Complete, что означает, что вы не сможете выполнять такие циклы. Вы можете сделать некоторые очень умные вещи с SQL и древовидными структурами, но я не могу придумать способ описать строку, которая имеет определенный идентификатор «в своей иерархии» для иерархии произвольной глубины.

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

0 голосов
/ 04 октября 2008

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

В действительно грубом псевдокоде вы захотите что-то вроде этого: 

getChildren(parent){
    children = query(SELECT * FROM table WHERE parent_id = parent.id)
    return children
}

printTree(root){
    print root
    children = getChildren(root)
    for child in children {
        printTree(child)
    }
}

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

Однако, учитывая популярность такого рода структуры данных, вполне может быть, что MySQL поможет вам в этом, в частности, чтобы сократить количество запросов, которые вам нужно сделать.

Редактировать: Подумав об этом, бессмысленно делать все эти запросы. Если вы все равно читаете всю таблицу, тогда вы можете просто вылить все это в оперативную память - при условии, что она достаточно мала!

...