Welcome to php club

Деревья в базах данных => Идеальная библиотека

Идеальная библиотека


Какой должна быть идеальная библиотека для хранения деревьев в базах данных?


При составлении требований к идеальной библиотеке использовались идеи popoff, Rin, Макс, su1d, JVN, vladax.


  • в идеальной библиотеке структура дерева хранится отдельно от данных. Это необходимо для увеличения скорости обработки дерева и для выполнения некоторых следующих пунктов
  • в идеальной библиотеке порядок сортировки элементов никогда не задается структурой дерева, потому что не все способы хранения деревьев позволяют задавать порядок в структуре
  • идеальная библиотека позволяет не изменяя никакой код обработки (добавления, редактирования, удаления, чтения) данных изменять способ хранения деревьев
  • идеальная библиотека позволяет добавлять, удалять, перемещать, выбирать разными способами элементы дерева, а так же проверять и восстанавливать целостность дерева
  • идеальная библиотека позволяет удалять вершины вместе со всеми дочерними вершинами (либо только все дочерние вершины, а сама вершина остается), поддерживает каскадное удаление из зависимых таблиц и вызов callback функций для удаления информации, которая не хранится в таблицах. Удаляются сначала дети, потом родители: ни одна вершина не может быть удалена, если у нее есть дети.
  • идеальная библиотека должна уметь работать с разными базами данных – использовать абстрактный доступ к базам данных
  • идеальная библиотека должна уметь использовать триггеры и хранимые процедуры, а так же работать без них – в зависимости от того, поддерживает ли их используемая база данных
  • идеальная библиотека не содержит в себе ошибок и поставляется вместе с модулями автоматизированного тестирования (юнит-тестами)
  • идеальная библиотека должна уметь хранить в одной таблице дерево несколькими разными способами. Какими именно – задает пользователь.
    Это нужно, например, для того, чтобы на время операций по добавлению большого количества элементов отключать расстановку l и r (в Nested Sets), а после операции – расставить l и r, используя parent_id (в Adjacency List).
  • идеальная библиотека позволяет воспользоваться всеми преимуществами выбранных способов хранения деревьев. Например, в Nested Sets можно хранить в структуре дерева порядок элементов дерева, чего нельзя, например, в Adjacency List.
  • при комбинировании должен выбираться тот способ хранения дерева, который работает быстрее для решения каждой отдельной задачи. Например, при комбинировании Nested Sets и Adjacency List для поиска всех непосредственных детей заданного родителя лучше использовать Adjacency List.

Особенности для библиотек Nested Sets


  • библиотека должна уметь добавлять узлы в любом нужном месте: левым или правым ребенком или братом для заданного элемента
  • функция перемещения должна уметь выполнять несколько перемещений в дереве за один вызов. В идеальной библиотеке обновление таблицы для всех перемещений должны выполняться одним sql-запросом
  • функция перемещения должна уметь перемещать в любых возможных направлениях: на позицию выше, правее, левее; вставить ребенком или братом слева или справа относительно заданного узла
  • все функции обновления должны быть оптимизированы таким образом, что бы пересчитывать минимальную часть дерева.
    Например, функция добавления элементов в дерево, освобождая место для вставляемого узла, не должна сдвигать в дереве исключительно, например, правую часть. Левая часть может оказаться меньше, в таком случае лучше обновлять именно левую часть дерева.
  • Нумерация узлов (left/right) не обязательно должна начинаться с 1, в частности она может быть и отрицательной.
  • идеальная библиотека должна позволять хранить в одной таблице не одно дерево, а несколько. Деревья различаются между собой идентификатором. Поскольку для этого требуется введение дополнительного поля в таблицу, то должна быть отдельная настройка, задающая наличие этой возможности.
    Например, древовидный форум. Каждая тема – отдельное дерево в таблице. Тогда добавление нового сообщения в тему не затронит другие темы.

Особенности реализации идеальной библиотеки


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

 
Комментариев нет. [Показать комментарии/форму]