Представление упорядочивания в реляционной базе данных

Миксин plays_as_list в Rails обрабатывает это в основном так, как вы описали в # 1. Он ищет столбец INTEGER с именем position (который вы, конечно, можете переопределить) и использует его для выполнения ORDER BY. Когда вы хотите переупорядочить вещи, вы обновляете позиции. Он отлично служил мне каждый раз, когда я его использовал.

В качестве побочного примечания, вы можете избавиться от необходимости постоянно менять положение при INSERTS / DELETES, используя разреженную нумерацию - вроде как в прежние времена ... вы можете пронумеровать свои позиции 10, 20, 30 и т. д. и если вам нужно вставить что-то между 10 и 20, вы просто вставляете его с позицией 15. Аналогичным образом при удалении вы можете просто удалить строку и оставить пробел. Перенумеровать нужно только тогда, когда вы действительно меняете порядок или если вы пытаетесь сделать вставку, и нет подходящего промежутка для вставки.

Конечно, в зависимости от вашей конкретной ситуации (например, есть ли у вас другие строки, уже загруженные в память или нет), может иметь смысл или не иметь смысла использовать подход пробелов.

Я бы сделал последовательный номер с триггером на таблице, который «освобождает место» для приоритета, если он уже существует.

Если объекты не сильно привязаны к другим таблицам, а списки короткие, проще всего удалить все в домене и просто повторно вставить правильный список. Но это непрактично, если списки большие и у вас есть много ограничений, чтобы замедлить удаление. Я думаю, что ваш первый метод действительно самый чистый. Если вы запустите его в транзакции, вы можете быть уверены, что ничего странного не произойдет, пока вы находитесь в середине обновления, чтобы испортить заказ.

Я сделал это в своем последнем проекте, но это было сделано для таблицы, которую нужно было заказывать только изредка, и к которой не обращались слишком часто. Я думаю, что интервальный массив был бы лучшим вариантом, потому что его переупорядочение было бы самым дешевым в среднем случае, просто включая изменение одного значения и запрос на два).

Кроме того, я предполагаю, что ORDER BY будет в значительной степени оптимизирован поставщиками баз данных, поэтому использование этой функции будет выгодно для производительности по сравнению с реализацией связанного списка.

Другой альтернативой было бы (если ваша СУБД это поддерживает) использование столбцов типа array. Хотя это нарушает правила нормализации, это может быть полезно в подобных ситуациях. Одна из известных мне баз данных с массивами - это PostgreSQL.

Просто подумайте о вариант №1 против №3: разве опция разнесенного массива (# 3) не только откладывает проблему с обычным массивом (# 1)? Какой бы алгоритм вы ни выбрали, либо он сломан, и вы столкнетесь с проблемами с № 3 позже, либо он работает, а затем № 1 должен работать так же хорошо.

Используйте число с плавающей запятой для представления позиции каждого элемента:

Пункт 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, я обнаружил, что это решение является наиболее работоспособным. Кажется, что в реляционной базе данных нет «правильного способа» сделать это.

У меня была такая же проблема, и я, вероятно, потратил как минимум неделю на то, чтобы правильно моделировать данные, но я думаю, что наконец-то понял. Используя тип данных array в 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 для родительской строки.

https://docs.djangoproject.com/en/dev/ref/validators/#django.core.validators.validate_comma_separated_integer_list