SQL 中的链表

Linked List in SQL

提问by

Whats the best way to store a linked list in a mysql database so that inserts are simple (i.e. you dont have to reindex a bunch of stuff every time) and such that the list can easily be pulled out in order.

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

采纳答案by Adrian Dunston

Store an integer column in your table called 'position'. Record a 0 for the first item in your list, a 1 for the second item, etc. Index that column in your database, and when you want to pull your values out, sort by that column.

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

To insert a value at index 3, modify the positions of rows 3 and above, and then insert:

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

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

回答by cfeduke

Using Adrian's solution, but instead of incrementing by 1, increment by 10 or even 100. Then insertions can be calculated at half of the difference of what you're inserting between without having to update everything below the insertion. Pick a number large enough to handle your average number of insertions - if its too small then you'll have to fall back to updating all rows with a higher position during an insertion.

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

回答by B0fh

create a table with two self referencing columns PreviousID and NextID. If the item is the first thing in the list PreviousID will be null, if it is the last, NextID will be null. The SQL will look something like this:

创建一个包含两个自引用列 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
}

回答by Rory

The simplest option would be creating a table with a row per list item, a column for the item position, and columns for other data in the item. Then you can use ORDER BY on the position column to retrieve in the desired order.

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

To manipulate the list just update the position and then insert/delete records as needed. So to insert an item into list 1 at index 3:

要操作列表，只需更新位置，然后根据需要插入/删除记录。因此，要在索引 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;

Since operations on the list can require multiple commands (eg an insert will require an INSERT and an UPDATE), ensure you always perform the commands within a transaction.

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

A variation of this simple option is to have position incrementing by some factor for each item, say 100, so that when you perform an INSERT you don't always need to renumber the position of the following elements. However, this requires a little more effort to work out when to increment the following elements, so you lose simplicity but gain performance if you will have many inserts.

这个简单选项的一个变体是让每个项目的位置增加某个因子，比如 100，这样当您执行 INSERT 时，您不必总是需要重新编号以下元素的位置。但是，这需要更多的努力来确定何时增加以下元素，因此如果您有许多插入，您会失去简单性但会提高性能。

Depending on your requirements other options might appeal, such as:

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

• If you want to perform lots of manipulations on the list and not many retrievals you may prefer to have an ID column pointing to the next item in the list, instead of using a position column. Then you need to iterative logic in the retrieval of the list in order to get the items in order. This can be relatively easily implemented in a stored proc.

• If you have many lists, a quick way to serialise and deserialise your list to text/binary, and you only ever want to store and retrieve the entire list, then store the entire list as a single value in a single column. Probably not what you're asking for here though.

• 如果您想对列表执行大量操作而不是多次检索，您可能更喜欢使用 ID 列指向列表中的下一项，而不是使用位置列。然后您需要在检索列表中进行迭代逻辑，以便按顺序获取项目。这可以在存储过程中相对容易地实现。

• 如果您有很多列表，可以快速将列表序列化和反序列化为文本/二进制，并且您只想存储和检索整个列表，然后将整个列表作为单个值存储在单个列中。可能不是你在这里要求的。

回答by user9252

A linked list can be stored using recursive pointers in the table. This is very much the same hierarchies are stored in Sql and this is using the recursive association pattern.

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

You can learn more about it here(Wayback Machine link).

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

I hope this helps.

我希望这有帮助。

回答by Mike Monette

There are a few approaches I can think of right off, each with differing levels of complexity and flexibility. I'm assuming your goal is to preserve an order in retrieval, rather than requiring storage as an actual linked list.

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

The simplest method would be to assign an ordinal value to each record in the table (e.g. 1, 2, 3, ...). Then, when you retrieve the records, specify an order-by on the ordinal column to get them back in order.

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

This approach also allows you to retrieve the records without regard to membership in a list, but allows for membership in only one list, and may require an additional "list id" column to indicate to which list the record belongs.

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

An slightly more elaborate, but also more flexible approach would be to store information about membership in a list or lists in a separate table. The table would need 3 columns: The list id, the ordinal value, and a foreign key pointer to the data record. Under this approach, the underlying data knows nothing about its membership in lists, and can easily be included in multiple lists.

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

回答by FlyTigert

This post is old but still going to give my .02$. Updating every record in a table or record set sounds crazy to solve ordering. the amount of indexing also crazy, but it sounds like most have accepted it.

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

Crazy solution i came up with to reduce updates and indexing is to create two tables (and in most use cases you don's sort all records in just one table anyway). Table A to hold the records of the list being sorted and table B to group and hold a record of the order as a string. the order string represents an array that can be used to order the selected records either on the web server or browser layer of a webpage application.

我想出的减少更新和索引的疯狂解决方案是创建两个表（并且在大多数用例中，您无论如何都不会将所有记录排序在一个表中）。表 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
}

The format of the order sting should be id, position and some separator to split() your string by. in the case of jQuery UI the .sortable('serialize') function outputs an order string for you that is POST friendly that includes the id and position of each record in the list.

订单字符串的格式应该是 id、位置和一些分隔符来 split() 你的字符串。在 jQuery UI 的情况下，.sortable('serialize') 函数为您输出一个订单字符串，该字符串对 POST 友好，其中包括列表中每条记录的 id 和位置。

The real magic is the way you choose to reorder the selected list using the saved ordering string. this will depend on the application you are building. here is an example again from jQuery to reorder the list of items: http://ovisdevelopment.com/oramincite/?p=155

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

回答by Vadzim

https://dba.stackexchange.com/questions/46238/linked-list-in-sql-and-treessuggests a trick of using floating-point position column for fast inserts and ordering.

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

It also mentions specialized SQL Server 2014 hierarchyidfeature.

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

回答by HumbleWebDev

This is something I've been trying to figure out for a while myself. The best way I've found so far is to create a single table for the linked list using the following format (this is pseudo code):

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

LinkedList(

链表(

• key1,
• information,
• key2

• 键 1，
• 信息，
• 钥匙2

)

)

key1 is the starting point. Key2 is a foreign key linking to itself in the next column. So your columns will link something link something like this

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

col1

第 1 列

• key1 = 0,
• information= 'hello'
• key2 = 1

• 键 1 = 0,
• 信息= '你好'
• 键 2 = 1

Key1 is primary key of col1. key2 is a foreign key leading to the key1 of col2

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

col2

列2

• key1 = 1,
• information= 'wassup'
• key2 = null

• 键 1 = 1,
• 信息 = 'wassup'
• 键 2 = 空

key2 from col2 is set to null because it doesn't point to anything

col2 中的 key2 被设置为 null 因为它不指向任何东西

When you first enter a column in for the table, you'll need to make sure key2 is set to null or you'll get an error. After you enter the second column, you can go back and set key2 of the first column to the primary key of the second column.

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

This makes the best method to enter many entries at a time, then go back and set the foreign keys accordingly (or build a GUI that just does that for you)

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

Here's some actual code I've prepared (all actual code worked on MSSQL. You may want to do some research for the version of SQL you are using!):

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

createtable.sql

创建表

create table linkedlist00 (

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

info varchar(10),

key2 int

)

register_foreign_key.sql

register_foreign_key.sql

alter table dbo.linkedlist00

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

*I put them into two seperate files, because it has to be done in two steps. MSSQL won't let you do it in one step, because the table doesn't exist yet for the foreign key to reference.

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

Linked List is especially powerful in one-to-manyrelationships. So if you've ever wanted to make an array of foreign keys? Well this is one way to do it! You can make a primary table that points to the first column in the linked-list table, and then instead of the "information" field, you can use a foreign key to the desired information table.

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

Example:

例子：

Let's say you have a Bureaucracy that keeps forms.

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

Let's say they have a table called file cabinet

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

FileCabinet(

文件柜（

• Cabinet ID (pk)
• Files ID (fk) )

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

each column contains a primary key for the cabinet and a foreign key for the files. These files could be tax forms, health insurance papers, field trip permissions slips etc

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

Files(

文件(

• Files ID (pk)

• File ID (fk)

• Next File ID (fk)

• 文件 ID (pk)

• 文件 ID (fk)

• 下一个文件 ID (fk)

)

)

this serves as a container for the Files

这用作文件的容器

File(

文件（

• File ID (pk)

• Information on the file

• 文件 ID (pk)

• 文件信息

)

)

this is the specific file

这是特定文件

There may be better ways to do this and there are, depending on your specific needs. The example just illustrates possible usage.

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

回答by Stephen

Increment the SERIAL 'index' by 100, but manually add intermediate values with an 'index' equal to Prev+Next / 2. If you ever saturate the 100 rows, reorder the index back to 100s.

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

This should maintain sequence with primary index.

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