插入（x）-将记录x插入表中
删除（x）-从表中删除记录x
Before（x，n）-返回排序后的列表中记录x之前的'n'个记录。
排序列表。
第一（n）-返回排序列表中的前n个记录。
最后（n）-返回排序列表中的最后n个记录。 br />比较（x，y）-给定表中的两个记录x和y，找到x>
y。表中“排名”属性的值，并通过对该属性进行排序进行查询。但是在这种方法中，插入/修改具有等级的记录成为昂贵的操作。有更好的方法吗？
具体来说，我正在寻找使用Amazon的SimpleDB实现表的方法。但是对关系数据库的一般回答也应该会有所帮助。使用该应用程序的用户。
如果有10万活跃用户（超级乐观：P），那么我每天的估算值大约为
50万次选择，10万次插入和删除，500k更新
我希望表总共增加到500k。项目的等级将不断变化，我需要保持表格更新。
#1 楼
如果等级不是完全任意的，而是可以从其他属性（例如姓名，球员得分等）得出的，那么请仔细看一下乔尔的答案。数据，则应将其存储为记录表中的一列。假设Amazon的SimpleDB与典型的RDBMS相似，则可以对该列进行索引，并使用适当的索引策略快速满足上述所有查询。对于RDBMS，这是正常的。鉴于您期望较高的插入和更新活动，但相对较高的读取活动，我建议您执行以下操作：将表聚集在排名上，特别是如果您的绝大多数查询都针对排名。如果没有，或者如果在SimpleDB中没有选择聚类键，则只需创建一个以rank为首列的索引。这将满足查询3-6。
首先在记录上创建索引，然后再进行排序（或者，在SQL Server的世界中，仅记录并进行排序，或者仅记录是否已基于排名进行记录）就可以满足查询7。
可以通过适当地分隔数据（即在SQL Server中设置
INCLUDE）来优化操作1和2。如果您在排名上聚类，这尤其重要。在插入或更新排名时，请在等级编号之间保持尽可能大的距离，以最大程度地减少您需要对现有记录进行重新排名以适应排名的可能性。等级插入或更新。例如，如果您以1000为步长对记录进行排名，那么您将留出足够的空间来存储大约一半的更改，而插入的可能性很小，那么您需要重新排列不直接涉及这些更改的记录。重新排序所有记录以重置它们之间的排名差距。
您可以调整批量重新排列的频率以及行列间隔大小，以适应相对于现有记录数的预期插入或更新数。因此，如果您有10万条记录，并希望插入和更新的记录占其中的10％，请留出足够的空间容纳1万个新排名，并每晚重新排名。
重新排序50万条记录是一项昂贵的操作，但对于这样的数据库，每天或每周下班时间进行一次检查应该没问题。这种非工作时间的大规模重新排名可保持排名差距，这使您不必在正常和高峰时段为每次排名更新或插入而重新排名很多记录。在大小超过100K的表上，我不建议使用链表方法。不能很好地适应这些大小。
评论
等级是可修改的。我希望队伍不断变化，不断插入新的记录。我担心这样的情况，当我插入一个具有等级的新元素，然后需要更改排序顺序在新记录之下的所有记录的排名。当我的数据库中有成千上万条记录时，这不是一项昂贵的操作吗？
– chitti
2011年9月13日，1：16
@chitti-啊，这是一个问题。您可以排列排名（例如0、1000、2000、3000等），并在排名空缺时定期对所有记录重新排名。但是，如果您希望获得的记录数不胜数，则无法扩展。
–尼克·查马斯（Nick Chammas）
2011年9月13日，下午1:21
@chitti-实际上，这有点好笑。这正是数据库引擎在为数据建立索引时要处理的问题，因为它们在对数据进行排序并在添加或更改数据时对其进行重新排序。如果您查找FILLFACTOR，您将发现它基本上是为索引中的记录创建额外的空间，就像我描述的排名差距为排名更改和插入创建空间一样。
–尼克·查马斯（Nick Chammas）
2011年9月13日下午1:28
感谢您提供更新的答案。 “等级”是我数据的任意属性。我几乎确信我需要一个自定义索引列。看看这个SO链接是否有类似的问题。最佳答案提供有关如何处理此类排名列的建议。
– chitti
2011年9月14日7:45
@chitti-这个问题的公认答案很好。它建议使用与我在此处详细介绍的方法相同的方法，并建议使用小数而不是整数，以极大地扩展您在分配和更改等级时的灵活性。很棒的发现。
–尼克·查马斯（Nick Chammas）
2011-09-14 15:20
#2 楼
我通常使用您描述的“等级”方法。当需要对项目进行重新排序时，我不必花时间去更新行，而是可以删除列表中的所有记录，然后以正确的顺序重新插入新项目，从而摆脱困境。很明显，此方法已优化用于检索。另一种方法是通过使用表上的“前身”反身外键列将记录建模为链接列表：
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
您可以轻松地检索列表并以很少的开销添加和删除项目，但是以正确的顺序取出记录将很棘手。也许有一个聪明的方法可以在单个查询中执行此操作，可能有很多别名表连接。
在对树型关系（类别，文件夹，集和子集）。我通常具有某种递归功能，可以在应用程序中重建完整的树。
评论
链表模型整洁。要在SQL Server中按顺序检索这种层次结构，可以使用递归CTE。
–尼克·查马斯（Nick Chammas）
2011-09-13 3:32
但是，对于一个高脚的桌子，建立这种层次结构会非常昂贵。优点是可以轻松进行等级更改/插入/等。根据chitti的预期负载曲线，这实际上可能是最好的方法。
–尼克·查马斯（Nick Chammas）
2011-09-13 3:37
对于“比较”以外的所有操作，链接列表选项看起来都是最好的主意。任何想法我将如何实现比较而不必跟踪被比较的两个元素之间的路径？
– chitti
2011年9月13日下午5:07
如果您具有项目的ID，我认为Compare（）会很简单，除非我误解了Compare（）的含义。当您说：“如果x> y查找”，您的意思是“如果x在y之前查找”？如果没有自定义索引或可以遍历列表的存储过程（或@Nick提到的有趣的CTE功能），我看不到这容易。
–bpanulla
2011-09-13 22:18
这种类型的解决方案还近似于图形数据模型（en.wikipedia.org/wiki/Graph_theory）。经过优化以存储图形节点和边的存储系统可能比RDBMS更好。三元和四元商店以及Neo4J之类的图形数据库在这方面非常出色。
–bpanulla
2011-09-13 22:25
#3 楼
我认为要做的是存储用于计算排名的一个或多个属性，然后在它们之上建立索引。为什么不让数据库引擎按照设计的目的执行操作，而不是试图强迫数据库按排序顺序物理存储数据或使用手动管理的链表？评论
如果“用于计算等级的属性”是任意的怎么办？例如：一组基于用户的任意操作重新排序的购物车条目。
– chitti
2011年9月14日7:48
当您说等级是任意的时，您是什么意思？必须使用一种算法来计算排名。例如：“基于购物车的条目”-基于如何？数据库中必须存储一些东西，作为排名计算的驱动力。它可能是多种事物的组合，但是这些事物必须以某种方式存储在客户表或与客户相关的表中。如果它在数据中，则可以创建一个计算它的函数。如果可以计算，则可以存储它并对其进行索引。
–乔尔·布朗（Joel Brown）
2011年9月14日上午11:11
假设我们需要维护购物车中商品的顺序，并且用户可以使用Web ui来“任意”更改顺序。您如何将这样的项目列表存储在数据库中，以及如何维护排序顺序？
– chitti
2011年9月15日下午1:55
如果我对您的理解正确，那么通过“任意更改”购物车中商品的顺序，就意味着用户可以在列表中上下拖动商品，并将其放到所需的位置。我想这让我有些吃惊。用户为什么要这样做？如果他们能做到，他们会做很多吗？在购物车中使用简单的物品序列真的对性能有很大影响吗？在我看来，从1到购物车中物品的数量再加上FK到订单的序列号将为您提供所需的索引。只需在拖拽物品时更新物品即可。
–乔尔·布朗（Joel Brown）
2011-09-15 3:22
购物车只是我给出的一个例子，表明在某些情况下“等级”可以是任意的。可能那不是一个很好的例子。 netflix dvd队列可以是一个更好的示例。仅出于争论的目的，想象一下一个netflix队列，其中包含100k项，可由用户任意重新排序，并且他每分钟执行一次。在这个假设的应用程序中，您将如何设计一个数据库来存储电影的有序列表？
– chitti
2011-09-15 3:30
#4 楼
这些是诸如simpleDB之类的非RDBMS的局限性。您所需的功能不能在simpleDB的DB端实现，必须从编程端/应用程序实现。对于像
SQL server这样的RDBMS，所需的功能对聚簇索引是基本的。Insert（x）-将记录x插入表中>简单插入。
Delete（x）-从表中删除记录x>简单删除。 > Before（x，n）-返回排序列表中记录x之前的'n'条记录。 >选择前n个结果，其中x小于值并按子句排序。
之后（x，n）-返回排序列表中记录x之后的'n'个记录。 >选择前n个结果（其中x大于值并按子句排序）。
First（n）-从排序列表中返回前'n'个记录。 >选择前n个结果。
最后（n）-返回已排序列表中的最后“ n”个记录。 >按先后顺序选择前n个结果。
比较（x，y）-给定表中的两个记录x和y，确定x> y。 > TSQL IF语句。
评论
SimpleDB确实提供自动索引，排序和基本查询语言。即使选择RDBMS，我的问题仍然存在。问题是因为数据库中数据的排名会随意更改，并且无法将它们捕获为可以建立索引的单个属性（除非使用自定义排名列）。
– chitti
2011-09-14 8:01
评论
详细说明您的预期负载配置文件。每天有多少次选择/插入/更新？您最想优化哪些操作？您希望桌子每天增加或增加多少？这是球员排名委员会吗？无论如何，我已经根据您的预期负载配置文件在下面用反馈更新了我的答案。
不，它不是球员排名委员会。
您最终使用了什么方法？
我什至不确定这里要问的是什么，或者从洗衣清单中不需要做的事情。