当前位置：首页 > news >正文

什么是低基数什么是高基数

news 2026/7/5 12:36:13

在数据库和存储引擎的语境中，基数指的是某个字段中不同唯一值的数量。

假设你有1000 万条文档：

因为不同的压缩/索引方案对基数的敏感度完全不同，这也是上一轮讨论各种数值存储方案时反复提到基数的原因：

字典编码的压缩率 ≈log₂(基数) / 原始位宽。基数越低，收益越大；当基数接近文档总数时，字典 + ID 序列反而比原始数据更大。
位图索引的空间 ≈基数 × 文档数 / 8。基数翻倍，空间翻倍。所以只对低基数字段建位图。
Lucene 的位宽自适应：numBitsPerValue = ceil(log₂(max - min + 1))。它不关心有多少唯一值，只关心值域跨度。所以即使基数很高，只要值域集中（比如 1000 万个文档的值都在 0~65535 之间），仍然只需 16 bits/值，压缩效果很好。
B-Tree 的查询效率取决于区分度。低基数时等值查询返回海量行，索引选择性差；高基数时近似 O(log N)，效率高。

一句话记忆：基数 = 唯一值个数。选存储/索引方案前，先问自己"这个字段有多少种不同的值"，答案直接决定了哪种方案最合适。

Lucene 当前采用的“位宽自适应 + 分块/全局二选一”方案，本质上是一种面向随机访问的轻量级列存压缩。但在更广泛的数据库和存储引擎领域，针对数值型数据还有多种截然不同的方案。

以下按设计哲学分类梳理：

代表系统：ClickHouse (LowCardinality)、Apache Doris、Elasticsearch Keyword
核心思想：不直接存数值本身，而是将每个唯一值映射为一个整数 ID，再对 ID 序列做压缩。
适用场景：低基数数值（状态码、枚举、年龄等）
与 Lucene 的区别：Lucene 的 SortedNumericDocValues 不做字典编码；它假设值是连续或近似连续的整数，直接用位宽压缩。字典编码在低基数时空间效率远超位宽压缩，但高基数时字典本身的开销会成为瓶颈。

代表系统：Parquet / ORC / Arrow、DuckDB
核心思想：在 RLE / Delta / Bit-Packing 之上，叠加通用块压缩器。
典型组合：Delta Encoding → RLE → ZSTD/LZ4/Snappy
与 Lucene 的区别：Lucene 的.dvd不使用任何通用压缩器（不用 LZ4/ZSTD），因为 DocValues 需要 O(1) 随机访问，通用压缩器的解压代价不可接受。Parquet/ORC 是面向批量扫描优化的，可以容忍解压开销换取更高压缩率。

代表系统：FastPFOR、StreamVByte、SIMD-BitPacking
核心思想：利用 CPU 的 SIMD 指令集，一条指令同时处理 128/256/512 bit 的位宽打包/解包。
与 Lucene 的区别：Lucene 的PackedInts/DirectWriter是纯标量 Java 实现。FastPFOR 等库在解码吞吐上可达 Lucene 的5~10 倍，但通常作为底层编解码库嵌入使用，而非独立的存储格式。Lucene 10+ 已开始引入 Panama Vector API 做类似优化。

代表系统：InnoDB (B+Tree)、RocksDB / LevelDB (LSM)
核心思想：数值作为 Key 或 Value 的一部分，按排序结构组织，通过树遍历定位。
与 Lucene 的区别：这是完全不同的范式。Lucene DocValues 是纯列存、无树结构、O(1) 定位；B-Tree/LSM 是面向范围查询和有序遍历优化的，随机点查需要 O(log N) 次 I/O。DocValues 不适合做范围聚合以外的复杂数值查询，而 B-Tree 恰好擅长这个。

代表系统：Gorilla (Facebook TSDB)、InfluxDB TSM、QuestDB
核心思想：
- 整数时间戳：Delta-of-Delta 编码（二阶差分），因为时间间隔通常是常数。
- 浮点值：XOR 编码，相邻值的 IEEE754 表示通常只有少数 bit 不同。
与 Lucene 的区别：Lucene 把浮点数转成 sortable long 后当整数处理，丢失了浮点数的局部相关性。Gorilla XOR 编码对浮点监控数据的压缩率比 Lucene 方案高一个数量级，但完全不适用于非时序数据。