代码之家 › 专栏 › 技术社区 › Jörg Brenninkmeyer

如何在数据库中存储经常改变位置的订购项

linked-list indexing recursion data-structures sql

Jörg Brenninkmeyer · 技术社区 · 14 年前

我需要能够在数据库中存储大量订购项目的列表。到目前为止,这是直截了当的:

ID Position OtherFields
 1     45      ...
 2   4736      ...
 3    514      ...
 ...

在查询中,我总是需要仅获取一些项目(根据其他字段筛选),但顺序是正确的。也很容易,在位置上放置索引并使用“按位置排序”。

现在问题 :项目经常改变其位置,而不仅仅是1或2。如果ID2将位置从4736更改为2000,我需要更新它的位置以及旧位置2000和4735之间所有元素的位置,每行增加一个。每个事务不仅改变一个ID,而且也改变了一些ID,而且在短时间内可以有许多事务。

我认为最优雅的方式来处理更新问题是使用链接列表而不是位置列,在该列中,我可以通过将其前置任务链接到其后续任务来从旧位置移除ID 2,然后通过将其新前置任务和后续任务链接到其他位置来将其插入。这将是一个常数和少量的更新每一个位置的变化,它也将是我的首选方式来处理这些变化(在Java中,在我的情况下)。然而,这引发了n+1问题查询以正确的顺序-即使对于一些元素,我也必须在最坏的情况下浏览整个列表,以找出它们的正确顺序。

所以我的问题是 :您建议如何在必要的更新和查询性能之间取得良好的平衡?

到目前为止,我看到两个有希望的方向:

是否有一个DBMS(理想情况下是OpenSource)不仅可以用句法手段处理链表,而且还可以用良好的性能处理链表,例如通过使用链表元素的内部索引?
也许这也是一个选项,只要有一个blob,整个链接列表将存储在其中!这样一个链表能得到多大的内存/它在数据库中会使用多少内存,当获取到1000.000个条目时?我使用Java+Hibernate以防它很重要。我想在获取blob之后,即使是内存中的整个列表也应该处理得非常快!?

当然,也欢迎其他想法!

3 回复 | 直到 14 年前

Mark Byers 14 年前

如果你放松约束 Position 列必须包含从1到n的整数,并允许它包含任何数字,然后您可以高效地进行搜索和更新。

您可以通过计算平均(A+B)第2部分,在位置为A和B的其他两个项目之间插入一个项目。例如,如果A是10000,B是12000,那么您的新职位是11000。有时,由于集群的原因,您会用完间隙,此时您可以运行整个表,更均匀地重新分布位置。

Abe Miessler 14 年前

用十进制表示位置怎么样?如果这样,可以使用以下方法将其置于其他位置之间:

原始记录包括:

ID    Position  Otherfields
--------------------------
1     1.0
2     2.0
.
.
.
5000  5000.0

那么说你把身份证1号移到5000号之前

ID    Position  Otherfields
--------------------------
1     4999.9
2     2.0
.
.
.
5000  5000.0

现在假设您要将ID 2置于1和5000之间:

ID    Position  Otherfields
--------------------------
1     4999.9
2     4999.91
.
.
.
5000  5000.0

这样,您只更改一个记录…

更新:

在重新阅读了@mark byers的建议之后,我们的解决方案似乎非常相似,尽管使用十进制对我来说似乎简单得多…

-1

Community CDub 7 年前

以下内容可能会有所帮助。它不会直接回答您的问题,但可以对如何执行此操作(如果可以满足您的要求)提供一些帮助:

ranking entries in mysql table