Varint：全面解析可变长度整数编码

SQLite
, ,

SQLite 是一种广泛使用的嵌入式数据库引擎，其高效性在于采用了多种优化技术来减少存储空间并提升性能。其中，Varint（可变长度整数）是一种重要的编码方式。本文将详细解析 Varint 的定义、在 SQLite 中的应用以及其具体工作原理。

什么是 Varint？

Varint 是一种 可变长度整数编码，它通过根据整数值的大小动态调整存储字节数来减少存储空间。对于较小的整数，Varint 只使用 1 个字节，而较大的整数可以使用最多 9 个字节进行存储。

Varint 的核心思想是对每个字节的最高位（most significant bit, MSB）进行特殊标记：

  • 如果 MSB 为 1，表示当前字节是整数编码的一部分，后续还有更多字节。
  • 如果 MSB 为 0，表示当前字节是编码的最后一个字节。

Varint 在 SQLite 中的作用

SQLite 广泛使用 Varint 来存储整数值，尤其是在以下场景：

  • 数据库文件中的页头和记录头。
  • 存储 B 树节点中的键和值。
  • 记录长度和偏移量的表示。

通过 Varint 编码，SQLite 在存储效率和解析速度之间取得了良好的平衡，使其成为轻量级、高性能的数据库解决方案。

可变长度编码的基础知识

定义与用途

可变长度编码是一种针对整数或其他数据类型的压缩方法。通过动态调整数据的存储长度，减少了固定长度编码可能造成的空间浪费。例如，一个整数 1 在固定长度编码中可能需要 4 个字节，而在 Varint 编码中仅需 1 个字节即可存储。

与固定长度编码的比较

编码类型 优点 缺点
固定长度编码 访问速度快，位置可直接计算 可能浪费存储空间
可变长度编码 (Varint) 节省空间，适合小型或稀疏数据 读取时需要额外的解码操作

使用可变长度编码的优点

SQLite 采用 Varint 编码的主要原因在于：

  • 存储效率：小整数使用更少的字节，整体存储需求降低。
  • 灵活性：适应不同范围的数据，满足各种存储需求。
  • 性能平衡：尽管解码增加了一些计算量，但与存储和传输成本相比微不足道。

SQLite 中 Varint 的存储结构

Varint 的编码规则

Varint 使用一个或多个字节存储整数，每个字节的结构如下：

  • 最低 7 位：表示整数的实际数据。
  • 最高 1 位：控制位，用于指示是否有后续字节。

示例：

  • 整数 0x7F（127），可以用一个字节存储：01111111。
  • 整数 0x80（128），需要两个字节存储：10000000 00000001。

如何表示不同范围的整数

根据 Varint 的规则，整数越大，使用的字节数越多。SQLite 使用 Varint 表示以下范围的整数：

字节数 可表示的整数范围
1 0 - 127
2 128 - 16,383
3 16,384 - 2,097,151
4 - 9 更大范围的整数

Varint 的实际存储示例

以下示例演示了 Varint 的存储过程：

  1. 整数 300 的二进制表示为 100101100，分为两个字节存储：
    • 第一个字节：10101100（最高位为 1，表示有后续字节）。
    • 第二个字节：00000010（最高位为 0，表示结束）。

Varint 的工作原理

数据分段的原理

Varint 将整数拆分为 7 位一组，并通过控制位标识每组是否为最后一个字节。这种方法允许高效存储不同范围的整数。

高效解析整数的步骤

SQLite 解析 Varint 时，会逐个读取字节并检查最高位：

  1. 如果最高位为 1，提取低 7 位，拼接到结果中，并继续读取下一字节。
  2. 如果最高位为 0，提取低 7 位，拼接后结束。

示例：
解析整数 300 时：

  • 读取第一个字节 10101100，提取 00101100。
  • 读取第二个字节 00000010，提取 00000010。
  • 拼接结果为 00000010 00101100，即整数 300。

减少存储空间的策略

通过存储小整数时只使用必要的字节数，Varint 显著减少了存储需求。这对于 SQLite 这种面向嵌入式环境的数据库尤为重要。

SQLite 使用 Varint 的场景

表头信息中的 Varint

SQLite 表头使用 Varint 存储字段数量、字段偏移等信息，从而在节省存储空间的同时保持可扩展性。

B 树结构中的 Varint 应用

SQLite 的 B 树节点使用 Varint 表示键值长度、子节点指针等数据，从而提高查找性能并减少磁盘占用。

数据类型与 Varint 的结合

某些字段类型（如 INTEGER 和 TEXT）的长度信息也通过 Varint 表示，为存储更高效提供了可能。

Varint 的性能优势

空间效率对比

与固定长度编码相比，Varint 在存储小型数据时节省了大量空间。例如：

  • 整数 5 的固定长度表示需要 4 字节，而 Varint 表示只需 1 字节。

对查询速度的影响

尽管 Varint 增加了解码步骤，但由于其存储紧凑性，减少了磁盘 I/O 和内存使用，从而间接提升了查询性能。

如何在性能与存储之间取得平衡

SQLite 在需要高效存储时使用 Varint，而在性能关键部分（如固定偏移量读取）中避免使用 Varint，以实现性能与存储的最佳平衡。

Varint 的限制与注意事项

范围限制

Varint 最多使用 9 个字节，限制了其能够表示的整数范围（最大 64 位无符号整数）。

对极大整数的处理

对于极大整数，Varint 的编码效率降低，可能需要更多字节来存储。

读取和写入时的性能影响

解码和编码 Varint 会增加 CPU 的运算负担，尤其是在频繁访问或大量数据处理时。

Varint 解码实现（rust）

解码算法的实现

编码过程通过将整数拆分为 7 位一组并添加控制位实现；解码则逆向操作，逐字节拼接。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

pub fn encode_varint(mut num: u64) -> Vec<u8> {
    let mut buffer = Vec::new(); // 用于存储编码后的字节
    loop {
        let mut byte = (num & 0x7F) as u8; // 提取低7位
        num >>= 7; // 右移7位
        if num != 0 {
            byte |= 0x80; // 设置最高位为1，表示还有后续字节
        }
        buffer.push(byte); // 添加当前字节到结果中
        if num == 0 {
            break; // 没有更多数据，结束循环
        }
    }
    buffer
}

pub fn decode_varint(buffer: &[u8]) -> anyhow::Result<(usize, u64)> {
    let mut result = 0u64; // 记录结果
    let mut n = 0; // 记录读取的字节数
    loop {
        let byte = buffer[n];
        // byte & 0x7F 获取低7bits有效数据
        // result << 7 result 左移7位
        // ｜ 或运算
        result = (result << 7) | ((byte & 0x7F) as u64);
        n += 1;
        if byte & 0x80 == 0 { // 取高位，1继续，0终止
            break;
        }
        if n >= 9 { // 存储最多 64 位的无符号整数（u64），最多需要 9 个字节来表示
            anyhow::bail!("varint too long"); 
        } 
    }
    Ok((n, result))
}