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

У меня есть коллекция объектов в базе данных. Изображения в фотогалерее, товары в каталоге, главы в книге и т. Д. Каждый объект представлен в виде строки. Я хочу иметь возможность произвольно упорядочивать эти изображения, сохраняя этот порядок в базе данных, чтобы при отображении объектов они были в правильном порядке.

Например, допустим, я пишу книгу, и каждая глава - это объект. Я пишу свою книгу и располагаю главы в следующем порядке:

Введение, Доступность, Форма против Функции, Ошибки, Согласованность, Заключение, Индекс

Он переходит к редактору и возвращается в следующем порядке:

Введение, форма, функция, доступность, согласованность, ошибки, заключение, индекс

Как я могу сохранить этот порядок в базе данных надежным и эффективным способом?

У меня были следующие идеи, но я не в восторге ни от одной из них:

  1. Массив. Каждая строка имеет идентификатор заказа, при изменении заказа (путем удаления с последующей вставкой) идентификаторы заказа обновляются. Это делает поиск простым, поскольку это просто 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

  2. Связанный список. В каждой строке есть столбец для идентификатора следующей строки в порядке. Обход здесь кажется дорогостоящим, хотя, возможно, есть какой-то способ использовать его, ORDER BYо котором я не думаю.

  3. Разнесенный массив. Установите orderingID (как в # 1), чтобы он был большим, поэтому первый объект равен 100, второй - 200 и т. Д. Затем, когда вставка происходит, вы просто помещаете ее в (objectBefore + objectAfter)/2. Конечно, иногда это необходимо перебалансировать, чтобы у вас не было слишком тесных связей (даже с плавающими точками вы в конечном итоге столкнетесь с ошибками округления).

Ничто из этого не кажется мне особенно элегантным. У кого-нибудь есть лучший способ сделать это?

21.08.2008 23:01:30
11 ОТВЕТОВ

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

В качестве дополнительного примечания, вы можете избавиться от необходимости всегда выполнять повторное позиционирование на ВСТАВКАХ / УДАЛЕНИЯХ, используя разреженную нумерацию - что-то вроде базовой версии в прошлом ... вы можете нумеровать свои позиции 10, 20, 30 и т. Д. и если вам нужно вставить что-то между 10 и 20, вы просто вставляете это с позицией 15. Аналогично, при удалении вы можете просто удалить строку и оставить пробел. Вам нужно выполнять повторную нумерацию только тогда, когда вы действительно меняете порядок или если вы пытаетесь выполнить вставку, и в ней нет подходящего пробела для вставки.

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

4
21.08.2008 23:11:17
+1 за упоминание редкой нумерации. Я использовал драгоценность ранжированной модели для этого в прошлом.
Jared Beck 3.09.2014 22:05:29

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

1
21.08.2008 23:12:30
Это требует O (n) реструктуризации при каждой вставке!
cdleary 6.10.2008 08:18:10

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

2
22.08.2008 01:39:15

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

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

2
22.08.2008 01:58:14

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

7
22.08.2008 05:32:46
Я не понимаю это решение, которое, видимо, является лучшим ответом. Не могли бы вы немного рассказать о том, как использовать массив для каждой строки? Спасибо
Pierre 18.12.2015 16:52:09

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

3
25.08.2008 17:24:13

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

Элемент 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)

2
18.09.2008 00:22:32
Это / не будет / продолжаться бесконечно. Для чисел с плавающей запятой (doubles) значения будут сходиться после 53 раундов, в патологическом случае. Даже если ваша СУБД использует десятичные числа произвольной точности, у вас будет много раздувания структуры данных.
cdleary 6.10.2008 08:16:28
Итак, добавьте непредвиденное обстоятельство, которое реструктурирует со сложностью O (n), когда интервал становится ниже порогового значения. Теперь у вас есть операция O (n), происходящая примерно через каждые 1/10000 операций. Алгоритм деления пополам лучше всего, если вы умеете его использовать.
Chris Conlan 15.12.2018 14:42:47

У меня тоже была эта проблема. Я был под большим давлением времени (не так ли все), и я выбрал вариант № 1, и только обновленные строки изменились.

Если вы поменяете позицию 1 на 10, просто выполните два обновления, чтобы обновить порядковые номера 1 и 10. Я знаю, что это алгоритмически просто, и это O (n) худший случай, но наихудший случай, когда у вас есть полная перестановка списка. Как часто это будет происходить? Это для вас, чтобы ответить.

1
18.09.2008 00:34:31
РЕШЕНИЕ

Поскольку я в основном сталкивался с этим с Django, я нашел это решение наиболее эффективным. Кажется, что нет никакого «правильного» способа сделать это в реляционной базе данных.

1
29.03.2009 14:47:15
Пользовательский интерфейс jQuery скрывает так много, что я не знаю, по какой схеме это следует. Основываясь на том факте, что модель использует IntegerFieldдля упорядочения, она, вероятно, использует обновления O (n) и следует опции OP 1 #.
Chris Conlan 15.12.2018 14:23:59

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

Это все еще немного нестабильное решение, но оно, вероятно, будет работать лучше, чем вариант № 1, поскольку вариант 1 требует обновления порядкового номера всех других строк при изменении порядка.

0
28.01.2016 10:32:16

Схема № 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 для записи (1) INSERT, поскольку информация об упорядочении будет храниться как одно поле в строке родительского элемента.

Другим недостатком является то, что JOINтеперь для родительского ряда требуется обновить порядок.

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

0
15.12.2018 15:04:28