Mysql-为什么使用B+树

1、普通二叉查找树：
左边节点值比根节点小，右边节点值比根节点大，复杂度O(n)


优点：可以解决大量数据索引无法一次加载进内存中的问题，二叉搜索树可以批量加载数据进内存
缺点：检索时间与树的高度有关，树的高度越高，检索次数及时间相对就越久
     极端情况下，如果数据本身就是有序的，二叉搜索树就会退化成链表，性能会急剧降低(弊端--链化)

2、平衡二叉树：
它是动态的，左右同一层级左右子树的绝对值不会大于1，其随着树的高度增加，查找速度也越来越慢，复杂度O(logn)

优点：始终保持同一级左右子树的绝对值不会大于1
缺点：
1、数据的深度(高度)决定着他的IO操作次数，IO操作耗时大
2、每一个磁盘块（节点/页）保存的数据量太小了，没有很好的利用操作磁盘IO的数据交换特性， 
   也没有利用好磁盘IO的预读能力， 从而带来频繁的IO操作
   
   交换特性：我们可以一次读4K数据的，现在只读了1个结点进去，而且这个结点只存了一个数据，非常浪费操作系统资源
   预读能力：每一次IO时，不仅仅把当前磁盘地址的数据加载到内存，同时也把相邻数据也加载到内存缓冲区中

以平衡二叉树结点为例，讲解一下mysql中索引存在的结构模型：
1、mysql中，一个结点通常以磁盘块存在，磁盘块中保留着关键字、数据区、子节点引用
2、其中关键字一半是指我们在建立索引时候的依据，(比如以id为索引，那么关键字就是id)
3、数据区一般指向真正的数据地址，子节点引用是指向的较小的左磁盘块和关键字值更大的右磁盘块。
4、我们采用树状结构优化索引不需要一次加载所有磁盘块，而只需要依次比较并加载即可。
5、如下图，我们找id为8的数据，先加载磁盘块1，发现8<10，通过磁盘块1的左子节点引用找到磁盘块2并加载，
   8>5...加载磁盘块5，匹配数据，并通过数据区找到真正数据位置。
   
例：   
1、查10：3次
2、回旋查找的问题：
   查找大于5的数据：先定位到5，然后再往回查找大于5的数据，若大于5的数据很多时，效率则很慢

B-Trees树的特性
B-树所有节点中不仅存储键值，也会存储数据（key,value）
1、根节点至少包括两个孩子
2、树中每个节点最多含有m个孩子（m>=2）(m个孩子就称之为m阶树)
3、关键字个数最多为m-1个(根据孩子结点来的,比孩子结点少一个)
4、除根节点和叶节点外，其他每个节点至少有ceil（m/2）个孩子
   (为什么是ceil(m/2),主要是为了最大限度降低层高，提高搜索效率。)
5、所有叶子节点都位于同一层

例：
1、查10：2次。   解决了树的高度问题：树越矮，查找速度越快
2、回旋查找的问题：（依然存在）
   查找大于5的数据：先定位到5，然后再往回查找大于5的数据，若大于5的数据很多时，效率怎很慢

B+Trees树 的特性：
1、非叶子节点只存储key值，不存储数据的。
2、叶子节点即存储(key,value)，即存储数据。
3、B+Trees树 比 B-Trees树 多了一个单向链表(非叶子节点)，链表对所有数据进行了一个从小到大排序

为什么B+Tree更适合用来做存储索引?
1、B+树的磁盘读写代价更低：
2、B+树的查询效率更加稳定：
3、B+树天然有序，更有利于对数据库的扫描：

为什么使用B+树：
1、B+ 树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的，链表连着的。
2、那么 B+ 树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。
3、B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比存储即存索引又存记录的 B 树，
   B+ 树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O次数会更少。

Hash 索引和 B+ 树索引区别是什么？
1、B+ 树可以进行范围查询，Hash 索引不能。
2、B+ 树支持联合索引的最左侧原则，Hash 索引不支持。
3、B+ 树支持 order by 排序，Hash 索引不支持。
4、Hash 索引在等值查询上比 B+ 树效率更高。
5、B+ 树使用 like 进行模糊查询的时候，like 后面（比如%开头）的话可以起到优化的作用，Hash 索引根本无法进行模糊查询。


1、查10：3次。
2、回旋查找的问题：通过单向链表解决了该问题(所以该B+树范围查找速度非常快，这也是为什么排序的时候，需要使用索引排序)
   查找大于5的数据：先定位到5，然后直接把5后面的数据直接从单链表中拿出来，不用再向之前通过回旋查找一个一个拿去大于5的值。