我有几百万条记录(经常更新(，有两个属性：
- 时间戳
- 人气得分
我正在寻找一种数据结构(也许是某种度量树？(，它可以在一维上进行快速范围搜索(例如，所有大于时间戳值的记录(，并在另一个维度上定位位于该范围内的前K个记录(即流行度得分(。换句话说，我可以将这个查询表述为"；查找时间戳大于T〃的前K个流行记录；。
我目前有一个简单的实现，我在线性时间复杂度中过滤N个记录，然后使用部分排序算法识别前K个记录。但考虑到我们需要支持的并发用户数量，这还不够快。
我对KD树不是很熟悉，但我看到一些流行的实现同时支持范围搜索和查找K个最近的邻居，但我的要求在这里有点特殊——所以我想知道是否有一种方法可以更快地做到这一点，而可能会牺牲额外的索引开销。
如果您将按照时间戳对元组列表(record_name, timestamp)进行初始排序，并创建一个以记录名称为键、以(popularity_score, timestamp_list_idx)元组为值的字典，您将能够：
- 对特定时间戳O(logn(执行二进制搜索
- 提取O(1(中大于的值，因为数组已排序
- 提取O(1(中匹配的人气投票，因为它们在字典中
- 根据字典更新O(1(中的受欢迎程度得分记录
- 通过从字典值中的元组中提取记录的索引来更新O(1(中的特定时间戳
假设您有具有所需时间戳范围的m记录，则可以
- 根据流行度从它们生成一个最大堆，这需要O(m(，然后用O(klogm(从该堆执行
k弹出，因为我们需要在每次弹出后重新填充根。这意味着您要执行的操作将采用O(m+klogm(。假设k << m，这将在O(m(中运行 - 用大小为
k的列表遍历m唱片，以跟踪最受欢迎的k歌曲。在传递完所有m记录后，您将获得列表中的前k。这也需要O(m(
就复杂性而言，方法1比方法2花费的时间稍长，但如果您突然想知道k+1最受欢迎的记录，您可以从堆中弹出另一项，而不是用k+1长列表再次传递整个m记录。