LSM-Tree全称是Log Structured Merge Tree（日志合并树），是一种分层，有序，面向磁盘的数据结构，其核心思想是充分了利用了，磁盘批量的顺序写要远比随机写性能高出很多，围绕这一原理进行设计和优化，以此让写性能达到最优，正如我们普通的Log的写入方式，这种结构的写入，全部都是以Append的模式追加，不存在删除和修改。当然有得就有舍，这种结构虽然大大提升了数据的写入能力，却是以牺牲部分读取性能为代价，故此这种结构通常适合于写多读少的场景。故LSM被设计来提供比传统的B+树或者ISAM更好的写操作吞吐量，通过消去随机的本地更新操作来达到这个目标。这里面最典型的例子就属于Kakfa了，把磁盘顺序写发挥到了极致，故而在大数据领域成为了互联网公司标配的分布式消息中间件组件。
虽然这种结构的写非常简单高效，但其缺点是对读取，特别是随机读很不友好，这也是为什么日志通常用在下面的两种简单的场景：
- 数据是被整体访问的，大多数数据库的WAL（write ahead log）也称预写log，包括mysql的Binlog等
- 数据是通过文件的偏移量offset访问的，比如Kafka。
想要支持更复杂和高效的读取，比如按key查询和按range查询，就得需要做一步的设计，这也是LSM-Tree结构，除了利用磁盘顺序写之外，还划分了内存+磁盘多层的合并结构的原因，正是基于这种结构再加上不同的优化实现，才造就了在这之上的各种独具特点的NoSQL数据库，如Hbase，Cassandra，Leveldb，RocksDB，MongoDB，TiDB等。
C0 Tree 和 C1 Tree 可能是某种结构树，如：二叉树，B-tree，B+tree，red-black tree，skipList。
LSM-TREE 最核心的思想是：做延迟的归并排序，会先把数据写入到日志里以追加的方式，然后写到内存中，并以 tree 的结构管理，当写入的数据在内存中达到一定的阀值，在以顺序方式映射到磁盘中，这种方式在磁盘中会有很多的小子树，每个树都会有自己的索引位置。当查询的时候会便利所有的小子树的索引文件，这种方式并没有一个整树读取的快，所以 LSM-TREE 牺牲了部分的读性能，换取更高的写性能（因为不需要在对以前的数据进行排序，只对内存的排序）。
当达子树达到一定量的时候可以进行合并，减少读性能的丢失。
C0树不一定要具有一个类B-树的结构。Hbase 中采用了线程安全的 ConcurrentSkipListMap 数据结构。
Hbase 底层会为Hbase的row-key建立索引，索引在通过行键查询时，速度很快，在实际的应用场景中，一般也是按行键来查询。但是目前Hbase的短板在于没有为列建立索引机制。所以很多企业解决办法：通过ES（全文检索引擎）为Hbase建立索引。这种模式称为Hbase的二级索引。
网友评论