LSM 树(Log-Structured Merge Tree)

LSM树而且通过批量存储技术规避磁盘随机写入问题。

LSM树的设计思想非常朴素, 它的原理是把一颗大树拆分成N棵小树,它首先写入到内存中(内存没有寻道速度的问题,随机写的性能得到大幅提升),在内存中构建一颗有序小树,随着小树越来越大,内存的小树会flush到磁盘上。磁盘中的树定期可以做merge操作,合并成一棵大树,以优化读性能。

常见索引对比

一般来说,索引本身很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。

这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以决定索引性能的一个最重要指标就是在查找过程中磁盘I/O操作次数的渐进复杂度,换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

一般来讲,索引有如下几种数据结构:

B+ Tree

1、B+树索引:mysql的默认索引类型,B+树的内结点只存储了key没有存储data,节点的出度大,树的高度小,查找的磁盘寻址次数就少,因此拥有不错的性能

Hash

2、hash索引:hash表的查找复杂度只有O(1),索引的检索可以一次定位,不像B+Tree 索引需要从根节点到枝节点,但不支持范围查找,另外在有大量重复键值或者数据量非常大的情况下,哈希索引的效率也是极低的,因为存在所谓的哈希碰撞问题。

FULLTEXT

3、FULLTEXT索引:全文索引,lucene、elasticsearch的默认索引类型,也叫反向索引、倒排索引,即根据关键字来找到文档

空间索引

4、空间索引:mongodb和MySQL 5.7之后的版本都支持空间索引,用于对GIS数据类型的索引,比如根据自己所在位置查询来查询附近50米的POI(point of interest)

位图索引

5、位图索引:位图索引是一种特殊的索引,适用范围比较小,只适用于字段值固定并且值的种类很少的情况,比如性别,只能有男和女,或者级别,状态等

ps: 这种常规的索引效果不好,直接使用位图索引看起来不错。

LSM

6、LSM:Log Structured-Merge Tree,当前许多产品都在使用,比如HBase, Cassandra, LevelDB, SQLite。

LSM通过消去随机的本地更新操作,把磁盘随机写操作变为顺序写操作,从而得到更好的写操作吞吐量。

LSM树的设计思想非常朴素,将对数据的修改增量保持在内存中,达到指定的大小限制后将这些修改操作批量写入磁盘。

文件是不可修改的,他们永远不会被更新,新的更新操作只会写到新的文件中。读操作会依次从最新的文件查找,通过周期性的合并这些文件来减少文件个数。所以写入性能大大提升,读取时可能需要先看是否命中内存,否则需要访问较多的磁盘文件。

综上,LSM索引相比哈希索引能够大幅提高写性能,数据量非常大的情况下因为哈希碰撞哈希索引的效率低。

拓展阅读

B+ Tree

参考资料

https://blog.csdn.net/qq_26222859/article/details/79645243