概率型数据结构专栏 - 专栏

1. HyperLogLog：用 12KB 近似统计海量去重数

HyperLogLog 用极小的固定内存（Redis 实现仅 12KB）估算数据集中不同元素的数量（基数），误差约 0.81%。Redis 的底层实现。

2026-07-30

2. Count-Min Sketch：用 KB 内存估算海量数据频率

Count-Min Sketch 用 KB 级固定内存估算数据流中每个元素的出现频率，误差单侧高估（永远不会低估）。常用于 Top-K 统计、网络流量分析、数据库查询频率估算。

2026-07-30

3. 跳表：用概率分层实现 O(log n) 有序索引

跳表用概率随机化替代传统平衡树的严格旋转，实现了 O(log n) 期望复杂度的有序集合。Redis ZSet、LevelDB、RocksDB 均使用跳表作为核心数据结构。

2026-07-30

4. T-Digest：高精度估算 p99 与 p999 分位数

T-Digest 解决流式数据的分位数估算问题（p50/p99/p999），核心洞察是"越靠近边界的质心越精确"，使得极端分位数（如 p99.9）的精度远高于普通近似方法。Prometheus、Elasticsearch、InfluxDB 均内置 T-Digest。

2026-07-30