Как сохранить упорядоченные элементы, которые часто меняют положение в БД

Мне нужно иметь возможность хранить большой список упорядоченных элементов в БД. До сих пор это прямолинейно:

ID Position OtherFields
 1     45      ...
 2   4736      ...
 3    514      ...
 ...

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

Теперь проблема: элементы меняют свою позицию часто, а не только на 1 или 2. Если ID 2 изменяет позицию с 4736 по 2000, мне нужно обновить ее позицию и позицию всех элементы между старой позицией 2000 и 4735, добавив по 1 в каждой строке. И это не только один идентификатор, который изменяется за транзакцию, но и несколько, и за короткое время может быть много транзакций.

Я думаю, что самый элегантный способ справиться с проблемой update будет использовать связанный список вместо столбца Position, где я могу просто удалить ID 2 из его старой позиции, связывая своего предшественника с его преемником а затем вставить его в другое место, связав его между его новым предшественником и преемником. Это будет постоянным и небольшим количеством обновлений для каждого изменения позиции, а также моим предпочтительным способом обработки изменений (в Java в моем случае). Однако это вызывает проблему N + 1 для запросов в правильном порядке - даже для нескольких элементов, я должен пройти весь список в худшем случае, чтобы узнать их правильный порядок.

Итак, мой вопрос: Что вы посоветуете, чтобы получить хороший баланс между необходимыми обновлениями и производительностью запросов?

До сих пор я вижу два перспективных направления:

Есть ли СУБД (в идеале OpenSource), который может обрабатывать связанные списки не только с синтаксическим сахаром, но и с хорошей производительностью, например. используя внутренние индексы для связанных элементов?
Возможно, это также будет возможность просто иметь BLOB, где будет храниться весь Связанный список! Насколько велика может быть такой Linked List получить/сколько памяти он будет использовать в БД и когда выберете, пусть скажем 1.000.000 записей? Я использую Java + Hibernate в случае, если это имеет значение. Я полагаю, что обработка даже целого списка в памяти после извлечения BLOB должна быть довольно быстрой!?

Но, конечно, другие идеи приветствуются!

Ответ 1

Если вы расслабляете ограничение на то, что столбец Position должен содержать целые числа от 1 до N и вместо этого позволить ему содержать любые числа, вы можете эффективно выполнять поиск и обновления.

Вы можете вставить элемент между двумя другими позициями с позициями A и B, вычислив средний (A + B) DIV 2. Например, если A - 10000, а B - 12000, то ваша новая позиция - 11000. Иногда вы будете запускать из-за разрывов из-за кластеризации, после чего вы можете пропустить всю таблицу, распределяя позиции более равномерно.

Ответ 2

Как использовать десятичную позицию для позиции? Если вы это сделаете, вы можете использовать следующий метод, чтобы поместить его между другими позициями:

Оригинальные записи:

ID    Position  Otherfields
--------------------------
1     1.0
2     2.0
.
.
.
5000  5000.0

Затем скажите, что вы перемещаете ID 1 до 5000

ID    Position  Otherfields
--------------------------
1     4999.9
2     2.0
.
.
.
5000  5000.0

Теперь скажем, вы хотите установить идентификатор 2 между 1 и 5000:

ID    Position  Otherfields
--------------------------
1     4999.9
2     4999.91
.
.
.
5000  5000.0

Таким образом вы меняете только одну запись...

UPDATE:

После повторного чтения предложения @Mark Byers кажется, что наши решения очень похожи, хотя использование десятичного числа кажется намного проще для меня...

Ответ 3

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

ранжирование записей в таблице mysql