设计支持范围查找的日志时间戳系统

题目

设计支持范围查找的日志时间戳系统

信息

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

考点

数据结构设计, 二分查找, 平衡树/线段树

快速回答

设计一个高效的数据结构支持以下操作：

• insert(timestamp): 插入时间戳
• query(start, end): 返回 [start, end] 范围内的所有时间戳

核心实现方案：

1. 使用平衡二叉搜索树（如Java的TreeSet）或跳表存储数据
2. 插入操作保持有序性（平均O(log n)）
3. 范围查询利用二分查找定位边界（O(log n + k)，k为结果数量）
4. 替代方案：线段树（适合频繁范围查询但插入较少场景）

问题背景

在日志处理系统中，需要高效存储时间戳并支持快速范围查询（如查询9:00-10:00的所有日志）。数据量可能达到百万级，要求插入和查询都高效。

核心解决方案

1. 平衡二叉搜索树（推荐）

import java.util.*;

class LogSystem {
    private TreeSet<Long> timestamps;

    public LogSystem() {
        timestamps = new TreeSet<>();
    }

    // O(log n) 插入
    public void insert(long timestamp) {
        timestamps.add(timestamp);
    }

    // O(log n + k) 范围查询
    public List<Long> query(long start, long end) {
        return new ArrayList<>(timestamps.subSet(start, true, end, true));
    }
}

原理说明：

• TreeSet基于红黑树实现，自动维护有序性
• subSet()方法利用树的有序特性快速定位边界
• 查询时先通过二分查找定位start节点（O(log n)），然后线性遍历后继节点直到end（O(k)）

2. 跳表（SkipList）实现

from sortedcontainers import SortedList

class LogSystem:
    def __init__(self):
        self.timestamps = SortedList()  # 基于跳表实现

    def insert(self, timestamp: int) -> None:
        self.timestamps.add(timestamp)  # O(log n)

    def query(self, start: int, end: int) -> List[int]:
        left = self.timestamps.bisect_left(start)  # 二分找左边界
        right = self.timestamps.bisect_right(end)   # 二分找右边界
        return self.timestamps[left:right]  # O(k)

3. 线段树（备选方案）

// 适用于值域已知且范围不大的场景
class SegmentTree {
    vector<vector<int>> tree;
    int n;

    void update(int idx, int l, int r, int pos, int val) {
        if (l == r) {
            tree[idx].push_back(val);
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) update(2*idx, l, mid, pos, val);
        else update(2*idx+1, mid+1, r, pos, val);
        tree[idx].push_back(val);
    }

    void query(int idx, int l, int r, int ql, int qr, vector<int>& res) {
        if (ql > r || qr < l) return;
        if (ql <= l && r <= qr) {
            for (int t : tree[idx]) res.push_back(t);
            return;
        }
        int mid = (l + r) / 2;
        query(2*idx, l, mid, ql, qr, res);
        query(2*idx+1, mid+1, r, ql, qr, res);
    }
};

最佳实践

• 首选平衡树/跳表：JDK的TreeSet或Python的SortedList已高度优化
• 内存优化：若时间戳范围固定，可考虑位图或压缩存储
• 分页支持：实际系统中应支持分页查询，避免返回超大结果集
• 并发场景：使用ConcurrentSkipListSet（Java）或读写锁

常见错误

• 错误1：使用无序数组，导致查询需要O(n)扫描
• 错误2：用哈希表存储，无法高效支持范围查询
• 错误3：手写平衡树时忽略旋转操作导致退化
• 错误4：线段树未做离散化导致内存爆炸

扩展知识

• LSM树：LevelDB/RocksDB的存储引擎，适合写多读少场景
• B+树：数据库索引标准结构，优化磁盘访问
• 时间序列数据库：专用TSDB（如InfluxDB）使用时间分片+列式存储
• 复杂度对比：

  数据结构	插入	查询	内存
  平衡树	O(log n)	O(log n + k)	O(n)
  线段树	O(log n)	O(log n + k)	O(n log n)
  有序数组	O(n)	O(log n + k)	O(n)