Я тут почитал статью о разных способах хранения дерева в базе и чойто задумалсо,
вот этот способ хранения вложенных множеств, не помню как его именно в статье
называли он хорош, только я его с трудом понимаю, а способ когда эелемент хранит
ссылку на предка он очень прост но у него при этом есть масса недостатков.
Когда то давно когда я не знал ничего про вложенные множества, как впрочем и про id, p_id
когда мне захотелось положить дерево в базу, я ничего проще (id, p_id) не выдумал.
Позже когда я понял что придетцо издеваца над базой при чтении целых веток я просто закалбасил
дополнительную таблицу которая хранила всех предков каждого элемента в дереве и их уровни вложенности.
это позволило, легко читать дерево, от любой ветки в любом направлении до любого уровня вложенности,
а так же легко получать любую информацию о количестве потомков.
при этом, процедура создания новых, или перемещания старых веток с одного места в другое осталась
такой же простой к тому же никакие вычисления или чобы то нибыло не выходило за пределы базы данных.
Вот два основных недостатка которые я вижу, это то что при получении списка потомков или родителей
приходица объединять в запросе две таблицы, и второе это жуткое дублирование хоть и ключей
но все же дублирование...
Хочу узнать мнение людей с опытом, :)
на сколько недостатки подобного способа хранения, перевешивают его достоинства
:))))) (вот сказнул)
Здравствуйте, ha_sash, Вы писали:
_>Хочу узнать мнение людей с опытом, _>на сколько недостатки подобного способа хранения, перевешивают его достоинства _>)) (вот сказнул)
_>и вообще хранят ли деревья таким образом?
С точки зрения удобства работы с деревьями, хранящимися как куча элементов с ссылкой на родителя, все зависит от СУБД (ИМХО).
По крайней мере в Oracle можно написать вот такую штуку и она выберет все поддерево вершины с id = Param:
select *
from table_name
start with id = Param
connect by prior id = parent_id
Учите матчасть .
Транзитивное замыкание вместе с уровнем вложенности хранить тоже можно. В некоторых случаях полезно (например, когда надо быстро узнавать ответ на вопрос "Содержится ли А в поддереве Б") и дает выигрыш по скорости, если правильно построить потом индексы. Проблемы с ним, действительно, такие, что надо очень аккуратно следить за поддержкой этой структуры, например, с помощью триггера на основной таблице.
Короче, хорошо-плохо (приемлимо-неприемлимо) еще очень зависит от конкретной задачи, что потом надо будет делать с данными.
Здравствуйте, ha_sash, Вы писали:
_>Когда то давно когда я не знал ничего про вложенные множества, как впрочем и про id, p_id _>когда мне захотелось положить дерево в базу, я ничего проще (id, p_id) не выдумал. _>Позже когда я понял что придетцо издеваца над базой при чтении целых веток я просто закалбасил _>дополнительную таблицу которая хранила всех предков каждого элемента в дереве и их уровни вложенности.
_>Вот два основных недостатка которые я вижу, это то что при получении списка потомков или родителей _>приходица объединять в запросе две таблицы, и второе это жуткое дублирование хоть и ключей _>но все же дублирование... _>и вообще хранят ли деревья таким образом?
Тоже в свое время читал про самые разные способы представления иерархического дерева в базе...
Но также ничего более оптимального чем две таблицы (как и у тебя — одна id, p_id + еще мои доп. параметры типа знака (вернее даже не знака, а коэф) с которым одно значение подключено к другому, другая все предки каждого элемента в дереве и их уровни вложенности + суммарный коэф вхождения)
Дело в том что по дереву необходимо делать достаточно много расчетов — т.е., например, каждая ветка есть сумма всех ее подветок с соответствующими коэф (притом еще необязательно что подветка в ветке встречаеться единожды и с одинаковыми коэф).
В базу заносились какие либо интервалные данные (например часовые). На основании этих данных надо было иметь информацию по суммам за сутки, за месяц, квартал, год, по суммам подветок, также за час, сутки, месяц, квартал, год...
Раньше все данные и суммы были представлены отдельными таблицами, а суммы считались через триггеры...
А теперь представте себе заводим мы одно часовое значение (я уже вообще молчу если храниться надо меньшие интервалы)
в тригере наобходимо пересчитать по этому значению все суммы за сутки и т.д., потом обновить все суммы каждого вышестоящего параметра со всеми их суммами за сутки, месяц и т.д. Короче если дерево большое и сильно разветвленное, а данные только первого уровня без всяких сумм уже порадка 80 млн, понятно наверное как все жутко тормозило.
Введение такой структуры как у тебя мговенно решило много задач, сделало проще структуру базы и т.д.
Скажу по секрету, что ввод данных ускорился по моим подсчетам в среднем в 100 раз, а извлечение всяких разных сумм замедлилось всего процентов на 10-20%
Остаеться еще одна хотелка которая раньше совсем не была реализована. И я не знаю каким самым оптимальным образом реализовтаь ее на новой структуре базы... Версионность этого дерева. Например, сегодня немного меняеться структура поддерева... Теперь необходимо учесть при расчете суммы за месяц что до вчера оно считалось по одному дереву, а с сегодня уже по другому.
Кто что может подсказать по этому поводу, какие идеи может быть есть?
Пока что есть идея кэшировать суммы, дело в том что не все суммы из дерева нужны всем и постоянно... А допустим запоминать эти суммы при их расчете при извлечении... А потом при вводе какого либо прааметра от которого зависит эта сумма за данный промежуток времени считать такую сумму невалидно — и обновлять ее при последующем извлечении...
Здравствуйте, Au1, Вы писали:
Au1>Здравствуйте, ha_sash, Вы писали:
_>>Хочу узнать мнение людей с опытом, _>>на сколько недостатки подобного способа хранения, перевешивают его достоинства _>>)) (вот сказнул)
_>>и вообще хранят ли деревья таким образом?
Au1>С точки зрения удобства работы с деревьями, хранящимися как куча элементов с ссылкой на родителя, все зависит от СУБД (ИМХО).
Au1>По крайней мере в Oracle можно написать вот такую штуку и она выберет все поддерево вершины с id = Param:
Au1>select * Au1> from table_name Au1> start with id = Param Au1> connect by prior id = parent_id
Au1>Учите матчасть .
Au1>Транзитивное замыкание вместе с уровнем вложенности хранить тоже можно. В некоторых случаях полезно (например, когда надо быстро узнавать ответ на вопрос "Содержится ли А в поддереве Б") и дает выигрыш по скорости, если правильно построить потом индексы. Проблемы с ним, действительно, такие, что надо очень аккуратно следить за поддержкой этой структуры, например, с помощью триггера на основной таблице.
Au1>Короче, хорошо-плохо (приемлимо-неприемлимо) еще очень зависит от конкретной задачи, что потом надо будет делать с данными.
А если у дерева такая структура
У1
- У2_1
+ У3_2
- У2_2
- У3_1
- У3_2
И по знакам надо посчитать суммы (я уж не говорю если там будут не знаки, а например коэффициенты) — такая матчасть даже для Oracle не помогает...
Т.е. мы конечно попытались решить этим способом нашу задачу — не сильно помогло — тормоза и невозможность по нижнему уровню найти всех предков с соответсвующими коэф с которыми они попадут к этому предку
но я бы сделал журнал, который протоколировал бы все изменения дерва разумеецо с датами и всеми остальными толбами которые необходимы для отделеняи однго нужного тебе варианта от другова, (протоколировал тоесть полностью все изменения)...
а на основе такого журнала можно создавать временные таблицы пряма в памяти и пряма за определенный промежуток времени и делать расчеты,..
Здравствуйте, ha_sash, Вы писали:
_>Такое сложности мне даже стыдно писать...
_>но я бы сделал журнал, который протоколировал бы все изменения дерва разумеецо с датами и всеми остальными толбами которые необходимы для отделеняи однго нужного тебе варианта от другова, (протоколировал тоесть полностью все изменения)...
_>а на основе такого журнала можно создавать временные таблицы пряма в памяти и пряма за определенный промежуток времени и делать расчеты,..
_>это канечно если я вообще понял о чем реч
Правильно понял .
Только вот тут как раз и начинает вылазить уж очень сильное дублирование
допустим в первой таблице порядка 10 тыс записей — соответственно во второй образуеться уже около (при порядка 1000 суммарных параметрови в среднем 5 уровневой вложенности) — как думаешь сколько?
а теперь если еще и хранить историю изменений и для каждого расчетного параметра извлекать и формировать несколько вариантов дерева...
Короче очень сильно начинает затормаживаться чтение данных...
Для нашей системы конечно менее критично чтение всяких сумм (гораздо больше данных пишеться в базу чем читаеться)... но я так думаю что пользователи тоже не хотят ждать по минуте для извлечения сумм...
Здравствуйте, Mckey, Вы писали:
M>Здравствуйте, ha_sash, Вы писали:
_>>Такое сложности :) мне даже стыдно писать...
_>>но я бы сделал журнал, который протоколировал бы все изменения дерва разумеецо с датами и всеми остальными толбами которые необходимы для отделеняи однго нужного тебе варианта от другова, (протоколировал тоесть полностью все изменения)...
_>>а на основе такого журнала можно создавать временные таблицы пряма в памяти и пряма за определенный промежуток времени и делать расчеты,..
_>>это канечно если я вообще понял о чем реч :)
M>Правильно понял :).
M>Только вот тут как раз и начинает вылазить уж очень сильное дублирование
M>допустим в первой таблице порядка 10 тыс записей — соответственно во второй образуеться уже около (при порядка 1000 суммарных параметрови в среднем 5 уровневой вложенности) — как думаешь сколько? M>а теперь если еще и хранить историю изменений и для каждого расчетного параметра извлекать и формировать несколько вариантов дерева... M>Короче очень сильно начинает затормаживаться чтение данных... M>Для нашей системы конечно менее критично чтение всяких сумм (гораздо больше данных пишеться в базу чем читаеться)... но я так думаю что пользователи тоже не хотят ждать по минуте для извлечения сумм... :(
Если все настолько серьезно, дублирование канечно огромное,.. но так на мой взгляд сохраняеца полная хренология, я бы предположил что по подобному журналу вполне можно сделать откат до заданной даты,.. мне кажецо актуальную часть журнала можно было бы хранить напосредственно в базе, а все поражняки сливать куда нить или удалчять,.. и по поводу тормозни,. я думаю если все настолько серьезно,. то может быть решением было бы перенести эту задачу на другой сервер? реплицируешь туда чать данных он делает расчет, при этом основная система не тормозит. если это канечно вообще возможно реализовать :)
Здравствуйте, ha_sash, Вы писали:
_>и вообще хранят ли деревья таким образом?
Такой способ называется транзитивное замыкание, частенько оказывается наилучшим вариантом.
P. S.
1. Падонковский и около падонковский сленг на сайте строго запрещен, не надо язык коверкать, здесь технический форум.
2. Избыточное цитирование так же категорически не приветствуется.
M>И по знакам надо посчитать суммы (я уж не говорю если там будут не знаки, а например коэффициенты) — такая матчасть даже для Oracle не помогает... M>Т.е. мы конечно попытались решить этим способом нашу задачу — не сильно помогло — тормоза и невозможность по нижнему уровню найти всех предков с соответсвующими коэф с которыми они попадут к этому предку
Гм... а в чем проблема?
select sum(ct) from
(select *
from table_name
start with id = Param
connect by prior id = parent_id
)
Для каждого узла (сомнительно, что это реально надо). Если грамотно расставить индексы (по parent_id и по id) проблем должно быть немного.
В проблему поиска предка по к-ту я, честно говоря, не въехал... Ну, делаем, там,
select * from table_name where parent_id = :param and ct = :param2
чем плохо? При наличии индексов...
Если нужно пройтись по дереву снизу вверх и чего-то там посчитать, то это вроде тоже решается так или иначе.
Хотя признаю: спал сегодня мало, могу нести разную ерунду...
Здравствуйте, ha_sash, Вы писали:
_>на сколько недостатки подобного способа хранения, перевешивают его достоинства
Зависит от ситуации. Иногда это наилучший метод. Основной минус, пожалуй — тяжелая реализация update-а (ситуации, когда узел дерева переезжает к другому родителю, и нужно перепривязать всех его потомков).
Здравствуйте, Softwarer, Вы писали:
S>Здравствуйте, ha_sash, Вы писали:
_>>на сколько недостатки подобного способа хранения, перевешивают его достоинства
S>Зависит от ситуации. Иногда это наилучший метод. Основной минус, пожалуй — тяжелая реализация update-а (ситуации, когда узел дерева переезжает к другому родителю, и нужно перепривязать всех его потомков).
Абсалютно ничего сложного, меняешь родителя и копируешь данные о его предках плюс добоаляя к предкам самого родителя,...
)) (вот сказнул)
.
Мы уже победили, просто это еще не так заметно...
