sql - SQL 之上的列表实现

Question

我需要在 SQL 数据库之上实现一个列表抽象。此列表抽象需要支持附加、删除和插入操作。

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

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

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 位不是很好的可扩展性。我已经尝试过不同的 key 方案和“之间”实现。但是大多数/全部都存在插入时快速增长的 key 长度的问题。我的直觉告诉我对此有一个最佳策略，但我却找不到解决方案。

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

有什么想法吗？

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;