Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничный nested-set / 25 сообщений из 27, страница 1 из 2
  1  все
10.04.2015, 11:51
    #38932889
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Добрый день коллеги.

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

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

И написать несколько реализаций такого базового интерфейса.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
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. Сорь за возможные огрехи в описании базового интерфейса. Надеюсь суть будет ясна и так.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 14:50
    #38933113
petalvik
petalvik
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
mayton,

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

При беглом ознакомлении у меня возникли следующие мысли. В такой модели вставки работают медленно, как их улучшить? Возьмём пример каталога с одеждой. Мужская имеет индексы с 2 по 9. Если нужно будет добавить что-то, то придётся пересчитывать много индексов. А почему бы не сделать их с большими пропусками? Например, мужской одежде назначить изначально индексы с 2 по 900 (или 9000, или 9000000). Мужским костюмам индексы дать с 3 по 80 (а не 8). Таким образом пересчитывать все индексы придётся гораздо реже, лишь когда отведённое про запас место кончится.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 14:57
    #38933126
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Насколько я понимаю, модель NestedSet предполагает очень редкие модификации дерева.
Например - работа со справочником. Классификатором. Или конфигурацией оконного
выпадающего меню.

По поводу диапазона цифирок Left, Right. Можно взять 0 и 10^38 (макимальное значение
NUMBER поля для Oracle). Но будет-ли это рационально с точки зрения хранения?
Многие БД хранят числа в квази-текстовом формате. BinHex, BCD.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 15:18
    #38933152
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Вставку можно порешать пустотами. Т.е. не нумеровать 1,2,3... а 10,20,30... надо вставить между 20-30 делаешь 25 и т.д. Тогда в худшем случае (например станет 25,26,27 и надо вставить между 25-26) потребуется перенумировать небольшой кусок.

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

И предусматривать пакетную вставку, чтобы сразу дать блок данных, чтобы сразу распределить боле-мене равномерно.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 15:24
    #38933163
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
maytonМожно взять 0 и 10^38 (макимальное значение NUMBER поля для Oracle). Но будет-ли это рационально с точки зрения хранения?
Это будет нерационально с точки зрения скорости выборки. Чем больше размер значения, тем медленнее операция сравнения двух значений.
Тестил в свое время на MSSQL скорости используя GUID и обычный ID int(4). C GUID`ами скорости в разы медленнее, да и понятно, т.к. он в 4 раза больше места занимает (16 байт против 4х).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 15:45
    #38933180
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Была оригинальная идея. Я хотел ее обсудить.

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



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

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

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

Код: plsql
1.
2.
3.
4.
5.
6.
create table nestedset(
  id number,
  name varchar2(2000),
  left RATIONAL,
  right RATIONAL
);


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

Может взлетит в MSSQL/.Net с их новыми возможностиями по интеграции ДотНет кода и СКЛ машины.
Если в форуме есть МССКЛ-щики то пусть поправят.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 15:46
    #38933182
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Стоп.

Не от 0 до 1. А от нуля до плюс положительной бесконечности.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 16:00
    #38933197
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Или такой вариант.
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
create table nestedset(
  id number,
  name varchar2(2000),
  left_numerator number,
  left_denominator number,
  right_numerator number,
  right_denominator number
);


Чисто математически - взлетает но про поддержку БД в сортировках и сравнениях придётся забыть.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 16:05
    #38933203
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
maytonБыла оригинальная идея. Я хотел ее обсудить.

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

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

ИМХУ тут идеального алгоритма вставки не придумать на все случаи жизни. Надо исходить из задачи: одно дело поштучно вставлять в разные части дерева, другое - сразу блок записей в одну ноду.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 16:31
    #38933235
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Там кстати еще одна большая проблема: отсортировать по Name внутри одного уровня вложенности.

Например там в примере select ... order by Left чудесным образом даст отсортированный справочник на всех уровнях вложенности, читай построчно и выводи, но не дай бог потребуется переименовать какой-нибудь верхний узел так что он переедет в другой конец, например Women`s в Girl`s.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 16:40
    #38933248
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Тебе подобные запросы ничего не напоминают?
Код: plaintext
1.
2.
3.
4.
5.
SELECT DISTINCT Child.Node, Child.Left, Child.Right
FROM Tree AS Child, Tree AS Parent 
WHERE Parent.Left < Child.Left AND Parent.Right > Child.Right  -- associate Child Nodes with ancestors
GROUP BY Child.Node, Child.Left, Child.Right
HAVING MAX(Parent.Left) = 1


Помнишь как быстро считалось select`ом перекрытие диапазонов IP-шников?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 18:14
    #38933351
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Dima TНе надо их туда крутить. Как их сравнивать? Каждый раз приводить к одному знаменателю?

Ну... ты вроде-бы в теории чисел не новичок. Сравнение дробей - суть умножение числителей и знаменателей крест-на-крест.
И сравнение. Достаточно простая формула совершенно не требующая расчёта НОД.

P.S. В тему был мой топик о золотых треугольниках .. к сож не могу найти.

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

Насчёт хранения приближённого числа которое может быть использовано в поиске (по аналогии с хеш-кодом) я много
думал. Можно рядом положить вещественное чтобы (грубо) отсекать те data-rows которые ну 100% не попадают
в интервал поиска. Но покая я не определился с критерием точности - поскипаю эту оптимизацию. Хотя она
интересна.

По поводу int32 - полностью согласен. Это чрезвычайно длинная последовательность особенно с формулой Штерна
когда при движении вправо-вниз мы инкременируем числитель а влево-вниз - знаменатель у нас получается
очень медленный рост счётчика который при обычном режиме sequence в БД (справочник или классификатор)
переполнится только через много много лет.

ИМХУ тут идеального алгоритма вставки не придумать на все случаи жизни. Надо исходить из задачи: одно дело поштучно вставлять в разные части дерева, другое - сразу блок записей в одну ноду.
Да. Я думаю что дерево Штерна не будет иметь особого перформанса для вставки.
Но я предлагаю исходить из того что на 0.1% вставок в справочник приходится примерно
99.9% чтений (full-table-scan).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 18:16
    #38933353
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Dima TОно двоичное. Как третий узел вставить?
Ну... оно вобщем-то никакое. Не двоичное и не троичное. К преимуществу
этого дерева я могу отнести то что промежуточные узлы в которых нет
потомков - можно удалить. И при этом структура сохраняется. Ведь
семантическая связь идёт с корнем только через Left, Right и больше ничего
не нужно.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 18:25
    #38933363
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Dima TТам кстати еще одна большая проблема: отсортировать по Name внутри одного уровня вложенности.

Например там в примере select ... order by Left чудесным образом даст отсортированный справочник на всех уровнях вложенности, читай построчно и выводи, но не дай бог потребуется переименовать какой-нибудь верхний узел так что он переедет в другой конец, например Women`s в Girl`s.
В создающем скрипте я не указал поле depth. Я честно говоря не знаю нужно оно
или нет. С точки зрения оптимизации поиска... вроде-бы нужно. Если мы выбираем
всех потомков Node1 у которой уровень равен 5 то можно сразу отсекать всех кто меньше 5.
И наоборот. Если это гео-классификатор городов и стран и улиц и домов то можно ограничить поиск
городами с другой стороны.

Сразу сходу добавлю что nested-set скорее всего не выдержит конкуренции с обычным
сильно-ветвящимся деревом который мы можем закодить в С++ с использованием
коллекций в узлах.

Но я надеюсь что алгоритмы расчёта Left/Right могут быть полезны в реляционных БД. Там где
технически нет возможности вложить data-row коллекцию ссылок на другие data-row.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 18:37
    #38933372
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Вобщем... буду последователен.

Накатываю патчик на создающий скрипт.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
create sequence ns_pk;

create table nestedset(
  id number primary key, -- This is fucken PK. Or Not? It it nessesary?
  name varchar2(2000),  -- This is fucken body of Node. Is it possible to use 'TYPE'? Idntknw.
  depth number not null, 
  l1 number not null,
  l2 number not null,
  r1 number not null,
  r2 number not null
);



Я кое-что изменил. Не люблю длинные имена. Пускай числитель и знаменатель для Left/Right будут просто 1-м и 2-м числом.
Для краткости формул.

Еще остались нерешённые вопросы.

Где будет PK? Теоретически комбинация двух числителей и знаменателей уже является PK.

Нужно-ли кешировать результат деления? В каких запросах это поможет и какова будет возможная погрешность?

Тестовая выборка? Откуда взять? За неимением гео-классификатора я просто возьму кусок своей файловой системы
где узлы - это каталоги.

Тестовые запросы. Какие они должны быть? Надо оценить точечные (OLTP) на выборку. И выборка целых поддеревьев.
Если представить что мы работаем с GUI и пользователь кликает по TreeControl и раскрывает классификаторы.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 19:34
    #38933415
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
maytonDima TНе надо их туда крутить. Как их сравнивать? Каждый раз приводить к одному знаменателю?

Ну... ты вроде-бы в теории чисел не новичок. Сравнение дробей - суть умножение числителей и знаменателей крест-на-крест.
И сравнение. Достаточно простая формула совершенно не требующая расчёта НОД.
Я про НОД не писал :) Именно одно сравнение и два умножения против одного сравнения. Разница в скорости на порядок, если не больше.

maytonВ создающем скрипте я не указал поле depth. Я честно говоря не знаю нужно оно
или нет. С точки зрения оптимизации поиска... вроде-бы нужно.
Вроде толку от него немного. Хотел написать что ты про него забыл, но примера зачем он нужен не придумал.

Не знаток и не любитель деревьев. Нездоровая структура не вписывающаяся никуда. Там где можно ее заменить на иерархию с ограниченным числом уровней - менять однозначно.

Про nested-set сегодня впервые от тебя узнал, если честно. Сначала очарование - затем осознание и разочарование. Вот и написал что с ходу в глаза бросилось. Потом почитал инет, есть польза для быстрого охвата диапазона, элементарно быстро за раз средствами SQL посчитать что-то связанное с конкретным узлом. Тут очень эффективно сверху охватывется все что внизу, поэтому я бы лучше добавил классическое parent_id, которое позволяет эффективно идти снизу вверх.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 19:49
    #38933425
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
maytonГде будет PK? Теоретически комбинация двух числителей и знаменателей уже является PK.

PK должен быть абстрактный. Просто счетчик (или GUID) не связанный ни с чем. Не надо никогда предавать другие смыслы PK, мизерная оптимизация обернется гигансткими проблемами, например на него ссылается 100500 записей дочерних таблиц, а тебе надо его немного поменять потому что его смысл поменялся.

maytonНужно-ли кешировать результат деления? В каких запросах это поможет и какова будет возможная погрешность?

Данные где? Если в СУБД, то надо ее встроенными средствами пользоваться по максимуму и не прикручивать сверху велосипеды, быстрее не будет.

maytonТестовая выборка? Откуда взять? За неимением гео-классификатора я просто возьму кусок своей файловой системы
где узлы - это каталоги.

Тестовые запросы. Какие они должны быть? Надо оценить точечные (OLTP) на выборку. И выборка целых поддеревьев.
Если представить что мы работаем с GUI и пользователь кликает по TreeControl и раскрывает классификаторы.

по хорошему надо какую-то реальную задачу. Файловая система - задача не очень, хотя обычные к ней запросы идеально оптимизируются:
1. Сколько файлов в папке
2. выбрать файлы по маске из папки с подпапками.
Для второго надо parent_id чтобы полный путь восстановить.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 20:01
    #38933431
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Я всегда очень пристальное внимание уделяю тестовой выборке. Мда. Файловая система
- не очень т.к. я не смогу придумать актуальных запросов.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 20:09
    #38933434
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Dima Tmaytonпропущено...

Ну... ты вроде-бы в теории чисел не новичок. Сравнение дробей - суть умножение числителей и знаменателей крест-на-крест.
И сравнение. Достаточно простая формула совершенно не требующая расчёта НОД.
Я про НОД не писал :) Именно одно сравнение и два умножения против одного сравнения. Разница в скорости на порядок, если не больше.
Запутал ты меня своими теориями чисел, два произведения мелочь :)

Главное: невозможно использовать индексы, т.к. результат сравнения зависит от обоих значений, т.е. всегда тупой перебор декартова произведения. А это супер тормоз.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 20:18
    #38933438
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Помнишь я говорил про краеугольный камень современных dbms (heap organized tables).
Для них невозможо построить план table-scan с участием предиката

WHERE a1 < x and x < a2;

?

Этот вопрос частично решают spatial-системы. Которые шуршат по картографии
но это тема очень specific. И не все БД поддерживают spatial запросы.

И в этой теме я вобщем-то подразумеваю FTS. Единственное дополнение - можно
фильтровать по depth или только по left к примеру.

Или можно сегментировать таблицу по подтипам. Но это суть - выборка из разных
таблиц с предусловием. С последующим union.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 20:19
    #38933439
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
maytonДля них невозможо построить план table-scan с участием предиката

Тьху. Я имею в виду невозможно использовать эффективно два индекса.
Обычно или левый или правый.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 20:37
    #38933448
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Dima TПро nested-set сегодня впервые от тебя узнал, если честно. Сначала очарование - затем осознание и разочарование. Вот и написал что с ходу в глаза бросилось. Потом почитал инет, есть польза для быстрого охвата диапазона, элементарно быстро за раз средствами SQL посчитать что-то связанное с конкретным узлом. Тут очень эффективно сверху охватывется все что внизу, поэтому я бы лучше добавил классическое parent_id, которое позволяет эффективно идти снизу вверх.
Это не последний способ. Еще есть материализация маршрута. Когда в ключе хранят путь.

idpathdepth0Clothing01Clothing/Men's12Clothing/Men's/Suits23Clothing/Woman's1

Способ достаточно быстрый и жлобский. Но неудобно делать манипуляции родительских вершин.
И лавинообразно растёт использование диска.

Впрочем я такой способ видел в одной биллинговой БД.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.04.2015, 20:54
    #38933458
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
maytonЭто не последний способ. Еще есть материализация маршрута. Когда в ключе хранят путь.
тоже читал, но имху это еще большая экзотика. Пользы очень мало.
maytonя такой способ видел в одной биллинговой БД.
Я тоже разные извраты видел, но не могу сказать что это от большого ума, чаще от желания внедрить что-то нестандартное. Жажда творчества неистребима :)
maytonПомнишь я говорил про краеугольный камень современных dbms (heap organized tables).
Для них невозможо построить план table-scan с участием предиката
WHERE a1 < x and x < a2;
Потому что никто ничего не придумал лучше теории реляционных бд. Может и придумал, но по этой теории столько понаделано, что переделывать никто не будет. Поэтому надо подстраиваться под то что есть, иначе любая иновационная поделка упрется в полную несовместимость с наделанным, и это будет не в пользу поделки. Хотя если придумают что-то реально мощнее реляционных бд - со временем они уйдут.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.04.2015, 21:07
    #38937730
ДохтаР
ДохтаР
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
maytonПомнишь я говорил про краеугольный камень современных dbms (heap organized tables).
Для них невозможо построить план table-scan с участием предиката

WHERE a1 < x and x < a2;

?

Этот вопрос частично решают spatial-системы. Которые шуршат по картографии
но это тема очень specific. И не все БД поддерживают spatial запросы.

И в этой теме я вобщем-то подразумеваю FTS. Единственное дополнение - можно
фильтровать по depth или только по left к примеру.

Или можно сегментировать таблицу по подтипам. Но это суть - выборка из разных
таблиц с предусловием. С последующим union.

Велосипед

В стебельковых срачах, эта тема вкратце обсуждалась.
Я даже приблизительный класс аллокатора выкладывал .
Жаль что тему в Других СУБД удалили .
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.04.2015, 22:04
    #38937775
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Тяпничный nested-set
Спасибо док. Я стебельковые читал и немало. Но про m-tree чет не помню.

Но в любом случае спасибо.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничный nested-set / 25 сообщений из 27, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]