听了蚂蚁金服OceanBase的一场线下MeetUp,了解到其底层使用LSM, 又分动态数据区和静态数据区.其中动态数据区使用B+树和HashTable,前者用于范围检索,后者用于更快速的单行直等查询.

最近频繁听到LSM,一探究竟,在此记录.


非常适用于写多读少的场景


此前看过操作系统的文件系统, 磁盘的顺序读写随机读写,差了三个数量级.

对于Mysql的Innodb存储引擎, 对数据读取,做了比较好的优化.但写入操作的效率一直饱受诟病(关系型数据库的通病).

查找primary-key的过程很高效,但是调整B+树的磁盘IO开销却很大,因此关系型数据库mysql的写效率一致饱受诟病。那有没有一种替代B+树的数据组织模型,在不太影响读效率的前提下,提高数据的写效率(随机写->顺序写)



参考:

关于LSM树:

浅析LSM存储模型

在LSM里面,我们把内存里的二叉树称为memtable。

布隆过滤器的特点是,它可能会把一个不存在的key判定为存在;但是它绝不会把一个存在的key判定为不存在。这是可以接受的,因为对于极少数误判为存在的key,只是多几次搜索而已,只要不会将存在的key误判为不存在就行。而且它带来的好处是显而易见的:可以节省大量的对不存在的key的搜索时间。

如果把key作为搜寻目标的是,那布隆过滤器的特点就是”宁肯误杀,绝不漏过”

LSM存储引擎基本原理

数据存储检索之B+树和LSM-Tree

LSM-Tree,即日志结构合并树( Log-Structured Merge-Tree)

看图轻松理解数据结构与算法系列(NoSQL存储-LSM树)


有道云笔记-lsm

LSM树由来、设计思想以及应用到HBase的索引


关于B+树:

B-Tree和B+Tree

数据结构: B-Tree 简介及插入

BTree和B+Tree详解

什么是B-Tree


论文:

The Log-Structured Merge-Tree (LSM-Tree)