mysql - 在 MySQL 中查找条目的百分位数分数的时间复杂度是多少？

Question

我们有一个动态的集合(排名每隔几分钟就会改变)。我们想要显示用户的百分位数分数。

在 MySQL 中查找用户的排名/百分位数的时间复杂度是多少？(忽略所有磁盘寻道，假设整个索引都在 RAM 中)

MySQL 是否在索引中存储额外信息以加快计算速度？

我正在使用的查询:

SELECT COUNT(*) FROM score_table WHERE score>X"

SELECT COUNT(*) FROM score_table;

Answer 1

对于此查询:

SELECT COUNT(*)
FROM score_table
WHERE score > X;

我非常确定 MySQL 会从“X”之后的值开始扫描索引。我不认为它对计算索引中叶子的大小进行了优化。因此，此操作的时间复杂度为 O(n)，但速度会很快，因为索引位于内存中。

如果分数变化如此之快，很难想出一个好的数据结构来计算排名。根据分数变化的程度，您可能可以采取一些技巧来优化查询。