什么是log式存储？

log式存储：只能向文件尾追加记录，写入文件的数据就不能再改动了。这是最快的写文件方式（据说比随机写内存还快！），其中的哲学就是，这是最简单的写文件方式，简单带来高效；实际原因是，顺序写磁盘时，磁盘臂不需要寻道，另外也可以先写入内存，达到一定量后，一次性flash到磁盘

最简单的log存储引擎

写数据

向文件尾追加数据。接下来问题是如何读数据

读数据

最暴力方法：逆序扫描文件，直到发现数据，效率O(n)

为了优化读取速度：可以建立索引。由于是log存储方式，文件中的key是乱序的，因此为了快速查找，必须为每个key建立索引。其实就是维护一个hash表，记录每个key在磁盘上的位置。缺点：所有key必须存放于hash表中（内存中），限制了存储引擎可以存储的数量。Bitcask就是这样实现的。我一种直觉是：索引没必要保存所有的key。下一节，我们看看是否有办法令索引只保存少量key，即可查到指定的key

对log排序的存储引擎

原理

其实，log方式严格保持记录的时序，适合作为消息队列的存储结构

但是，数据库对时序的要求低很多：数据库只要求，同一个key的更新操作必须遵守时序，不同key的顺序可以任意

如果数据库中，不同key之间是有序的，那么二分查找就可以，索引可以采用红黑树、跳表。

这就是SSTable（Sorted String Table），key有序的存储文件。

实现

数据存储的实现：写数据时，先写到内存中（红黑树），内存达到阈值，就把数据flash到磁盘形成SSTable。SSTable多了，就merge。

索引的实现：每个SSTable有一个索引文件，索引支持二分，所以可以用红黑树或跳表。

当然还有些细节优化，比如SSTable存储的数据，可以进行分块压缩，用来降低需要的磁盘空间，也可以提高数据载入内存的速度。具体：可以研读一下《Designing Data-Intensive Applications》一书的“SSTable and LSM-Trees”一节，Leveldb，RocksDB，HBase，Cassandra，Lucene 都是这样实现的

时间复杂度

写：直接写入内存，O(logn)

读：O(logn1) + (width + hight)*O(S) * O(logn2) width是顶层SSTable数量，hight是SSTable层数，O(S)是访问磁盘的复杂度，两个O(logn)都是查找内存中的红黑树的复杂度。但是！！！查找可以被优化，在加载索引前，可以先查bloom filter，每个SSTable有一个bloom filter，所有bloom filter存放在内存中，这样，访问磁盘次数可以降低到两次（一次加载索引，一次加载数据）

容错

任何系统，都要考虑容错。当数据库进程崩溃，机器意外宕机时，会出现的问题是：内存中的数据丢失，应对措施是，每次更新一条记录时，同时向磁盘输出一条log，通过log，可以完整复现所有的更新操作。这就是WAL（write ahead log），由于向文件追加log属于顺序写磁盘，所以速度非常快。另外，log不必要是无限长的，已经落盘的数据，对应生成它们的log可以扔掉，只保留内存数据的log即可。

总结

小数据量的情景，用简单的log是存储即可，必要时加一个hash索引，实现方便简单

数据量大的情景，还是需要维护一个有序的数据结构，然后二分查找。

采用SSTable后，不再是严格的log式存储。牺牲了一点写效率，但是，读数据时，只需两次磁盘访问，提高了读效率。从时间复杂度上分析，写效率仍然很优秀，读效率比写要差很多，适合写多读少的情景。另外，由于底层存储（SSTable）中，key是有序的，scan操作效率非常高。