数据库排序的时间复杂性

Question

我目前正在开发一个移动应用程序，并使用Codeigniter MySQL。我现在面临的情况是，我有一张书表(这个表将是带有记录的100k+ )。在这个表中，我有一个名为NotSelling的列。db示例：

Book A 45
Book B 0
Book C 159
Book D 78
.
.
.
Book Z 450

上面的数字是显示在db中的NotSelling列中的数字。我需要从这张大桌子上提取前20本书。现在，我的解决方案是对表进行排序，然后使用TOP提取前20条记录。

我想知道的是对桌子进行排序的性能。正如我所确定的那样，不断地对表格进行排序，仅仅获得前20名的结果将需要一段相当长的时间。我已经得到了解决这个问题的办法：

• 索引NotSelling问题。
• 缓存查询(但我已经阅读过粗失效，这可能会导致问题，就我的情况而言，失效频率会很高)
• 对表进行排序，获取前20项记录，将它们放在另一张表中，然后定期更新表，大约每小时就更新一次。

但是，所有这些是否有人知道这个问题的更好的解决方案，或者有一种方法/方法来优化我想要做的功能的性能？请注意，我是一个新手，所以如果任何人能够指出我在正确的方向，我可以阅读有关数据库的性能，我会非常感激。

Answer 1

我觉得你想的太多了。这绝对是一个过早优化的案例。尽管上述所有解决方案都是完全有效的。您应该知道，100K+记录对Mysql来说是比较好的。我们过去经常在有30行order行的表上使用优秀的perf。

但是，必须对要排序的列进行索引，并对表模式进行双重检查。注册表。缓存也不要担心，当表没有更改时，mysql会为重复查询执行缓存。但列索引是必要的、首要的、最重要的要求。

Answer 2

不要担心排序的性能。如果事实证明这是一个问题，则可以通过添加索引来在稍后的时间在数据库中修复这个问题。

在设计阶段，优化是分散注意力的。相反，请关注实现所代表的问题的功能和直接性。只要这些都是目标，其他的东西就可以相对容易地固定下来。

Answer 3

根据支持列的索引的数据结构中保存什么样的元数据，可以在O(n)时间内进行遍历，而n是返回的项目数。

这意味着，从理论上讲，无论你有100万还是200万亿的记录，只要你有一个指数，把前20个记录拉出来的速度就会一样快。在实践中，会有性能差异，因为一个小的索引将适合内存，而一个大的索引将不得不使用磁盘。

总之，你太担心了。作为Srikar Appal，一个正确索引的100 k记录表对MySQL来说不算什么。