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

Question

У меня есть cms, которая хранит комментарии к статьям.Эти комментарии могут быть как многопоточными, так и не многопоточными.Хотя технически они одинаковы, только столбец ответа остается пустым, когда он не является потоковым.Мое приложение работает на SQLLite, MySQL и pgsql, поэтому мне нужен довольно стандартный SQL.

В настоящее время у меня есть таблица комментариев

comment_id
article_id
user_id
comment
timestamp
thread (this is the reply column)

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

Если комментарии не являются потоковыми, я могу легко просто упорядочить их по метке времени.

Если они имеют резьбу, я сортирую их следующим образом

ORDER BY SUBSTRING(c.thread, 1, (LENGTH(c.thread) - 1))

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

Answer 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

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

• Если один компонент идентификатора потока вырастет до 2 цифр, сортировка по идентификатору потока не приведет к ожидаемому порядку.Простым решением является обеспечение того, чтобы все компоненты идентификатора потока были дополнены нулями, чтобы иметь одинаковую ширину.
• Сортировка по убыванию идентификатора потока не приводит к ожидаемому порядку убывания.

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

Answer 2

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

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

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

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

Answer 3

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

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

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

• Иерархические запросы в MySQL - подражание Oracle's 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 специфичный, но это действительно быстро.

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

Answer 4

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

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

Answer 5

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

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

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

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

Затем вы можете использовать рекурсивное общее табличное выражение для отображения многопоточного представления.Доступен пример здесь.

Answer 6

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

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

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

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