将订购清单存储在数据库中（间隙方法）

| 我想在Google App Engine数据存储区中保留一个大的有序列表（数百万个元素）。需要快速插入。 最简单的方法是添加一个表示订单的索引属性（或列）\“ order_num \”。例如，列表[A，B，C]将像这样存储：

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

但是，这不能让您快速插入。例如，如果我想在A后面插入X，则必须将B和C重编号为X的“腾出空间”，即，让B变成3，C变成4，X变成2。这将是一场灾难如果我有数百万个元素。 我找到了一种可行的解决方案，称为“缺口方法”，此处介绍。这种方法在相邻元素之间保持间隔。像这样：

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

当我想在A后面插入X时，我可以简单地将X的order_num设置为（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)

例如，query（11）是C，query（3）是A。 是否可以设计一个数据存储架构以使此查询快速进行？还是唯一的方法是我计划在查询时一个一个地累积它？