database - 维护 "ordering string"以排序数据库元素的算法

Question

我有一个数据库，我想在其中存储特定元素的任意排序。有问题的数据库不支持订单集，所以我必须自己做。

一种方法是为元素的位置存储一个浮点值，然后在插入新元素时取周围元素位置的平均值:

Item A - Position 1
Item B - Position 1.5  (just inserted).
Item C - Position 2

现在，由于各种原因我不想使用 float ，我想改用字符串。例如:

Item A - Position a
Item B - Position aa  (just inserted).
Item C - Position b

我希望这些字符串尽可能短，因为它们永远不会被“整理”。

谁能建议一种尽可能高效和紧凑地生成此类字符串的算法？

谢谢，

蒂姆

Answer 1

将“am”或“an”位置分配给项目 B 并使用二进制除法步骤进行另一个插入是合理的。 这类似于 26-al 数字系统，其中 'a'..'z' 符号对应于 0..25。

a b   //0 1
a an b  //insert after a  - middle letter of alphabet  
a an au b  //insert after an
a an ar au b  //insert after an again (middle of an, au)
a an ap ar au b   //insert after an again
a an ao ap ar au b //insert after an again
a an ann ao...  //insert after an, there are no more place after an, have to use 3--symbol label
....
a an anb...  //to insert after an, we treat it as ana
a an anan anb  // it looks like 0 0.5 0.505 0.51  

二叉树结构的伪代码:

function InsertAndGetStringKey(Root, Element): string
  if Root = nil then
    return Middle('a', 'z') //'n'

  if Element > Root then
    if Root.Right = nil then
      return Middle(Root.StringKey, 'z') 
    else
       return InsertAndGetStringKey(Root.Right, Element)   

  if Element < Root then
    if Root.Left = nil then
      return Middle(Root.StringKey, 'a') 
    else
       return InsertAndGetStringKey(Root.Left, Element) 

Middle(x, y): 
  //equalize length of strings like (an, anf)-> (ana, anf)
  L = Length(x) - Length(y)
  if L < 0 then
    x = x + StringOf('a', -L) //x + 'aaaaa...' L times
  else if L > 0 then
    y = y + StringOf('a', L)  

  if LL = LastSymbol(x) - LastSymbol(y)  = +-1 then
    return(Min(x, y) + 'n')  // (anf, ang) - > anfn
  else
    return(Min(x, y) + (LastSymbol(x) + LastSymbol(y))/2) // (nf, ni)-> ng