blocks|key|1764991|text|在表中存储一个名为“position”的整型列。为列表中的第一项记录0，为第二项记录1，依此类推。在数据库中为该列建立索引，当您想要提取值时，按该列排序。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1764992|+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;|code-block|syntax|javascript|1764993|要在索引3处插入值，请修改第3行及以上行的位置，然后插入：|1764994|+update+linked_list+set+position+=+position+%2B+1+where+position+>=+3;
+insert+into+linked_list+(my_value,+position)+values+("new+value",+3);+|1764995|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

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.

<pre><code> 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;
</code></pre>

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

<pre><code> update linked_list set position = position + 1 where position &gt;= 3;
 insert into linked_list (my_value, position) values ("new value", 3); 
</code></pre>

blocks|key|1765121|text|创建一个包含两个自引用列PreviousID和NextID的表。如果该项是列表中的第一项，则PreviousID将为空，如果它是最后一项，则NextID将为空。SQL将如下所示：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1765122|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
}|code-block|syntax|javascript|1765123|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

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:

<pre><code>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
}
</code></pre>

blocks|key|1765029|text|使用Adrian的解决方案，但不是递增1，而是递增10甚至100。然后，可以按照插入内容的差值的一半来计算插入内容，而不必更新插入内容下的所有内容。选择一个足够大的数字来处理您的平均插入次数-如果它太小，那么您将不得不在插入期间使用更高的位置更新所有行。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1765030|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

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.

blocks|key|1765064|text|链表可以使用表中的递归指针来存储。这是非常相同的层次结构存储在Sql中，这是使用递归关联模式。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1765065|你可以通过here+(Wayback+Machine链接)了解更多信息。|offset|length|1765066|我希望这能帮到你。|1765067|entityMap|0|LINK|mutability|MUTABLE|url|https://web.archive.org/web/20180729174436/http://www.tomjewett.com/dbdesign/dbdesign.php?page=recursive.php^0|0|5|4|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@$D|R|E|S|1|T]]|A|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]]]

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.

You can learn more about it <a href="https://web.archive.org/web/20180729174436/http://www.tomjewett.com/dbdesign/dbdesign.php?page=recursive.php" rel="nofollow noreferrer">here</a> (Wayback Machine link).

I hope this helps.

blocks|key|1765214|text|我可以立即想到几种方法，每种方法都具有不同程度的复杂性和灵活性。我假设您的目标是在检索时保留顺序，而不是要求存储为实际的链表。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1765215|最简单的方法是为表中的每条记录分配一个序数值(例如，1，2，3，...)。然后，在检索记录时，在序数列上指定一个排序依据，以使它们重新按顺序排列。|1765216|这种方法还允许您在不考虑列表中的成员身份的情况下检索记录，但只允许一个列表中的成员身份，并且可能需要额外的“list+id”列来指示记录所属的列表。|1765217|一种稍微复杂但也更灵活的方法是将有关成员资格的信息存储在一个或多个单独的表中。该表需要3列:列表id、序数值和指向数据记录的外键指针。在这种方法下，底层数据对其在列表中的成员身份一无所知，并且可以轻松地包含在多个列表中。|1765218|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

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. 

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.

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.

blocks|key|1550376|text|这篇文章很老了，但仍然会给我的.02$。更新表或记录集中的每条记录听起来很难解决排序问题。索引的数量也很疯狂，但听起来大多数人都接受了。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1550377|我想出了一个疯狂的解决方案来减少更新和索引，那就是创建两个表(在大多数用例中，您不会只在一个表中对所有记录进行排序)。表A用于保存正在排序的列表的记录，表B用于分组并将订单的记录作为字符串保存。排序字符串表示可用于对网页应用程序的web服务器或浏览器层上的所选记录进行排序的数组。|1550378|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
}|code-block|syntax|javascript|1550379|order+string的格式应该是id、position和一些分隔符，以将字符串拆分()。在序列化UI的情况下，.sortable(‘jQuery’)函数为您输出一个POST友好的订单字符串，其中包括列表中每条记录的id和位置。|1550380|真正神奇的是您选择使用保存的排序字符串对所选列表进行重新排序的方式。这将取决于您正在构建的应用程序。下面是来自jQuery的一个重新排序项目列表的示例：http://ovisdevelopment.com/oramincite/?p=155|offset|length|1550381|entityMap|0|LINK|mutability|MUTABLE|url|http://ovisdevelopment.com/oramincite/?p=155^0|0|0|0|0|24|18|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|X|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|Y|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|Z|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|10|8|@]|9|@$M|11|N|12|1|13]]|A|$]]|$1|O|3|-4|5|6|7|14|8|@]|9|@]|A|$]]]|P|$Q|$5|R|S|T|A|$U|V]]]]

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. 

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. 

<pre><code>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
}
</code></pre>

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. 

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: <a href="http://ovisdevelopment.com/oramincite/?p=155" rel="nofollow">http://ovisdevelopment.com/oramincite/?p=155</a>

blocks|key|1765458|text|https://dba.stackexchange.com/questions/46238/linked-list-in-sql-and-trees建议使用浮点位置列进行快速插入和排序。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1765459|它还提到了专门的SQL+Server+2014+hierarchyid功能。|1765460|entityMap|0|LINK|mutability|MUTABLE|url|https://dba.stackexchange.com/questions/46238/linked-list-in-sql-and-trees|1|http://technet.microsoft.com/en-us/library/bb677173.aspx^0|0|22|0|0|O|B|1|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@$A|Q|B|R|1|S]]|C|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@$A|U|B|V|1|W]]|C|$]]|$1|F|3|-4|5|6|7|X|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]|N|$5|I|J|K|C|$L|O]]]]

<a href="https://dba.stackexchange.com/questions/46238/linked-list-in-sql-and-trees">https://dba.stackexchange.com/questions/46238/linked-list-in-sql-and-trees</a> suggests a trick of using floating-point position column for fast inserts and ordering.

It also mentions specialized SQL Server 2014 <a href="http://technet.microsoft.com/en-us/library/bb677173.aspx" rel="nofollow noreferrer">hierarchyid</a> feature.

blocks|key|1765326|text|我认为添加一个Datetime类型的created列和一个int类型的position列要简单得多，所以现在您可以有重复的位置，在select语句中使用order+by+position，created+desc选项，您的列表将按顺序读取。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1765327|entityMap^0|7|8|T|3|24|8|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]|$9|K|A|L|B|C]|$9|M|A|N|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|O|8|@]|D|@]|E|$]]]|G|$]]

I think its much simpler adding a created column of <code>Datetime</code> type and a position column of <code>int</code>, so now you can have duplicate positions, at the select statement use the <code>order by</code> position, created desc option and your list will be fetched in order.

blocks|key|1765539|text|将序列'+index‘递增100，但手动添加'index’等于Prev%2BNext+/+2的中间值。如果您曾使这100行饱和，请将索引重新排序为100s。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1765540|这应该与主索引保持顺序。|1765541|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

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.

This should maintain sequence with primary index.

blocks|key|1549951|text|可以通过让列包含偏移量(列表索引位置)来存储列表--中间的insert在新父元素上递增，然后执行insert。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1549952|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

A list can be stored by having a column contain the offset (list index position) -- an insert in the middle is then incrementing all above the new parent and then doing an insert.

blocks|key|1765631|text|您可以像双端队列(deque)一样实现它，以支持快速推送/弹出/删除(如果知道oridnal+)和检索，您将拥有两个数据结构。一个是实际数据，另一个是在键的历史记录上添加的元素数量。权衡:对于链表O(n)中间的任何插入，这个方法都会更慢。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1765632|create+table+queue+(
++++primary_key,
++++queue_key
++++ordinal,
++++data
)|code-block|syntax|javascript|1765633|你会有一个关于queue_key%2Bordinal的索引|1765634|您还可以使用另一个表来存储添加到队列中的行数……|1765635|create+table+queue_addcount+(
++++primary_key,
++++add_count
)|1765636|当将一个新项目推送到队列的两端(左或右)时，您总是会递增add_count。|1765637|如果你往后推，你就可以把序数...|1765638|ordinal+=+add_count+%2B+1|1765639|如果你往前推你可以把序数..。|1765640|ordinal+=+-(add_count+%2B+1)|1765641|更新|1765642|add_count+=+add_count+%2B+1|1765643|这样，您可以删除队列/列表中的任何位置，但它仍然会按顺序返回，并且您还可以继续推送新项目来保持顺序。|1765644|您可以选择重写序数，以避免在发生大量删除时溢出。|1765645|您还可以在序数上建立索引，以支持列表的快速有序检索。|1765646|如果你想支持插入到中间，你需要找到需要插入的序号，然后用该序号插入。然后在该插入点之后将每个序数递增1。另外，像往常一样递增add_count。如果序数为负，您可以递减所有较早的序号以进行更少的更新。这将是O(n)|1765647|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1A|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|1B|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|1C|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|1D|8|@]|9|@]|A|$]]|$1|K|3|L|5|D|7|1E|8|@]|9|@]|A|$E|F]]|$1|M|3|N|5|6|7|1F|8|@]|9|@]|A|$]]|$1|O|3|P|5|6|7|1G|8|@]|9|@]|A|$]]|$1|Q|3|R|5|D|7|1H|8|@]|9|@]|A|$E|F]]|$1|S|3|T|5|6|7|1I|8|@]|9|@]|A|$]]|$1|U|3|V|5|D|7|1J|8|@]|9|@]|A|$E|F]]|$1|W|3|X|5|6|7|1K|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|D|7|1L|8|@]|9|@]|A|$E|F]]|$1|10|3|11|5|6|7|1M|8|@]|9|@]|A|$]]|$1|12|3|13|5|6|7|1N|8|@]|9|@]|A|$]]|$1|14|3|15|5|6|7|1O|8|@]|9|@]|A|$]]|$1|16|3|17|5|6|7|1P|8|@]|9|@]|A|$]]|$1|18|3|-4|5|6|7|1Q|8|@]|9|@]|A|$]]]|19|$]]

You could implement it like a double ended queue (deque) to support fast push/pop/delete(if oridnal is known) and retrieval you would have two data structures. One with the actual data and another with the number of elements added over the history of the key. Tradeoff: This method would be slower for any insert into the middle of the linked list O(n).
<pre><code>create table queue (
 primary_key,
 queue_key
 ordinal,
 data
)
</code></pre>
You would have an index on queue_key+ordinal
You would also have another table which stores the number of rows EVER added to the queue...
<pre><code>create table queue_addcount (
 primary_key,
 add_count
)
</code></pre>
When pushing a new item to either end of the queue (left or right) you would always increment the add_count.
If you push to the back you could set the ordinal...
<pre><code>ordinal = add_count + 1
</code></pre>
If you push to the front you could set the ordinal...
<pre><code>ordinal = -(add_count + 1)
</code></pre>
update
<pre><code>add_count = add_count + 1
</code></pre>
This way you can delete anywhere in the queue/list and it would still return in order and you could also continue to push new items maintaining the order.
You could optionally rewrite the ordinal to avoid overflow if a lot of deletes have occurred.
You could also have an index on the ordinal to support fast ordered retrieval of the list.
If you want to support inserts into the middle you would need to find the ordinal which it needs to be insert at then insert with that ordinal. Then increment every ordinal by one following that insertion point. Also, increment the add_count as usual. If the ordinal is negative you could decrement all of the earlier ordinals to do fewer updates. This would be O(n)

What's the best way to store a linked list in a MySQL database so that inserts are simple (i.e. you don't have to re-index a bunch of stuff every time) and such that the list can easily be pulled out in order?

Linked List in SQL

数据结构

SQL数据库

SQL Server

数据库

服务器

jQuery

MySQL

在MySQL数据库中存储链表的最好方法是什么，这样插入就很简单(即不必每次都对一堆东西重新索引)，并且可以很容易地按顺序取出链表？

问SQL中的链表
EN

回答 11

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问SQL中的链表EN

回答 11

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问SQL中的链表
EN