Тяпничный nested-set

Добрый день коллеги.

Традиционно в БД для представления деревьев используют списки смежности.
К недостаткам такого варианта можно отнести сложность движения от корня
к самому дальнему потомку и массовые выборки.

Есть интерес - попробовать NestedSet
http://en.wikipedia.org/wiki/Nested_set_model

И написать несколько реализаций такого базового интерфейса.

template<class Node>
class NestedSet{
 public:
 virtual void insertRootNode(Node node);
 virtual void insertNode(Node node,Node parent);
 virtual void dropNodes(int left,int right);
 virtual NodeIterator selectChildNodes(Node node);
}

Какие вопросы нужно решить?

По какой формуле расчитывать Left, Right?

Как уплотнять или двигать границы NestedSet если Node вставить уже невозможно (Right-Left)<1

Оптимизация итератора

Оптимизация для популярных БД (MSSQL, Oracle, MySQL)

P.S. Сорь за возможные огрехи в описании базового интерфейса. Надеюсь суть будет ясна и так.

mayton,

ух, позавчера прочёл эту статью. Интересовался разными моделями данных.
Правда, у меня пока интерес теоретический.

При беглом ознакомлении у меня возникли следующие мысли. В такой модели вставки работают медленно, как их улучшить? Возьмём пример каталога с одеждой. Мужская имеет индексы с 2 по 9. Если нужно будет добавить что-то, то придётся пересчитывать много индексов. А почему бы не сделать их с большими пропусками? Например, мужской одежде назначить изначально индексы с 2 по 900 (или 9000, или 9000000). Мужским костюмам индексы дать с 3 по 80 (а не 8). Таким образом пересчитывать все индексы придётся гораздо реже, лишь когда отведённое про запас место кончится.

Насколько я понимаю, модель NestedSet предполагает очень редкие модификации дерева.
Например - работа со справочником. Классификатором. Или конфигурацией оконного
выпадающего меню.

По поводу диапазона цифирок Left, Right. Можно взять 0 и 10^38 (макимальное значение
NUMBER поля для Oracle). Но будет-ли это рационально с точки зрения хранения?
Многие БД хранят числа в квази-текстовом формате. BinHex, BCD.

Вставку можно порешать пустотами. Т.е. не нумеровать 1,2,3... а 10,20,30... надо вставить между 20-30 делаешь 25 и т.д. Тогда в худшем случае (например станет 25,26,27 и надо вставить между 25-26) потребуется перенумировать небольшой кусок.

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

И предусматривать пакетную вставку, чтобы сразу дать блок данных, чтобы сразу распределить боле-мене равномерно.

mayton
Можно взять 0 и 10^38 (макимальное значение NUMBER поля для Oracle). Но будет-ли это рационально с точки зрения хранения?

Это будет нерационально с точки зрения скорости выборки. Чем больше размер значения, тем медленнее операция сравнения двух значений.
Тестил в свое время на MSSQL скорости используя GUID и обычный ID int(4). C GUID`ами скорости в разы медленнее, да и понятно, т.к. он в 4 раза больше места занимает (16 байт против 4х).

Была оригинальная идея. Я хотел ее обсудить.

Дерево Штерна.



Это бесконечная последовательность рациональных чисел которые замкнуты в интервал от 0 до 1. И генерить
их очень удобно. Для вставок в дочерние узлы. И схема получается весьма элегантная.

Но к сожалению я не знаю как рациональные дроби прикрутить к БД.

Тоесть такой вариант

create table nestedset(
  id number,
  name varchar2(2000),
  left RATIONAL,
  right RATIONAL
);

С рациональным (гипотетическим типом). Но в Оракле это не взлетит т.к. оракл не позволяет
перегружать типы.

Может взлетит в MSSQL/.Net с их новыми возможностиями по интеграции ДотНет кода и СКЛ машины.
Если в форуме есть МССКЛ-щики то пусть поправят.

Стоп.

Не от 0 до 1. А от нуля до плюс положительной бесконечности.

Или такой вариант.

create table nestedset(
  id number,
  name varchar2(2000),
  left_numerator number,
  left_denominator number,
  right_numerator number,
  right_denominator number
);

Чисто математически - взлетает но про поддержку БД в сортировках и сравнениях придётся забыть.

mayton
Была оригинальная идея. Я хотел ее обсудить. Дерево Штерна.

Оно двоичное. Как третий узел вставить?

mayton
Но к сожалению я не знаю как рациональные дроби прикрутить к БД.

Не надо их туда крутить. Как их сравнивать? Каждый раз приводить к одному знаменателю?
Хранить десятичное с высокой точностью тоже не вариант, чем больше размер значения, тем медленнее операция сравнения двух значений.
int 4 байта идеальный вариант.

ИМХУ тут идеального алгоритма вставки не придумать на все случаи жизни. Надо исходить из задачи: одно дело поштучно вставлять в разные части дерева, другое - сразу блок записей в одну ноду.

Там кстати еще одна большая проблема: отсортировать по Name внутри одного уровня вложенности.

Например там в примере select ... order by Left чудесным образом даст отсортированный справочник на всех уровнях вложенности, читай построчно и выводи, но не дай бог потребуется переименовать какой-нибудь верхний узел так что он переедет в другой конец, например Women`s в Girl`s.