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

Question

У меня есть смс, который хранит комментарии против статей. Эти комментарии могут быть как потоковыми, так и не потоковыми. Хотя технически они совпадают только с тем, что столбец ответа остается пустым, когда он не содержит потоков. Мое приложение работает на 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

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

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

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

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

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

Answer 4

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

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

Answer 5

К сожалению, методы чистого 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 6

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

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

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

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