My<cod/>.net
Представление порядка в реляционной базе данных
У меня есть коллекция объектов в базе данных. Картинки в фотогалерее, товар в каталоге, главы в книге и т. д. Каждый объект представлен в виде строки. Я хочу иметь возможность произвольно упорядочивать эти изображения, сохраняя этот порядок в базе данных, чтобы при отображении объектов они были в правильном порядке.
Например, предположим, что я пишу книгу,и каждая глава-это объект. Я пишу свою книгу и размещаю главы в следующем порядке:
Введение, доступность, форма и Функция, Ошибки, Последовательность, Заключение, Индекс
Он отправляется в Редактор и возвращается со следующим предложенным порядком:
Введение, Форма, Функция, Доступность, Последовательность, Ошибки, Заключение, Индекс
Как я могу хранить этот заказ в базе данных надежным и эффективным способом?
У меня были следующие идеи, но я не в восторге от них:
Массив. Каждая строка имеет порядок ID, когда порядок изменяется (через удаление с последующей вставкой), порядок IDs обновляются. Это упрощает поиск, так как это просто
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. Конечно, это должно было бы быть перебалансировано время от времени, поэтому у вас нет вещей слишком близко друг к другу (даже с поплавками, вы в конечном итоге столкнетесь с ошибками округления).
Ни один из них не кажется мне особенно элегантным. У кого-нибудь есть лучший способ сделать это?
Acts_as_list mixin в Rails обрабатывает это в основном так, как вы описали в #1., он ищет столбец INTEGER с именем position (из которого вы можете переопределить имя, конечно) и использует его для выполнения заказа. Когда вы хотите изменить порядок вещей, вы обновляете позиции. Он прекрасно служил мне каждый раз, когда я его использовал.
В качестве дополнительной заметки вы можете удалить необходимость всегда делать перестановку на вставках/удалениях, используя разреженную нумерацию - вроде того, как это было раньше... вы можете количество позиций 10, 20, 30 и т. д. и если вам нужно вставить что-то между 10 и 20, вы просто вставляете его с позиции 15. Точно так же при удалении вы можете просто удалить строку и оставить пробел. Вам нужно только сделать повторную нумерацию, когда вы фактически меняете порядок или если вы пытаетесь сделать вставку и нет подходящего зазора для вставки.
Конечно, в зависимости от вашей конкретной ситуации (например, независимо от того, есть ли у вас другие строки, уже загруженные в память, или нет), возможно, имеет смысл использовать подход gap.
Если объекты не сильно привязаны к другим таблицам, а списки короткие, проще всего удалить все в домене и просто повторно вставить правильный список. Но это не практично, если списки большие, и у вас есть много ограничений, чтобы замедлить удаление. Я думаю, что ваш первый метод действительно самый чистый. Если вы запускаете его в транзакции, вы можете быть уверены, что ничего странного не произойдет, пока вы находитесь в середине обновления, чтобы испортить заказ.
Я сделал это в своем последнем проекте, но это было для стола, который только иногда нужно было специально заказывать, и он не был доступен слишком часто. Я думаю, что разнесенный массив был бы лучшим вариантом, потому что его переупорядочивание было бы самым дешевым в среднем случае, просто включающим изменение одного значения и запрос на два).
Кроме того, я бы предположил, что 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) худший случай, но этот худший случай-когда у вас есть полная перестановка списка. Как часто это будет происходить? Это вам предстоит ответить.
Поскольку я в основном сталкивался с этим с Django, я нашел это решение наиболее работоспособным. Похоже, что в реляционной базе данных нет никакого "right way", чтобы сделать это.
У меня была такая же проблема, и, вероятно, я потратил по крайней мере неделю на себя о правильном моделировании данных, но я думаю, что наконец-то получил его. Используя тип данных массива в 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, что зависит от DB.
С точки зрения сложности это дало бы Scheme #1 O (1) пишет для INSERT , потому что информация о порядке будет храниться как одно поле в строке родительского элемента.
Другим недостатком является то, что для обновления порядка теперь требуется JOIN для родительской строки.