在第三节中，曾经向读者介绍了 clickhouse 在解决数据时依照 block 为单位进行压缩，之后写入磁盘数据文件中。
在第三节中，曾经向读者介绍了 clickhouse 在解决数据时依照 block 为单位进行压缩，之后写入磁盘数据文件中。这样能够缩小数据量的大小缩小磁盘 io 工夫。然而，如果没有索引，则意味着每次查问时都须要读取所有的数据，即便通过压缩曾经升高了 6.2 倍的数据量，这仍然要花费很多的磁盘 IO。此时索引就呈现了，能够再次帮忙咱们缩小查问时须要读取的数据量。
在介绍 clickhouse 的索引之前，咱们先回顾一下关系型数据库 MySQL 中罕用的索引技术——B + 树。B + 树算法超出本文内容，在这里不做深刻探讨，咱们次要剖析下 MySQL 应用 B + 树的目标和 B + 树的实质。其实，B + 树实质是一颗 N 叉树，其叶子节点就是有序排列的索引值，因而在查问时能够依据这棵树疾速定位到数据所在，而且因为其有序，能够适应范畴查找。下图展现了一颗 B + 树。
B + 树示意图
理解了 B + 树的实质之后，读者能够试着答复一个问题：clickhouse 是否有必要应用 B + 树进行索引？为什么？
如果您的答案是不须要，那么阐明您曾经对 clickhouse 和 MySQL 存储引擎都理解地比拟深刻了。如果您的答案是须要或者不确定，那么也不必焦急，上面就会具体阐明起因。
这个问题的答案就是不须要，起因在于 clickhouse 的存储引擎和 MySQL 的存储引擎设计上的不同。MySQL 因为要反对事务，应用 MVCC 的事务管制机制，因而会呈现一个问题：数据的插入程序和索引的排序不同。例如我对 age 列做索引，我的插入程序为 44，21，20，33，19。这组数据在 B + 树中须要被重新排列为 19，20，21，33，44。这就是数据的插入程序和索引排序不同的状况。而在关系型数据库中数据的插入程序就是存储引擎写入数据文件的程序。
在 clickhouse 的存储引擎中，在第三章和番外篇中曾经具体介绍了 LSM 机制，clickhouse 的存储引擎通过 LSM 机制保证数据的依照主键的程序写入存储引擎，也就是说即便插入程序为 44，21，20，33，19。这组数据在通过 clickhouse 的 LSM 机制后写入数据文件的程序就是 19，20，21，33，44。这意味着 clickhouse 在存储数据时曾经有序存储了，因而不须要再次应用 B + 树进行索引了。
一级索引
综上，其实 clickhouse 的一级索引非常简单，只须要记录每一个 block 第一个值即可。例如一组一亿行的数据，主键范畴从 1～100,000,000。存储到 clickhouse 后依照 8192 行为一个 block，那么一共有 12208 个 block。索引为 1，8193，16635…… 在查问时只须要就能够依据值确定到须要读取哪几个 block 了。例如我须要查问 id>500 and id <12258 的数据，那就只须要读取第 0 块和第 1 块 block 即可。
在 clickhouse 的数据存储文件中，一级索引存在于 primary.idx 中。一级索引的实质是存储了每个 block 中数据的最小值，从而为确定须要查问的数据确定好其所在的 block。它简历了数据到 block 的映射关系。简略来说，给定一个数据，通过一级索引可能疾速查问到这个数据所在的 block。从而防止查问一个数据须要遍历整个数据集。
标记
下面一部分曾经给读者介绍了什么是一级索引。但一级索引并不能独自实现疾速查找的指标。或者说，一级索引只实现了数据到 block 的映射。但还存在一个问题，我即便曾经晓得我的数据存储在了第一个 block，那我如何定位到这个 block 的地位呢？这个问题的答案就须要通过标记文件来实现。换句话说，标记文件存储了 block 到文件偏移量的映射。
这个问题其实也不难理解，咱们晓得一个 block 是 8192 行数据组成的。如果每个 block 的大小都是 64M。那么找到第 N 个 block 的地址就很容易，通过 N*64m 即可，但要害 block 通过压缩后是无奈保障其大小的，也就是说每个 block 的大小是不同的。那么就必须将每个 block 的起始地位存储下来，不便查找。
在 clickhouse 的理论解决中，每行标记有 3 个字段组成 blockid, 数据文件中的偏移量，压缩后块中偏移量。每个字段是 8 字节，因而每个标记一共 24 字节。通过 blockid 能够 N*24B 疾速定位到地位。
其实有 blockid 和数据文件中偏移量，就曾经能够快读定位了，那么 clickhouse 标记文件中的第三项压缩后块中偏移量是用来做阐明的呢？这个问题的答案其实和 clickhouse 对于压缩块的解决无关。第三章曾经提过，clickhouse 依照每 8192 行生成一个 block。但如果 8192 行的数据仍然很小怎么办？例如 UInt8 类型，一行数据只有 8 位 1 字节。即便 8192 行数据也仅仅只有 8192Byte=8KB。这个数据量用来压缩还是显得太小。因而，clickhouse 在解决时，会依照每个压缩块最小 64KB，最大 1M 的规定进行解决。即一个 block 数据总和小于 64K 时，会持续取下一个 block。因而会呈现多个 block 呈现在一个压缩块中。标记文件中的第三个参数就是用来解决这种状况的。
因而假如一个标记文件的内容如下：
| 0 | 0 | 0 |
| 1 | 0 | 8192 |
| 2 | 0 | 16384 |
| 1 | 12016 | 0 |
标记文件内容
读取第 2 块 block 时，依据 2*24Byte=48，定位到（2，0，16384）这一行，而后依据 0，从 bin 文件中读取偏移量 = 0 的数据块，通过解压缩后再依据 16384 读取解压缩后从 16384 开始的数据，即可找到对应的原始数据。
总结
—
clickhouse 的索引因为其存储引擎的设计，能够做的非常简单。次要有一级索引和标记组成。一级索引实现数据到 block 的映射，标记实现 block 到文件偏移量的实现。另外，因为一级索引十分小，1 亿条数据只须要 1 万多行的索引，因而一级索引能够常驻内存，减速查找。
同时，clickhouse 还提供了二级索引，不过二级索引比较简单，且不是必须的，对整体性能影响也不大，因而我会在番外篇中介绍二级索引。
至此，clickhouse 的存储引擎的设计曾经更新结束，下一期我将通过一个残缺的例子串联起整个 clickhouse 的存储引擎的工作原理。并且对之前写得局部进行优化，尤其是减少大量的图片来向读者更清晰地介绍概念。
置信通过这几节的内容，大家对 clickhouse 的设计哲学也有了肯定的意识。这边我又要提出一个新的疑难，读者能够当时思考一下：依照本文目前的介绍来看，clickhouse 的减速强在设计上，那么为什么 clickhouse 要应用 C++ 语言编写？应用 JAVA 是否实现同样的性能？为什么？这个问题将会引出下一部分的核心内容：clickhouse 的计算引擎。让咱们在下一部分重逢，开始一段更有挑战的旅程。