<rmcreative>

RSS

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

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

  1. №9625
    MT
    MT 15.02.2015, 18:43:23

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

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

  2. №9626
    oWeRQ
    oWeRQ 15.02.2015, 19:56:17

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

  3. №9627
    Sam
    Sam 15.02.2015, 20:10:47

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

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

  4. №9628
    Etki
    Etki 15.02.2015, 20:44:27

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

  5. №9629
    Sam
    Sam 15.02.2015, 21:26:28

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

  6. №9631
    Максим
    Максим 16.02.2015, 15:41:35

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

  7. №9632
    wartur
    wartur 18.02.2015, 14:24:29

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

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

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

  8. №9636
    Olexander
    Olexander 20.02.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() чтобы оно было уникальным.

  1. Почта опубликована не будет.

  2. Можно использовать синтаксис Markdown или HTML.

  3. Введите ответ в поле. Щёлкните, чтобы получить другую задачу.