在SQL之上列出实现

Question

我需要在SQL DB之上实现列表抽象。此列表抽象需要支持追加，删除和插入操作。

我的计划是实现一个键值表，其中键包含sort / order-information，value包含列表值。要将元素附加到顶部，我只需要创建一个在前一个顶部之上排序/排序的键。要插入元素，我只需要创建一个键，在插入位置的两个条目之间进行排序/排序。有了这样的方案，我不需要重新平衡表，因为我在中间插入一个元素。

一种可能的天真实现是使用分数来表示密钥。要在两个元素之间插入一个值，我只计算两个元素的键的平均值，并将其用作插入值的键。大多数数据库都具有数字的精确度。为了克服这个问题，我们可以将数字转换为字符串，并使用各种任意精度库来计算平均值。使用此方案，密钥增长1位pr插入。参见下面的示例实现

function between(prev_key:number,next_key:number):number {
  var insert_key = (prev_key + next_key) / 2.0;
  assert(insert_key > prev_key && insert_key < next_key);
  return insert_key;
}

对于插入的每一行，将密钥增加1位数的可扩展性不是很高。我已经尝试了不同的关键方案和“之间”实现。但是大多数/全部都存在插入时快速增长的键长度的问题。我的直觉告诉我有一个最佳的策略，但解决方案是我的想法。

注意我在这个例子中使用数字作为键类型，但是键可以是字符串或任何其他类型，只要我能够正确生成键和顺序。

有任何想法吗？

Answer 1

通过使用单个值来索引值，您将在本质上是一个数组的基础上实现一个列表。

实际使用类似于列表的数据结构将更容易，即，每个条目具有指向下一个和前一个节点的指针。在SQL中，指针是外键。在内存列表中，节点的标识将是其地址，这是随机的，因此在SQL中，您可以简单地使用自动增量PK：

CREATE TABLE List (
    ID   INTEGER PRIMARY KEY,
    Prev INTEGER REFERENCES List,
    Next INTEGER REFERENCES List,
    Value
);

要插入或删除，您必须调整节点本身及其相邻节点中的Prev / Next值。

要遍历列表，您必须遵循Next指针，这需要递归CTE：

WITH RECURSIVE iteration AS (
  SELECT Value, Next
  FROM List
  WHERE ID = 0    -- or Prev IS NULL, or however you identify the first entry

  UNION ALL

  SELECT Value, Next
  FROM List
  JOIN iteration ON List.ID = iteration.Next
)
SELECT Value FROM iteration;

Answer 2

经过一夜的睡眠后，我想我找到了一种方法来为初始帖子中提到的算法问题生成有效的密钥。

诀窍是在需要扩展插入时的密钥长度时保留一系列值。因此，我们不是像平均时那样添加一个数字，而是“保留”N个数字。在这个保留范围内，对于每个插入键，我们可以将其计数为1，其中键大于之前的值。这使得O（log n）密钥长度在保留范围内。如果我们需要下降，我们将没有空间，需要再次扩展。但第二个技巧是扭转每次扩展的保留范围。因此，在下一个保留范围内，我们从顶部开始计数。

初步测试表明，这种结构为随机插入和列表和头部中相同位置的多个插入生成非常紧凑的键。但是，如果你用恰当的插入模式“攻击”这个结构，我认为可以使密钥大小增加。所以递归CTE可能是更安全的方法。

如果需要，我可以稍后详细说明