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

Question

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

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

В запросах мне всегда нужно получать только несколько элементов (отфильтрованных на основе других полей), но в правильном порядке.Также легко, поставить индекс на Позицию и использовать «Порядок по Позиции».

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

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

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

Пока я вижу два многообещающих направления:

1. Существует ли СУБД (в идеале OpenSource), которая может обрабатывать связанные списки не только с синтаксическим сахаром, но и с хорошей производительностью, например, используя внутренние индексы для связанных элементов?

2. Может быть, будет также вариант иметь BLOB, в котором будет храниться весь связанный список!Насколько большим может быть такой Связанный список / сколько памяти он будет использовать в БД, и когда будет получено, скажем, 1.000.000 записей?Я использую Java + Hibernate в случае, если это имеет значение.Я предполагаю, что обработка даже всего списка в памяти после извлечения BLOB должна быть довольно быстрой!?

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

Answer 1

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

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

Answer 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

Теперь предположим, что вы хотите поместить ID 2 в диапазоне от 1 до 5000:

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

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

ОБНОВЛЕНИЕ:

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

Answer 3

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

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