介绍

B+树只有叶节点存放数据，其余节点用来索引，而B树是每个索引节点都会有Data域。所以从Mysql（Inoodb）的角度来看，B+树是用来充当索引的，一般来说索引非常大，尤其是关系性数据库这种数据量大的索引能达到亿级别，所以为了减少内存的占用，索引也会被存储在磁盘上。

那么Mysql如何衡量查询效率呢？– 磁盘IO次数。

为什么不用B树

1、B+树的IO次数少

B树的每个节点都有data域（指针），这无疑增大了节点大小，说白了增加了磁盘IO次数（磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，一次IO多耗时），而B+树除了叶子节点其它节点并不存储数据，节点小，磁盘IO次数就少。

2、B+树查询速度更稳定。

B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;

3、B+树天然具备排序功能。

B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。

4、B+树全节点遍历更快。

B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

为什么不用红黑树

B树是多路树，红黑树是二叉树！红黑树一个节点只能存出一个值，B树一个节点可以存储多个值，红黑树的深度会更大,定位时 红黑树的查找次数会大一些。

数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

  1. 在增删改查的过程中，时间复杂度为log2n，而b+是logmN，体现在内存和磁盘的IO上，代价比较大。在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下的情况,B树可以有多个子女，从几十到上千，可以降低树的高度。
  2. 特别是插入的时候，红黑树需要进行节点颜色调整，对于频繁的插入而言，这是一个耗时的过程，而b+树仅仅是页分裂问题。另外从并发交付来说，要么线程不安全，要么加锁虽然线程安全，但是牺牲了效率。
  3. 区间查找而言，b+树的叶子节点带有双向链表，因此比较方便。对于红黑树而言，虽然可以实现，比如通过中序遍历的方式，但是实现起来比较复杂。

为什么不用哈希表

MySQL中存储索引用到的数据结构是B+树，B+树的查询时间跟树的高度有关，是log(n)，如果用hash存储，那么查询时间是O(1)。既然hash比B+树更快，为什么mysql用B+树来存储索引呢？

  1. 假设瓶颈不在hash数组上（hashmap由数组加链表构成），一方面，对于庞大数据量的链表来说，查找的时间复杂度为O（n），
  2. 另一方面从磁盘IO性能考虑，链表足够长，频繁的io会导致极差的性能。
  3. 对于区间查找，可行性为0。

为什么不用跳表

  1. 虽然在区间查找上两者不相上下，如果纯粹基于内存工作，那就是redis。两者的主要区别，那就是一个是关系型，另一个是非关系型，redis是基于某个key进行排序构造的，如果像mysql那样建立二级索引，那么每一个都是“聚簇索引”，得不偿失，维护也麻烦（就是说跳表无法解决索引问题）。
  2. 还是数据关系型的问题，虽然说跳表这个结构也可以以Json格式来存储数据库的行数据，但是类似主外键关系、模糊查找等功能，无法提供或者提供起来较为繁琐。
  3. 如果考虑到足够大的数据，大到需要使用硬盘的话，内存和磁盘进行io的内容会是什么？是跳表的每一层数据，前几层可能还好，越往下，可能不是一次页交换可以容纳下的，那么跳表在查找上的优势尽失，反观mysql，每次交换出来的非叶子节点都是索引，可查找范围大，io次数少，性能高。

参考

为什么mysql用B+树做索引而不用B-树或红黑树

跳表，红黑树，b+树，hashmap的区别？