百分位排序方法全解析：从百行数据到亿级并发的技术选型

Xilejun 5 min read

从百行数据到亿级并发的百分位排序技术选型，详解精确算法与近似算法的适用场景。

以航旅纵横"飞行里程超越全国 X% 旅客"为切入点，系统讲解不同数据规模下的百分位计算方案。

一、问题从何而来

航旅纵横 App 中，每位旅客打开年度账单时都会看到一行字：

"您的年度飞行里程 25,000 公里，超越了全国 93.2% 的旅客。"

这背后是一个经典的数据问题：给定一个值，快速求出它在整体分布中的百分位。

看似简单，但当数据量从一千行涨到六亿行、从单机查询变成万级并发时，"排序"这件事的解法会发生质的变化。

本文按照数据量从小到大的顺序，逐一分析各方案的技术原理、适用边界和工程取舍。

二、数据规模与方案概览

方案 | 适用数据量 | 精度 | 查询延迟 | 实现复杂度

--- | --- | --- | --- | ---

全量排序 | < 100 万行 | 精确 | 秒级 | 低

分桶预计算 | 百万 ~ 十亿行 | 可控（取决于桶粒度） | 毫秒级 | 中

近似 sketches（T-Digest / CKMS） | 亿 ~ 千亿级 | 近似（误差 < 0.5%） | 毫秒级 | 中高

采样估计 | 十亿+ 行 | 统计近似 | 毫秒级 | 低

分布式排序 | PB 级 | 精确 | 分钟级 | 高

下面逐一展开。

三、方案一：全量排序（小数据场景）

3.1 原理

最直接的方法——把所有数据排好序，用值的排名除以总数得到百分位。

SQL 实现：

SELECT
    pax_id,
    total_distance,
    PERCENT_RANK() OVER (
        ORDER BY total_distance
    ) AS percentile
FROM pax_flight_annual
WHERE year = 2025;

Python 实现：

import numpy as np

# 给定一个里程值，求它在分布中的百分位
mileage = 25000
all_mileages = np.array([...])  # 所有旅客里程
percentile = (np.searchsorted(np.sort(all_mileages), mileage) / len(all_mileages)) * 100
# 结果：93.2

3.2 时间复杂度

操作 | 复杂度

--- | ---

排序 | O(N log N)

单次查询（预排序数组中二分查找） | O(log N)

3.3 适用场景

  • 团队内部数据分析（几千 ~ 几万行）
  • 离线报表生成（数据量可控，对延迟不敏感）
  • 单次计算而非实时服务

3.4 优点

  • 实现极其简单——一个 SQL 窗口函数或一行 NumPy 调用
  • 结果精确——没有任何近似
  • 灵活性高——可以同时计算任意百分位（P50、P90、P99）
  • 不需要预处理——随用随算

3.5 缺点

  • 无法扩展——N = 6 亿时，排序耗时数分钟，无法满足在线查询
  • 内存开销大——全量数据必须驻留内存或磁盘
  • 并发差——每次查询都要重新排序或维护全量有序结构
  • 数据更新代价高——新增一条记录，需要重新排序

四、方案二：分桶预计算（中大数据场景）

4.1 原理

将数据按值域划分为若干个桶（bucket），预先统计每个桶内的数据量及累计百分位。查询时，只需找到目标值所在的桶，直接读取预计算的百分位。

这正是航旅纵横最可能采用的方案。

数据结构：

CREATE TABLE mileage_percentile_bucket (
    year            INT,
    bucket_key      INT,           -- 里程桶下界
    bucket_upper    INT,           -- 里程桶上界
    pax_count       BIGINT,        -- 桶内旅客数
    cumulative_pct  DECIMAL(6,4),  -- 累计百分位
    PRIMARY KEY (year, bucket_key)
);

示例数据：

里程桶 (km) | 旅客数 | 累计旅客数 | 累计百分位

--- | --- | --- | ---

0 - 500 | 180,000,000 | 180,000,000 | 30.00%

500 - 1,000 | 90,000,000 | 270,000,000 | 45.00%

1,000 - 2,000 | 90,000,000 | 360,000,000 | 60.00%

2,000 - 5,000 | 90,000,000 | 450,000,000 | 75.00%

5,000 - 10,000 | 60,000,000 | 510,000,000 | 85.00%

10,000 - 30,000 | 54,000,000 | 564,000,000 | 94.00%

30,000 - 100,000 | 27,000,000 | 591,000,000 | 98.50%

100,000+ | 9,000,000 | 600,000,000 | 100.00%

查询过程（两步）：

-- Step 1: 查该旅客里程
SELECT total_distance FROM pax_flight_annual
WHERE pax_id = 12345 AND year = 2025;
-- → 25000 km

-- Step 2: 查桶表得到百分位
SELECT cumulative_pct FROM mileage_percentile_bucket
WHERE year = 2025 AND bucket_key <= 25000
ORDER BY bucket_key DESC LIMIT 1;
-- → 94.00%

4.2 桶的划分策略

桶的划分直接影响精度和存储成本。三种常见策略：

等宽分桶（Equal-Width）

[0, 10000), [10000, 20000), [20000, 30000), ...
  • 优点：实现简单
  • 缺点：数据分布不均时（如飞行里程极度右偏），低密度区域浪费桶数，高密度区域精度不足

等频分桶（Equal-Frequency / Quantile Bucket）

每个桶内的数据量大致相等
  • 优点：每个桶的精度一致
  • 缺点：桶的边界不规则，需要预排序才能确定边界

对数分桶（Logarithmic）

[0, 100), [100, 200), [200, 400), [400, 800), ... [65536, 131072)
  • 优点：低值区精度高（大多数用户所在区间），高值区精度适中
  • 缺点：实现稍复杂

推荐：对于右偏分布（如飞行里程），对数分桶或等频分桶是最优选择。

4.3 桶内线性插值（提升精度）

粗桶不够精确时，可在桶内做线性插值：

假设目标值 25000 km 落在 [10000, 30000) 桶内
桶下界百分位 = 85.00%，桶上界百分位 = 94.00%
插值：85.00% + (25000 - 10000) / (30000 - 10000) × (94.00% - 85.00%)
    = 85.00% + 0.75 × 9.00%
    = 91.75%

精度从「桶级误差」提升到「接近精确」。

4.4 时间复杂度

操作 | 复杂度

--- | ---

预计算（批量聚合） | O(N)（全表扫描一次）

单次查询 | O(log B)，B = 桶数量

数据更新 | O(1)（更新事实表），桶表定时刷新

4.5 适用场景

  • 数据量百万到数十亿级
  • 值域范围已知且相对稳定
  • 需要毫秒级在线响应
  • 查询维度有限（如仅按里程）

4.6 优点

  • 查询极快——O(log B)，B 通常在 2000 以下，近似 O(1)
  • 存储成本极低——几千行桶表 vs 数亿行原始数据
  • 可缓存——桶表可常驻 Redis，进一步提升响应速度
  • 支持高并发——读操作无锁竞争

4.7 缺点

  • 精度受桶粒度限制——除非桶极细，否则有量化误差
  • 维度爆炸——如果要同时支持"里程百分位"、"飞行次数百分位"、"城市覆盖百分位"，每种维度都需要独立的桶表
  • 值域变化需要重建桶——如旅客里程逐年增长，桶边界需要调整
  • 非实时——桶表需要离线批处理刷新（通常 T+1）

五、方案三：近似 Sketch 算法（超大数据场景）

5.1 为什么需要近似算法？

当数据量达到亿级以上，且需要：

  • 流式处理（数据持续涌入，不能存全量）
  • 多维度查询（里程、次数、金额等，每种都要百分位）
  • 任意百分位（不限于预定义的桶边界）

此时分桶预计算也不够用了。Sketch（草图）算法应运而生。

5.2 T-Digest

核心思想：用一组"质心点"（centroids）来近似表示整个数据分布。

原始数据：[100, 200, 300, 500, 800, 1200, 2000, 5000, 10000, 50000]

T-Digest 质心点（压缩后）：
[(100, 0.05), (350, 0.20), (1000, 0.45), (5000, 0.65), (50000, 0.95)]
  ↑ 值      ↑ 估计分位

每个质心包含两个信息：均值和权重（该质心代表多少个数据点）。

关键特性——自适应精度：

  • 在分布的尾部（p99、p01 等极端分位），质心更密集，精度更高
  • 在分布的中部（p50），质心较稀疏，精度略低
  • 这恰好符合业务需求：我们更关心"你是不是前 1%"，而不太关心"你是不是前 51%"

精度表现：

分位区间 | 典型精度

--- | ---

p1, p99 | 误差 < 0.1%

p5, p95 | 误差 < 0.5%

p25, p50, p75 | 误差 < 1%

内存占用：

  • 压缩比通常 100:1 到 1000:1
  • 6 亿个数据点 → 约 3000-5000 个质心 → 内存 < 100 KB

使用方式（PostgreSQL）：

-- 安装扩展
CREATE EXTENSION tdigest;

-- 构建摘要
SELECT tdigest(total_distance) AS dist
FROM pax_flight_annual
WHERE year = 2025;

-- 从摘要中查询任意百分位
SELECT
    tdigest_percentile(dist, 0.5)  AS p50,   -- 中位数
    tdigest_percentile(dist, 0.932) AS p93_2, -- 第93.2百分位
    tdigest_cdf(dist, 25000) AS pct          -- 25000km对应的百分位
FROM summary_table
WHERE year = 2025;

5.3 CKMS Quantile Sketch

Cormode-Korn-Muthukrishnan-Srivastava 算法，Streaming 百分位查询的经典方案。

与 T-Digest 的区别：

维度 | T-Digest | CKMS

--- | --- | ---

精度策略 | 自适应（尾部更精确） | 均匀（全程固定精度 ε）

合并方式 | 支持高效 merge | 原生支持 merge

数学保证 | 启发式，无严格界 | 有严格 ε-近似保证

实现复杂度 | 中等 | 中等

适用场景 | 需要尾部高精度 | 需要全程均匀精度

CKMS 的核心参数 ε 控制精度。设 ε = 0.001，则任何百分位的误差不超过 0.1%。

内存占用：O((1/ε) × log(εN))，N 为数据量。ε = 0.001 时，6 亿数据点约需几十 KB。

5.4 DDSketch（DataDog 开源）

核心创新：用对数桶替代线性桶，天然适合长尾分布。

值域映射到桶索引：
bucket_index = floor(log(value) / gamma)

gamma 越小，桶越细，精度越高

优势：

  • 对长尾分布精度极高（天然匹配飞行里程这种右偏分布）
  • 支持快速 merge（不同节点上的 sketch 可以高效合并）
  • 数学上有严格的相对误差保证

5.5 适用场景

  • 数据量亿级以上
  • 数据流式到达（不可回溯、不可存储全量）
  • 需要同时查询多个维度、多个百分位
  • 监控系统（如 Prometheus 的 histogram 就基于类似思想）
  • 分布式场景（各节点本地计算 sketch，中心节点合并）

5.6 优点

  • 内存极小——百万分之一压缩比，百亿数据仅需几 MB
  • 流式友好——数据到来时增量更新，不需要全量存储
  • 可合并——分布式场景下各节点 sketch 可高效聚合
  • 精度可控——通过参数调节精度/内存的平衡
  • 多维度扩展性好——每种维度一个 sketch，互不干扰

5.7 缺点

  • 结果是近似的——无法返回精确值（对于排行榜等场景不适用）
  • 实现复杂度高——需要引入第三方库或自研
  • 调试困难——sketch 是压缩摘要，无法还原原始数据
  • 不支持精确的 COUNT 或 SUM——sketch 只回答分位数问题

六、方案四：采样估计（快速粗算场景）

6.1 原理

不处理全量数据，而是随机采样一部分，用样本的百分位估计总体的百分位。

import random

# 6亿数据中随机采样10万条
population = [...]  # 全量数据（或流式采样）
sample = random.sample(population, 100000)
sample.sort()

# 查询百分位
percentile = (bisect.bisect_left(sample, 25000) / len(sample)) * 100

6.2 采样方法

均匀随机采样：每条数据以固定概率 p 被选中。

蓄水池采样（Reservoir Sampling）：适用于流式数据，不需要预先知道总量。

import random

def reservoir_sample(stream, k):
    reservoir = []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)
        else:
            j = random.randint(0, i)
            if j < k:
                reservoir[j] = item
    return reservoir

6.3 适用场景

  • 数据量极大（十亿+），且"大致准确"就够了
  • 临时分析、快速探索
  • 数据无法全量获取（如外部 API 限流）

6.4 优点

  • 实现最简单——几十行代码
  • 内存可控——只保留样本
  • 速度快——不需要全量处理

6.5 缺点

  • 统计误差——样本量 10 万时，P95 的置信区间约 ±0.3%
  • 尾部精度差——极端值（P99.9）在样本中可能不出现
  • 不可重复——每次采样结果不同
  • 不适合精确场景——"你超越了 93.2%"变成"你大约超越了 93% 左右"

七、方案五：分布式排序（PB 级精确计算）

7.1 原理

当数据量超过单机处理能力（PB 级），将数据分片到多个节点，各自排序后合并。

节点1: 排序后 → [quantile_1_1, quantile_1_2, ..., quantile_1_k]
节点2: 排序后 → [quantile_2_1, quantile_2_2, ..., quantile_2_k]
节点3: 排序后 → [quantile_3_1, quantile_3_2, ..., quantile_3_k]
                ↓ 合并
全局百分位

MapReduce 伪代码：

# Map: 每条记录发送到对应分片
def map(record):
    shard = hash(record.pax_id) % num_shards
    emit(shard, record.total_distance)

# Reduce: 每个分片内部排序，计算本地百分位
def reduce(shard, distances):
    distances.sort()
    n = len(distances)
    # 输出百分位锚点
    for p in [0.01, 0.05, 0.10, ..., 0.99]:
        emit(p, distances[int(p * n)])

7.2 适用场景

  • PB 级数据仓库
  • 需要精确结果
  • 离线批处理（日级别刷新可接受）

7.3 优点

  • 精确——无近似
  • 可横向扩展——增加节点即可处理更多数据
  • 成熟——Hadoop/Spark 生态支持完善

7.4 缺点

  • 延迟高——分钟到小时级
  • 成本高——需要集群资源
  • 工程复杂——需要维护分布式基础设施

八、方案对比与选型决策

8.1 全景对比

维度 | 全量排序 | 分桶预计算 | T-Digest / CKMS | 采样 | 分布式排序

--- | --- | --- | --- | --- | ---

**数据规模** | < 100 万 | 百万 ~ 十亿 | 亿 ~ 千亿 | 十亿+ | PB+

**精度** | 精确 | 可控（取决于桶） | 近似（误差 < 0.5%） | 统计近似 | 精确

**查询延迟** | 秒 ~ 分钟 | < 5 ms | < 5 ms | < 5 ms | 分钟 ~ 小时

**内存占用** | O(N) | O(B)，B≈2000 | O(1/ε × log N) | O(样本量) | O(N/节点)

**实时性** | 随用随算 | T+1 刷新 | 近实时 | 实时 | T+1 批处理

**实现复杂度** | 低 | 中 | 中高 | 低 | 高

**多维度扩展** | 简单 | 每维度一张桶表 | 每维度一个 sketch | 每维度一个样本 | 需多轮 MR

**典型产品** | Excel / pandas | 航旅纵横 / 支付宝年度账单 | Prometheus / DataDog | 快速数据分析 | Hive / Spark

8.2 决策树

数据量是否 < 100 万？
├── 是 → 全量排序
│        精确、简单、够用
└── 否 → 需要精确结果吗？
         ├── 是 → 数据量 > PB？
         │        ├── 是 → 分布式排序
         │        └── 否 → 分桶预计算（细粒度桶 + 桶内插值）
         └── 否 → 数据是否流式到达？
                  ├── 是 → T-Digest / CKMS（流式 sketch）
                  └── 否 → 需要多维度吗？
                           ├── 是 → T-Digest / CKMS（多 sketch）
                           └── 否 → 分桶预计算（最简单高效）

九、实战建议

9.1 你的数据量在哪个区间？

场景 | 典型数据量 | 推荐方案

--- | --- | ---

团队 KPI 排名 | 几十 ~ 几千 | 全量排序

企业内部 BI 仪表盘 | 几万 ~ 几百万 | 全量排序 或 分桶

全国性 C 端产品（航旅纵横级别） | 数亿 | 分桶预计算

超大规模监控（APM、流量分析） | 十亿+ / 天 | T-Digest / CKMS

数据仓库离线分析 | PB 级 | 分布式排序

9.2 工程落地 Checklist

选分桶预计算时：

  • [ ] 确认数据的分布形态（是否偏态？是否有极端值？）
  • [ ] 选择合适的分桶策略（等宽 / 等频 / 对数）
  • [ ] 确定桶数量（精度 vs 存储的平衡点）
  • [ ] 设计桶内插值逻辑（避免桶边界处的跳变）
  • [ ] 建立桶表的离线刷新 pipeline
  • [ ] 在 Redis 中缓存桶表，应对高并发

选 T-Digest / CKMS 时：

  • [ ] 评估可接受的误差范围（ε）
  • [ ] 选型：尾部精度优先 → T-Digest；全程均匀 → CKMS；长尾分布 → DDSketch
  • [ ] 设计分布式 merge 策略（如果多节点）
  • [ ] 确定存储格式（二进制序列化）
  • [ ] 建立定期全量重建机制（防止 sketch 漂移）

9.3 一个常见的误区

"我们数据量大，用分布式排序就能解决一切。"

错误。 分布式排序解决的是"算得出来"，但没有解决"算得快"。对于在线查询场景，无论用多少台机器，全量排序都不可能做到毫秒级。

正确的思路是：将"计算"和"查询"分离——离线用复杂方法（全量排序 / sketch 聚合）生成摘要，在线用简单方法（查桶 / 查 sketch）返回结果。

十、总结

百分位计算的本质是在精度、速度和资源之间做取舍：

  • 小数据：直接排序，简单粗暴但最精确
  • 中大数据：分桶预计算，用极低的存储成本换取毫秒级查询
  • 超大数据：Sketch 算法，用可接受的近似误差换取极小的内存占用
  • PB 数据精确计算：分布式排序，用时间和资源换取精确结果

航旅纵横的"超越全国 X% 旅客"功能，完美诠释了分桶预计算方案的价值——6 亿行原始数据，压缩为 2000 行桶表，查询从分钟级降到毫秒级，这就是"空间换时间"的力量。

*本文基于工程实践总结，如有疏漏欢迎交流。*

作者：xilejun · v1.0 · 2026-05-05

📖 相关文章
● Tableau 自定义 SQL 参数化 + Apache Doris 倒排索引：亿级大表的毫秒级实时点查实践
● 8.1  计算的演进及分类：从Excel、SQL到Tableau
● SQL函数分类新思路：基于计算上下文的PostgreSQL速查表
● SQL 别裁新解：PostgreSQL函数分类速查表
● 大数据太慢？Tableau Server 优化性能方法一览
——————————————————————————————

No comments yet

Continue reading