Как хранить упорядоченный список в базе данных

15 февраля 2015

Время от времени мне прилетают в почту занятные вопросы. Последний про хранение упорядоченного списка в базе данных.

Имеется возможность загрузки фото в альбомы. Нужно реализовать возможность упорядочивать фото в пределах альбома. Автор уже хранит порядок в поле order, но его напрягает, что при перетаскивании какой-либо из картинок нужно обновлять order у фотографий всего альбома.

Для начала, стоит оценить частоту изменений порядка фото. Если операция не очень частая и выполняется, например, только админом раз в день и в альбомах не очень много фото, можно смело хранить order как integer и обновлять, как автор и делает.

Если же операция достаточно частая, можно схитрить и хранить order как decimal. В этом случае при вставке или перемещении фото между двумя другими необходимо обновить только order непосредственно перемещаемой записи.

Если мы перемещаем фото C и засовываем его между фото A и фото B, то значение order для него вычисляется как

C.order = A.order + (B.order - A.order) / 2;

UPD: из за ограничений точности следует проверять, влезет ли в базу очередное значение. Если нет — пересчитывать order. Даже несмотря на то, что от пересчётов мы не избавились, их частота сократилась для худшего случая на порядок.

Комментарии RSS по email OK

№9625

MT 15 февр. 2015 г., 18:43:23

Как вариант, в случае использования целых весов элементов можно воспользоваться школьным BASIC’овским трюком — вес элементов инкрементировать десятками: 10, 20, 30 и т. д.

Тогда пересчёт весов других элементов будет требоваться нечасто (только если «места» между конкретными двумя элементами не осталось), и даже если потребуется — то не обязательно всех.
№9626

oWeRQ 15 февр. 2015 г., 19:56:17

Стоит учитывать, что если order = id и между элементами нет пробелов, B.order - A.order == 1, а 1 очень плохо несколько раз делится пополам, даже decimal(n, 6) быстро закончится, чтобы потом не возиться с дробями можно использовать integer order = id * 1024(хватит на 10 перемещений "во внутрь"), временами пресчитывать order.
№9627

Sam 15 февр. 2015 г., 20:10:47

oWeRQ, хорошо подмечено. В decimal влезает, в случае того же MySQL, 13 знаков после запятой. То есть хватит на 13 делений.

MT, это усложнит алгоритм, хотя и с decimal мы тоже рано или поздно упрёмся.
№9628

Etki 15 февр. 2015 г., 20:44:27

экономия на спичках
№9629

Sam 15 февр. 2015 г., 21:26:28

Etki, в случаях когда операций изменения порядка мало — однозначно.
№9631

Максим 16 февр. 2015 г., 15:41:35

Есть еще вариант организовать нечто вроде упорядоченного списка, то есть добавить поля nextEl и prevEl которые хранят id следующего и предыдущего элементов. Правда с выборкой из бд придется немного схитрить. С другой стороны нам обычно надо либо выбрать все элементы, либо один. Так что это не критично.
№9632

wartur 18 февр. 2015 г., 14:24:29

Sam, Вот написал че для Yii1 yii-sorter.wartur.ru/

Это примерно то что ты написал =).

Кстати там много разных методов вставки у меня получилось. Прочитай про алгоритм работы. github.com/wartur/yii-sorter/blob/master/ALGORITHM.ru.md
№9636

Olexander 20 февр. 2015 г., 23:05:13
Делаю сортировку 1 запросом:
```
UPDATE `table_name` SET `order` =
  CASE
    WHEN `order` = 6 THEN 3
    ELSE `order` + 1
  END
WHERE `order` BETWEEN 3 AND 6;
```
Переместить элемент с весом 6 на место элемента с весом 3. Изначально при вставке (INSERT) полю order присваиваем insert_id() чтобы оно было уникальным.