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

Если нету - оцените, как часто будут добавляться сегменты.
Если редко - то тоже есть лучшее решение.
Храните порядок в real, равномерно от 1 до N + 1

Вставлять лучше по много сразу.
Если надо вставить одну, то даете ей OrderSK дробный, 0.5 - в начало, N+0.5 - в конец, K+0.5 - в середину

Если надо вставить M записей после K, то равномерно распределяете дробные значения:
new_order(M, K) = (K+1)/(М+1) + K

и после вставки сразу же переупорядочивать:

Забыл сказать, почему это лучше, - это резко упрощает логику.

1. Например интервал в 100 целых можно поделить надвое только 6 раз.
2. Есть ограничение в 99 вставок за раз, хотя и неактуально, но всеже - придется о нем помнить.
3. Получаете порядковый номер "бесплатно". В случае запасного интервала порядок будет стоить дополнительного запроса.

Есть все же ограничение, следует помнить о нем.
если у вас уже есть примерно 10 миллионов сегментов, то можно вставить за раз еще только 10 миллионов сегментов, не больше - мантисса не позволит :)
Если это для вас плохое ограничение, то используйте double :)

mcureenab gpХраните порядок в real, равномерно от 1 до N + 1


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


В зависимости от конкретной БД можно придумать более экзотические варианты, например на базе пользовательских типов. Но почти наверняка экзотика будет во всём проигрывать дедовским методам.

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

Вам всеравно придется переупорядочивать, только это "иногда" будет стоить дополнительного гимороя, и усложнения логики. Лучше переупорядочивать всегда после вставки.

Вообще я и сам знаю, что целочисленный метод легче понять. Не знаете как с плавающими работать, работайте с целыми. По сути, это не меняет алгоритма, просто за норму (единицу) принимается 2^(битность целого/2), и нумеровать при вставке можно без дробей, через один.
берется 16 битное целое, шаг - 256. Максимальное хранение - 254 сегмента, вставка - до 254 за раз.
Или берется 32 битное целое. Хранилище - 65534, вставка - максимум по 65634 элемента.
По моему - достаточно, и не дорого.


Алгоритм 2.
Бинарная вставка. Вставлять можно только по 1 записи.

Выбираете шаг 2^P. Это изначальный шаг, или - после переупорядочивания.
В таблице дорог храните счетчик вставок до упорядочивания.
Пред вставкой проверяете счетчик, если он достиг P-1, то восстанавливаете интервалы.
Вставляете по 1 строчке, деля интервал пополам, увеличиваете счетчик для дороги.

Экономия на перетряхиваниях индекса - в P-1 раз.
Тоесть если выбрать шаг 65536, то гарантированно вставить без переупорядочивания можно 15 раз.

Сори - не так.
Счетчика не надо,
Просто оценивается интервал при вставке, если он мал, то предпринимается переупорядочивание.

В общем, мы уже говорим об одном и том же давно.

про "может статься" и регламентные работы вы загнули, надо сказать.

Кстати, если использовать 32 битное целое (у вас - 38байт), то вероятность переупорядочивания = 1/15 в самом худшем случае (вставка в одно и то же место), а при равномерных вставках, и длине существующей коллекции 100 сегментов - меньше тысячной.

Алгоритм с локальным анализом прилежащей области существует, и даже не нужно рекурсии. Нужно просто выбрать целочисленный "коофициент улучшения" Q > 2, и найти такой отрезок, который позволяет все элменты в этом отрезке расположить на расстоянии не меньше Q друг от друга. Это делается в один запрос и один апдейт.

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