o7412369815963
в данном методе вставить элементы можно только к элементам верхнего уровня, к вставленным объектам не вставить… типа того, имхо, да и выборка не простой селект.

А причем тут уровень? Я говорю не о каком то дереве, а что принцип нужно менять на double linked list. Ты просто тогда будешь иметь цепь в которую при вставке елемента ненужно будет менять половину списка. А то что запрос чуть сложнее “select from table order by col”, это нонсенс.

P.S. как это не вставить елемент в любое место? Запросто ведь.

Вот еще пример обо чем я:

id name parent_id

aaa John null
bbb Mike aaa
ccc Tom bbb

Для того чтобы вставить Peter после Mike, нужно:

1) вставить новую запись: ddd Peter bbb
2) поменять parent_id у Tom на ddd

Тогда будешь иметь таблицу:

id name parent_id

aaa John null
bbb Mike aaa
ccc Tom ddd
ddd Peter bbb

а после запроса получишь в порядке:
John, Mike, Peter, Tom

o7412369815963
база - MongoDB (sql привел для объяснения), сейчас в данной коллекции около 5000 документов, алгоритм хочу с расчетом на будущее (до 1млн), да и вообще полезно знать подобные алгоритмы

размер базы, думаю, в данном случае не важен, буть то он 1Мб или 1Гб. вставка идет одной/двумя командами - алгоритм не измениться. конечно может от размера БД хост будет плющить, тут уже распараллеливать , кластеризовать и т.д, но это уже совсем другая задача…

o7412369815963
обычная sql: mysql, mssql, пострадж и подобные.

:D

ЗЫ
Я отваливаю с этой темы.

nerijus
А то что запрос чуть сложнее “select from table order by col”, это нонсенс.

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

nerijus

o7412369815963
в данном методе вставить элементы можно только к элементам верхнего уровня, к вставленным объектам не вставить… типа того, имхо, да и выборка не простой селект.

А причем тут уровень? Я говорю не о каком то дереве, а что принцип нужно менять на double linked list. Ты просто тогда будешь иметь цепь в которую при вставке елемента ненужно будет менять половину списка.

вот тут поподробней, попробую с имитировать ситуацию

значит есть таблица:
Id int
ParentId : ид родителя
ChildId : ид на элемент
Description nvarchar(30)
————
#есть 2 записи
1, null, x, x
2, null, x, x
#вставляем запись после 1-ой
1, null, x, x
2, null, x, x
3, 1, x, x
#вставляем запись после 3-ей
1, null, x, x
2, null, x, x
3, 1, x, x
4, 3, x, x

выполняем тот джойн:
SELECT parentList.Id, parentList.ParentId, childList.Id AS ChildId
FROM LinkedList parentList
LEFT JOIN LinkedList childList ON parentList.Id = childList.ParentId
получается такой (бессмысленный) результат:
1, null, 3
2, null, null
3, 1, 4
4, 3, null

где я ошибся?

nerijus
aaa John null
bbb Mike aaa
ccc Tom ddd
ddd Peter bbb

а после запроса получишь в порядке:
John, Mike, Peter, Tom

SELECT parentList.Id, parentList.name, parentList.ParentId, childList.Id AS ChildId
FROM LinkedList parentList
LEFT JOIN LinkedList childList ON parentList.Id = childList.ParentId
результат
id, name, parent, child_id
aaa John null bbb
bbb Mike aaa ddd
ccc Tom ddd null
ddd Peter bbb aaa

не совпадает с обещанным результатом

Lexander

o7412369815963
база - MongoDB (sql привел для объяснения), сейчас в данной коллекции около 5000 документов, алгоритм хочу с расчетом на будущее (до 1млн), да и вообще полезно знать подобные алгоритмы

размер базы, думаю, в данном случае не важен, буть то он 1Мб или 1Гб. вставка идет одной/двумя командами - алгоритм не измениться. конечно может от размера БД хост будет плющить, тут уже распараллеливать , кластеризовать и т.д, но это уже совсем другая задача…

o7412369815963
обычная sql: mysql, mssql, пострадж и подобные.

:D

ЗЫ
Я отваливаю с этой темы.

если не знаете монгу - можете с ней не заморачиваться, я для этого и веду тему на sql т.к. его знают многие, а перенести простое решение с sql на монгу запросто: селекты заменяем find'ами, вместо join используем вложеные элементы, вот и все

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

:) Да ты не ищи проблем там где их нет.

o7412369815963
значит есть таблица:
Id int
ParentId : ид родителя
ChildId : ид на элемент
Description nvarchar(30)

ChildId ненужен

o7412369815963
#есть 2 записи
1, null, x, x
2, null, x, x
#вставляем запись после 1-ой
1, null, x, x
2, null, x, x
3, 1, x, x

после вставки будет:
1, null, x
2, 3, x <- (Предыдущий уже будет не 1-й, а 3-й елемент)
3, 1, x

o7412369815963
получается такой (бессмысленный) результат:

Результат тут нормальный. Это же double linked list то есть один елемент связан с другим. Если мешает названия можешь поменять на previuos_id, next_id, возможно яснее будет. Теперь сделай функцию для итерации от начала до конца и все (и неважно коким порядком данные пришли с дб, когда ты знаешь какой елемент стоит в переди и какой с зади).

дак это просто список получается, подбиваем результат:
* для вставки делается 2 запроса
* после выборки всех данных их нужно превращать в массив перед отдачей клиенту.
- т.к. это веб проект, то в основном будет происходить выборка данных, значить нагрузка выборки наносит больший удар на итоговую производительность чем нагрузка вставки
- если далее развивать проект, например постраничный вывод который есть почти на всех сайтах, то этот метод вообще не годиться т.к. вместо того что-б выдать 20 элементов для текущей страницы придется тащить все 5000 элементов, потом строить массив, и только из него брать те самые 20 элементов.

итого: этот вариант проигрывает варианту с генерацией кодов

o7412369815963
для вставки делается 2 запроса

Уж луче чем полмиллиона

o7412369815963
после выборки всех данных их нужно превращать в массив перед отдачей клиенту.

Да причем тут массив? Какая тебе разница в каком порядке данные будут внутри процесса. Разница тут только в итерации. Вместо for element in list: print.element, будешь писать while next: print element; next = element.next

o7412369815963
если далее развивать проект, например постраничный вывод который есть почти на всех сайтах, то этот метод вообще не годиться т.к. вместо того что-б выдать 20 элементов для текущей страницы придется тащить все 5000 элементов, потом строить массив, и только из него брать те самые 20 элементов.

Для этого можно сначала взять только id в кеш, сделать сортировку (как индекс в дб), а потом выбирать с “select in list” (для web страницы, данных же не будет много).

А так делай как хочешь, не мне же потом страдать если что.