Mysql为什么最终用B+树做索引?

一 .为什么要使用索引?

索引能极大的减少存储引擎需要扫描的数据量 索引可以把随机IO变成顺序IO(索引指向(左小右大)) 索引可以帮助我们在进行分组、排序等操作时，避免使用临时表

二 有哪些数据结构可以优化索引?

• 生成索引，建立二叉查找树进行二分查找
• 生成索引，建立B-Tree结构进行查找
• 生成索引，建立B+-Tree结构进行查找
• 生成索引，建立Hash结构进行查找

2.1如果优化优化索引,提升查找效率,我们可能第一时间想到二叉查找树

如图,二叉查找树采用左低右高的方式建立树,可以相对来说提高我们的查找效率,但是某些极端情况下,如数据一直是升序的,可以导致树像链表一样,查找速度大大下降

2.2 如果是普通二叉查找树,肯定弊端十分明显了--链化

而我们知道,针对普通二叉查找树,我们可以用平衡二叉查找树代替的,这样不久可以解决它的弊端了嘛?

2.3 那为啥不用平衡二叉树呢?

它太深了 数据处的（高）深度决定着他的IO操作次数，IO操作耗时大 它太小了 每一个磁盘块（节点/页）保存的数据量太小了 没有很好的利用操作磁盘IO的数据交换特性(我们可以一次读4K数据的,现在只读了1个结点进去,而且这个结点只存了一个数据,非常浪费操作系统资源) 也没有利用好磁盘IO的预读能力（空间局部性原理）(预读；每一次IO时，不仅仅把当前磁盘地址的数据加载到内存，同时也把相邻数据也加载到内存缓冲区中。) 从而带来频繁的IO操作 操作系统方面具体细节可以百度,百度百科比我说的好...

2.4 以平衡二叉树结点为例,讲解一下mysql中索引存在的结构模型

mysql中,一个结点通常以磁盘块存在,磁盘块中保留着关键字,数据区,子节点引用 其中关键字一半是指我们在建立索引时候的依据,(比如以id为索引,那么关键字就是id) 数据区一般指向真正的数据地址,子节点引用是指向的较小的左磁盘块和关键字值更大的右磁盘块. 我们采用树状结构优化索引不需要一次加载所有磁盘块,而只需要依次比较并加载即可. 如上图,我们找id为8的数据.先加载磁盘块1,发现8<10,通过磁盘块1的左子节点引用找到磁盘块2并加载,8>5...加载磁盘块5,匹配数据,并通过数据区找到真正数据位置.

3 关于B树,B+树结构简单描述一下,扫盲

B树和B+树,每个结点中不再只有左右两个孩子了,而是我们可以定义为任意个孩子,其中m个孩子就是m阶树,我们下面结构图中看到的关键字是结点的值(数据库中可体现在,如果我们用id做索引,关键字就是id),索引则是孩子的指向.其中B树的关键字保存了数据信息,而我们B+树没有,B+树关键字保存的索引信息.

3.1 B-Tree 多路平衡查找树

m阶B树定义

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

3.2为什么用B-树可以很矮,很胖，速度很快呢?

这是因为,我们mysql一般把一个结点数据定义为一页,一页数据是16K=16*1024byte,如果我们用的平衡二叉树,假如定义的索引为int型id,一个id 4byte,加上其他数据一个id索引可能页就8byte左右,这才占了一次io的多少?这何等的浪费资源??而我们用B树后,B树是多路平衡查找树,我们可以定义 16*1024/8 一页数据可以存两千多数据,这样效率提升了何止一点半点呢!

这其实也就是为啥我们一般慎用uuid做主键,因为它长度太长了,如果用uuid,太占用空间,我们索引的路数会变少,层数变少,效率会有所下降.

3.3 B+Tree(Mysql使用的索引数据结构)

B+树是B树的变体，其结构定义基本与B树相同，除了：

• 非叶子节点的子树指针与关键字个数相同
• B+非叶节点不保存数据相关信息，只保存关键字和子节点的引用所有搜索均在叶子结点结束
• 所有叶子节点均有一个链指针指向下一个叶子结点,相邻节点具有顺序引用的关系(便于范围查找)
• B+节点关键字搜索采用闭合区间,就算我们中途知道到了相等的关键字也要一直到叶子 结点

B+Tree结构图

3.3.0 为什么B+Tree更适合用来做存储索引

• B+树的磁盘读写代价更低 B+Tree内部结构并没有指向关键字具体信息的指针,关键字不存放数据,只存放索引信息,因此内部结点相对B-Tree更小; 如果把所有内部结点的关键字存放同一盘块中,这个磁盘块所能容纳的关键字也更多,一次性读入内存中的所需要查找的关键字也就越多,相对来说IO读写次数也就降低了
• B+树的查询效率更加稳定 由于内部结点并不是最终指向文件内容的结点而只是叶子结点中关键字的索引,所以任何关键字的查找必须走一条从根节点到叶子结点的路,所有查询的长度相同,导致每个数据的查询效率也几乎是相同的
• B+树天然有序,更有利于对数据库的扫描 B-Tree树在提高IO性能时候,并没有解决元素遍历效率底下问题.而B+Tree只需要遍历叶子结点就可以解决对全部关键字信息的扫描,做范围查询相当方便(所有叶子节点均有一个链指针指向下一个叶子结点)

B树B+树和之前的平衡二叉树的速度方面为啥差那么多呢?

从查找过程中发现，在结点树比较小的情况下,B树的比对次数和磁盘IO的次数与二叉树相差不了多少，所以这样看来并没有什么优势。过程分析

但是仔细一看会发现，B树B+树都是一次加载许多数据进去,比对是在内存中完成中，不涉及到磁盘IO，耗时可以忽略不计。另外B树种一个节点中可以存放很多的key（个数由树阶决定）。

相同数量的key在B树中生成的节点要远远少于二叉树中的节点，相差的节点数量就等同于磁盘IO的次数。这样到达一定数量后，性能的差异就显现出来了。

Mysql中B+树索引的具体体现形式

......马上讲

4 有没有其他索引可能的选项?

hash和BitMap也可以做索引,但是有一些弊端

运用Hash和itMap

Hash索引结构

Hash索引比较的是进行Hash运算之后的Hash值(Hash运算之后的值并不一定和运算之前的键值一样),因此只能用于等值过滤而不是范围查询 正常来说Hash索引直接比较keys值和经过hash运算之后的buckets值,IO操作更少效率更快,那么为什么我们不用Hash而用B+Tree呢?

4.1 Hash索引缺点

• 仅仅能满足“="，“IN"，不能使用范围查询
• 无法被用来避免数据的排序操作
• 不能利用部分索引键查询
• 不能避免表扫描
• 遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高

4.2 BitMap

BitMap结构

缺点

• 一般只适合只有查询结果只有确认几个值的情况(比如说男女)
• 锁力度较大,因为底层存储位图在高并发情况下可能会发生顺序变化而造成数据丢失,所以必须加锁