Представление порядка в реляционной базе данных
https://stackoverflow.com/questions/21388
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть коллекция объектов в базе данных.Изображения в фотогалерее, товары в каталоге, главы в книге и т. д.Каждый объект представлен в виде строки.Я хочу иметь возможность произвольно упорядочивать эти изображения, сохраняя этот порядок в базе данных, чтобы при отображении объектов они были в правильном порядке.
Например, предположим, что я пишу книгу, и каждая глава является объектом.Я пишу свою книгу и располагаю главы в следующем порядке:
Введение, доступность, форма vs.Функция, ошибки, согласованность, вывод, индекс
Он отправляется в редактор и возвращается со следующим предложенным порядком:
Введение, форма, функция, доступность, последовательность, ошибки, заключение, указатель
Как я могу сохранить этот порядок в базе данных надежным и эффективным способом?
У меня были следующие идеи, но ни одна из них меня не в восторге:
Множество.Каждая строка имеет идентификатор заказа. При изменении порядка (путем удаления с последующей вставкой) идентификаторы заказа обновляются.Это упрощает поиск, поскольку это просто
ORDER BY, но кажется, что его легко сломать.// REMOVAL
UPDATE ... SET orderingID=NULL WHERE orderingID=removedID
UPDATE ... SET orderingID=orderingID-1 WHERE orderingID > removedID
// INSERTION
UPDATE ... SET orderingID=orderingID+1 WHERE orderingID > insertionID
UPDATE ... SET orderID=insertionID WHERE ID=addedIDСвязанный список.В каждой строке есть столбец для идентификатора следующей строки в порядке упорядочения.Обход здесь кажется дорогостоящим, хотя можно каким-то образом использовать
ORDER BYо чем я не думаю.Разнесенный массив.Установите для orderingID (как указано в № 1) большое значение, чтобы первый объект имел значение 100, второй — 200 и т. д.Затем, когда происходит вставка, вы просто помещаете ее в
(objectBefore + objectAfter)/2.Конечно, время от времени это нужно будет перебалансировать, чтобы не располагать объекты слишком близко друг к другу (даже при использовании чисел с плавающей запятой вы в конечном итоге столкнетесь с ошибками округления).
Ничто из этого не кажется мне особенно элегантным.Есть ли у кого-нибудь лучший способ сделать это?
Решение 9
Поскольку я чаще всего сталкивался с этим при работе с Django, я обнаружил это решение быть максимально работоспособным.Кажется, что не существует «правильного способа» сделать это в реляционной базе данных.
Другие советы
Другой альтернативой было бы (если ваша СУБД поддерживает это) использовать столбцы типа массив.Хотя это нарушает правила нормализации, в подобных ситуациях это может быть полезно.Одна известная мне база данных, имеющая массивы, — это PostgreSQL.
Миксин act_as_list в Rails обрабатывает это в основном так, как вы описали в пункте 1.Он ищет столбец INTEGER с именем Position (его имя, конечно, можно переопределить) и использует его для выполнения ORDER BY.Когда вы хотите изменить порядок вещей, вы обновляете позиции.Он отлично служил мне каждый раз, когда я его использовал.
В качестве примечания: вы можете избавиться от необходимости всегда выполнять перепозиционирование при ВСТАВКЕ/УДАЛЕНИИ, используя разреженную нумерацию - вроде как в те времена...вы можете нумеровать свои позиции 10, 20, 30 и т. д.и если вам нужно вставить что-то между 10 и 20, просто вставьте это с позиции 15.Аналогично при удалении вы можете просто удалить строку и оставить пробел.Перенумерацию нужно выполнять только тогда, когда вы действительно меняете порядок или если вы пытаетесь вставить, и нет подходящего пробела для вставки.
Конечно, в зависимости от вашей конкретной ситуации (например.независимо от того, загружены ли у вас другие строки в память или нет), использование подхода с пробелами может иметь смысл, а может и не иметь.
Просто мысль, учитывая вариант №1 против №3:разве опция разнесенного массива (№ 3) не откладывает проблему обычного массива (№ 1)?Какой бы алгоритм вы ни выбрали, либо он сломан, и позже у вас возникнут проблемы с №3, либо он работает, и тогда №1 должен работать так же хорошо.
Если объекты не имеют жесткого набора ключей в других таблицах и списки короткие, проще всего удалить все в домене и просто повторно вставить правильный список.Но это непрактично, если списки большие и у вас есть много ограничений, замедляющих удаление.Я думаю, что ваш первый метод действительно самый чистый.Если вы запустите его в транзакции, вы можете быть уверены, что пока вы находитесь в середине обновления, не произойдет ничего странного, что могло бы испортить заказ.
Я сделал это в своем последнем проекте, но это было для стола, который нужно было специально заказывать лишь изредка и к которому обращались не слишком часто.Я думаю, что разнесенный массив будет лучшим вариантом, потому что его переупорядочение в среднем будет самым дешевым, просто включающим изменение одного значения и запрос к двум).
Кроме того, я предполагаю, что ORDER BY будет довольно сильно оптимизирован поставщиками баз данных, поэтому использование этой функции будет более выгодным для производительности, чем реализация связанного списка.
Используйте число с плавающей запятой для представления положения каждого элемента:
Пункт 1 -> 0,0
Пункт 2 -> 1.0
Пункт 3 -> 2.0
Пункт 4 -> 3.0
Вы можете поместить любой элемент между любыми двумя другими элементами, просто разделив его пополам:
Пункт 1 -> 0,0
Пункт 4 -> 0,5
Пункт 2 -> 1.0
Пункт 3 -> 2.0
(Пункт 4 перенесен между пунктами 1 и 2).
Процесс деления пополам может продолжаться почти бесконечно из-за способа кодирования чисел с плавающей запятой в компьютерной системе.
Пункт 4 -> 0,5
Пункт 1 -> 0,75
Пункт 2 -> 1.0
Пункт 3 -> 2.0
(Переместите элемент 1 сразу после элемента 4)
Я бы сделал последовательное число с триггером в таблице, который «освобождает место» для приоритета, если он уже существует.
У меня тоже была эта проблема.У меня был сильный цейтнот (не правда ли, у всех нас), и я выбрал вариант №1 и обновлял только те строки, которые изменились.
Если вы замените позицию 1 на позицию 10, просто выполните два обновления, чтобы обновить номера заказа позиции 1 и позиции 10.Я знаю, что это алгоритмически просто, и это худший случай O(n), но худший случай — это полная перестановка списка.Как часто это будет происходить?Это вам отвечать.
У меня была та же проблема, и я, вероятно, потратил как минимум неделю на размышления о правильном моделировании данных, но думаю, что наконец-то понял.Используя тип данных массива в PostgreSQL, вы можете хранить первичный ключ каждого заказанного элемента и соответствующим образом обновлять этот массив, используя вставки или удаления при изменении вашего заказа.Ссылка на одну строку позволит вам сопоставить все ваши объекты на основе порядка в столбце массива.
Это все еще немного нестабильное решение, но, вероятно, оно будет работать лучше, чем вариант №1, поскольку вариант 1 требует обновления порядкового номера всех остальных строк при упорядочивании изменений.
Схема №1 и Схема №3 имеют одинаковую сложность во всех операциях, кроме INSERT пишет.На схеме №1 записано O(n) INSERT а на схеме №3 записано O(1). INSERT.
Для любой другой операции с базой данных сложность такая же.
Схему №2 даже рассматривать не стоит, поскольку она DELETE требует O(n) чтения и записи.Схема №1 и схема №3 имеют O(1) DELETE как для чтения, так и для записи.
Новый метод
Если ваши элементы имеют отдельный родительский элемент (т.они имеют общую строку внешнего ключа), то вы можете попробовать следующее...
Django предлагает независимое от базы данных решение для хранения списков целых чисел внутри CharField().Одним из недостатков является то, что максимальная длина хранимой строки не может превышать max_length, который зависит от БД.
С точки зрения сложности это дало бы схему № 1 записи O(1) для INSERT, поскольку информация о заказе будет храниться как одно поле в строке родительского элемента.
Еще одним недостатком является то, что JOIN в родительскую строку теперь требуется для обновления порядка.
