Как сохранить заказанные объекты, которые часто меняют положение в DB
Я должен смочь сохранить большой список заказанных объектов в DB. До сих пор это просто:
ID Position OtherFields
1 45 ...
2 4736 ...
3 514 ...
...
В запросах я всегда должен получать всего несколько объектов (фильтрованный на основе OtherFields), но в правильном порядке. Легкий также, помещая индекс на Положение и с помощью "порядок Положением".
Теперь проблема: Объекты часто меняют свое Положение, и не только 1 или 2. Если идентификатор 2 меняет Положение от 4 736 до 2000, я должен обновить его Положение и Положение всех элементов между старым Положением 2000 и 4735, добавив 1 в каждой строке. И это не только один идентификатор, который изменяется на транзакцию, но некоторых, и в течение короткого времени может быть много транзакций.
Я думаю, что самый изящный способ решить проблему обновления использовал бы связанный список вместо столбца Position, куда я могу просто удалить идентификатор 2 из его старого положения путем соединения его предшественника с его преемником и затем вставить его в другом месте путем соединения его между его новым предшественником и преемником. Это было бы константой обновления и небольшое количество обновлений на изменение Положения, и это также будет мой предпочтительный способ обработать изменения (в Java в моем случае). Однако это повышает проблему N+1 для запросов в правильном порядке - даже для нескольких элементов, я должен пройти целый список в худшем случае для обнаружения их правильного порядка.
Таким образом, мой вопрос: Что Вы рекомендовали бы получить хороший баланс между необходимыми обновлениями и производительностью запросов?
До сих пор я вижу два обещать направления:
Существует ли DBMS (идеально OpenSource), который может обработать связанные списки не только с синтаксическим сахаром, но также и с хорошей производительностью, например, при помощи внутренних Индексов для связанных элементов?
Возможно, это также была бы опция просто иметь BLOB, где целый Связанный список будет сохранен в! Как большой такой Связанный список мог добраться / сколько памяти он использовал бы в DB и при выборке для скажем, 1 000 000 записей? Я использую Java +, в спящем режиме в случае, если он имеет значение. Я предполагаю, что обработка даже целого списка в памяти после выборки BLOB должна быть довольно быстрой!?
Но конечно другие идеи приветствуются также!
3 ответа
Если вы ослабите ограничение, согласно которому столбец Position должен содержать целые числа от 1 до N, и вместо этого разрешите ему содержать любые числа, вы сможете эффективно выполнять как поиск, так и обновления.
Вы можете вставить элемент между двумя другими элементами с позициями A и B, вычислив среднее (A + B) DIV 2. Например, если A равно 10000, а B равно 12000, тогда ваша новая позиция будет 11000. Иногда вы будете запускать из пробелов из-за кластеризации, после чего вы можете пройти через всю таблицу, более равномерно перераспределяя позиции.
Как насчет использования десятичной дроби для позиции? Если вы это сделаете, вы можете использовать следующий метод, чтобы поместить его между другими позициями:
Исходные записи:
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 выяснилось, что наши решения очень похожи, хотя использование десятичной дроби кажется слишком большим. мне проще ...
Следующее может быть полезным. Он не отвечает напрямую на ваши вопросы, но может пролить свет на то, как это сделать (если это возможно для ваших требований):