索引的原理与使用

索引是帮助MySQL高效获取数据的排好序的数据结构。索引的数据结构：二叉树、红黑树、Hash表、B-Tree；

MySQL的索引使用的是B+树而不是使用的B树，因为B树不管叶子节点还是非叶子节点，都会保存数据，这样导致在非叶子节点中能保存的指针数量变少，指针少的情况下要保存大量数据，只能增加树的高度，而在查找数据时一次页的查找代表一次IO，导致IO操作变多，查询性能变低；

Hash

对索引的key进行一次hash计算就可以定位出数据存储的位置，很多时候Hash索引要比B+ 树索引更高效，仅能满足=，IN，不支持范围查询，hash冲突问题

B-Tree

叶子节点具有相同的深度，叶子节点的指针为空，所有索引元素不重复，节点中的数据索引从左到右依次递增排列

B+Tree

非叶子节点不存储数据，只存储索引即冗余，可以放更多的索引，叶子节点包含所有索引字段，叶子节点用指针连接，方便范围查询，提高区间访问的性能。冗余索引的构建时，是提取叶子节点中索引最小的索引。

MySQL文件页大小为16K，假设一行数据大小为1K，一页就能存16条数据，也就是一个叶子节点能存16条数据；再看非叶子节点，假设主键ID为bigint类型，那么长度为8B，指针大小在Innodb源码中为6B，一共就是14B，一页里就可以存储16K/14=1170个(主键+指针)，一颗高度为2的B+树能存储的数据为：1170*16=18720条，一颗高度为3的B+树能存储的数据为：1170 * 1170 * 16 = 21902400（千万级条）

SHOW GLOBAL STATUS like 'Innodb_page_size’;

B+Tree是一颗有序的树，对于联合索引A、B、C，在A相等的情况B是有序的，在A、B相等的情况C是有序的

聚集索引

聚集索引即叶节点包含了完整的数据记录，每个InnoDB表有且仅有一个主键索引即聚集索引，二级索引等都是非聚集索引，需要回表，再去查询聚集索引从而找到具体的数据。

单从索引查询效率来说，聚集索引比非聚集索引要快，非聚集索引叶节点上的数据是存储的主键索引的ID。当表未建立主键索引时，MySQL会使用唯一性索引来作为主键索引，当表没有主键索引和唯一性索引时，将使用隐藏字段rowId作为主键索引。

主键索引中行是按照聚集索引物理排序的，若主键频繁改变，物理顺序会改变，MySQL要不断调整B+树，且中间可能会产生页面的分裂和合并等等，会导致性能会急剧降低。

非聚集索引

除了主键索引以外的索引都叫做非聚集索引，或叫辅助索引、二级索引，非聚集索引叶子节点不包含行记录全部数据，叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了相应行数据的聚集索引键。

辅助索引的存在并不影响数据在聚集索引中的组织，因此每张表上可有多个辅助索引，当通过辅助索引来寻找数据时，InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录，该过程也被称为回表。根据辅助索引的值查询一条完整的用户记录需要使用到2棵B+树，一次辅助索引一次聚集索引。

非聚集索引查询时需要回表到主键索引中查询具体的数据，但一般查询到的主键ID可能是乱序的，回表效率很低下，故引入了MRR即Multi Range Read多范围读取针对于辅助索引上的范围查询进行优化，收集辅助索引对应主键rowid，进行排序后回表查询，将随机IO转顺序IO。但MRR优化措施的条件比较苛刻。

辅助索引上之虽然可以存放完整数据从而避免回表操作，但存放完整数据太占磁盘空间，导致存储空间大量浪费，且每次对数据的变化要在所有包含数据的索引中全部都修改一次，性能也非常低下。

自适应哈希索引

InnoDB存储引擎内部监控索引热数据，然后内部创建一个Hash索引，称之为自适应哈希索引Adaptive Hash Index, AHI仅数据库自身创建并使用，并不能对其进行干预，控制参数Innodb_adaptive_hash_index和innodb_adaptive_hash_index_parts，可通过show engine innodb status命令查看hash索引使用情况。InnoDB存储引擎使用的哈希函数采用除法散列方式，其冲突机制采用链表方式。

哈希索引只能用来搜索等值的查询，如SELECT * FROM table WHERE index co=xxx，对于其他查找类型，如范围查找，是不能使用哈希索引的，可通过hash searches和non-hash searches可大概了解使用哈希索引后的效率，默认AHI为开启状态。若发现监视索引查找和维护哈希索引结构的额外开销远远超过了自适应哈希索引带来的性能提升就需要关闭这个功能。

同时在MySQL 5.7中自适应哈希索引搜索系统被分区，每个索引都绑定到一个特定的分区，每个分区都由一个单独的latch锁保护，分区由innodb_adaptive_hash_index_parts配置选项控制，早期版本中自适应哈希索引搜索系统受到单个latch锁的保护，这可能成为繁重工作负载下的争用点，innodb_adaptive_hash_index_parts默认情况下为8最大设置为512。

联合索引

例：where age = 30 and position = 'dev'该语句是不能用到索引的，因为虽然在某一个页里面age和position是排好序的，但跳过name在不同的页相比较age和position是乱序的。

MylSAM存储引擎

MylSAM索引文件和数据文件是分离的，即索引是非聚集索引（非聚蔟索引）

InnoDB存储引擎

InnoDB三大特性：自适应哈希索引、双写缓存区、BufferPool

文件系统的最小单元是块，一个块的大小是4K，在文件系统中即使一个文件只有一个字节，但也不得不占4KB的磁盘空间。

InnoDB存储引擎的最小存储单元是Page页，页可用于存放数据也可用于存放键值+指针，指针大小在InnoDB源码中设置为6字节，在B+树中叶子节点存放数据，非叶子节点存放键值+指针，默认一个页的大小是16382即16K。InnoDB的所有数据文件后缀为ibd，其大小始终都是16K的整倍数。数据表中的数据都是存储在页中，若一行数据大小为1K，则一页可存放16行这样的数据。InnoDB索引文件和数据文件是一个文件，表数据文件本身就是按B+Tree组织的一个索引结构文件。

一个页中不可能所有空间都用于存放数据，它还会存放一些少量的其他字段比如page level，index number等等。

为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？

若InnoDB表没有设置主键，MySQL会从数据表中选择一列数据都不相等的列作为主键索引，若找不到这样的列，MySQL会创建一个隐藏列来作为主键索引。使用整型作为主键在做比较时效率高很多。之所以用自增主键，若插入数据的主键是无序的，插入时需要对数据索引做平衡之类的操作，插入效率变低。

为什么非主键索引结构叶子节点存储的是主键的索引值？

一致性和节省存储空间

InnoDB二级索引结构

全文索引

InnoDB也支持全文索引即倒排索引，只对数据类型char、vachar、text支持创建全文索引，MySQL5.6.X版本开始支持全文索引。但不推荐使用MySQL全文索引，一张表只能有一个全文索引，对中文或非拉丁文分词非常差。

索引的代价

空间上每建立一个索引都要为它建立一棵B+树，每一棵B+树的每一个节点都是一个数据页，一个页默认会占用16KB的存储空间，一棵很大的B+树由许多数据页组成会占据很多的存储空间。

时间上每次对表中的数据进行增、删、改操作时，都需要去修改各个B+树索引，而增、删、改操作可能会对节点和记录的排序造成破坏，故存储引擎需要额外的时间进行一些记录移位，页面分裂、页面回收的操作来维护好节点和记录的排序。若建了许多索引，每个索引对应的B+树都要进行相关的维护操作，必然会对性能造成影响。一般一张表6-7个索引以下都能够取得比较好的性能权衡。

前缀索引

有时候需要索引很长的字符列，这会让索引变得大且慢，可以使用拟哈希索引，将很长的字符串进行hash运算，最终将hash值存库，还可以使用前缀索引来解决。

在Varchar字段上建立索引时，必须指定索引长度，没有必要对全字段建立索引，根据实际文本区分度决定索引长度，索引长度与区分度是一对矛盾体，一般对字符串类型数据，长度为20的索引，区分度会高达90%以上，可以使用count(distinct left(列名, 索引长度))/count(*)来确定区分度。

但是前缀索引的缺点很明显，无法使用前缀索引做ORDER BY和GROUP BY，也无法使用前缀索引做覆盖扫描。

有时候后缀索引也有用途，如找到某个域名的所有电子邮件地址，MSQL原生并不支持反向索引，但是可以把字符串反转后存储，并基于此建立前缀索引，也可以通过触发器或者应用程序自行处理来维护索引。

MySQL索引类型

从数据结构角度可分为B+Tree树索引、哈希索引、FULLTEXT索引、用于GIS数据类型创建的SPATIAL索引即R-Tree索引

从物理角度分为聚集索引、非聚集索引

从逻辑角度分为主键索引、普通索引或单列索引、联合索引或多列索引、唯一索引、非唯一索引

密集索引即索引中不仅存储了索引的key还包括数据，MySQL中主键索引即聚集索引才是密集索引。与之相对的是稀疏索引，非聚集索引都是稀疏索引，所有二级索引都是稀疏索引。

三星索引

索引将相关的记录放到一起即一个查询相关的索引行是相邻的或者至少相距足够靠近必须扫描的索引片宽度就会缩至最短则获得一星，若索引中的数据顺序和查找中的排列顺序一致则获得二星即排序星；若索引中的列包含了查询中需要的全部列则获得三星即宽索引星；

可以理解为第三颗星比重是50%，第一颗星为27%，第二颗星为23%，所以大部分情况下，会先考虑第一颗星，但会根据业务情况调整这两颗星的优先度。

对于一个查询而言，一个三星索引，可能是其最好的索引，若查询使用三星索引，一次查询通常只需要进行一次磁盘随机读以及一次窄索引片的扫描，因此其响应时间通常比使用一个普通索引的响应时间少几个数量级。