Python-сообщество

в БД есть таблица отсортированная по полю “Ключ”, для неё нужно сделать 2 вида операции:
1) поменять местами рядом стоящие элементы
2) вставить элемент после текущего элемента.
требование - минимум обращений к БД!

с первым пунктом все просто - просто поменять значение ключей у этих элементов,
а вот для второго варианта пока в раздумьях…

есть у кого какие идеи?

я пока что придумал такой вариант: в текущем элементе хранить номер последнего вставленного-подчиненного элемента, и уменьшать его для следующего вставленного элемента, пример:
элементы: 1, 2, 3, 4
вставляем после 2: 1, 2, 2-9, 3, 4
вставляем после 2: 1, 2, 2-8, 2-9, 3, 4
вставляем после 2-8: 1, 2, 2-8, 2-8-9, 2-9, 3, 4
…
когда код станет сильно большим или дойдет до 0 (2-9 -> 2-0), то врубать переиндексацию.
для того что-б больше элементов можно было добавить без пересчета коды строить из символов и цифр и начинать отсчет от “zzz” (будет уменьшаться до “000” по мере добавления элементов)

Вот сейчас придет ZZZ, он тебе покажет, как с него отсчет начинать :)

А какая разница где находятся элементы в БД? Минимум обращений к БД - это минимум обращений к жесткому диску (самый тормознутый элемент в системе). Неужели такая специфическая конфигурация машины?

Или это чисто теоретическая задачка?
Если так, то при условии использования в качестве ключа что-то типа decimal(10, 3) можно легко выполнить обе операции одним движением.

нет разници где находятся элементы в БД.
у меня на веб-морду выходит таблица, строки таблицы отсортированы ( select * from table order by KEY ), нужно сделать вставку строки.
когда я буду выполнять команду вставки (insert into table …), что писать в поле “ключ”? что-бы после очередного select'a к БД, новая строка была в нужном месте.
например есть таблица:
1 Вася Пупкин
2 Иван Иванович
3 Бил Гейц
4 Путин
мне нужно вставить новую строку после Второй строки: “Медвед”, после инсерта в БД, в идеале должно быть:
1 Вася Пупкин
2 Иван Иванович
3 Медвед
4 Бил Гейц
5 Путин
но №3 уже занят Билом Гейцем, и получается нужно переписать все номера начина с 3, а их может быть десятки тысяч.

Отредактировано (Июнь 2, 2010 11:52:01)

странная у тебя какая-то бд)

сортируй вставками по индексам http://z0mbie.daemonlab.org/sort.html#sort_index

Вообще, интересная задача. Будем считать, что обычный list.insert не канает…

Если скорость построения этого списка не важна, то можно ассоциировать элементы с весом и версией.

Пример:
[
    ('ZZZ', 1, 1),
    ('o7412369815963', 10, 1),
]

[
    ('ZZZ', 1, 1),
    ('o7412369815963', 10, 1),
    ('ZZZ', 100, 2),
]

Zubchick
странная у тебя какая-то бд)

сортируй вставками по индексам http://z0mbie.daemonlab.org/sort.html#sort_index

ZZZ

[
    ('ZZZ', 1, 1),
    ('o7412369815963', 10, 1),
    ('ZZZ', 100, 2),
]

Добавляя, инкрементиуем версию (третий параметр) и получается, что мой вес будет больше.

Построение (чтение) такой схемы будет затратным, но запись быстрой. Единственная проблема – расстояния между вЕсами. Т.е. может оказаться, что впихнуть ещё один элемент невозможно. для этого нужно делать vacuum.
Ну и ещё момент – нужно держать в памяти эталонную базу (или просто индекс базы?), чтобы быстро находить нужный вес.

Я правильно понял, что ты хочешь?

o7412369815963
данные в БД хранятся не массивом, а “списком”

Lexander
Забудь эту порочную практику и нормализируй БД.
А какую цель ты преследуешь, возясь с этими операциями? Чем страшен повторный запрос к БД? Тем более, что СУБД наверняка план его выполнения в кеше держит.
Я, собственно, чего спрашиваю. У меня складывается стойкое впечатление, что ты пытаешься решить второстепенную проблему или ее последствия. В простонародье - делаешь костыль.

Вставки делать с большим инкрементом (с запасом).
На момент вставки известны ключи предыдущей записи и следующей. Берем среднее значение и делаем вставку.

Пример.
1000 - мак
2000 - виндовс
3000 - линукс

Вставляем “бсд” но вторую позицию, т.е. между 1000 и 2000.
Ключ новой записи = (1000 + 2000) / 2 = 1500.
Если ключ меньше 50 ночью запускаем процедуру перестройки ключей с целью увеличения интервала. Причем, достаточно только для проблематичного интервала, а не всю таблицу.

Из накладных расходов - простая мат. операция вычисления следующего значения ключа. На время выполнения запроса на вставку не повлияет.

Отредактировано (Июнь 2, 2010 20:13:46)