数据库中三种基本的存储引擎
1. 三种基本存储引擎概述
哈希存储引擎(Redis)
哈希表的持久化实现，支持增、删、改以及随机读取操作，但不支持顺序扫描,对应的存储系统key-value存储系统。对应key-value的插入以及查询，哈希表的复杂度都是O(1),明显比树的操作快，如果不是遍历有序数据，推荐使用Hash存储引擎。B(+)树存储引擎(B-树 MongoDB B+树 MySQL)
持久化实现，不仅支持单条记录的增删改查，还支持顺序扫描(B+树的叶子节点之间的指针)，对应的存储系统就是关系型数据库MySQL。
- LSM树(Log-Structed Merge Tree)存储引擎(HBase)
和B树存储引擎一样，同时支持增删改查顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。
2. B(+)树 [B-树也称为B树]
B[-]树
树是有序的，且查找效率高，考虑到磁盘IO问题，数据库索引是存储在磁盘上的，当数据量比较大的时候，索引的大小可能有几个G甚至更多。当利用索引查询时，不可能将整个索引加载到内存中，能做的只有逐一加载每一个磁盘页，磁盘页对应着索引树的节点。
当使用二叉树来存储索引时，最坏的情况下磁盘的IO次数等于索引树的高度，为了减少IO的次数，将原先瘦高的二叉树转换成矮胖的B-(B)树。
B树是一种多路平衡查找树，它的每一个节点最多包含k个孩子，k被称为B树的阶。k的大小取决于磁盘页的大小。
B - 树的基本特征:一个m阶的B树
- 根节点至少有两个子女。
- 每个中间节点都包含k-1个元素，其中m/2 <= k <=m。
- 每个叶子节点都包含k-1个元素，其中 m/2 <= k <= m。
- 所有叶子节点都位于同一层。
- 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
一个3阶B[-]树:一个节点包含的最大节点数(有序)
B树的插入和删除操作较为复杂，为了维持多路平衡，需要进行位置变换操作。
3. LSM树(日志结构合并树)
一个LSM树
设计思想:
将对数据的修改增量保存在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，不过读取的时候稍微麻烦，不过读取的时候稍微麻烦，需要合并磁盘历史数据和内存中最近修改操作，所以写入性能大大提升，读取时可能需要先看是否命中内存，否则需要访问较多的磁盘文件。极端的来说，基于LSM树实现的HBase写性能比MySQL高了一个数量级，读性能低了一个数量级。
原理:
把一颗大树拆分成N棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树会定期做merge操作，合并成一棵大树，以优化读性能。
HBase架构图
HBase存储的设计思想
- 因为小树先写到内存中，为了防止内存数据丢失，写内存的同时需要暂时持久化到磁盘，对应了HBase的MemStore和HLog。
- MemStore上的树达到一定大小之后，需要flush到HRegion磁盘中(一般是Hadoop DataNode),这样MemStore就变成了DataNode上的磁盘文件StoreFile，定期HRegionServer对DataNode的数据做merge操作，彻底删除无效空间，多个小树在这个时机合并成大树，来增强读性能。