1.概述

转载：ClickHouse表引擎 MergeTree 索引与数据存储方式

2.一级索引

MergeTree 主键使用 primary key 定义，定义主键后，会将数据依据 index_granularity 参数设置的间隔（默认：8192）为表生成一级索引保存到 primary.idx 文件中，索引文件按照 primary key 进行排序。但更常用 order by 代替主键，这时索引文件（primary.idx）与数据文件（column_name.bin）会按照相同的规则排序。

2.1 系数索引

primary.idx 文件内的一级索引采用稀疏索引的方式实现的，如下图所示：

• 稠密索引每一个索引都会对应一条数据记录。
• 一条稀疏索引标记对应一段数据，稀疏索引就像是一本书的目录，每个目录只会对应章节的开始位置，而不会对应到具体的每个字。
• 使用稀疏索引的好处是使用少量的索引就能标记大量的数据记录的区间位置，而且数据量越大这种优势就会越明显。
• mergetree 使用 12208 条索引标记就能为1 亿行数据记录提供索引。
• 由于稀疏索引占用空间小，所以 primary.idx 中的数据时常驻内存的，读取速度非常快。

2.2 索引粒度

索引粒度对于 MergeTree 而言是一个非常重要的概念，索引粒度如同标尺一样，会标注整个数据的长度，最终数据会形成多个间隔的小段。

• 在新版本中也支持使用自适应粒度，使用 enable_mixed_granularity_parts参数开启。
• MergeTree 使用 index_granularity 参数设置索引粒度（默认：8192），数据通过索引粒度被标记成多个区间，每个区间最多 8192条数据。
• MergeTree 使用 MarkRange 表示一个具体的区间，并通过 start 和 end 表示具体范围。
• index_granularity 参数除了作用于一级索引以外还会影响数据标记（.mrk）和数据文件（.bin）。
• 标记文件与一级索引文件粒度相同，彼此对齐，数据文件也会依据粒度间隔生成压缩数据块。
• 查询数据时需要数据索引、数据标记和数据文件一起工作完成查询功能。

2.3 索引数据的生成规则

MergeTree 的一级索引属于稀疏索引，需要间隔 index_granularity 行数据才会生成一条索引记录，其索引值会依据声明的主键字段获取。

索引值为间隔index_granularity行数据取一次主键值作为索引值，将几次取指拼接到一起形成最终索引值，索引数据最终会被保存到primary.idx 文件中进行保存。

如下图ID 作为主键 ，order by (ID)

MergeTree 对稀疏索引的存储是非常紧凑的，索引值前后相连，按主键顺序紧密排列在一起，clickhouse 中很多数据结构都被设计的非常紧凑，如使用位读取代替专门的标识位或状态码，不浪费一点空间，这也是 clickhouse 性能出色的原因之一。

如果使用多个主键，索引如下图所示，order by (ID,EventData)

2.4 索引的查询过程

要想知道索引是如何工作的，需要先知道 MarkRange是什么，MarkRange 是clickhouse 中用于定义标记区间的对象，MergeTree 按照index_granularity的间隔粒度将一段完整的数据划分成多个小的间隔数据段，其中的每个小的数据段都是一个 MarkRange。

MarkRange 与索引编号对应，使用 start 和 end 两个属性表示其区间范围，通过与 start 和 end 对应的索引编号的取值，即能够得到它对应的数值区间，而数值区间表示了此 MarkRange包含的数据范围。

一份 192 行的测试数据，主键为 String 类型的 ID，取值范围从 A000 ，A001，A002 … A192。MergeTree 索引粒度 index_granularity = 3，根据索引生成规则，primary.idx 文件内的索引数据如下图所示：

根据索引数据，MergeTree 会将此数据片段划分成192/3=64 个小的MarkRange，相邻的 MarkRange 步长为 1，所有 MarkRange 的最大步长为[A000,+inf]

对于索引的查询就是两个数值区间的交集判断，一个区间是基于主键的查询条件转换来的，另一个区间是与 MarkRange 对应的数值区间。

整个索引查询大约分为三个步骤：

1. 生成查询条件区间：将查询条件转换为条件区间，单个查询条件也会被转换为区间的形式，如：

where ID = 'A0003'
['A0003','A0003']

where ID > 'A0003'
['A0003',+inf]

where ID < 'A0003'
[-inf,'A0003']

1. 做递归交集判断：以递归的形式依次对 MarkRange 的数值区间与条件区间做交集判断，从最大的区间 ['A0000',+inf] 开始。

• • 如果不存在交集，则直接使用剪枝算法优化此段MarkRange。
• • 如果存在交集，且 MarkRange 步长大于 merge_tree_coarse_index_granularity （默认：8），则将该区间进一步拆分成对应数量的子区间，并重复递归，继续做交集判断。
• • 如果存在交集，且 MarkRange 步长小于 merge_tree_coarse_index_granularity （默认：8），则记录 MarkRange 并返回。

1. 合并MarkRange区间：将最终匹配的 MarkRange 聚集到一起，合并他们的范围。MarkRange 通过递归持续向下拆分区间，最终将MarkRange 定位到最细的粒度，使得在后面取数据时能够最小化扫描数据的范围。

当查询条件是 where ID = ‘A0003’ 最终需要读取 [A000,A003] 和 [A003,A006] 两个区间的数据，他们对应MarkRange[0,2] 范围，而其他无用的区间都被剪掉了。

3.二级索引

• 除了一级索引之外，MergeTree 还支持二级索引
• 二级索引又称为跳数索引，由数据的聚合信息构成。
• 根据索引类型不同，聚合信息的内容也不相同。
• 设计二级索引的目的与一级索引一样，也是为了在查询时减少扫描数据的范围
• 二级索引需要在 create 语句内定义，支持元组和表达式的声明形式。
• 如果声明了二级索引，那么在会额外生成对应的索引文件（skp_idx_[column].idx）与标记文件（skp_idx_[column].mrk）
  声明方式：INDEX index_name expr TYPE index_type(...) GRANULARITY Granularity

3.1 granularity 与 index_granularity

index_granularity：定义数据的粒度，数据通过索引粒度被标记成多个区间。

granularity：定义汇聚信息汇总的粒度，定义了一个跳数索引能跳过多少index_granularity的区间数据。

3.2 跳数索引的生成规则

• 按照 index_granularity 粒度间隔将数据划分成 N 段，共有 [0,N-1] 个区间（N = 总行数/index_granularity 向上取整）
• 根据索引定义时声明的表达式，从 0 区间开始，依次按 index_granularity 粒度从数据中获取聚合信息，每次向前移动 1 步，聚合信息逐步累加。
• 当移动 granularity 次区间时，汇总并声称一行跳数索引数据。

以 minmax 类型索引为例介绍二级生成方式：

minmax 索引的聚合信息是在一个 index_granularity 区间内 granularity 的最小值与最大值。

一下图为例，设置 index_granularity = 8192 ，granularity = 3，则会将数据按照 index_granularity 划分为 N 份，MergeTree 会从第 0 份开始获取聚合信息。当获取到第三个分区时，汇总并生成第一个 minmax 索引，前 3 段minmax极值汇总后取值为 [1,9]

3.3 跳数索引的类型

MergeTree 共支持 4 种跳数索引，分别是：minmax 、 set 、 ngrambf_v1 和 tokenbf_v1。
在一张表中可以同时声明多个跳数索引。

CREATE TABLE skip_test
(
    `id` String,
    `name` String,
    `event_date` date,
    INDEX a id TYPE minmax GRANULARITY 5,
    INDEX b length(id) * 8 TYPE set(1000) GRANULARITY 5,
    INDEX c (id, name) TYPE ngrambf_v1(3, 256, 2, 0) GRANULARITY 5,
    INDEX d id TYPE tokenbf_v1(256, 2, 0) GRANULARITY 5
)
ENGINE = MergeTree
ORDER BY id

3.3.1 minmax

minmax索引 记录了一段数据内的最小值和最大值
索引的作用类似分区目录的 minmax 索引，能够快速跳过无用的数据区间。
sql

-- 示例
INDEX a id TYPE minmax GRANULARITY 5

-- minmax 索引会记录这段数据区间内 id 字段的最小值与最大值，极值计算设计 5 个 index_granularity 区间的数据

3.3.2 set

set 索引直接记录了声明字段或表达式的取值（唯一值，不重复）
完整形式为：set(max_rows)，其中 max_rows 是一个阈值，表示在一个index_granularity 内，索引最多记录的数据行数
如果 max_rows = 0 ，表示无限制

-- 示例
INDEX b length(id) * 8 TYPE set(1000) GRANULARITY 5,

-- set 索引会记录 id 长度 * 8 的值，每个 index_granularity 最多记录 1000 条

3.3.3 ngrambf_v1

• ngrambf_v1索引记录的是数据短语的布隆过滤器

• ngrambf_v1索引只支持 String 和FixedString 类型

• ngrambf_v1索引只能提升in、notIn、like、equals和 notEquals 的查询性能

• 完整形式为：ngrambf_v1(n, size_of_bloom_filter_in_bytes, number_of_hash_functions, random_seed)

• n：token 长度，根据 n 长度，将数据切割为 token 短语

• size_of_bloom_filter_in_bytes：布隆过滤器的大小

• number_of_hash_functions：布隆过滤器中使用 hash 函数的个数

• random_seed：hash 函数的随机种子

-- 示例
INDEX c (id, name) TYPE ngrambf_v1(3, 256, 2, 0) GRANULARITY 5,

-- ngrambf_v1索引会按照3 的粒度，将数据切分成短语 token，
-- token 会经过两次 hash 函数再被写入
-- 布隆过滤器的大小是 256 字节

3.3.4 tokenbf_v1

tokenbf_v1索引也是一种布隆过滤器索引，可以看做是ngrambf_v1索引的变种。
tokenbf_v1索引除了短语 token 处理的方法与ngrambf_v1索引不同，其他方面处理都是一样的。
tokenbf_v1索引会自动按照非字符的，数字的字符分割 token
sql

-- 示例
INDEX d id TYPE tokenbf_v1(256, 2, 0) GRANULARITY 5

-- token 会经过两次 hash 函数再被写入
-- 布隆过滤器的大小是 256 字节

4.数据存储

4.1 各列独立存储

MergeTree 中数据时案列存储的，具体到每个字段时也是独立存储的。

每个列字段都有一个与之对应的 [column_name].bin 文件，这些文件承载着数据最终的物理存储。

数据文件以分区目录的形式被组织存放，所以 [column_name].bin 文件只会保存当前分区内的这一部分数据。

按列存储的优势在于可以减少扫描的数据量

按列存储还可以优化压缩的效率，同一字段的类型相同且重复率更高。

MergeTree 将数据写入 bin 文件也是经过设计的：

数据会经过压缩，目前支持的压缩算法有：LZ4(默认)、ZSTD、Multiple和Delat几种算法。

数据会按照 order by 的声明排序。

数据以压缩块的形式被组织并写入 bin 文件中

4.2 压缩数据块

压缩数据块由头信息和压缩数据两部分组成
头信息使用固定 9 个字节表示，分为三个部分

压缩算法（1 个 UInt8 整型表示，1 字节）
压缩后的数据大小（1 个 UInt32 整型表示，4 字节）
压缩前数据大小（1 个 UInt32 整型表示，4 字节）

.bin 数据文件是由多个数据压缩块组成的，每个数据压缩块的头信息又是由 CompressionMethod_CompressedSize_UncompressedSize组成的。

可以通过 clickhouse 提供的clickhouse-compressor工具查看某个.bin 数据文件的统计信息。

# 查看 data.bin 压缩数据统计信息
[root@node3 data]# clickhouse-compressor --stat db_merge/t_merge_tree_partition/202001_1_1_2/data.bin
2    12
6    16
8    18

# 每一行代表一个数据压缩块的头信息，分别代表着压缩后的数据大小与未压缩的数据大小

每个压缩数据块的体积，按照其压缩前的数据字节大小，被严格控制在 64KB~1MB 之间，分别由 min_compress_block_size （默认 65536） 与min_compress_block_size （默认：1048576）参数指定。

数据压缩块的大小和间隔（index_granularity）内的数据实际大小有关。

MergeTree 在写入数据过程中，会依照 index_granularity 粒度，按批次取数据并进行处理。设下一批未压缩数据大小为 x 字节，写入数据遵循如下规则：

1. x < 64KB：当单批次数据小于 64KB 时，继续获取下一批数据，直到累积到 64KB后，生成下一个数据压缩块。
2. 64KB < x < 1MB：当单批次数据大于64KB 且小于 1M 时，直接生成下一个数据压缩块。
3. x > 1MB：当单批次数据大于 1MB 时，将数据按照 1MB 截取，生成数据压缩块，其余的数据按照前面的规则执行，此时可能生成多个压缩数据块。

一个 .bin 数据压缩文件，是由一个到多个压缩数据块组成，每个数据压缩块在 64KB 到 1MB 之间，多个数据块之间，按照写入顺序，首尾相连，紧密的排列在一起。

数据文件中写入压缩数据块的目的：

• 数据被压缩后能够大大减少占用磁盘的空间并增加传输效率，但额外的压缩与解压缩会带来 CPU 性能的损耗，所以需要控制被压缩的数据大小，以保证在性能损耗与数据压缩之间保持平衡。
• 在读取某一列数据时，需要将压缩文件加载到内存并解压，这样才能进行后续的数据处理，通过数据压缩块可以在不读取整个.bin 文件的情况下，将读取粒度降低到数据压缩块级别，减少数据读取的范围。

5.数据标记

如果把MergeTree 比作一本书，那么这本书的 一级章节目录就是 primary.idx 一级索引，书中的文字就是 .bin 文件中的数据。一级章节目录与书中的文字的联系由 数据标记（.mrk）建立。

数据标记记录了两个非常重要的信息：

一级章节对应的页码信息
文字在某一页的起始位置

通过数据标记后，很容易就能找到快速的从一本书中找到你想看的那一页，并知道从哪行开始阅读。

5.1 数据标记的生成规则

数据标记是衔接一级章节与数据的桥梁，每本书的每个章节也都会有各自的桥梁。从上图能够发现数据标记的首个特征即数据标记与索引区间是对齐的，都按照index_granularity的粒度间隔。这样只需要简单通过索引区间的下标编号就能找到对应的数据标记。

为了能够与数据衔接，数据标记文件与 .bin 文件也是一一对应的。即每个列字段 [column].bin 文件都有一个与之对应的[column].mrk 数据标记文件，用于记录 .bin 文件中的偏移量信息。

一行标记文件使用一个元组表示，元组内包含两个整数的偏移量信息，分别表示：在此段数据区间内，对应的 .bin 压缩文件中，压缩数据块的起始偏移量，以及对该数据块解压后，其未压缩数据的起始偏移量。

每一行标记数据都表示了一个片段的数据（默认 8192 行）在 .bin 文件中的读取位置信息。标记数据与索引数据不同，不能常驻内存，而是使用 URL（最近最少使用）缓存策略加快其读取速度。

5.2 数据标记的工作方式

Merge 在读取数据时，必须通过标记数据的位置信息才能找到所需的数据。整个查询过程大致可以分为读取数据压缩块和读取数据两个步骤，下面图示说明了标记数据与压缩数据的对应关系。

字段了性为 UInt8，每行占用一个字节，index_granularity粒度为 8192，所以一个索引片段占用数据大小是 8192B，根据压缩块的生成规则，当单批次数据小于 64KB 时，继续获取下一批数据，直到累积到 64KB后，生成下一个数据压缩块。

可以看到标记文件中，每 8 个标记文件对应一个压缩块，（64KB=65536B， 1B*8192= 8192B，65536/8192=8）所以能够看到标记文件中，压缩文件中每 8 行的偏移量都是相同的，因此该 8 行数据都指向了同一个压缩块。

这 8 行数据中的解压缩文件偏移量按照 8192B 累加，当累加到 65536 后设置为 0，根据规则生成下一个压缩数据块。

5.2.1 读取压缩数据块

• 在读取某一列数据时，Merge 无需加载整个 .bin 文件，这个特性需要借助标记文件中的压缩文件偏移量来实现。
• 在标记文件中，上下相邻的像个压缩文件中的起始偏移量，构成了与获取当前标记对应的压缩数据块的偏移量区间。
• 由当前标记数据开始向下寻找，直到找到不同的压缩数据偏移量截止，此时得到一组压缩数据偏移量区间，即压缩数据在 .bin 文件中 [0,12016] 字节就能读取到第 0 个压缩数据块。
• 压缩数据块加载到内存后会进行解压，接着就到了读取数据的环节。

5.2.2 读取数据

• 在读取解压后的数据时，Merge不需要扫描全部解压数据
• 可以根据需要，以 index_granularity 的粒度为单位加载特定小段数据，这个特性需要依靠标记文件中解压文件偏移量来实现。
• 上下相邻两个解压缩数据块中的起始偏移量构成了获取当前标记对应的数据偏移量。
• 依靠这个区间，能够在数据解压缩后依照偏移量获取数据，如通过[0,8192] 来获取压缩文件 0 中的第一个数据片段。

6.分区,索引,标记和数据压缩总结

分区、索引、标记数据和压缩数据都是 Merge 的重要组成部分，前面介绍过这不各部分的特点之后，现在需要将它们汇聚在一次做一个总结，下面从写入、查询。数据标记与压缩数据的对应关系三个部分介绍。

6.1 写入过程

写入数据的第一步是生成分区目录，伴随着每一批数据的写入都会生成一个新的目录。

在后续的某个时间属于相同分区的目录会合并到一起。

接下来按照 index_granularity 的粒度 分别生成 primary.idx一级索引、如果声明了二级索引也会生成二级索引、每一个列字段对应的 .mrk 标记文件和 .bin 压缩数据文件。

6.2 查询过程

• 数据查询的本质是一个不断减小数据范围的过程
• Merge 可以依次借助分区索引、一级索引和二级索引将数据扫描范围缩至最小
• 然后借助标记数据将需要解压与计算的数据范围缩至最小

下图示意了在经过层层过滤获取最小数据范围的过程

如果一条语句没有指定任何的 where 条件，或者指定了 where 条件但是没有匹配到任何索引，那么 Merge 就不能预先减小数据范围，在后续的查询中会扫描所有的分区目录，以及目录内的数据。虽然不能减少数据范围，但是 Merge 仍然能借助数据标记，以多线程的形式同时读取多个压缩数据块，以提升性能。

6.3 数据标记与压缩数据块的对应关系

如下图所示，数据标记与压缩数据块存在三种关系

多对一
一对一
一对多

6.3.1 多对一

多个数据标记对应一个数据压缩块，当一个数据间隔内的未压缩数据不到 64KB 时会出现这种关系。

6.3.2 一对一

一个数据标记对应一个数据压缩块，当一个数据间隔内的未压缩数据大于 64KB 且小于 1MB 时会出现这种关系。

6.3.3 一对多

一个数据标记对应多个数据压缩块，当一个数据间隔内的未压缩数据大于 1MB 时会出现这种关系。