SQL 中的链表

https://stackoverflow.com/questions/65205

09-06-2019
|

题

在 mysql 数据库中存储链接列表以便插入简单的最佳方法是什么（即你不必每次都重新索引一堆东西），这样就可以轻松地按顺序拉出列表。

解决方案

在表中存储一个名为“位置”的整数列。为列表中的第一项记录 0，为第二项记录 1，依此类推。为数据库中的该列建立索引，当您想要提取值时，请按该列排序。

 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 行及以上行的位置，然后插入：

 update linked_list set position = position + 1 where position >= 3;
 insert into linked_list (my_value, position) values ("new value", 3);

其他提示

使用 Adrian 的解决方案，但不是增加 1，而是增加 10 甚至 100。然后，可以根据插入内容之间的差异的一半来计算插入，而无需更新插入下方的所有内容。选择一个足够大的数字来处理平均插入次数 - 如果它太小，那么您将不得不在插入期间更新所有具有更高位置的行。

创建一个包含两个自引用列 PreviousID 和 NextID 的表。如果该项目是列表中的第一个项目，则 PreviousID 将为 null，如果是最后一个项目，则 NextID 将为 null。SQL 看起来像这样：

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
}

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

您可以了解更多相关信息这里.

我希望这有帮助。

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

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 的索引 3 处：

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 列指向列表中的下一项，而不是使用位置列。然后，您需要在列表检索中迭代逻辑，以便按顺序获取项目。这可以在存储过程中相对容易地实现。
如果您有许多列表，有一种将列表序列化和反序列化为文本/二进制的快速方法，并且您只想存储和检索整个列表，然后将整个列表作为单个值存储在单个列中。但可能不是你在这里要求的。

这篇文章很旧，但仍然会给我 0.02 美元。更新表或记录集中的每条记录对于解决排序问题听起来很疯狂。索引的数量也很疯狂，但听起来大多数人都已经接受了。

我想出的减少更新和索引的疯狂解决方案是创建两个表（并且在大多数用例中，您无论如何都不会在一张表中对所有记录进行排序）。表 A 保存正在排序的列表的记录，表 B 将顺序记录分组并保存为字符串。order 字符串表示一个数组，可用于在 Web 服务器或网页应用程序的浏览器层上对所选记录进行排序。

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

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

它还提到了专门的 SQL Server 2014 层次结构ID 特征。

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

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

此方法还允许您检索记录，而不考虑列表中的成员资格，但仅允许一个列表中的成员资格，并且可能需要附加的“列表 ID”列来指示记录属于哪个列表。

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

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

这是我自己一段时间以来一直试图弄清楚的事情。到目前为止，我发现的最好方法是使用以下格式为链接列表创建一个表（这是伪代码）：

链表(

键1,
信息，
键2

)

key1 是起点。Key2 是一个外键，在下一列中链接到自身。所以你的专栏将链接一些像这样的链接

第 1 列

键1 = 0，
信息='你好'
键2 = 1

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

列2

键1 = 1，
信息='wassup'
键2=空

col2 中的 key2 设置为 null，因为它不指向任何内容

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

这是一次输入多个条目的最佳方法，然后返回并相应地设置外键（或者构建一个专门为您执行此操作的 GUI）

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

创建表.sql

create table linkedlist00 (

key1 int primary key not null identity(1,1),

info varchar(10),

key2 int

)

注册外键.sql

alter table dbo.linkedlist00

add foreign key (key2) references dbo.linkedlist00(key1)

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

链表在以下方面尤其强大 一对多 关系。那么，如果您曾经想创建一个外键数组呢？嗯，这是一种方法！您可以创建一个指向链表中第一列的主表，然后可以使用指向所需信息表的外键来代替“信息”字段。

例子：

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

假设他们有一张名为 文件柜

文件柜（

机柜 ID（包）
文件ID（FK））

每列包含文件柜的主键和文件的外键。这些文件可以是纳税表格、健康保险文件、实地考察许可单等

文件（

文件 ID（pk）
文件 ID (fk)
下一个文件 ID (fk)

)

这是文件的容器

文件（

文件 ID（pk）
文件信息

)

这是具体的文件

可能有更好的方法可以做到这一点，具体取决于您的具体需求。该示例仅说明可能的用法。

列表可以通过包含偏移量（列表索引位置）的列来存储——中间的插入然后将所有内容递增到新父级之上，然后执行插入。

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

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

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow