前言

网上已经有了很多相关mysql索引原理的文章，但是都存在一些问题，有的是直接复制别人的比较老的文章，有的直接开篇讲B+Tree的原理，过程不是很清楚，即使原理讲清楚了，没有各种数据结构的对比也很难体现出B+Tree的优越性，其实我觉得从一些问题来看，然后根据发现问题解决问题的思路来看，这样可能学习效果会更好，所以写了这篇文章，希望你能喜欢

问题列表

1:数据库中最常见的优化方式是什么？
加索引(相信这个大家都知道)
2:为什么加索引能优化慢查询？
。。。。。
3:哪些数据结构可以优化查询速度？
。。。。。
4:这些数据结构都可以优化查询速度，为何mysql会选择B+Tree
。。。。。

数据库查询过程

对于一般字段而言，mysql查询都是采用的全表扫描的方式来进行数据查询

WechatIMG111007.png

索引的几种数据结构

在这里先给大家介绍一个网站
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
这个网站可以模拟各种数据结构的插入和查找的动画过程，这样更容易理解

二叉树

二叉树其实就是遵循了一个规律来排列，左小右大

二叉树.png

这样的话比比如我们查询9 通过两次比对就可以查询到

但是二叉树这种数据结构存在一些问题，比如数据是递增或者递减的顺序插入，二叉树就很容易形成单路链表

单路链表

如果遇到这种情况那么查找数据就普通的没有加索引的情况没什么区别了

红黑树

红黑树是一种自平衡二叉查找树，平衡二叉树的目的是为了减少二叉查找树层次，提高查找速度
比如依次插入 1到9，二叉树可能就和上图所展示的单路链表一样，红黑树可以自动旋转，减少层数

红黑树.png

散列表(hash)

散列表也为哈希表，又直接寻址改进而来。在哈希的方式下，一个元素k处于h(k)中，即利用哈希函数h，根据关键字k计算出槽的位置。函数h将关键字域映射到哈希表T[0...m-1]的槽位上

散列表

散列表的缺点
1）Hash 索引仅仅能满足”=”,”IN”和”<=>”查询，不能使用范围查询。
2）Hash 索引无法被用来避免数据的排序操作。
3）Hash 索引不能利用部分索引键查询。
4）Hash 索引在任何时候都不能避免表扫描。
5）Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。

B树

为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构：

• d为大于1的一个正整数，称为B-Tree的度。
• h为一个正整数，称为B-Tree的高度。
• 每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d。
• 每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null 。
• 所有叶节点具有相同的深度，等于树高h。
• key和指针互相间隔，节点两端是指针。
• 一个节点中的key从左到右非递减排列。
• 所有节点组成树结构。
• 每个指针要么为null，要么指向另外一个节点。
• 如果某个指针在节点node最左边且不为null，则其指向节点的所有key小于v(key1)v(key1)，其中v(key1)v(key1)为node的第一个key的值。

• 如果某个指针在节点node最右边且不为null，则其指向节点的所有key大于v(keym)v(keym)，其中v(keym)v(keym)为node的最后一个key的值。
  如果某个指针在节点node的左右相邻key分别是keyikeyi和keyi+1keyi+1且不为null，则其指向节点的所有key小于v(keyi+1)v(keyi+1)且大于v(keyi)v(keyi)。

  
  
  BTree

另外，由于插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质，而且B-Tree也是不支持范围查找的，所以一般不采用

B+树

B+Tree其实和BTree类似，但是也有很多区别，我们先看图

image

image

B+Tree的叶子节点

image

注意：聚簇索引(Innodb)的叶子节点包含了整行数据和索引

innodb的索引如图所示

innodb索引.png

而非聚簇索引(myisam)的叶子节点只包含了索引，而不包含数据行本身
其实从数据库保存文件也能看出来，对于非聚簇索引(myisam)的表来说，数据库保存了三个文件
user_m.frm 表结构定义数据
user_m.MYD 表数据
user_m.MYI 索引文件
myisam索引如图所示

mysiam索引.png

而非聚簇索引(Innodb)，数据库只保存了一个文件user_i.frm 所以说他的索引和数据是在一起的。
有一个非常形象的例子大家可以理解一下
非聚簇索引(myisam)相当于是一本书前面的目录，咱们可以根据目录去找到对应的内容
而聚簇索引(Innodb)相当于是书每一页下面的页码，页码和书本的内容是在一起的
B+Tree的优势

1. 在单元素查询的时候，B+Tree会从根节点，逐层向下查找，最终找到要匹配的叶子节点，只需要三次磁盘IO就能找到，这个流程看起来和BTree差不多，其实并不是这样

• 首先B+树的非叶子节点不包含数据，所以同样的磁盘页可以容纳更多的节点元素，所以相同的数据情况下，B+Tree会显得更加“矮胖”，所以查询磁盘IO的次数会少
• 另外B+Tree的查询必须最后查找到叶子节点，而B-Tree只要找到了元素即可，不一定必须是得找到叶子节点，所以B-Tree的查询性能很不稳定，B+Tree的查询性能相对稳定很多。

2. 对于范围查询来说B-Tree非常麻烦，如下图

   
   
   image
   
   

   比如我想查找大于3的数据
   中序遍历到元素6：
   中序遍历到元素8：
   中序遍历到元素9：
   中序遍历到元素11，遍历结束：

   
   
   image
   
   这种回环运算非常麻烦
   像B+Tree就简单了很多
   

   直接叶子节点链表指过去就行

   
   
   image

最后总结一下B+Tree的特征和优势
B+树的特征：

• 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

• 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

• 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

B+树的优势：

• 单一节点存储更多的元素，使得查询的IO次数更少。

• 所有查询都要查找到叶子节点，查询性能稳定。

• 所有叶子节点形成有序链表，便于范围查询。

索引下推

符合索引(age,name)
在5.6之前
先根据name把所有数据查询出来，然后在server层进行age所有字段筛选
在5.6 之后
从存储引擎拉取数据的时候，会根据age 和name两个字段做筛选，将符合条件的数据拉回

计算数据库能存储多少数据的方法(大概计算)

首先每个索引页可以存储的大小是16kb，这个值可以查到

show global status like 'innodb_page_size'

计算方法如图

innodb索引.png

辅助索引

上面我们说的其实都是基于主键索引，如果非主键索引(辅助索引)查询数据是什么样的呢？
① 在辅助索引上检索name(这个name是例子，意思是代表非主键索引)，到达其叶子节点获取对应的主键；
② 使用主键在主索引上再进行对应的检索操作
这个过程也被称为回表

覆盖索引.png

之所以这么做的原因是 保证数据一致性和节省存储空间，可以这么理解：商城系统订单表会存储一个用户ID作为关联外键，而不推荐存储完整的用户信息，因为当我们用户表中的信息（真实名称、手机号、地址）修改后，不需要再次维护订单表的用户数据，同时也节省了存储空间

select * from table where name = ‘123’；
select id from table where name = ‘123’；
两个表查询的过程是不一样的 select * 需要回表
覆盖索引：在查询普通索引的时候，如果叶子节点保存的刚好是要查询的字段，此时叫覆盖索引