最简单的方法是添加表示订单的索引属性(或列)“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,不需要重新编号.
但随着这些差距变小,可能需要重新编号.我的问题是,有没有任何已知的重编号策略？并决定差距的大小？
谢谢！
UPDATE
这里有更多细节.假设我在数据库中有一个元素列表,每个元素都有一个名为my_num的整数属性. my_num的值是任意正整数.假设我有一个列表[A,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)
解决方法
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个值,所以平均值总是有一个有限的二进制开发和一个有限的字符串.它有效地定义了二叉树.
如你所知,二进制树并不总是很平衡,换句话说,一些字符串在插入足够多后会比其他字符串长得多.为了简短起见,你可以使用任何偶数基数 – 它必须是偶数,因为那时两个值的平均值的发展是有限的.
但无论你做什么,字符串可能会变长,你必须在某些时候做一些内务处理,清理值,以便有效地使用字符串空间.这个算法给你的是确定在清理之间,系统将继续滴答作响.
