关于数据结构：SQL中的链表

Linked List in SQL

什么是将链接列表存储在mysql数据库中的最佳方法，以使插入变得简单(即您不必每次都重新索引一堆东西)并且可以轻松地按顺序取出列表。

创建一个具有两个自引用列PreviousID和NextID的表。如果该项是列表中的第一件事，则PreviousID为null，如果为最后一项，则NextID为null。 SQL将如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13

CREATE TABLE tblDummy
{
PKColumn INT NOT NULL,
PreviousID INT NULL,
DataColumn1 VARCHAR(50) NOT NULL,
DataColumn2 VARCHAR(50) NOT NULL,
DataColumn3 VARCHAR(50) NOT NULL,
DataColumn4 VARCHAR(50) NOT NULL,
DataColumn5 VARCHAR(50) NOT NULL,
DataColumn6 VARCHAR(50) NOT NULL,
DataColumn7 VARCHAR(50) NOT NULL,
NextID INT NULL
}

使用Adrian的解决方案，而不是增加1，而不是增加10，甚至是100。然后，可以按插入之间的差值的一半来计算插入，而不必更新插入下面的所有内容。选择一个足够大的数字来处理您的平均插入次数-如果该数字太小，那么您将不得不后退以在插入过程中以较高的位置更新所有行。

在表中存储一个称为" position"的整数列。为列表中的第一项记录0，为第二项记录1，以此类推。对数据库中的该列进行索引，然后在要提取值时按该列排序。

1
2
3

ALTER TABLE linked_list ADD COLUMN POSITION INTEGER NOT NULL DEFAULT 0;
ALTER TABLE linked_list ADD INDEX position_index (POSITION);
SELECT * FROM linked_list ORDER BY POSITION;

要在索引3处插入值，请修改第3行及以上行的位置，然后插入：

1 2	UPDATE linked_list SET POSITION = POSITION + 1 WHERE POSITION >= 3; INSERT INTO linked_list (my_value, POSITION) VALUES ("new value", 3);

最简单的选择是创建一个表，其中每个列表项有一行，项目位置的列，以及该项目中其他数据的列。然后，您可以在位置列上使用ORDER BY以所需的顺序进行检索。

1
2
3
4
5
6

CREATE TABLE linked_list
( list_id INTEGER NOT NULL
, POSITION INTEGER NOT NULL
, DATA VARCHAR(100) NOT NULL
);
ALTER TABLE linked_list ADD PRIMARY KEY ( list_id, POSITION );

要操作列表，只需更新位置，然后根据需要插入/删除记录。因此，要在索引1的列表1中插入项目：

1
2
3
4
5
6
7
8

BEGIN TRANSACTION;

UPDATE linked_list SET POSITION = POSITION + 1 WHERE POSITION >= 3 AND list_id = 1;

INSERT INTO linked_list (list_id, POSITION, DATA)
VALUES (1, 3,"some data");

commit;

由于列表上的操作可能需要多个命令(例如，插入操作将需要INSERT和UPDATE)，因此请确保始终在事务中执行命令。

此简单选项的一种变体是使每个项目的位置增加一定的比例，例如100，这样，在执行INSERT时，不必总是对以下元素的位置重新编号。但是，这需要花费更多的精力才能确定何时增加以下元素，因此，如果您要插入很多插入元素，则会失去简单性，但会获得性能。

根据您的要求，其他选项可能很有吸引力，例如：

如果要在列表上执行很多操作，而又没有很多检索操作，则最好使用一个ID列指向列表中的下一个项目，而不要使用position列。然后，您需要在列表的检索中使用迭代逻辑，以便按顺序获取项目。这可以在存储的过程中相对容易地实现。
如果您有很多列表，则可以使用一种快速的方法来将列表序列化和反序列化为文本/二进制，并且只想存储和检索整个列表，然后将整个列表作为单个值存储在单个列中。虽然可能不是您要的。

可以使用表中的递归指针来存储链表。这与Sql中存储的层次结构几乎相同，并且使用的是递归关联模式。

您可以在此处了解更多信息(Wayback Machine链接)。

我希望这有帮助。

这是我本人一段时间以来一直在尝试解决的问题。到目前为止，我发现的最好方法是使用以下格式(这是伪代码)为链接列表创建一个表：

链表(

密钥1，
信息，
键2

)

key1是起点。 Key2是在下一列中与其自身链接的外键。所以您的专栏将链接类似这样的链接

col1

key1 = 0，
信息="你好"
key2 = 1

Key1是col1的主键。 key2是指向col2的key1的外键

col2

key1 = 1
信息="废话"
key2 =空

col2中的key2设置为null，因为它没有指向任何东西

首次在表格中输入一列时，您需要确保将key2设置为null，否则会出现错误。输入第二列后，您可以返回并将第一列的key2设置为第二列的主键。

这是一次输入多个条目，然后返回并相应地设置外键的最佳方法(或构建一个可以为您完成此操作的GUI)

这是我准备的一些实际代码(所有实际代码都在MSSQL上运行。您可能需要对所使用的SQL版本进行一些研究！)：

createtable.sql

1
2
3
4
5
6
7
8
9

CREATE TABLE linkedlist00 (

key1 INT PRIMARY KEY NOT NULL IDENTITY(1,1),

info VARCHAR(10),

key2 INT

)

register_foreign_key.sql

1
2
3

ALTER TABLE dbo.linkedlist00

ADD FOREIGN KEY (key2) REFERENCES dbo.linkedlist00(key1)

*我将它们放入两个单独的文件中，因为必须分两步完成。 MSSQL不允许您一步一步地完成操作，因为该表尚不存在以供外键引用。

链接列表在一对多关系中特别强大。因此，如果您曾经想制作一个外键数组？好吧，这是一种方法！您可以使主表指向链接列表表中的第一列，然后可以使用外键指向所需的信息表，而不是" information"字段。

例：

假设您有一个保留表格的官僚机构。

假设他们有一个称为文件柜的表

文件柜(

内阁编号(pk)
文件ID(fk)
)

每列都包含一个用于橱柜的主键和一个用于文件的外键。这些文件可能是税表，健康保险文件，实地考察许可单等

文件(

文件ID(pk)
档案编号(fk)
下一个文件ID(fk)

)

这用作文件的容器

文件(

档案编号(pk)
文件信息

)

这是特定的文件

可能有更好的方法，具体取决于您的特定需求。该示例仅说明了可能的用法。

https://dba.stackexchange.com/questions/46238/linked-list-in-sql-and-trees建议使用浮点位置列进行快速插入和排序的技巧。

它还提到了专用的SQL Server 2014层次结构功能。

该帖子很旧，但仍然会给我.02 $。更新表或记录集中的每个记录听起来很疯狂，无法解决排序问题。索引的数量也很疯狂，但是听起来大多数人都接受了它。

我想出的减少更新和建立索引的疯狂解决方案是创建两个表(在大多数情况下，无论如何，您都不会对所有记录进行排序)。表A用于保存要排序的列表的记录，表B用于将订单的记录分组并保存为字符串。 order字符串表示一个数组，可用于对Web应用程序的Web服务器或浏览器层上的选定记录进行排序。

1
2
3
4
5
6
7
8
9
10
11

CREATE TABLE A{
Id INT PRIMARY KEY IDENTITY(1,1),
DATA VARCHAR(10) NOT NULL
B_Id INT
}

CREATE TABLE B{
Id INT PRIMARY KEY IDENTITY(1,1),
GroupName varchat(10) NOT NULL,
ORDER VARCHAR(MAX) NULL
}

订单字符串的格式应为id，位置和分隔符，以split()分隔字符串。对于jQuery UI，.sortable('serialize')函数为您输出一个POST友好的订单字符串，其中包括列表中每个记录的ID和位置。

真正的魔咒是您选择使用保存的排序字符串对选定列表进行重新排序的方式。这将取决于您正在构建的应用程序。这是jQuery的一个示例，用于重新排序项目列表：http://ovisdevelopment.com/oramincite/?p=155

我可以想到几种方法，每种方法具有不同的复杂性和灵活性。我假设您的目标是保留检索顺序，而不是要求将其存储为实际的链接列表。

最简单的方法是为表中的每个记录分配序数值(例如1、2、3，...)。然后，当您检索记录时，在序号列上指定一个排序依据以使它们恢复顺序。

这种方法还允许您检索记录而无需考虑列表中的成员资格，但是只允许一个列表中的成员资格，并且可能需要附加的"列表ID"列以指示记录属于哪个列表。

一种稍微复杂但又更灵活的方法是将有关成员资格的信息存储在一个或多个列表中的单独表中。该表将需要3列：列表ID，序数值和指向数据记录的外键指针。在这种方法下，基础数据对其列表中的成员身份一无所知，并且可以轻松地将其包含在多个列表中。

将SERIAL"索引"增加100，但是手动添加"索引"等于Prev + Next / 2的中间值。如果您使100行饱和，请将索引重新排序为100s。

这应该与主索引保持顺序。

我认为添加创建的Datetime类型的列和int的位置列要简单得多，因此现在您可以拥有重复的位置，在select语句中使用order by位置，创建的desc选项，您的列表将是按顺序获取。

可以通过使列包含偏移量(列表索引位置)来存储列表-中间插入一个，然后在新的父对象上方递增所有内容，然后进行插入。