下面mysql教程栏目带大家深入剖析下MySQL中的索引，介绍一下MySQL索引的一些知识，希望对大家有所帮助！
MySQL 数据库应该是最常用的数据库之一，在各种大大小小的公司都可以看到它的身影，你对 MySQL 数据库掌握的如何呢？想要更好的使用它，那么我们就必须先了解它，正所谓的工欲善其事，必先利其器。
本篇文章就带领大家一起来深入剖析MySQL索引的一些知识，先来了解什么是索引，以及索引存储模型的推演，底层数据结构为什么会选择B+树其缘由？
索引是什么？
一张表有 500 万条数据，在没有索引的 name 字段上执行一条 where 查询：
select * from user_innodb where name ='小马';
如果 name 字段上面有索引呢？在 name 字段上面创建一个索引，再来执行一下相同的查询。
ALTER TABLE user_innodb DROP INDEX idx_name; ALTER TABLE user_innodb ADD INDEX idx_name (name);
有索引的查询和没有索引的查询相比，效率相差几十倍。
通过这个案例大家应该可以非常直观地感受到，索引对于数据检索的性能改善是非常大的。
那么索引到底是什么呢？为什么可以对我们的查询产生这么大的影响？创建索引的时候发生了什么事情？
索引定义
数据库索引，是数据库管理系统（DBMS）中一个排序的数据结构，以协助快速查询、更新数据库表中数据。
数据是以文件的形式存放在磁盘上面的，每一行数据都有它的磁盘地址。如果没有索引的话，我们要从 500 万行数据里面检索一条数据，只能依次遍历这张表的全部数据，直到找到这条数据。
但是我们有了索引之后，只需要在索引里面去检索这条数据就行了，因为它是一种特殊的专门用来快速检索的数据结构，我们找到数据存放的磁盘地址以后，就可以拿到数据了。
索引类型
在 InnoDB 里面，索引类型有三种：普通索引、唯一索引（主键索引是特殊的唯一索引）、全文索引。
普通（Normal）：也叫非唯一索引，是最普通的索引，没有任何的限制。
唯一（Unique）：唯一索引要求键值不能重复。另外需要注意的是，主键索引是一种特殊的唯一索引，它还多了一个限制条件，要求键值不能为空。主键索引用 primay key 创建。
全文（Fulltext）：针对比较大的数据，比如我们存放的是消息内容，有几 KB 的数据的这种情况，如果要解决 like 查询效率低的问题，可以创建全文索引。只有文本类型的字段才可以创建全文索引，比如 char、varchar、text。
索引是一种数据结构，那么它到底应该选择一种什么数据结构，才能实现数据的高效检索呢？
索引存储模型推演
二分查找
双十一过去之后，你女朋友跟你玩了一个猜数字的游戏。 猜猜我昨天买了多少钱，给你五次机会。
10000？低了。30000？高了。接下来你会猜多少？ 20000。为什么你不猜 11000，也不猜 29000 呢？
这个就是二分查找的一种思想，也叫折半查找，每一次，我们都把候选数据缩小了 一半。如果数据已经排过序的话，这种方式效率比较高。
所以第一个，我们可以考虑用有序数组作为索引的数据结构。
有序数组的等值查询和比较查询效率非常高，但是更新数据的时候会出现一个问题，可能要挪动大量的数据（改变 index），所以只适合存储静态的数据。
为了支持频繁的修改，比如插入数据，我们需要采用链表。链表的话，如果是单链表，它的查找效率还是不够高。
所以，有没有可以使用二分查找的链表呢？
为了解决这个问题，BST（Binary [?ba?n?ri] Search Tree）也就是我们所说的二叉查找树诞生了。
二叉查找树（ Binary Search Tree）
左子树所有的节点都小于父节点，右子树所有的节点都大于父节点。投影到平面以后，就是一个有序的线性表。
二叉查找树既能够实现快速查找，又能够实现快速插入。
但是二叉查找树有一个问题：查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成 O(n)。
什么情况是最坏的情况呢？
还是刚才的这一批数字，如果我们插入的数据刚好是有序的，2、10、12、15、 21、28
这个时候 BST 会变成链表（ “斜树”），这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的。
造成它倾斜的原因是什么呢？
因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。
所以，我们有没有左右子树深度相差不是那么大，更加平衡的树呢？
这个就是平衡二叉树，叫做 Balanced binary search trees，或者 AVL 树。
平衡二叉树（AVL Tree）
平衡二叉树的定义：左右子树深度差绝对值不能超过 1。
是什么意思呢？比如左子树的深度是 2，右子树的深度只能是 1 或者 3。
这个时候我们再按顺序插入 1、2、3、4、5、6，一定是这样，不会变成一棵“斜树”。
那 AVL 树的平衡是怎么做到的呢？怎么保证左右子树的深度差不能超过 1 呢？ 例如：插入 1、2、3。
当我们插入了 1、2 之后，如果按照二叉查找树的定义，3 肯定是要在 2 的右边的，这个时候根节点 1 的右节点深度会变成 2，但是左节点的深度是 0，因为它没有子节点，所以就会违反平衡二叉树的定义。
那应该怎么办呢？因为它是右节点下面接一个右节点，右-右型，所以这个时候我们要把 2 提上去，这个操作叫做左旋。
同样的，如果我们插入 7、6、5，这个时候会变成左左型，就会发生右旋操作，把 6 提上去。
所以为了保持平衡，AVL 树在插入和更新数据的时候执行了一系列的计算和调整的操作。
平衡的问题我们解决了，那么平衡二叉树作为索引怎么查询数据？ 在平衡二叉树中，一个节点，它的大小是一个固定的单位，作为索引应该存储什么内容？
第一个：索引的键值。比如我们在 id 上面创建了一个索引，我在用 where id =1 的条件查询的时候就会找到索引里面的 id 的这个键值。
第二个：数据的磁盘地址，因为索引的作用就是去查找数据的存放的地址。
第三个因为是二叉树，它必须还要有左子节点和右子节点的引用，这样我们才能找到下一个节点。比如大于 26 的时候，走右边，到下一个树香港vps的节点，继续判断。
如果是这样存储数据的话，我们来看一下会有什么问题。
首先，索引的数据，是放在硬盘上的。查看数据和索引的大小：
select CONCAT(ROUND(SUM(DATA_LENGTH/1024/1024),2),'MB') AS data_len, CONCAT(ROUND(SUM(INDEX_LENGTH/1024/1024),2),'MB') as index_len from information_schema.TABLES where table_schema='gupao' and table_name='user_innodb';
当我们用树的结构来存储索引的时候，因为拿到一块数据就要在 Server 层比较是不是需要的数据，如果不是的话就要再读一次磁盘。访问一个节点就要跟磁盘之间发生一次 IO。InnoDB 操作磁盘的最小的单位是一页（或者叫一个磁盘块），大小是 16K(16384 字节)。
那么，一个树的节点就是 16K 的大小。 如果我们一个节点只存一个键值+数据+引用，例如整形的字段，可能只用了十几个或者几十个字节，它远远达不到 16K 的容量，所以访问一个树节点，进行一次 IO 的时候，浪费了大量的空间。
所以如果每个节点存储的数据太少，从索引中找到我们需要的数据，就要访问
本文来源网站：info110.com，若侵权，请联系删除。
