索引概述

索引(index)，是帮助MySQL高效获取数据的数据结构(有序)，在数据之外，数据库系统还维护者满足特定查询算法的数据结构，这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。

从用户表中查询年龄为35岁的员工: select * from user where age=35; 此条语句是逐行进行遍历查找的，当查到age=35这一条记录(有可能不止这条)，继续往下查找直到查完这张表为止。这种情况是无索引的查找称之为全表扫描，效率极低。

有索引的情况,同样是这张表,同样是根据age进行查找，因为对age建立了索引，有了专门的数据结构指向age每行的地址，就如书目录一样，能够快速地找到age=35这一行记录。

索引的优点是提高数据检索的效率，降低数据库的IO成本，通过索引列对数据进行排序，降低CPU的消耗。缺点是索引列也是要占用磁盘空间的，索引大大提高了查询效率，同时也降低了更新表的速度，如对表进行insert、update、delete时，效率会降低。

索引结构

因为MySQL的索引是在存储引擎层实现的，不同的存储引擎有不同的结构，主要包含以下几种:

索引结构 描述

B+Tree索引 最常见的索引类型,大部分引擎都支持B+Tree索引

Hash索引 底层数据结构是用哈希表实现的,只有精确匹配索引列的查询才有效不支持范查询

R-Tree(空间索引) 空间索引是MyISAM引擎的一个特殊索引类型,主要用于地理空间数据类型.

Full-text(全文索引) 是一种通过建立倒排索引,快速匹配文档的方式,类似于Lucene，Solr,ES

B+Tree 索引 支持InnoDB/MyISAM/Memory/

Hash索引 支持Memory,不支持innodb和myisam

R-tree索引 支持MyISAM,不支持innodb、memory

Full-text 5.6版本的MySQL支持innodb；支持MyISAM,不支持memory。

日常中只要没有特别声明，一般所说的所以都是指B+树结构组织的索引。

B-Tree：叫做多路平衡查找树

以一棵最大度数(max-degree)为5(即5阶)的B-tree为例(即每个节点最多存储4个key,5个指针) ，树的度数是指一个节点的子节点个数。如图示:

如图根节点最多能存储4个key,同时4个key对应5个指针，分别指向他们的子节点。小于20的走第一个指针，20到30之间的走第二个指针，在30到62之间走第三个指针，62到89之间走第四个指针，大于89的走第五个指针。

输入以下数据看B-TRee的分裂过程

100 65 169368 900 556 780 35 215 1200 234 888 158 90 1000 88 120 268 250

B+Tree: 是B-Tree的升级版，不同的是所有的元素都会出现在叶子节点，非叶子节点主要是起到索引的作用，非叶子节点是用来存放数据的，叶子节点会形成一个单向链表，每个节点通过指针指向下一个节点，最终形成单向链表。

中间节点向上分裂，同时出现在叶子节点，形成单向链表。

MySQL索引中的数据结构对B+Tree进行了优化，在原有的基础上增加了一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的B+Tree，提高区间访问的性能。

Hash索引就是采用一定的hash算法，将键值换算成新的hash值，映射到对应的槽位上，然后存储在hash表中。如果两个或者多个键值，映射到一个相同的槽位上，它们就产生hash冲突也就是常说的hash碰撞，可以通过键表来解决。

hash索引的特点

1、hash索引只能用于对等的比较=,in ，不支持范围查询between > <,...

2、无法利用索引完成排序操作

3、查询效率高，通常只需一次检索就可以，效率通常要高于B+Tree

在MySQL中，支持hash索引的是memory引擎，innodb有自适应的hash功能，hash索引是存储引擎根据B+Tree索引在指定条件下自动构建的。

为什么InnoDB存储引擎选择使用B+Tree索引结构?

1、相对于二叉树，层级更少，搜索效率高。

2、对于B-Tree，无论是叶子节点还是非叶子节点，都会保存数据，这样导致一页中存储的 键值减少，指针跟着减少，在同样保存大数据量时只能增加树的高度，导致性能降低。

3、相对于hash索引，B+Tree支持范围匹配和排序操作。

MySQL的索引结构介绍到此。

索引分类

1. 主键索引，主要针对于表中主键创建的索引，默认自动创建只能有一个 primary

2.唯一索引，避免同一个表中某数据列中的值重复，可以有多个 unique

3.常规索引，用于自定义快速定位数据，可以有多个。

4. 全文索引，全文索引查找的是文本中的关键词，而不是比较索引中的值，可以有多 个，fulltext。

在innodb存储引擎中根据索引的存储形式，还可以分为聚集索引和二级索引。

聚集索引:将数据存储与索引放到一块，索引结构的叶子节点保存了行数据，聚集索引只 能有一个。

如果存在主键，主键索引就是聚集索引；如果不存在主键，将使用第一个unique 索引作为聚集索引；如果表没有主键，或没有合适的唯一索引，则innodb会自动 生成一个rowid作为隐藏的聚集索引。

聚集索引的结构就是叶子节点下挂的数据就是这一行的数据，比如5指针下row， 就是id为5的这一行数据。

二级索引: 将数据与索引分开存储，索引结构的叶子节点关联的是对应的主键(或者说是对 于的id值)，可以有多个。

回表查询: 先在二级索引查询，查到对应的主键ID，再回聚集索引根据id查对应 的数据。