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

Question

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

Более конкретно, учитывая древовидную таблицу (id, data, data, parent_id) и одну строку в таблице, можно ли получить всех потомков (child / grandchild / etc) или, в этом отношении, всех предков (parent / grandparent) / etc) не зная, как далеко или вверх он пойдет, используя один запрос?

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

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

Answer 1

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

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

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

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

Answer 2

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

• http://forums.mysql.com/read.php?10,32818,32818
• Управление иерархическими данными в MySQL
• http://lists.mysql.com/mysql/201896

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

Answer 3

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

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

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

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

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

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

Answer 4

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

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

Answer 5

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

Представьте, что у вас есть такие записи (отступы подразумевают иерархию, а числа - 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"

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

Answer 6

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

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

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

Answer 7

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

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

Answer 8

Я использовал процедуру "С эмулятором", описанную в https://stackru.com/questions/27013093/recursive-query-emulation-in-mysql (предоставленной yossico). До сих пор я получил очень хорошие результаты (с точки зрения производительности), но у меня нет большого количества данных или большого количества потомков для поиска / поиска.

Answer 9

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

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

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 поможет вам в этом, особенно для сокращения количества запросов, которые вам нужно выполнить.

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