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

Я хочу сохранить большой упорядоченный список (миллионы элементов) в хранилище данных Google App Engine. Требуется быстрая вставка.

Самый простой способ - добавить индексированное свойство (или столбец) «order_num», представляющее порядок. Например, список [A, B, C] будет храниться следующим образом:

content   order_num
--------------------
   A         1
   B         2
   C         3  

Однако это не ' t дает вам быструю вставку. Например, если я хочу вставить X после A, мне нужно изменить нумерацию B и C, чтобы «освободить место» для X, т. Е. Пусть B станет 3, C станет 4, а X станет 2. Это будет катастрофой, если я имеют миллионы элементов.

Я нашел возможное решение, называемое «подходом с разрывом», описанное здесь . Такой подход сохраняет разрыв между соседними элементами. Примерно так:

content   order_num
--------------------
   A         1000
   B         2000
   C         3000

Когда я хочу вставить X после A, я могу просто добавить X с его порядковым номером, установленным на (1000 + 2000) / 2 = 1500, перенумерация не требуется.

Но с уменьшением этих промежутков, перенумерация может потребоваться. У меня вопрос, есть ли известная стратегия перенумерации? Как определить размер промежутков?

Спасибо!

ОБНОВЛЕНИЕ

Вот подробности. Скажем, у меня есть список элементов в базе данных, и каждый элемент имеет целочисленное свойство с именем my_num. Значение my_num - произвольное положительное целое число. Предположим, у меня есть список [A, B, C, D], и их my_num равны

 element    my_num   
---------------------
   A          5        
   B          2
   C         10
   D          7

. Теперь давайте определим оператор Accum ():

accum(n) = element[0].my_num + element[1].my_num + ... + element[n-1].my_num

Итак, значения аккумуляторов для каждого элемента равны

 element    my_num   accum 
----------------------------
   A          5        5
   B          2        7
   C         10       17
   D          7       24

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

Я хочу разработать запрос, входным значением которого является целое число x:

query(x) = element[i] if accum(i-1) < x <= accum(i)

Например, запрос (11) - это C, а запрос (3) - A.

Возможно ли это разработать схему хранилища данных, чтобы сделать этот запрос быстрым? Или единственный способ - накапливать их по одному во время запроса, что я планирую делать?