Mysql索引

当你有一张一百万数据的表且没有加索引优化的话，查询一条记录的速度为0.5秒

而当你加入索引后，查询一条记录的速度为0.024秒

速度相差了20倍，这是一条创建MySql索引的语法

ALTER TABLE <表名> ADD  INDEX (<列名>);

在创建索引后，发生了什么？为什么添加索引后能产生这么大的变化?

1. 什么是索引？

要弄懂索引的查询为何如此之快，我们需要先知道索引是什么。

索引在MySql是帮助MySql高效获取数据的排好序的数据结构。而在程序中，包含了很多种的索引，比如二叉树，红黑树，B树，b+树

它为什么能产生如此高效的查询

1.1 那么在mysql中索引的数据结构是怎么样的？

1.1.2 二叉树排序树做索引

当让我们去设计一个存储数据的索引时，可以从最简单的二叉树排序树出发，利用它设计MySql的索引。

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。
若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
左、右子树也分别为二叉排序树；

当我们往其中持续插入数据时，比如 {1，2，3，4，5，6，7}，产生的树形结构如下图

此时我们通过查询当中的某一个数值，比如5，那么将会执行5次才获取到数据，这样的查询效果并不令人满意，因为假如是链表也可以满足这个需求

1.1.3 红黑树做索引

换一种数据结构试试，比如红黑树，也是二叉平衡树，Java用它来实现TreeMap。

红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。 在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
性质1. 结点是红色或黑色。
性质2. 根结点是黑色。
性质3. 所有叶子都是黑色。（叶子是NIL结点）
性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
性质5. 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。

依然用我们之前的数据例子，{1，2，3，4，5，6，7}，得到的属性结构如图：

此时我们进行查询数据 5 的话，需要4步才能找到，比二叉排序树要好一些。

那么如果我们使用它作为MySql的索引会发生什么？

如果是100万的数据量，此时，通过公式 $[2^=1000000]$ ，其中n为树形结构产生的高度，当数据量是100万的时候，意味着$[n\approx 19.931569 ]$ ,而树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下的情况。那么查询一次的轮询也是非常耗时的。

更好的方案去存储索引，能不能将深度 n 控制在3-5 次之间，既要存储大量数据，又要控制深度，那么如果对红黑树进行改造一下呢？

在每个父节点的同级，增加横向节点，意味着产生的效果是这样的

而这就是B-Tree,

1.1.4 B-Tree做索引

B-tree（多路搜索树，并不是二叉的）是一种常见的数据结构。使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。

B-tree中，每个结点包含：

1. 本结点所含关键字的个数；
2. 指向父结点的指针；
3. 关键字；
4. 指向子结点的指针；

对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。各结点的关键字和可以拥有的子结点数都有限制，规定m阶B-tree中，根结点至少有2个子结点，除非根结点为叶子节点，相应的，根结点中关键字的个数为1~m-1；非根结点至少有[m/2]（[]，向上取整）个子结点，相应的，关键字个数为[m/2]-1~m-1。

通过对B-Tree增加数据后，得到的效果是

这里要说一下B-Tree的特点

1. 关键字集合分布在整棵树中；
2. 任何一个关键字出现且只出现在一个结点中；
3. 搜索有可能在非叶子结点结束；
4. 其搜索性能等价于在关键字全集内做一次二分查找；
5. 自动层次控制；
   由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最低搜索性能为：
   其中，M为设定的非叶子结点最多子树个数，N为关键字总数；
   所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题
   由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并。

这看起来似乎已经满足了我们的要求，B-Tree搜索性能等价于在关键字全集内做一次二分查找，这样的搜索速度是相当快的，但是 B-Tree的每个节点都有data域（指针），这是什么意思呢？

也就是表示B-Tree的每个节点不仅包含了索引元素，而且存储了索引元素对应的数据，如图：

这无疑增加了节点大小，也就是增加了磁盘IO次数，而磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，一次IO多耗时。

MySql在此基础上进行了改变，使用B+Tree做索引

1.1.5 B+Tree做索引

B+Tree是B树的变种，有着比B树更高的查询性能，来看下m阶B+Tree特征：

1. 有m个子树的节点包含有m个元素（B-Tree中是m-1）
2. 根节点和分支节点中不保存数据，只用于索引，所有数据都保存在叶子节点中。
3. 所有分支节点和根节点都同时存在于子节点中，在子节点元素中是最大或者最小的元素。
4. 叶子节点会包含所有的关键字，以及指向数据记录的指针，并且叶子节点本身是根据关键字的大小，从小到大顺序链接。

以上，当中有很重要的两个特征，

根节点和分支节点不保存数据，只用于索引，所有数据都保存在叶子节点中。
叶子节点会包含所有的关键字，以及指向数据记录的指针，并且叶子节点本身是根据关键字的大小，从小到大顺序链接

这便解决了B-Tree中data域的问题
当我们用数据插入的时候，得到的树形结构图是

对这张图进行解释说明一下

使用语法 show GLOBAL STATUS like 'Innodb_page_size'; 可以知道MySql中默认的页大小容量为多少

1.1.6 为什么B+Tree会这样进行存放？

以索引中的一个节点为例，索引元素占8个字节，而指向下一级索引的指针占4个字节，那么在这一层节点中，可以存储的元素数量有$\frac{16KB}{14B} = \frac{16*1024}{14} \approx 1170 $ ，假设树的高度是 n=3,满载情况下

$$
1170 \cdot 1170 \cdot 16 = 21902400
$$

这样经过3次磁盘IO就能找到2000万中的某一条数据

这样便解决了数据库中查询的问题。

当然，有经验的程序员都知道，在创建MySql索引的时候，我们还可以选择HASH，通过HASH去创建索引。

1.1.7 通过Hash表做索引

哈希算法时间复杂度为O(1)，且不只存在于索引中，每个数据库应用中都存在该数据结构。

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

Hash索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像B-Tree索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以Hash索引的查询效率要远高于B-Tree索引。

那么既然效率这么高，为什么不使用Hash索引而还要使用B+Tree索引呢？

当中的原因有：

1. Hash索引仅仅能满足"=","IN"和"<=>"查询，不能使用范围查询。哈希索引只支持等值比较查询，包括**＝、 IN 、<=> ** (注意<>和＜＝＞是不同的操作）。 也不支持任何范围查询，例如WHERE price > 100。　　
   由于Hash索引比较的是进行Hash运算之后的Hash值，所以它只能用于等值的过滤，不能用于基于范围的过滤
2. Hash索引无法被用来避免数据的排序操作
3. Hash索引不能利用部分索引键查询。对于组合索引，Hash索引在计算Hash值的时候是组合索引键合并后再一起计算Hash值，而不是单独计算Hash值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash索引也无法被利用。
4. Hash索引在任何时候都不能避免表扫描。Hash索引是将索引键通过Hash运算之后，将 Hash运算结果的Hash值和所对应的行指针信息存放于一个Hash表中，由于不同索引键存在相同Hash值，所以即使取满足某个Hash键值的数据的记录条数，也无法从Hash索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。
5. Hash索引遇到大量Hash值相等的情况（产生Hash冲突）后性能并不一定就会比BTree索引高。
   对于选择性比较低的索引键，如果创建Hash索引，那么将会存在大量记录指针信息存于同一个Hash值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。

在基于上面的分析后，MySql的存储引擎索引实现并不完全就是这样

在mysql5之后，支持的存储引擎有十几个，但是常用的就那么几种，而且默认支持的也是InnoDB。我们可以通过命令 show ENGINES ; 知道当前MySql支持的存储引擎有哪些

1.2 MyISAM存储引擎

首先这里需要提到的一点是：存储引擎是用来形容表的，而不是数据库的。可以对每一张表设计不一样的存储引擎。

1.2.1 锁的粒度

MyISAM不支持行锁，所以读取时对表加上共享锁，在写入是对表加上排他锁。由于是对整张表加锁，相比InnoDB，在并发写入时效率很低。

1.2.2 数据存储形式

MyISAM采用的是索引与数据分离的形式，将数据保存在三个文件中.frm.MYD,.MYIs。

1.2.3 事务

MyISAM不支持事务。

1.2.4 索引实现

MyISAM是基于非聚簇索引进行存储的。

这意味着，索引中存储的是磁盘文件指针，如下图中叶子节点 15下方的 0x07

1.2.5 其他

MyISAM提供了大量的特性，包括全文索引，压缩，空间函数，延迟更新索引键等。

进行压缩后的表是不能进行修改的，但是压缩表可以极大减少磁盘占用空间，因此也可以减少磁盘IO，从而提供查询性能。

全文索引，是一种基于分词创建的索引，可以支持复杂的查询。

延迟更新索引键，不会将更新的索引数据立即写入到磁盘，而是会写到内存中的缓冲区中，只有在清除缓冲区时候才会将对应的索引写入磁盘，这种方式大大提升了写入性能。

1.3 InnoDB存储引擎

1.3.1 数据存储形式

使用InnoDB时，会将数据表分为.frm 和 idb两个文件进行存储。

1.3.2 锁的粒度

InnoDB采用MVCC(多版本并发控制) 来支持高并发，InnoDB实现了四个隔离级别，默认级别是REPETABLE READ，并通过间隙锁策略防止幻读的出现。它的锁粒度是行锁。

1.3.3 事务

InnoDB是典型的事务型存储引擎，并且通过一些机制和工具，支持真正的热备份。

1.3.4 索引实现

1. 表数据文件本身就是按B+Tree组织的一个索引结构文件
2. 聚集索引-叶节点包含了完整的数据记录

聚集索引如下图

这里InnoDB涉及到的几个面试题

1.35 为什么InnoDB表必须要有主键？并且推荐整形的自增主键？

首先InnoDB中必须要有主键。B+Tree的索引设计使得表必须需要主键用来平衡B+Tree，如果自己没有设置主键，那么MySql会自行建立一列数据用作主键。

主键递增更适应B+Tree。自增的主键进行插入数据时，会在平衡后进行累加，而UUID因为不是自增，这个B+Tree会不停的进行平衡，消耗资源、时间。

1.3.6 UUID为什么不推荐被当作主键

这是因为UUID比较时会先转化为ASCII码，然后进行比较，这个转化加比较是费时的，而且UUID的字符表更长，更占用空间。

说完了两个MySql的存储引擎之后，还有一种辅助索引，用来告诉InnoDB哪里可以找到与索引相对应的行数据。

1.4 辅助索引（Secondary Index）

辅助索引说的是，叶子节点中存储主键值，每次查找数据时，根据索引找到叶子节点中的主键值，根据主键值再到聚簇索引中得到完整的一行记录。

辅助索引如下图

1.4.1 为什么要设计辅助索引(二级索引)？

InnoDB在移动行时，无需维护二级索引，因为叶子节点中存储的是主键值，而不是指针。

聚簇索引的叶子节点存储了一行完整的数据，而二级索引只存储了主键值，相比于聚簇索引，占用的空间要少。当我们需要为表建立多个索引时，如果都是聚簇索引，那将占用大量内存空间，所以InnoDB中主键所建立的是聚簇索引，而唯一索引、普通索引、前缀索引等都是二级索引。

也就是说，假如当进行插入数据，修改数据，需要维护主键索引，又要维护非主键索引，那么这对于大数据量的插入绝对是种灾难。所以辅助索引就是为了解决这个问题，插入和修改数据时，只要维护主键索引就行。

1.5 联合索引

联合索引是指对表上的多个列进行索引。

也就是说将多个字段放入叶节点进行索引排序，如下图演示

联合索引也是一棵B+树，其键值数量大于等于2。键值都是排序的，通过叶子节点可以逻辑上顺序的读出所有数据。

假设说创建联合索引

ALTER TABLE person ADD  INDEX (`a`,`b`);

对于以下查询显然是可以使用（a，b）这个联合索引的

select * from table where a=xxx and b=xxx ;

select * from table where a=xxx;

参考文章:
算法可视化网站
如何计算B+树可以存放多少条数据
什么是B+Tree
mysql索引之哈希索引
浅谈MySQL存储引擎-InnoDB&MyISAM
聚集索引、辅助索引、覆盖索引、联合索引