Как индексировать элементы для частого изменения очереди?

Question

[Заур Ашурбеков]

Здравствуй, Тостер!
Короче говоря, есть упорядоченный список элементов, и у каждого элемента свой порядковый номер для сортировки. Теперь, в этот список, где-нибудь в середину нужно вставить новый элемент, и у всех идущих за ним элементов увеличить порядковый номер на i+1. Похожая операция и при удалении элемента. Всё бы ничего, но таких элементов может быть сотни, а то и тысяча и операция по изменению индекса сюда никак не подходит.

Потом подумал, а что если сортировать не числами, а лексикографически или дробью. Т.е. что бы вставить в между первым и вторым элементом можно будет просто вставить индекс 2.5 и т.д.

Что меня смущает, а вдруг есть ещё более правильные подходы? Задача то типовая, но толковых решений не нашёл.

Answer 1

[Андрей Сидоров]

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

upate table_name set position = position + 1 where position >= 5

При такой схеме при удалении элемента ничего с остальными элементами делать не нужно.

Решение оставлять "зазор между индексами" в 10-100-1000 и т.д., или делать индексы дробными совершенно не приемлимо. Оно не надёжно в долгосрочной перспективе.

И да, если говорить о типовых задачах, то эта задача типовая.
Есть хорошим гем acts_as_list, который делает как раз нужное. Использует он способ, который я описал ваше.

Comments

[Заур Ашурбеков]

то что нужно. Спасибо))

[Заур Ашурбеков]

если Вы его использовали, то как с нагрузками на сервер при операциях сдвига? Он не отправит сервер в думки на пару минут если там придётся тысячи элементов сдвигать?

[Андрей Сидоров]

Заур Ашурбеков при сдвиге помимо изменения позиции самого элемента, он делает лишь один запрос, пример которого я написал выше. как именно он отработает на ваших данных, лучше смотреть на продакшен базе через explain analyze. в большинстве случаев сервер не заметит этого, если у вас не слишком большая таблица

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

Answer 2

[freeExec]

В давние в давние времена, когда команды в BASIC нужно было нумеровать, нумеровали их через 10, чтобы можно было вставить без проблем и не заниматься увеличением i+1. Так и вам стоит тогда делать не дробные числа, а через сотню. А когда где-то расстояния будет уже на исходе делать сново ребаланс.

Comments

[Заур Ашурбеков]

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