mysql的innodb为什么用b+树, 不用红黑树/b树/跳表/LSM[上]?

思路

1.对比各个数据结构的优缺点
2.描述mysql的特点, 磁盘io, 页
3.用了b+树会给innodb带来什么好处
4.对比其他数据库说出区别, MongoDB, redis, RockDB

几种树的特点

红黑树

是一棵二叉树
近乎完全平衡
具有稳定的时间复杂度O(nlogN)

b树

树内的每个节点都存储数据
叶子节点之间无指针相邻

B+树

数据只出现在叶子节点
所有叶子节点增加了一个链指针

树的详细特点

mysql的innodb的底层数据结构从二叉树->AVL树->红黑树->b树->b+树的进化, 首先说明, 并不是除了b+树, 其他树就没有用处, 并不是的, 各类数据结构都有其用处, 只是面向的应用场景不一样.

二叉搜索树一般作为排序查找用, 刷算法的时候见得最多的就是它, 二叉搜索树虽然搜素快, 但是其有一个缺点就是最坏时间复杂度可退化为O(n), 退化成链表结构, 所以一般在开源软件中, 比较少见到它的出现.

AVL树也是二叉树, 不过它是一棵完全保持平衡的树, 即左右子树间的高度差不大于1, 严格遵守这个约束. 但是为了保证这个平衡, AVL树在动态插入删除时会花费更多的额外时间来进行左旋右旋来让树保持完全平衡. 这样在真正实际中是不科学的, 因为使用二叉搜索树就是为了加快查询, 但是要花费这么多额外的时间来保持平衡, 可能得不偿失.

所以, 一种实用性更好的平衡树被实现了. 红黑树是一棵平衡树, 但它不是完全平衡的, 不过会通过引入红黑两种意义上的节点来尽量保证左右子树高度差不大于1, 但有保证有良好的性能. 所以红黑树被应用在很多的开源软件中, 因为其快速的查找效率和稳定的时间复杂度O(logN). 比如linux的虚拟内存管理, c++STL的map, java的Hashmap, 经常作为hash结构的冲突元素存放结构等.

引出的问题

以上几个都是二叉树, 二叉树虽然是搜索查询性能好, 但一般是指在内存中. 如果是应用在磁盘这类的搜索, 那么会有以下几个问题:

1. 数据非常大时, 树高度会很高, 造成磁盘io扫描次数很高
1. 一个节点只是存放一个数据, 数据与数据之间在物理内存相隔甚远, 磁盘扫描需要频繁转动
1. 需要频繁的从磁盘读数据到内存中, 即使操作系统有预读, 但是带出来的大多是暂时用不上的无用数据, 造成浪费

鉴于以上几个问题, 有以下几点需要优化的:

1. 减少磁盘io扫描次数
1. 减少磁盘io转动频率
1. 利用好操作系统的预读, 局部性原理

更合适的数据结构

b树的出现就是为了解决以上问题(但并不是全部问题) 从以上b树的特点知道了, b树是N叉树, 层高大大降低, 因此可以减少磁盘io的扫描次数, 并且b树每个节点不是以一个数据为单位, 而是以页, 每个节点就是操作系统的一个页的大小, 因此可以存放更多的数据. 较好的利用操作系统预读, 局部性原理的特点, 每次从磁盘读出一个页, 然后再来查询.

由于b树所有的节点都可能包含目标数据，总是要从根节点向下遍历子树查找满足条件的数据行，这个特点带来了大量的随机 I/O，也是b树最大的性能问题.

但是, 在mysql的innodb中为什么不选用b树呢? 并不是b树不好, 而是有比他更合适的. b+树

b+树拥有b树的所有优点, 并且b+树的非叶子节点不存放数据, 而是单单存放索引, 只有在叶子节点存放索引+数据, 并且叶子节点通过前后指针构成双向链表的结构, 因此通过树结构定位到索引后, 可以通叶子节点的链表指针很快的直接遍历得到范围查询的结果这样更好的利用了顺序io比随机io性能更高的优化. 这个特点是b树不具备的.

b+树是innodb的底层数据结构, 通过N叉树, 节点页, 叶子节点链表串起来, 避免了过多的磁盘io扫描, 转动次数, 并且利用了操作系统的预读和局部性原理, 更支持了范围查询的功能.

跳表/LSM

下一章分析…未完待续

mysql b+树