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

前端之家收集整理的这篇文章主要介绍了将有序列表存储在数据库中(间隙方法)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我想在Google App Engine数据存储区中保留一个大型有序列表(数百万个元素).需要快速插入.

最简单的方法添加表示订单的索引属性(或列)“order_num”.例如,列表[A,B,C]将按如下方式存储:

  1. content order_num
  2. --------------------
  3. A 1
  4. B 2
  5. C 3

但是,这并不能让您快速插入.例如,如果我想在A之后插入X,我必须将B和C重新编号为X的“腾出空间”,即让B变为3,C变为4,X变为2.如果我这将是一场灾难拥有数百万个元素.

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

  1. content order_num
  2. --------------------
  3. A 1000
  4. B 2000
  5. C 3000

当我想在A之后插入X时,我可以简单地添加X,其order_num设置为(1000 2000)/ 2 = 1500,不需要重新编号.

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

谢谢!

UPDATE

这里有更多细节.假设我在数据库中有一个元素列表,每个元素都有一个名为my_num的整数属性. my_num的值是任意正整数.假设我有一个列表[A,C,D],它们的my_num是

  1. element my_num
  2. ---------------------
  3. A 5
  4. B 2
  5. C 10
  6. D 7

现在,让我们定义一个accum()运算符:

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

所以每个元素的累加值都是

  1. element my_num accum
  2. ----------------------------
  3. A 5 5
  4. B 2 7
  5. C 10 17
  6. D 7 24

但是,累积值可能不应存储在数据库中,因为列表会不断更新.保持快速插入更好.

我想设计一个输入是整数x的查询

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

例如,查询(11)是C,查询(3)是A.

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

解决方法

或者,您可以使用小数或字符串吗?
  1. content order
  2. --------------------
  3. A 'a'
  4. B 'b'
  5. 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”

  1. content order
  2. --------------------
  3. A '1011'
  4. new! '10111'
  5. B '1100'
  6. C '1101'

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

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

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

猜你在找的MsSQL相关文章