一、什么是索引？
众所周知，建立索引可以让数据库查询更快，那么索引究竟是什么？
索引，是数据库管理系统中一个排序的数据结构，并用以协助快速查询、 更新数据库表中数据。
是的，索引是一种数据结构，但是那么多的数据结构中为何MySQL要选择B+树呢？
MySQL5.5以后InnoDB储引擎使用的索引数据结构主要用：B+Tree；
下面内容让我们一起来了解下B+树相对于其他数据结构有何独特之处！
二、索引的优缺点
1、优点
- 索引大大减小了服务器需要扫描的数据量
- 索引可以帮助服务器避免排序和临时表
- 索引可以将随机I/O变成顺序I/O
2、缺点
- 虽然索引大大提高了查询速度，同时却会降低更新表的速度，如对表进行INSERT、UPDATE和DELETE。因为更新表时，MySQL不仅要保存数据，还要保存索引文件。
- 建立索引会占用磁盘空间的索引文件。一般情况这个问题不算严重，但如果你在一个大表上创建了多种组合索引，且伴随大量数据量插入，索引文件大小也会快速膨胀。
- 如果某个数据列包含许多重复的内容，为它建立索引就没有太大的实际效果。
- 对于非常小的表，大部分情况下简单的全表扫描更高效；
因此应该只为最经常查询和最经常排序的数据列建立索引。（MySQL里同一个数据表里的索引总数限制为16个）
数据库存在的意义之一就是是解决数据存储和快速查找的。那么数据库的数据存在哪？没错，是磁盘，磁盘的优点是啥？便宜！缺点呢？相比内存访问速度慢。
那么你知道MySQL索引主要使用的数据结构么？
B+树！
那 B+树 是什么样的数据结构？MySQL索引又是为什么选择了B+树呢？
其实最终选用 B+树 是经历了漫长的演化：
二叉排序树 → 二叉平衡树 → B-Tree（B树） → B+Tree（B+树）
有小伙伴问我“B树 跟 B-树有什么区别”？这里普及一下，MySQL数据结构只有B-Tree（B树）和B+Tree（B+树），多只是读法不同罢了，“B-Tree” 一般统称为B树，你叫他B-树~~
三、B+Tree索引的前世今生
1、二叉查找树(BST）
二叉查找树简称二叉树(BST)，英文全称：Binary Search Tree，这是一种什么样的数据结构呢？请看下图
在上面这棵树中，我们要找到8，先从根节点6开始比较，发现8比6大，就往右边走，就可以找到8
二叉树有两个特点
- 左子树所有的节点都小于父节点
- 右子树所有的节点都大于父节点
二叉树存在的问题
二叉树有一个严重的问题，那就是它的查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成 O(n)。
如下图：
上面就是一种极端情况下的二叉树，会退化成线性链表，这种如果要找到最后一个数6，就要从1开始遍历完整棵树，效率就会非常低。那么有没有一种相对平衡一点，不要出现这种极端情况的数据结构呢，所以就有了平衡二叉树。
2、平衡二叉树(AVL Tree)
平衡二叉树，英文全名叫做 Balanced binary search trees，简称AVL树，这个AVL并不是英文名的简称，而是发明者(G. M. Adelson-Velsky和E. M. Landis)两个人的人名缩写，请看下图一个平衡二叉树示例：
上图中也是从1开始插入6，如果是二叉树就会变成一种线性结构，但是平衡二叉树就会通过左旋和右旋操作，最终会生成上图所示的结构，感兴趣的可以进入网站自己操作观察旋转过程.
平衡二叉树的特点
平衡二叉树相比较二叉树具有一个特点就是：左右子树深度差绝对值不能超过 1，当然，平衡二叉树首先是一颗二叉树，只不过通过左旋和右旋实现左右子树深度差不超过1，避免了二叉树的极端情况的出现。
MySQL为何不选择平衡二叉树
既然平衡二叉树解决了普通二叉树的问题，那么mysql为何不选择平衡二叉树作为索引呢?
AVL树用来存储索引存在什么问题
我们知道，页（Page）是 Innodb 存储引擎用于管理数据的最小磁盘单位，页的默认大小为16KB。页也就是上图中的节点，每查询一次节点就需要进行一次IO操作，IO操作是一种非常耗时的操作，很多业务系统的瓶颈都是卡在IO操作上，所以如果我们需要提高查询效率的办法之一就是减少IO次数，那么问题就来了，AVL树一个节点上只存了一个关键字(索引值)+一个磁盘地址+左右节点的引用，这是远远达不到16KB的，会浪费了大量的空间。
上图中如果我们要找到6这条数据，需要进行3次IO(获取一个节点就是一个IO操作)，如果这棵树很高的话，就会进行大量的IO操作，所以说AVL树存在的最大问题就是空间利用不足，浪费了大量空间，数据量大的时候就会成为一颗瘦高的树。
那么我们可以怎么改进呢？答案很明显了，那就是每个磁盘块多存一点东西，也就是说每个磁盘多存几个关键字，因为关键字越多，路数越多；路数越多，树也就越矮越胖，相应的操作IO次数就会越少。
3、多路平衡树(Balanced Tree)
多路平衡树简称B树，又称B-树，和AVL树一样，B树在枝节点和叶子节点存储键值、磁盘地址、左右节点引用。请看下图的一个多路平衡树的示例：
B树的特点
相比较AVL树，B树一个磁盘上可以存多个关键字(值)，而且有一个特点就是：
分叉数（路数）永远比关键字数多1。
我们可以画出如下简图(下图中只画了3路，即两个关键字，实际取决于一页能存储多少个关键字)：
从上图可以很明显的看出，同样高度的树，B树能存的数据远远大于平衡二叉树。
B树是如何查找数据的
以上图为例，假如我们要找key=32这个数字，首先获取到根节点，发现18小于key，所以往右边走，获取到右边的数据，54和76，这时候遵循以下原则：
key<54,命中最左边分叉；
key=54,直接命中，返回数据；
54<key<76,走中间的一个分叉；
key=76,直接命中，返回数据；
key>76，命中右边分支；
这里因为key=32，所以走得是第1条，命中左边分支，这时候再去获取左边分支，获取到32和50，比较发现key=32，命中，返回数据。
从上面我们可以看出B树效率相对于AVL树，在数据量大的情况效率已经提高了很多，那么为什么MySQL还是不选择B树作为索引呢？
那么接下来让我们先看看改良版的B+树，然后再下结论吧！
4、B+树
B+树由B树改良而来，属于改良版的多路平衡查找树。
首先让我们来看看B+树到底长什么样呢：
对比B+树，我们可以发现一个很明显的区别就是叶子节点有一个箭头指引而且从左到右是有序的。
InnoDB中使用的B+树相比较于传统B+树，改进之后的B+树具有以下特点
InnoDB中B+树的特点
它的关键字的数量是跟路数相等的。
- B+树的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。而搜索到关键字不会直接返回，会到最后一层的叶子节点。
- B+树的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数据会指向下一个叶子节点的第一个数据，形成了一个有序链表的结构。
- 它是根据左闭右开的区间来检索数据的
按照B+树的特点，我们可以画出一个存储数据的简图，如下：
B+树是如何查找数据的
假设我们现在要找一个key=66，遵循如下步骤：
- 获取到根节点，依据左闭右开有如下区间：[1,28)，[28,66),[66,+∞)，命中了最后一个区间，虽然66在根节点，但是因为根节点不存储数据，所以是会往下继续搜索右边的节点
- 获取到右边节点，依据左闭右开有如下区间：[66,78),[78,89),[89,+∞)，命中左边的范围。
- 获取到第三排倒数第二块磁盘，找到66，返回数据。
B+树相对于B树的改进点
B+树是由B树改进而来的，所以B树能解决的问题，B+树都能解决，那么B+树能解决哪些B树所不能解决的问题呢？
- 扫库、扫表能力更强：如果我们要对表进行全表扫描，只需要遍历叶子节点就可以 了，不需要遍历整棵B+Tree
- B+Tree 的磁盘读写能力相对于 B Tree 来说更强：根节点和枝节点不保存数据区， 所以一个节点可以保存更多的关键字，一次磁盘加载(IO操作)能获取到相对更多的关键字。
- 天然具备排序能力：叶子节点上有下一个数据区的指针，数据形成了链表。
- 效率稳定：B+Tree 永远是在叶子节点拿到数据，所以 IO 次数是稳定的，而B树运气好根节点就拿到数据，运气不好就要到叶子节点才能拿到数据，所花费的时间会有差异。
四、为什么MySQL索引选择了 B+树 而不是 B树？
B+树更适合外部存储(一般指磁盘存储),由于内节点(非叶子节点)不存储data，所以一个节点可以存储更多的内节点，每个节点能索引的范围更大更精确。也就是说使用B+树单次磁盘I/O的信息量相比较B树更大，I/O效率更高。
mysql是关系型数据库，经常会按照区间来访问某个索引列，B+树的叶子节点间按顺序建立了链指针，加强了区间访问性，所以B+树对索引列上的区间范围查询很友好。而B树每个节点的key和data在一起，无法进行区间查找。
五、程序员你应该知道的索引知识点
1、回表查询
比如你创建了name， age索引 name_age_index，查询数据时使用了
|
1 |
select * from table where name ='磊丰' and age = 26; |
由于附加索引中只有name 和 age，因此命中索引后，数据库还必须回去聚集索引中查找其他数据，这就是回表，这也是你背的那条：少用select * 的原因。
2、索引覆盖
结合回表会更好理解，比如上述name_age_index索引，有查询
|
1 |
select name,age from table where name ='磊丰' and age = 26; |
此时select的字段name，age在索引name_age_index中都能获取到，所以不需要回表，满足索引覆盖，直接返回索引中的数据，效率高。是DBA同学优化时的首选优化方式。
3、最左前缀原则
B+树的节点存储索引顺序是从左向右存储，在匹配的时候自然也要满足从左向右匹配；通常我们在建立联合索引的时候，也就是对多个字段建立索引，相信建立过索引的同学们会发现，无论是Oracle还是 MySQL 都会让我们选择索引的顺序，比如我们想在a,b,c三个字段上建立一个联合索引，我们可以选择自己想要的优先级，a、b、c,或者是b、a、c 或者是c、a、b等顺序。
为什么数据库会让我们选择字段的顺序呢？不都是三个字段的联合索引么？这里就引出了数据库索引的最左前缀原理。
在我们开发中经常会遇到明明这个字段建了联合索引，但是SQL查询该字段时却不会使用索引的问题。比如索引abc_index:(a,b,c)是a,b,c三个字段的联合索引，下列sql执行时都无法命中索引abc_index的；
|
1 2 3 |
select * from table where c = '1'; select * from table where b ='1' and c ='2'; |
以下三种情况却会走索引:
|
1 2 3 4 5 |
select * from table where a = '1'; select * from table where a = '1' and b = '2'; select * from table where a = '1' and b = '2' and c='3'; |
从上面两个例子大家是否阔以看出点眉目？
是的，索引abc_index:(a,b,c)，只会在(a)、(a,b)、(a,b,c) 三种类型的查询中使用。其实这里说的有一点歧义，其实(a,c)也会走，但是只走a字段索引，不会走c字段。
另外还有一个特殊情况说明下，下面这种类型的也只会有 a与b 走索引，c不会走。
|
1 |
select * from table where a = '1' and b > '2' and c='3'; |
像上面这种类型的sql语句，在a、b走完索引后，c已经是无序了，所以c就没法走索引，优化器会认为还不如全表扫描c字段来的快。
最左前缀：顾名思义，就是最左优先，上例中我们创建了a_b_c多列索引,相当于创建了(a)单列索引，(a,b)组合索引以及(a,b,c)组合索引。
因此，在创建多列索引时，要根据业务需求，where子句中使用最频繁的一列放在最左边。
4、索引下推优化
还是索引name_age_index，有如下sql
|
1 |
select * from table where name like '陈%' and age > 26； |
语句有两种执行可能：
命中name_age_index联合索引，查询所有满足name以”陈”开头的数据， 然后回表查询所有满足的行。
命中name_age_index联合索引，查询所有满足name以”陈”开头的数据，然后顺便筛出age>20的索引，再回表查询全行数据。
显然第2种方式回表查询的行数较少，I/O次数也会减少，这就是索引下推。所以不是所有like都不会命中索引。
六、使用索引时的注意事项
1、索引不会包含有null值的列
只要列中包含有null值都将不会被包含在索引中，复合索引中只要有一列含有null值，那么这一列对于此复合索引就是无效的。所以我们在数据库设计时建议不要让字段的默认值为null。
2、使用短索引
对串列进行索引，如果可能应该指定一个前缀长度。例如，如果有一个char(255)的列，如果在前10个或20个字符内，多数值是惟一的，那么就不要对整个列进行索引。短索引不仅可以提高查询速度而且可以节省磁盘空间和I/O操作。
3、索引列排序
查询只使用一个索引，因此如果where子句中已经使用了索引的话，那么order by中的列是不会使用索引的。因此数据库默认排序可以符合要求的情况下不要使用排序操作；尽量不要包含多个列的排序，如果需要最好给这些列创建复合索引。
4、like语句操作
一般情况下不推荐使用like操作，如果非使用不可，如何使用也是一个问题。like “%陈%” 不会使用索引而like “陈%”可以使用索引。
5、不要在列上进行运算
这将导致索引失效而进行全表扫描，例如
|
1 |
SELECT * FROM table_name WHERE YEAR(column_name)<2021; |
6、不使用not in和<>操作
这不属于支持的范围查询条件，不会使用索引。
原创文章，作者：蓝洛水深，如若转载，请注明出处：https://blog.lanluo.cn/11539
微信扫一扫 
支付宝扫一扫 
