如何设计用于存储排序列表的数据库？

Question

如何设计用于存储排序列表的数据库？

chi*_*tti 47 database-design

我希望在数据库中存储一个排序列表。我想有效地执行以下操作。

Insert(x) - 将记录 x 插入表中
Delete(x) - 从表中删除记录 x
Before(x,n) - 返回排序列表中记录 x 之前的“n”条记录。
After(x,n) - 返回排序列表中记录 x 之后的“n”条记录。
First(n) - 从排序列表中返回前 'n' 条记录。
Last(n) - 返回排序列表中的最后 'n' 条记录。
Compare(x,y) - 给定表中的两条记录 x 和 y，查找是否 x > y。

我能想到的简单方法是在表中存储某种“等级”属性，并通过对该属性进行排序来进行查询。但是在这种方法中，插入/修改具有等级的记录成为一项代价高昂的操作。有没有更好的方法？

具体来说，我希望使用 Amazon 的 SimpleDB 来实现该表。但是关系数据库的一般答案也应该有帮助。

负载配置文件更新：

由于我正在为 Web 应用程序规划此功能，因此这取决于使用该应用程序的用户数量。

如果有 100k 活跃用户（超级乐观：P），那么我每天非常近似的估计是

500k 次选择，100k 次插入和删除，500k 次更新

我希望该表总共增长到 500k。

我希望优化更新、插入和比较操作。项目的排名会不断变化，我需要保持表格更新。

Answer 1

Nic*_*mas 22

如果排名不是完全任意的，而是可以从其他一些属性（例如姓名、玩家得分等）推导出来，那么请仔细看看乔尔的回答。

如果它是数据的任意属性，则应将其存储为记录表中的列。假设 Amazon 的 SimpleDB 类似于典型的 RDBMS，那么您可以索引此列并使用适当的索引策略快速满足上述所有查询。这对于 RDBMS 来说是正常的。

鉴于您期望高插入和更新活动，但也有相对高的读取活动，我建议执行以下操作：

根据排名对表进行聚类，尤其是当您的绝大多数查询都针对排名时。如果没有，或者如果在 SimpleDB 中选择集群键不可用，那么只需创建一个以 rank 作为前导列的索引。这将满足查询 3-6。
先在记录上建立索引，然后进行排名（或者，在 SQL Server 世界中，仅记录和INCLUDE-ing 排名，或者如果您已在排名上聚集，则仅记录）将满足查询 7。
操作 1 和 2 可以通过适当地间隔数据来优化（即FILLFACTOR在 SQL Server 中设置）。如果您按等级进行聚类，这一点尤其重要。
当您插入或更新排名时，尽可能多地保持排名编号之间的差距，以最大限度地减少您需要重新排名现有记录以适应排名插入或更新的可能性。例如，如果您以 1000 为步长对您的记录进行排名，那么您将留出足够的空间来容纳大约一半的更改和插入，而您需要对未直接参与这些更改的记录重新排名的机会很小。
每天晚上重新排列所有记录以重置它们之间的等级差距。
您可以调整批量重新排名的频率以及排名差距大小，以适应相对于现有记录数量的预期插入或更新数量。因此，如果您有 100K 条记录，并希望您的插入和更新占其中的 10%，请为 10K 新排名留出足够的空间并每晚重新排名。
对 500K 记录重新排序是一项昂贵的操作，但每天或每周在非工作时间完成一次对这样的数据库来说应该没问题。这种在非工作时间进行大规模重新排名以保持排名差距的原因是，您不必在正常和高峰时段为每次排名更新或插入重新排名许多记录。

如果您希望在 100K+ 大小的表上读取 100K+，我不建议使用链表方法。它不会很好地扩展到这些尺寸。

感谢更新的答案。“排名”是我的数据的任意属性。我几乎确信自定义索引列就是我所需要的。看看这个 [SO 链接](http://stackoverflow.com/questions/2940329/how-to-move-an-element-in-a-sorted-list-and-keep-the-couchdb-write-atomic)有一个类似的问题。最佳答案提供了有关如何处理此类排名列的建议。 (2认同)

Answer 2

bpa*_*lla 14

我通常使用您描述的“排名”方法。当项目需要重新排序时，我经常能够避免删除列表中的所有记录并以正确的顺序重新插入新项目，而不是在更新行时搞砸。该方法明显针对检索进行了优化。

另一种方法是通过使用表上的“前身”自反外键列将记录建模为链接列表：

ID   setID   item       predecessor
---  ------  ------     ------------
1    1       Apple      null
2    1       Orange     1
3    2       Cucumber   null
4    1       Pear       2
5    1       Grape      4
6    2       Carrot     3

Run Code Online (Sandbox Code Playgroud)

您可以轻松地检索列表并以很少的开销添加和删除项目，但以正确的顺序获取记录将是棘手的。也许有一种聪明的方法可以在单个查询中做到这一点，可能有很多别名表连接。

当我对树型关系（类别、文件夹、集合和子集）进行建模时，我经常使用后一种方法。我通常有某种递归函数来重建我的应用程序中的完整树。

这种类型的解决方案也近似于图形数据模型 (http://en.wikipedia.org/wiki/Graph_theory)。为存储图节点和边而优化的存储系统可能是比 RDBMS 更好的解决方案。三重和四重存储以及像 Neo4J 这样的图形数据库在这方面非常擅长。 (5认同)
链表模型很整洁。要在 SQL Server 中按顺序检索这样的层次结构，您将使用 [递归 CTE](http://msdn.microsoft.com/en-us/library/ms186243.aspx)。 (2认同)

Answer 3

Joe*_*own 6

我认为要做的事情是存储用于计算排名的一个或多个属性，然后在它们上建立一个索引。与其试图强制数据库按排序顺序物理存储数据或使用手动管理的链表，为什么不让数据库引擎做它设计要做的事情呢？

购物车只是我举的一个例子，表明在某些情况下“排名”可以是任意的。可能这不是一个很好的例子。Netflix DVD 队列就是一个更好的例子。只是为了争论，想象一个有 10 万个项目的 Netflix 队列，用户可以任意重新排序，他每分钟重新排序一次。在这个假设的应用程序中，您将如何设计一个数据库来存储电影的有序列表？ (4认同)
如果“用于计算等级的属性”是任意的怎么办？例如：根据用户的任意操作重新排序的一组购物车条目。 (3认同)

归档时间：	14 年，1 月前
查看次数：	46203 次
最近记录：	6 年，2 月前