nikolay_g ([info]nikolay_g) wrote in [info]ru_programming,
2005-01-17 11:08:00
  • Previous
  • Memorize
  • Share
  • Next

Способы реляционной организации древовидной иерархии

Недавно встал перед мной вопрос о древовидной иерархии в базе данных. Подумал сам, поискал решения других - решил вопрос. Также процесс решения вылился в обзор способов реляционной организации древовидной иерархии (http://www.grebenshikov.ru/written.phtml?a=1&id=127). Возможно, кому-то также будет полезно.

Также, интересны мнения и примеры других решений.

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    switch

    Your IP address will be recorded 

     
    Help
  • 16 comments

[info]_zerg

January 17 2005, 05:45:08 UTC 7 years ago

http://www.livejournal.com/users/demiurg/53125.html

[info]name_fa

January 17 2005, 07:51:52 UTC 7 years ago

Левые/правые индексы в своих поисках видели?

[info]nikolay_g

January 17 2005, 09:11:38 UTC 7 years ago

Просветите пожалуйста.

[info]name_fa

January 17 2005, 20:34:02 UTC 7 years ago

Ну, вкратце. Представьте себе дерево:


Обходим дерево "вокруг" от корня против часовой стрелки и нумеруем элементы в том порядке, в котором они попадаются у нас на пути:


Так, у каждого элемента получилось два номера - один "слева", а другой - "справа".
Нетрудно видеть (на самом деле, это легко доказывается), что элемент А является ребёнком элемента Б тогда и только тогда, когда левый индекс А находится между левым и правым индексами Б. Это позволяет быстро выбирать всех детей, всех родителей и т.п.

Если немного подумать, легко можно создать правило изменения левых/правых индексов при вставке/удалении/перемещении элементов. У нас в своё время эти правила работали на триггерах, и операции с БД получались вполне прозрачными.

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


А ещё - мне тут вот что пришло в голову: то, как это реализовать, вообще-то зависит от целей, которые вы преследуете.

[info]rblaze

January 17 2005, 09:28:37 UTC 7 years ago

Взять сразу иерархическую базу данных и не упираться в реляционные?

[info]ex_zorgg254

January 17 2005, 09:37:41 UTC 7 years ago

А лучше сразу две! Одну иерархическую и одну реляционную!

[info]nikolay_g

January 17 2005, 09:48:07 UTC 7 years ago

Приведите пример.

[info]ex_zorgg254

January 17 2005, 09:53:58 UTC 7 years ago

Пример чего?

[info]nikolay_g

January 17 2005, 10:01:08 UTC 7 years ago

Пример того случая, когда иметь две базы данных лучше, чем одну.
Для большинства задач это излишне.

[info]ex_zorgg254

January 17 2005, 10:02:39 UTC 7 years ago

Это была ирония.

[info]nikolay_g

January 18 2005, 02:42:27 UTC 7 years ago

Не разглядел. 8)

[info]bopox

January 17 2005, 09:38:42 UTC 7 years ago

Довольно похабная, надо заметить, статья.
Во первых не решена проблема собственно скорости, ежу понятно как уложить дерево в табличку, вопрос зачем? А нужно это при лингвистических или эвристических алгоритмах поиска для древовидного уменьшения энтропии, фактически мы использовали куда более навороченную систему для нормализации входящих данных (эдык 10mln в квартал).
К тому же SQL уходит в глубокий даун если есть циклические деревья или вообще граф-переходов, эту проблему тоже приходится решать...
Тут необходимо описывать процесс матчастью, а не местечковыми догадками без выводов.

[info]nikolay_g

January 17 2005, 09:57:30 UTC 7 years ago

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

[info]cousin_it

January 17 2005, 10:35:07 UTC 7 years ago

http://c2.com/cgi/wiki?TreeInSql

[info]cemb

January 17 2005, 23:50:20 UTC 7 years ago

базу пользуем реляционную а дерево бьем на домены. Корневой домен держим в памяти всегда в виде структуры. Остальные подгружаем-выгружаем по необходимости

[info]syarzhuk

January 22 2005, 19:16:10 UTC 7 years ago

Oracle: CONNECT BY
SQL Server workarounds: 1, 2
Create an Account
Forgot your login or password?
Facebook Twitter More login options
English • Español • Deutsch • Русский…