将有序列表存储在数据库中(间隙方法)

Question

我想在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,不需要重新编号.

但随着这些差距变小,可能需要重新编号.我的问题是,是否有任何已知的重新编号策略？并决定差距的大小？

谢谢!

UPDATE

这里有更多细节.假设我在数据库中有一个元素列表,每个元素都有一个名为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.

是否可以设计数据存储架构以使此查询更快？或者唯一的方法是在查询时逐个累积它,我打算做什么？

Answer 1

或者,您可以使用小数或字符串吗？

content     order
-------------------- 
   A         'a' 
   B         'b' 
   C         'c'

然后在a和b之间插入D,给它值"aa"

最好为二进制字符串显示生成字符串的算法:如果要在"1011"和"1100"之间插入内容,请执行以下操作:

• Avalue = 1 + 0*(1/2)+ 1*(1/4)+ 1*(1/8)
• Bvalue = 1 + 1*(1/2)+ 0*(1/4)+ 0*(1/8)

平均值,新值= 1 + 0*(1/2)+ 1*(1/4)+ 1*(1/8)+ 1*(1/16)new string ="10111"

content     order
-------------------- 
   A         '1011' 
   new!      '10111' 
   B         '1100' 
   C         '1101'

因为你总是平均2个值,所以平均值总是有限二进制开发和有限字符串.它有效地定义了二叉树.

如你所知,二进制树并不总是很平衡,换句话说,一些字符串在插入足够多后会比其他字符串长得多.为了简短起见,你可以使用任何偶数基数 - 它必须是偶数因为那时两个值的任何平均值的发展都是有限的.

但无论你做什么,字符串可能会变长,你必须在某些时候做一些内务处理,清理值,以便有效地使用字符串空间.这个算法给你的是确定在清理之间,系统将继续滴答作响.