database - 在数据库中存储有序列表(Gap 方法)

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。如果我这样做，这将是一场灾难有数百万个元素。

我找到了一个可行的解决方案，称为“差距方法”，描述了 here .这种方法在相邻元素之间保持间隙。像这样:

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。

是否可以设计一个数据存储架构来加快查询速度？或者唯一的方法是在我打算做的查询时一个一个地累积它？

Answer 1

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

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

然后在a和b之间插入D， 给它赋值'aa'

生成字符串的算法最适合二进制字符串:如果您想在“1011”和“1100”之间插入一些内容，请执行以下操作:

• 值 = 1+0*(1/2)+1*(1/4)+1*(1/8)
• B值= 1+1*(1/2)+0*(1/4)+0*(1/8)

平均值，新值 = 1+0*(1/2)+1*(1/4)+1*(1/8)+1*(1/16) 新字符串 = "10111"

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

因为您总是对 2 个值求平均值，所以平均值将始终具有有限的二进制发展和有限的字符串。它有效地定义了一个二叉树。

如您所知，二叉树并不总是平衡的，换句话说，在插入足够多之后，某些字符串会比其他字符串长得多。为了使它们简短，您可以使用任何偶数基数 - 它必须是偶数，因为这样两个值的任何平均值的发展都是有限的。

但是无论您做什么，字符串都可能会变长，并且您必须在某些时候进行一些内务处理，清理值以便有效地使用字符串空间。该算法为您提供的是确定性，即在两次清理之间，系统将继续运行。