前面介绍了clickhouse通过block和lsm来减少磁盘读取的数据量。严谨的逻辑应该时clickhouse通过lsm算法来实现数据预排序，从而减少了磁盘读取的数据量，本章番外主要为读者介绍什么是LSM算法，对LSM算法已经有了解的读者可以跳过本章。

LSM算法最早出现在1991年的ACM期刊上，之后其思想在各大大数据存储系统中被广泛使用，例如LevelDB,HBase,Cassandra……LSM算法由于适应的场景不同，存在很多的变体，clickhouse也使用lsm算来实现其预排序的功能，本文将着重介绍clickhouse中的使用，同时也会适当涉及一些其他系统的使用用以让读者体会架构设计的随心所欲。

我们都知道，用户在调用insert向clickhouse插入数据时，数据不一定是按已经按照排序键排序好的数据，大概率是乱序数据。那么这种乱序的请求如何做到写入磁盘时变得有序呢？这个就是LSM算法实现的。

LSM算法的几个核心步骤：

• 在于数据写入存储系统前首先记录日志，防止系统崩溃
• 记录完日志后在内存中以供使用，当内存达到极限后写入磁盘，记录合并次数Level为0(L=0)。已经写入磁盘的文件不可变。
• 每过一段时间将磁盘上L和L+1的文件合并

我们用一个示例来展示下整个过程

T=0时刻，数据库为空。

T=1时刻，clickhouse收到一条500条insert的插入请求，这500条数据时乱序的。此时，clickhouse开始插入操作。首先将500条插入请求一次性写入日志。接着在内存中进行排序，排序完成后将有序的结果写入磁盘，此时L=0；

T=2时刻，clickhouse收到一条800条ins