一、索引是什么

二、索引的底层实现原理

三、InnoDB的存储结构是怎样的？

四、InnoDB索引和MyIsam索引对比

五、Mysql为什么会选错索引

六、唯一索引和普通索引的区别

导读:本博文讲解了索引是什么和索引的底层原理，提到了 BTREE和 B+TREE hash底层实现以及mysql选错索引的原因和解决方式。同时涵盖高频面试题之InnoDB索引和MyIsam索引对比区别，唯一索引和普通索引的区别。

一、索引是什么

索引的概念：索引是一种特殊的文件，它们包含着对数据表里所有记录的引用指针。更通俗的说，数据库索引好比是一本书前面的目录，能加快数据库的查询速度

索引的作用：索引的目的在于提高查询效率，使原始的随机全表扫描变成快速顺序锁定数据

常用索引的分类：
普通索引：这是最基本的索引，它没有任何限制
唯一索引：引列的值必须唯一，但允许有空值（注意和主键不同）
组合索引：多个数据列组成的索引，遵守最左匹配原则

索引高性能保证：
把查询过程中的随机事件变成顺序事件
数据保存在磁盘上，而为了提高性能，每次又可以把部分数据读入内存来计算，访问磁盘的成本大概是访问内存的十万倍左右

磁盘IO与预读:
考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k

二、索引的底层实现原理

hash索引 无法满足范围查找，优点：等值检索快，范围检索很慢，因为hash值是不连续的

B-TREE 每个节点都是一个二元数组: [key, data]，所有节点都可以存储数据。key为索引key,data为除key之外的数据

B-TREE的缺点:插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。造成IO操作频繁。区间查找可能需要返回上层节点重复遍历，IO操作繁琐

B+Tree的改进：非叶子节点不存储data，只存储索引key；只有叶子节点才存储data

B+树高性能保证：

3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高
在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree
B+TREE 只在叶子节点存储数据 & 所有叶子结点包含一个链指针 & 其他内层非叶子节点只存储索引数据。只利用索引快速定位数据索引范围，先定位索引再通过索引高效快速定位数据。

三、InnoDB的存储结构是怎样的？

InnoDB物理存储结构分析

InnoDB以表空间Tablespace(idb文件)结构进行组织，每个Tablespace 包含多个Segment段，每个段(分为2种段：叶子节点Segment&非叶子节点Segment), 一个Segment段包含多个Extent，一个Extent占用1M空间包含64个Page（每个Page 16k），InnoDB B+Tree 一个逻辑节点就分配一个物理Page,一个节点一次IO操作。,一个Page里包含很多有序数据Row行数据，Row行数据中包含Filed属性数据等信息

索引值匹配检索过程：确定定位条件, 找到根节点Page No, 根节点读到内存, 逐层向下查找, 读取叶子节点Page,通过二分查找找到记录或未命中。（select * from user_info where id = 23）

索引范围查找：读取根节点至内存, 确定索引定位条件id=18, 找到满足条件第一个叶节点, 顺序扫描所有结果, 直到终止条件满足id >=21 （select * from user_info where id >= 16 and id < 21）

全表扫描：直接读取叶节点头结点，顺序扫描，返回符合条件记录，到最终节点结束（select * from user_info where user_name = 'daniel'）

四、InnoDB索引和MyIsam索引对比

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址，MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复

在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域

MyIsam叶子data域放的是指针

InnoDB 主键索引，又是聚簇索引（就是数据和索引放在一起，我们称之为聚簇索引，性能最高）

InnoDB非主键索引，非聚簇索引 data中存储的是id

InnoDB支持事务，MyISAM不支持
   InnoDB将多条SQL语言放在begin和commit之间，组成一个事务，具备事务的ACID
   InnoDB支持外键，而MyISAM不支持。对一个包含外键的InnoDB表转为MYISAM会失败
   InnoDB是聚集索引，数据文件是和索引绑在一起的，必须要有主键，通过主键索引效率很高。而MyISAM是非聚集索引，数据文件是分离的，索引保存的是数据文件的指针。主键索引和辅助索引是独立的
   InnoDB不保存表的具体行数，执行select count(*) from table时需要全表扫描。而MyISAM用一个变量保存了整个表的行数，执行上述语句时只需要读出该变量即可，速度很快
   Innodb不支持全文索引，而MyISAM支持全文索引，查询效率上MyISAM要高

实际场景的选择
   是否要支持事务，如果要请选择innodb，如果不需要可以考虑MyISAM；
   如果表中绝大多数都只是读查询，可以考虑MyISAM，如果既有读写也挺频繁，请使用InnoDB
   系统奔溃后，MyISAM恢复起来更困难，能否接受；
   MySQL5.5版本开始Innodb已经成为Mysql的默认引擎(之前是MyISAM)，说明其优势是有目共睹的，如果你不知道用什么，那就用InnoDB，至少不会差

五、Mysql为什么会选错索引

场景举例分析先造10万条数据入库:

CREATE TABLE `testwnn321` (`id` int(11) NOT NULL,`a` int(11) NOT NULL default 0,`b` int(11) NOT NULL default 0,PRIMARY KEY (`id`),KEY `a` (`a`),KEY `b` (`b`)
) ENGINE=InnoDB;

delimiter ;;
create procedure wnndata321()
begindeclare i int;set i=1;while(i<=100000)doinsert into testwnn321 values(i, i, i);set i=i+1;end while;
end;;
delimiter ;
call wnndata321();explain select * from testwnn321 where (a between 1000 and 2000) and (b between 50000 and 100000) order by b limit 1;

十万条数据入库后，我们先看看下面几个sql所使用的索引。

原因分析:

在多个索引的情况下，优化器一般会通过比较扫描行数、是否需要临时表以及是否需要排序等，来作为选择索引的判断依据
选择索引 b，则需要在 b 索引上扫描 5w 条记录，然后同样回到主键索引上过滤掉不满足 a 条件的记录，因为索引有序，所以使用 b 索引不需要额外排序

解决方法:

使用force index a让mysql直接选择a索引来处理此处查询

其他场景导致索引选择错误：

数据表有频繁的删除或更新操作导致的数据空洞造成的
造成原因：分析器 explain 的结果预估的 rows 值跟实际情况差距比较大，分析器分析扫描行数用的是抽样调查
解决方案：统计信息不对，那就修正。analyze table test 命令，可以用来重新统计索引信息

六、唯一索引和普通索引的区别

唯一索引:

定义：UNIQUE索引可以强制执行值唯一的一列或多列。一个表可以有多个UNIQUE索引。
场景：联系人的电子邮件唯一、联系人的身份证唯一 123@qq.com 数据库层面的严格唯一

查询上的区别:

对唯一索引，由于索引定义了唯一性，查找到第一个满足条件的记录后，就会停止检索
对普通索引，查找到满足条件的第一个记录’ab‘后，需查找下个记录，直到碰到第一个不满足k=’ab‘条件的记录
结论：mysql采用page页（一页16K）为数据单位从磁盘load出数据，除非刚好值为’ab‘的记录在一页的最后一条数据，否则执行性能区别微乎其微

修改上的区别:

对于唯一索引，所有更新操作要先判断该操作是否违反唯一性约束，唯一索引不会用change buffer
若所修改的数据在内存中
找到索引对应该存储的位置，判断、到没有冲突，插入值，语句执行结束
找到索引对应该存储的位置，插入值，语句执行结束。

若所修改的数据不在内存中
需要将数据页读入内存，判断到没有冲突，插入值，语句执行结束
将更新记录在change buffer，语句执行结束

change buffer的定义:
一种特殊的数据结构，该结构在次要索引中记录对页的更改
作用：提高更改索引操作性能，涉及更改缓冲区的一组功能统称为“更改缓冲区” ，由“插入缓冲区”，“删除缓冲区”和“清除缓冲区”组成
同步策略：当相关索引页被带入缓冲池而相关联的更改仍在更改缓冲区中时，该页的更改将使用更改缓冲区中的数据应用于缓冲池( 合并 )中。在系统大部分处于空闲状态或缓慢关机期间运行的“清除”操作会定期将新的索引页写入磁盘

结论：

唯一索引和普通索引在查询性能上没差别，主要考虑对更新性能影响
唯一索引可以从数据库上强制去重，但用不了change buffer的优化机制，从性能角度，推荐优先考虑非唯一索引