在海量数据中如何去获取TOPK,或者如何查询一个数据的排名。
常见的方法:
mysql索引存储
这种方法根据设置一个排行分数作为索引即可,但在海量数据场景下,它的查询性能变得低下,占用的内存也很高,只适合数据量不高和对性能要求不高情况下。
区间排序树
思路:比如存储100万个数据,以积分作为排行分数。
我们可以把[0,1000000]一级区间分为两个二级区间[0,500000)和[500000,1000000],在将二级区间往下细分,直到划分21级区间为[0,1),[1,2)…
这种思想二分查找和二叉查找树类似。
比如,需要查找一个积分为490000数据的排名,那么在是属于一级区间的[0,500000)当中的,那么的它的排名应该在[500000,1000000]count个用户后面,所以它的排名应该+= count ,然后继续往[0,500000]的右子树区间[250000,500000]查找,它在右子树,排名在[0,250000)用户前面,故不需要+=count,类似继续往下,直到[490000,490001)区间,就是这个数据的排名了。