sql - SQL中的链表

Question

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

score 18 · Accepted Answer

创建一个包含两个自引用列 PreviousID 和 NextID 的表。如果项目是列表中的第一个，PreviousID 将为空，如果是最后一个，NextID 将为空。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
}

score 17 · Accepted Answer

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

score 15 · Accepted Answer

在您的表中存储一个名为“位置”的整数列。为列表中的第一项记录 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);

score 4 · Accepted Answer

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

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

我希望这有帮助。

score 3 · Accepted Answer

最简单的选项是创建一个表，其中每个列表项有一行，项目位置的列和项目中其他数据的列。然后您可以在位置列上使用 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 );

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

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

score 3 · Accepted Answer

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

链表（

键1，
信息，
键2

)

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

col1

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

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

col2

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

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

)

register_foreign_key.sql

alter table dbo.linkedlist00

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

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

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

例子：

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

假设他们有一张叫做文件柜的桌子

文件柜（

机柜 ID (pk)
文件 ID (fk) )

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

文件（

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

)

这用作文件的容器

文件（

文件 ID (pk)
档案资料

)

这是特定的文件

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

score 2 · Accepted Answer

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

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

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

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

score 2 · Accepted Answer

这篇文章很旧，但仍然会给我 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、位置和一些分隔符来分割（）你的字符串。对于 jQuery UI，.sortable('serialize') 函数会为您输出一个对 POST 友好的订单字符串，其中包括列表中每条记录的 id 和位置。

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

score 2 · Accepted Answer

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

它还提到了专门的 SQL Server 2014 hierarchyid功能。

score 0 · Accepted Answer

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

score 0 · Accepted Answer

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

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

score -1 · Accepted Answer

可以通过让列包含偏移量（列表索引位置）来存储列表——中间的插入然后在新父级之上递增，然后进行插入。

score -1 · Accepted Answer

您可以像双端队列（deque）一样实现它，以支持快速推送/弹出/删除（如果已知 oridnal）和检索，您将拥有两个数据结构。一个带有实际数据，另一个带有在键的历史记录中添加的元素数量。权衡：对于任何插入到链表中间的 O(n)，此方法会更慢。

create table queue (
    primary_key,
    queue_key
    ordinal,
    data
)

你会有一个关于 queue_key+ordinal 的索引

您还将有另一个表存储添加到队列中的行数......

create table queue_addcount (
    primary_key,
    add_count
)

将新项目推送到队列的任一端（左或右）时，您总是会增加 add_count。

如果你推到后面，你可以设置序数......

ordinal = add_count + 1

如果你推到前面，你可以设置序数......

ordinal = -(add_count + 1)

更新

add_count = add_count + 1

这样，您可以删除队列/列表中的任何位置，它仍会按顺序返回，您还可以继续推送新项目以保持顺序。

如果发生大量删除，您可以选择重写序数以避免溢出。

您还可以在序号上有一个索引，以支持对列表的快速有序检索。

如果你想支持插入到中间，你需要找到它需要插入的序数，然后用那个序数插入。然后在该插入点之后将每个序数加一。此外，像往常一样增加 add_count。如果序数是负数，您可以递减所有较早的序数以减少更新。这将是 O(n)

sql - SQL中的链表

13 回答 13

Related

Reference