древовидные структуры, почему вложенные множества , а не

[SelenIT]

Screjet, прошу прощения, но что-то я не улавливаю нить (в прямом и переносном смысле, сорри за каламбур ). Не затруднит пояснить это все хотя бы простеньким примером?

 

[Screjet]

Ниче, есси типа в XML

<root>
	<!-- thread = 1 -->
	<node id=1 parent=null thread=1 path=null>
		<node id=2 parent=1 thread=1 path=1.2>
			<node id=3 parent=2 thread=1 path=1.2.3/>
			...
			<node id=[n>parent] parent=2 thread=1 path=1.2.n/>
		</node id=2>
		...
		<node id=[n>parent] parent=1 thread=1 path=1.n/>
	</node id=1>
	<!-- thread = 100 -->
	<node id=100 parent=null thread=100 path=null>
		<node id=101 parent=100 thread=100 path=1.100.101>
			<node id=102 parent=101 thread=100 path=1.100.101.102/>
			...
			<node id=[n>parent] parent=101 thread=100 path=1.100.101.n/>
		</node id=101>
		...
		<node id=[n>parent] parent=100 thread=100 path=1.100.n/>
	</node id=100>
</root>

Пути забыл нарисовать.

 

[SelenIT]

Screjet, спасибо! Теперь почти все ясно. А то я сперва подумал, что "нити" заводятся и для подчиненных нодов, и через один нод могут проходить несколько "нитей", по которым "распутывается" вышележащая структура.

Не до конца понял, правда, по какой схеме будут присваиваться Id-ы потомкам нода 101 (например).

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

 

[Screjet]

У меня как сделано: если нод без родителя (корневой) то он и является родителем нити, а если у нового нода есть родитель, то ИД нити берем у него. Это уже все реализация, какова она будет не имеет значения.

А второй вариант, когда в дополнительной таблице 1-М для каждого нода папки сохраняется список всех элементов, в т.ч. ноды подчиненных родителей. Но так не пробовал, да и число записей в этой таблице может достигать космических величин ( _число_нодов_ * _глубину_вложенности_для_каждого_ ).

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

-~{}~ 02.11.04 16:51:

Избыточность исходит из необходимости. Если нет необходимости одним запросом выбирать нить/сеть, тогда избыточна. То же самое можно сказать и про путь. Это все упрощает работу с деревом.

 

[SelenIT]

Screjet, я немного подумал над твоим вторым вариантом, и вдруг пришла в голову такая структура:

id, path_element, distance

где distance - число шагов (разность уровней вложенности) нода id и "старшего" нода path_element, через который проходит маршрут к данному ноду.

При distance=1, получим из этой схемы обычный adjacency list. Выбрав все path_element для данного id и отсортировав по убыванию distance, сразу получим полный путь. Так же элементарно находятся как все потомки, так и только непосредственные. Плюс, в отличие от nested sets не надо переписывать всю таблицу при добавлении/удалении/перемещении нода...

Вот только "космическое" число записей... оно, конечно, да... хотя для реального сайта даже при ~10E+4 нодов и средней глубине вложенности ~10E+1... в общем, обычного INT хватит надолго, а поиск по одним числовым полям должен быть шустрым... Разве такая структура не самодостаточна?

 

[Screjet]

Угу, согласен, тока дерево/нить когда выбирается из БД все равно сохраняется в виде дерева (в массиве, например), а сортировка (выборки) происходит по специальной паре Родитель--Порядок.

 

[SelenIT]

Имхо, модель "двух координат" по сути - как раз подобный массив в готовом виде

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