Быстрый реляционный метод хранения древовидных данных (например, потоковые комментарии к статьям)

Ответ 1

Мне очень нравится, как Drupal решает эту проблему. Каждому комментарию присваивается идентификатор потока. Этот идентификатор начинается с 1 для первого комментария. Если к этому комментарию добавлен ответ, ему присваивается идентификатор 1.1. Ответному комментарию 1.1 присваивается идентификатор потока 1.1.1. Ответственному комментарию 1.1 присваивается идентификатор потока 1.2. Вы поняли эту идею. Вычисление этих идентификаторов потоков может быть легко выполнено с помощью одного запроса при добавлении комментария.

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

1
1.1
1.1.1
1.2
1.2.1

Есть несколько проблем, которые нужно решить:

• Если один компонент идентификатора потока увеличивается до двух цифр, сортировка по идентификатору потока не приведет к ожидаемому порядку. Легким решением является то, что все компоненты идентификатора потока заполняются нулями одинаковой шириной.
• Сортировка по нисходящему идентификатору потока не приводит к ожидаемому убыванию.

Drupal решает первую проблему сложнее, используя систему нумерации, называемую vancode. Что касается второй проблемы, она решается путем добавления обратной косой черты (код ASCII выше цифр) для идентификаторов потоков при сортировке по убыванию. Вы можете найти более подробную информацию об этой реализации, проверив исходный код модуля комментариев (см. Большой комментарий перед функцией comment_get_thread).

Ответ 2

Я знаю, что ответ немного запоздалый, но для данных дерева используется таблица закрытия http://www.slideshare.net/billkarwin/models-for-hierarchical-data

Он описывает 4 метода:

• Список событий (простой родительский внешний ключ)
• Перечисление пути (стратегия Drupal, упомянутая в принятом ответе)
• Вложенные наборы
• Таблица закрытия (хранение данных предка/потомка в отдельном отношении [таблица] с возможным столбцом расстояния)

Последняя опция имеет преимущества простых операций CRUD по сравнению с остальными. Стоимость - это пространство, которое является размером O (n ^ 2) в узлах числового дерева в худшем случае, но, вероятно, на практике это не так уж плохо.

Ответ 3

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

Управление иерархическими данными в MySQL был для меня чистым золотом. Вложенные множества - это вторая модель, описанная в этой статье.

Ответ 4

У вас есть выбор между смежными и вложенными наборами моделей. Статья Управление иерархическими данными в MySQL дает хорошее представление.

Для теоретического обсуждения см. Celko Деревья и иерархии.

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

create Tablename (
  RecordID integer not null default 0 auto_increment,
  ParentID integer default null references RecordID,
  ...
)

Затем вы можете использовать рекурсивное выражение Common Table Expression для отображения потока. Пример доступен здесь.

Ответ 5

К сожалению, чистые методы SQL для этого довольно медленные.

NESTED SETS, предложенный @Marc W, довольно элегантен, но может потребоваться обновить все дерево, если ваши ветки дерева попадут в диапазоны, что может быть довольно медленным.

См. эту статью в своем блоге о том, как это сделать быстро в MySQL:

• Иерархические запросы в MySQL - эмуляция Oracle CONNECT BY

Вам нужно создать функцию:

CREATE FUNCTION hierarchy_connect_by_parent_eq_prior_id(value INT) RETURNS INT
NOT DETERMINISTIC
READS SQL DATA
BEGIN
        DECLARE _id INT;
        DECLARE _parent INT;
        DECLARE _next INT;
        DECLARE CONTINUE HANDLER FOR NOT FOUND SET @id = NULL;

        SET _parent = @id;
        SET _id = -1;

        IF @id IS NULL THEN
                RETURN NULL;
        END IF;

        LOOP
                SELECT  MIN(id)
                INTO    @id
                FROM    t_hierarchy
                WHERE   parent = _parent
                        AND id > _id;
                IF @id IS NOT NULL OR _parent = @start_with THEN
                        SET @level = @level + 1;
                        RETURN @id;
                END IF;
                SET @level := @level - 1;
                SELECT  id, parent
                INTO    _id, _parent
                FROM    t_hierarchy
                WHERE   id = _parent;
        END LOOP;
END

и используйте его в следующем запросе:

SELECT  hi.*
FROM    (
        SELECT  hierarchy_connect_by_parent_eq_prior_id(id) AS id, @level AS level
        FROM    (
                SELECT  @start_with := 0,
                        @id := @start_with,
                        @level := 0
                ) vars, t_hierarchy
        WHERE   @id IS NOT NULL
        ) ho
JOIN    t_hierarchy hi
ON      hi.id = ho.id

Это, конечно, MySQL конкретный, но он очень быстрый.

Если вы хотите, чтобы это было переносимым betwen PostgreSQL и MySQL, вы можете использовать PostgreSQL contrib для CONNECT BY и перенести запрос в хранимую процедуру с тем же именем для обеих систем.

Ответ 6

Собственно, это должен быть баланс между чтением и записью.

Если вы в порядке с обновлением ряда строк на каждой вставке, тогда вложенный набор (или эквивалент) даст вам легкие и быстрые чтения.

Кроме того, простой FK для родителя даст вам ультра-простую вставку, но вполне может стать кошмаром для извлечения.

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