哈希存储引擎、B树存储引擎、LSM树存储引擎详解

女爷i 2022-11-01 10:59 283阅读 0赞

### 哈希存储引擎、B树存储引擎、LSM树存储引擎详解 ###

*  1.前提
 *  2. 哈希存储引擎
 *  3. B树存储引擎
 *  4. LSM树存储引擎
 *   *  4.1 LSM主题思想
     *  4.2 LSM树在HBase中的应用
 *  小结

# 1.前提 #

讲LSM树之前，需要提下三种基本的存储引擎，这样才能清楚LSM树的由来：

*  哈希存储引擎。
 *  B树存储引擎。
 *  LSM树（Log-Structured Merge Tree）存储引擎。

# 2. 哈希存储引擎 #

哈希存储引擎哈希表的持久化实现，支持增、删、改以及随机读取操作，但不支持顺序扫描，对应的存储系统为key-value存储系统。

对于key-value的插入以及查询，哈希表的复杂度都是O(1)，明显比树的操作O(n)快，如果不需要有序的遍历数据，哈希表就非常适合。

代表性的数据库有：Redis，Memcache，以及存储系统Bitcask。

举例Bitcask的哈希表数据结构为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]  
Bitcask数据文件中的数据是一条一条写入操作，记录包含key、value、主键长度、value长度、时间戳以及crc校验值。

数据库所在服务器在内存中采用基于哈希表的索引数据结构，哈希表的作用是通过主键快速地定位到value的位置。哈希表结构中的每一项包含了三个用于定位数据的信息，分别是文件编号（file id），value在文件中的位置（value\_pos），value长度（value\_sz），通过读取file\_id对应文件的value\_pos开始的value\_sz个字节，这就得到了最终的value值。写入时首先将key-value记录追加到活跃数据文件的末尾，接着更新内存哈希表，因此，每个写操作总共需要进行一次顺序的磁盘写入和一次内存操作。

Bitcask在内存中存储了主键和value的索引信息，磁盘文件中存储了主键和value的实际内容。

# 3. B树存储引擎 #

相比哈希存储引擎，B树存储引擎不仅支持随机读取，还支持范围扫描。关系型数据库中通过索引访问数据，在Mysql InnoDB中，有一个称为聚集索引的特殊索引，行的数据存于其中，组织成B+树（B树的一种）数据结构。

B+树的数据结构：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]  
如图所示，MySQL InnoDB按照页面（Page）来组织数据，每个页面对应B+树的一个节点。

其中，叶子节点保存每行的完整数据，非叶子节点保存索引信息。数据在每个节点中有序存储，数据库查询时需要从根节点开始二分查找直到叶子节点，每次读取一个节点，如果对应的页面不在内存中，需要从磁盘中读取并缓存起来。

B+树的根节点是常驻内存的，因此，B+树一次检索最多需要h-1次磁盘IO，复杂度为O(h)=O(logdN)（N为元素个数，d为每个节点的出度，h为B+树高度）。

修改操作首先需要记录提交日志，接着修改内存中的B+树。如果内存中的被修改过的页面超过一定的比率，后台线程会将这些页面刷到磁盘中持久化。

# 4. LSM树存储引擎 #

## 4.1 LSM主题思想 ##

LSM-Tree主题思想为划分不同等级的数。可以想象一份索引由两棵树组成：一个存在于内存（可以使用其他树结构），一个存在于磁盘（如下图）。  
![图片: https://uploader.shimo.im/f/oJra2QZtrUyyJqOn.png][https_uploader.shimo.im_f_oJra2QZtrUyyJqOn.png]  
LSM树的设计思想非常朴素：将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，不过读取的时候稍微麻烦，需要合并磁盘中历史数据和内存中最近修改操作，所以写入性能大大提升，读取时可能需要先看是否命中内存，否则需要访问较多的磁盘文件。极端的来说，基于LSM树实现的HBase的写性能比Mysql高了一个数量级，读性能低了一个数量级。

数据首先会插入到内存中的树，为了防止数据丢失，写内存的同时需要暂时持久化到磁盘，即输入数据时数据会以完全有序的形式先存储在日志文件中（对应HBase的MemStore和HLog）。当日志文件被修改时，对应的更新会被先保存在内存中来加速查询。

当内存中树的数据达到阀值时，会进行合并操作。合并操作会从左至右遍历内存中的叶子节点与磁盘中树的叶子节点进行合并，当合并的数据量达到磁盘的存储页的大小时，会将合并的数据持久化到磁盘。同时更新父亲节点对叶子节点的指针（如下图）。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA5Liq5YaZ5rm_55qE56iL5bqP54y_size_13_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]  
查找通过合并的方式完成，首先搜索内存存储结构，接下来是磁盘存储结构。

LSM树所有节点都是满的并按页存储，经过多次的flush会创建很多数据存储文件，后台线程会将小文件聚合成大文件，因此磁盘的寻道操作就会被限制在一定数目的数据存储文件中，以优化读性能。磁盘上的树结构也可以分割成多个存储文件，因为所有的存储数据都是按照Key有序排列的，因此在现有节点中插入新的关键字不需要重新排序。

LSM-Tree属于传输型，在磁盘传输速率上进行文件的排序和合并以及日志操作，可以更好的拓展到更大的数据规模上，因为它会使用日志文件和一个内存存储结构把随机写操作转化为顺序写，读写独立，不会产生两种操作的竞争。

## 4.2 LSM树在HBase中的应用 ##

LSM树可以看成n层合并树。在HBase中，它把随机写转换成对MemStore和HFile的连续写。下图展示了LSM树数据写的过程。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]  
**数据写（插入，更新）**：数据首先顺序写如HLog（WAL），然后写到MemStore，在MemStore中，数据是一个2层B+树（上图中的C0树）。MemStore满了之后，数据会被刷到StoreFile（HFile），在StoreFile中，数据是3层B+树（图2中的C1树），并针对顺序磁盘操作进行优化。

**数据读**：首先搜索MemStore，如果不在MemStore中，则到StoreFile中寻找。

**数据删除**：不会去删除磁盘上的数据，而是为数据添加一个删除标记。在随后的major compaction中，被删除的数据和删除标记才会真的被删除。

LSM数据更新只在内存中操作，没有磁盘访问，因此比B+树要快。对于数据读来说，如果读取的是最近访问过的数据，LSM树能减少磁盘访问，提高性能。

以上就是hbase存储设计的重要思想，这里说明一下：

*  因为数据是先写到内存中，所以为了防止内存数据丢失，会先把数据写入hlog中，也符合了数据库中标准，先写日志，再写数据
 *  memstore上的树达到一定大小之后，需要flush到磁盘中，然后再定期做合并，提高读取的性能；

# 小结 #

对比三种引擎的实现：

*  `hash存储`引擎：哈希表持久化的实现，可以快速支持增删改查等随机操作，且时间复杂度为o(1)，但是不支持顺序读取扫描，对应的存储系统为k-v存储系统的实现。
 *  `b树存储`引擎：是b树的持久化实现，不仅支持单条记录的增删改查操作，还支持顺序扫描，对应的存储系统就是mysql。
 *  `lsm树存储`引擎和`b树存储`引擎，一样支持，增删改查，也支持顺序扫描操作。LSM牺牲了读性能，提高写性能。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]: /images/20221024/2ea02b0b54a84429a3359d8d6843b0eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]: /images/20221024/9197d7172c5440d08f174899e143c9d0.png
[https_uploader.shimo.im_f_oJra2QZtrUyyJqOn.png]: /images/20221024/a71ef3ac323847b6ad4d02504352bbc1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LiA5Liq5YaZ5rm_55qE56iL5bqP54y_size_13_color_FFFFFF_t_70_g_se_x_16]: /images/20221024/0a41602827ba41db86bf26ae287e07e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]: /images/20221024/a1ce50b3f0b74973a26fdcf3bde3940d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]: /images/20221024/af10be27731f433995b048e8f9cdb645.png