在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)，但是速度很快，因为索引在内存中。

如果分数变化如此之快，就很难找到一个很好的数据结构来计算排名。根据分数变化的多少，可能会有一些优化查询的方法。