前言前面已经写了有两篇章长度的文章，第三篇我一直在寻思着要写什么（其实并没有），按照脑图来的话，这篇文章我们该来讲讲关于索引的知识了，这可是 MySQL 性能优化很关键的知识点，千万千万不要错过，不过我这里会相对比较深入地探究，相信大家读完之后多少会有点收获 。
先送上两张飞机票还没读过前面文章的伙伴可以先前往阅读，由浅入深：
MySQL相关（一）- 一条查询语句是如何执行的
MySQL相关（二）- 一条更新语句是如何执行的
由于索引的知识点比较多，官网的内容也很多，如果大家想详细了解可以到官网，想先通读了解的话可以先看看我对索引的总结，这一章节分为三部分来讲：
- innodb 逻辑存储结构需要了解，作为番外篇
MySQL相关（番外篇）- innodb 逻辑存储结构；
- 索引的数据结构也作为另外的篇章，通过对查询算法的数据模型进行演算分析
MySQL相关（三）- 索引数据模型推演及 B+Tree 的详细介绍；
- 对索引的使用及优化规则也会作为单独的篇章
MySQL相关（四）- 性能优化关键点索引前面提到的脑图如下，想要完整高清图片可以到微信我的公众号下【6曦轩】下回复 MySQL 脑图获取：
文章插图
正文MySQL索引数据模型推演二分查找
双十一过去之后，你女朋友跟你玩了一个猜数字的游戏 。(假设程序员 new 了一个会购物的女朋友出来) 猜猜我昨天买了多少钱，给你五次机会 。10000？低了 。30000？高了 。接下来你会猜多少？ 20000 。为什么你不猜 11000，也不猜 29000 呢？其实这个就是二分查找的一种思想，也叫折半查找，每一次，我们都把候选数据缩小了一半 。如果数据已经排过序的话，这种方式效率比较高 。
所以第一个，我们可以考虑用有序数组作为索引的数据结构 。
有序数组的等值查询和比较查询效率非常高，但是更新数据的时候会出现一个问题，可能要挪动大量的数据（改变 index），所以只适合存储静态的数据 。
为了支持频繁的修改，比如插入数据，我们需要采用链表 。链表的话，如果是单链表，它的查找效率还是不够高 。
那么，有没有可以使用二分查找的链表呢？
为了解决这个问题，BST（Binary Search Tree）也就是我们所说的二叉查找树诞生了 。
二叉查找树二叉查找树的特点是什么？ 左子树所有的节点都小于父节点，右子树所有的节点都大于父节点 。投影到平面以后，就是一个有序的线性表 。
文章插图
二叉查找树既能够实现快速查找，又能够实现快速插入 。
- 但是二叉查找树有一个问题：
它的查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成 O(n) 。
- 什么情况是最坏的情况呢？
我们打开这样一个网站来看一下，这里面有各种各样的数据结构的动态演示，包括 BST 二叉查找树：
www.cs.usfca.edu/~galles/vis… 还是刚才的这一批数字，如果我们插入的数据刚好是有序的，2、6、11、13、17、 22 。这个时候我们的二叉查找树变成了什么样了呢？
它会变成链表（这种树也叫做“斜树”），这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的 。
【MySQL相关：索引数据模型推演及 B+Tree 的详细介绍】
- 造成它倾斜的原因是什么呢？
因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡 。
- 所以，我们有没有左右子树深度相差不是那么大，更加平衡的树呢？
这个就是平衡二叉树，叫做 Balanced binary search trees，或者 AVL 树（AVL 是发明这个数据结构的人的名字） 。平衡二叉树AVL Trees (Balanced binary search trees) 平衡二叉树的定义：
左右子树深度差绝对值不能超过 1 。
- 是什么意思呢？
比如左子树的深度是 2，右子树的深度只能是 1 或者 3 。这个时候我们再按顺序插入 1、2、3、4、5、6，一定是这样，不会变成一棵“斜树” 。
推荐阅读
- 配置Mysql 的url参数
- mysql查询小总结
- 如何在手机上查看搜索引擎快照？
- 如何彻底搞懂Mysql事务原理
- MySQL高级进阶：关于InnoDB存储结构，一文深入分析讲解
- 什么是搜索引擎营销？
- MYSQL5.7安装教程
- MySQL 5.6.28修改root用户密码（windows)
- MySQL深度分页：数千万的数据如何快速分页？
- 爆破SSH/MySQL账户竟如此简单
