1、概念
- block：一次写入生成的一个数据块。
- primary.idx文件：存储了稀疏索引,一个part对应一个稀疏索引。
- bin文件：真正存储数据的文件，由1到多个压缩数据组成。压缩数据是最小存储单位，由『头文件』和『压缩数据块』组成。头文件由压缩算法、压缩前的字节大小、压缩后的字节大小三部分组成；压缩数据块严格限定在压缩前64K~1M byte大小。（这个大小是ClickHouse认为的压缩与解压性能消耗最小的大小）。即，一个压缩数据块由N个block组成，一个bin文件又由N个压缩数据块组成。
- mrk文件：存储了block在bin文件中哪个压缩数据以及这个压缩数据的数据块中的起始偏移量。
| 索引中的mark index | 压缩数据index | 在压缩数据块中起始的字节数（偏移量） |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 12001 |
| 2 | 1 | 0 |
2、数据存储
数据以压缩数据为单位，存储在bin文件中。
压缩数据对应的压缩数据块，严格限定按照64K~1M byte的大小来进行存储。
（1）如果一个block对应的大小小于64K，则需要找下一个block来拼凑，直到拼凑出来的大小大于等于64K。
（2）如果一个block的大小在64K到1M的范围内，则直接生成1个压缩数据块。
（3）如果一个block的大小大于了1M，则切割生成多个压缩数据块。一个part下不同的列分别存储，不同的列存储的行数是一样的。
3、检索过程
以 where partition = '2019-10-23' and ID >= 10 and ID < 100 （ID是索引字段）的query描述大体检索流程:
- 每个索引都有对应的min/max的partition值，存储在内存中。当contition带上partition时就可以从这些block列表中找到需要检索的索引，找到对应的数据存储文件夹，命中对应的索引（primary.idx）
- 根据ID字段，把条件转化为[10,100)的条件区间,再把条件区间与这个partition对应的稀疏索引做交集判断。如果没有交集则不进行具体数据的检索；如果有交集，则把稀疏索引等分8份，再把条件区间与稀疏索引分片做交集判断，直到不能再拆分或者没有交集，则最后剩下的所有条件区间就是我们要检索的block值。
- 通过步骤2我们得到了我们要检索的block值。通过上面我们知道存在多个block压缩在同一个压缩数据块的情况并且一个bin文件里面又存在N个压缩数据的情况，所以不能直接通过block的值直接到bin文件中搜寻数据。我们通过映射block值到mrk中，通过mrk知道这个block对应到的压缩数据以及在压缩数据块里面的字节偏移量，就得到了我们最后需要读取的数据地址。
- 把bin文件中的数据读取到内存中，找到对应的压缩数据，直接从对应的起始偏移量开始读取数据。
4、example
(1)写入
假设表的index字段为Column A，一个Column A的字符长度为30KB；还有个非index字段Column B，一个Column B的字符长度为100KB；index_granularity=2。
依7次写入7行数据，数据如下
| A | B |
|---|---|
| a | 1 |
| a | 3 |
| b | 2 |
| b | 2 |
| c | 1 |
| a | 4 |
| a | 0 |
写入以后假设已经完全merge，则排序后为：
| A | B |
|---|---|
| a | 0 |
| a | 1 |
| a | 3 |
| a | 4 |
| b | 2 |
| b | 2 |
| c | 1 |
则生成的索引为：
| mark number | value |
|---|---|
| 0 | a |
| 1 | a |
| 2 | b |
| 3 | c |
(2)存储
根据压缩数据的64KB~1MB的理论，则在
Column A.bin文件中，对应的存储为：
（3个block才大于64KB，生成一个压缩数据块）
Column A.mrk文件中，对应的存储为：
| 索引中的mark number | 压缩数据index | 在压缩数据块中起始的字节数（偏移量） |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 61440(30 * 1024 * 2) |
| 2 | 1 | 30720 |
| 3 | 2 | 0 |
同理有Column B.mrk文件为：
Column B.bin文件为：
| 索引中的mark number | 压缩数据index | 在压缩数据块中起始的字节数（偏移量） |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 2 | 2 | 0 |
| 3 | 3 | 0 |
| 4 | 4 | 0 |
| 5 | 5 | 0 |
| 6 | 6 | 0 |
(3)搜索
以A='a'为例，则命中的索引mark number为0跟1。
再返回回来mrk文件中，以(0,0)代表压缩数据块0，偏移量0。例如对于Column A而言，mark number 0则命中[(0,0),(0,61440))对应的block，mark number 1命中了[(0,61441),(1,30720))对应的block。将这些block加载进内存，再通过偏移量计算，得到最终需要扫描的行。
5、other
- 为什么加了partition查询会变快？因为只需要扫描匹配partition对应的索引就可以，不加partition就需要扫描所有partition上的索引。
- 为什么用范围查询也能命中索引？理由如3。
6、reference
朱凯老师的分享，in ClickHouse Meetup
