时间戳

首页 > 解决方案 > 在 SQL 之上列出实现

sql - 在 SQL 之上列出实现

问题描述

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

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

一种可能的幼稚实现是使用小数作为键。要在两个元素之间插入一个值，我只需计算两个元素的键的平均值，并将其用作插入值的键。大多数数据库对数字都有有限的精度。为了克服这个问题，我们可以将数字转换为字符串并使用各种任意精度库来计算平均值。使用这种方案，密钥在插入前增加 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 位并不是非常可扩展的。我已经尝试了不同的密钥方案和“之间”实现。但是大多数/所有人都存在插入时快速增长的密钥长度的问题。我的直觉告诉我有一个最佳策略，但解决方案却让我望而却步。

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

有任何想法吗？

标签： sqlalgorithmsqlite

解决方案

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

实际上使用类似于列表的数据结构会更容易，即每个条目都有指向下一个和前一个节点的指针。在 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;

推荐阅读