什么是索引

在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针、清单。索引的作用相当于图书的目录，可以根据目录中的页码快速找到所需的内容

为什么要使用索引

• 快速查询数据（否则使用全表扫描在数据库数据大时，消耗大量数据库系统时间，并造成大量磁盘I/O操作效率太低，而使用索引大大提高查找效率）

什么样的信息能成为索引

• 主键、唯一键以及普通键等具备一定区分性的字段

索引的数据结构(优化索引)

• 生成索引，建立二叉查找树进行二分查找
• 生成索引，建立B-Tree结构进行查找
• 生成索引，建立B+-Tree结构进行查找
• 生成索引，建立Hash结构进行查找

二叉树

二叉树

• 二叉树左边小于索引，右边大于索引
• 当我要查找6时，就会从13的左边开始，在到8节点到左边往下找，到1节点右边找到6这样。但二叉树当层级很深时，反而效率会很低

m-way查找树

m-way查找树是是一种树形的存储结构，主要特点如下：

• 每个节点存储的key数量小于m个
• 每个节点的度小于等于m
• 节点key按顺序排序
• 子树key值要完全小于、大于或介于父节点之间

例如：3-way如图，m为3，那么每个节点最多拥有为2个（m-1）

待索引元素列表为：[5, 7, 12, 6, 8, 3, 4]

3-way

B-Tree

Btree是一种平衡的m-way查找树，它可以利用多个分支节点（子树节点）来减少查询数据时所经历的节点数，从而达到节省存取时间的目的。m称为B-Tree的度

B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点

B-Tree

定义：

• 根节点至少包括两个孩子
• 树中每个节点最多含有m个孩子（m>=2）
• 除根节点和叶节点(没有子节点的节点)外，其他每个节点至少有ceil（m/2）个孩子(ceil表示取上限，比如m/2=1.1那么ceil值为2)
• 所有叶子节点都位于同一层

B+-Tree

定义：

• 非叶子节点的子树指针与关键字个数相同
• 非叶子节点的子树指针P[i],指向关键字值[k[i],k[i+1]]的子树（例：取10，他的子树在10到20间）
• 非叶子节点仅用来索引，数据都保存在叶子节点中
• 所有叶子节点均有一个链指针指向下一个叶子节点

B+树

B树与B+树的区别

• 区别：B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。

• B+ 树优点：
  由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
  B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好；

• B树优点：由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速；

结论：
B+-Tree更适合来做存储索引，所有现在主流索引都是使用的B+树：

• 磁盘读写代价更低
• 查询效率更稳定
• 更有利于对数据库的扫描

Hash索引

通过hash算法计算出hash值，直接通过hash值到hash表中拿到对应的数据

优点：只需通过一次hash算法拿到索引

缺点：

• 仅能瞒住"=","IN",不能使用范围哦查询
• 无法被用来避免数据的排序操作
• 不能利用部分索引键来查询
• 不能避免表扫描
• 遇到大量hash值相等的情况后性能并不一定就会比B-Tree索引高

密集索引和稀疏索引的区别

• 密集索引文件中的每个搜索码值都对应一个索引值

• 稀疏索引文件只为索引码的某些值建立索引相

  
  

以MySql中包括的MyISAM（稀疏索引）和InnoDB（密集索引）存储引擎为例：
InnoDb：

• 若一个主键被定义，该主键则用作密集索引
• 若没有主键被定义，该表的第一个唯一非空索引作为密集索引
• 若以上条件都不满足，InnoDb内部会生成一个隐藏主键（密集索引）
• 非主键索引存储相关键位和其对应的主键值，包含两次查找

image.png

主键(primary key)和唯一键(unique key)

主键(primary key)

定义

• 主键用于唯一标识表中的每一条数据

特征

• 不能重复, 不能为空
• 注意：auto_increment只能修饰主键，所以自增长字段必须是主键 (primary key)，但主键不一定是自增字段
• 可以使用多个字段设置联合主建（注意主键只有一个）
  使用场景：
• 最少性: 尽量选择一个字段作为主键
• 稳定性: 尽量选择更新少的字段作为主键
• 尽量选择整数类型的字段作为主键
• 结论: 搞一个id字段类型为int, 设置自动增长, 作为主键

唯一键(unique key)

作用

• 避免添加重复数据, 也就是说如果想保证某一个字段的值永远不重复, 那么就可以将这个字段设置为唯一键

特征

• 唯一键不是主键, 主键有一个特点是不能重复, 但是唯一键不等于主键
• 一张表中只能有一个主键, 但是一张表中可以有多个唯一键

补充

• 普通索引（index）：允许出现相同的索引内容

• 组合索引：实质上是将多个字段建到一个索引里，列值的组合必须唯一

• 添加索引：alter table table_name add 索引（index、primary key、unique）+索引名+（字段名）。例：alter table mmall_user drop index index_email(email)

• 删除索引：alter table table_name drop 索引（index、primary key、unique）+索引名。例：alter table mmall_user drop index index_email

索引衍生问题

如何定位并优化满查询

根据慢日志定位到慢查询sql

• show variables like '%query%' 查询query变量

  
  
  query
  
  

  慢日志判断时间、慢日志状态和慢日志存储地址

• show status like '%slow_queries%'查询慢sql数量

  
  
  slow_queries

• set global slow_query_log=on 打开慢日志

  
  
  slow_query_log

• set global long_query_time=1 设置查询时间>=1秒时添加到慢日志（需要重启客户端有效，也可以直接去设置配置文件）

使用explain等工具分析sql

explain

使用explain+sql对sql进行分析，分析结果注意select_type和Extra这两个字段：

• type：当出现index、all时就是全表扫描。type比较多想要了解这里就不一一介绍
• extra：当出现以下2项意味着MySQL不能使用索引，效率收到重大影响。应尽可能对此进行优化
  Using filesort：MySQL对结果使用一个外部索引排序，而不是从表里按索引次序读到的相关内容，可能在内存或者磁盘上进行排序。MySQL中无法利用索引完成的排序操作成为文件排序
  Using temporary：MySQL在对查询结果排序时使用了临时表，常见于排序order by和分组查询group by

修改sql或者尽量让sql走索引

• 给需要查询的字段添加索引（添加方法上面以介绍）

联合索引的最左匹配原则的成因

索引时建立得越多越好吗

• 数据量小的表不需要建立索引，建立会增加额外的开销
• 数据变更需要维护索引，因此更能多大索引意味着更多的维护成本
• 更多的索引意味着也需要更能多大空间

数据库优化