设计带时间范围查询的键值存储系统

题目

设计带时间范围查询的键值存储系统

信息

• 类型：问答
• 难度：⭐⭐

考点

哈希表设计,时间范围查询,数据结构组合应用

快速回答

设计一个支持时间戳的键值存储系统，需要实现以下功能：

• put(key, value, timestamp)：存储带时间戳的键值对
• get(key, timestamp)：获取指定时间戳的键值（若不存在则返回最近的值）
• get_range(key, start, end)：获取键在时间范围内的所有值

核心解决方案：

1. 使用外层哈希表：以键为索引，值为时间有序列表
2. 内层数据结构：使用平衡二叉搜索树（TreeMap）或时间戳排序的数组存储时间戳-值对
3. 范围查询：通过二分查找快速定位时间范围

问题分析

需要设计一个支持时间版本化的键值存储，常见于监控系统、历史记录追踪等场景。核心挑战在于高效处理时间维度查询，同时保证基础操作的性能。

数据结构设计

from collections import defaultdict
import bisect

class TimeMap:
    def __init__(self):
        # 外层哈希表：key → 时间戳有序列表
        self.store = defaultdict(list)

    def put(self, key: str, value: str, timestamp: int) -> None:
        # 插入时保持时间戳升序（时间复杂度 O(1) 到 O(n)）
        bisect.insort_left(self.store[key], (timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        # 二分查找最近时间戳（时间复杂度 O(log n)）
        arr = self.store.get(key, [])
        idx = bisect.bisect_right(arr, (timestamp, chr(127))) - 1
        return arr[idx][1] if idx >= 0 else ""

    def get_range(self, key: str, start: int, end: int) -> list:
        # 范围查询（时间复杂度 O(log n + k)）
        arr = self.store.get(key, [])
        left = bisect.bisect_left(arr, (start, ""))
        right = bisect.bisect_right(arr, (end, chr(127)))
        return [val for _, val in arr[left:right]]

关键原理说明

• 外层哈希表：提供 O(1) 的键访问，值使用时间戳有序的数据结构
• 二分查找优化：利用 bisect 模块快速定位时间点（时间复杂度 O(log n)）
• 范围查询：通过两次二分查找确定起止位置，只需 O(log n + k) 时间（k 是结果数量）

最佳实践

• 选择有序结构：Python 中使用列表+二分足够高效，Java/C++可用 TreeMap
• 时间戳处理：确保时间戳单调递增（如使用 UTC 毫秒时间戳）
• 内存优化：若数据量极大，考虑分片存储或使用时间序列数据库

常见错误

• 错误1：使用无序字典存储时间戳，导致查询效率 O(n)
• 错误2：未处理时间戳不存在时的最近值查询
• 错误3：范围查询时未利用有序特性进行优化

扩展知识

• 生产级优化：使用跳表（SkipList）替代数组，平衡插入和查询效率
• 数据库应用：类似设计见于 InfluxDB 的时间序列存储引擎
• 分布式扩展：通过一致性哈希将键分布到不同节点
• 冷热分离：近期数据用内存存储，历史数据转存磁盘