mysql系列-索引

一 索引的基础

1.1 定义

索引是对数据库表中一列或多列的值进行排序的一种结构。本质上，是基于空间换时间的一种思路的实现。

常见的数据结构中, 哈希表和二叉平衡树的查找效率分别是O(1)和O(logn), 是效率最快的两个, MySQL也毫不意外的使用了这两种数据结构来做索引。 MySQL索引的数据结构有两种选择, B+Tree 和 Hash。

1.2 优点

1.2.1 提升检索效率

1、提高数据检索效率，降低数据库的IO成本；

2、降低数据排序成本，降低了CPU的消耗。

1.3 缺点

1.3.1 更新表速度降低

索引大大提高了查询速度，同时却降低更新表的速度。

MySQL不仅要保存数据，还要保存一下索引文件每次更新添加了索引列的字段，都会调整因为更新所带来的减值变化后的索引信息。

1.3.2 增加空间占用

索引也是一张表，该表保存了主键与索引字段，并指向实体表的记录，所以索引列也是要占用空间的。

1.4 生活中索引的应用

楼层索引

菜鸟驿站

图书目录索引

1.5 索引的分类

1.5.1 普通索引

1、语法

create index 索引名 on 表名 (字段名);

5.7版本InnoDB存储引擎，单表最大1017列，最多包含64个索引，联合索引最多16列。

https://dev.mysql.com/doc/refman/5.7/en/innodb-limits.html

CREATE TABLE `test_index` (  
    `c` bigint(16) NOT NULL AUTO_INCREMENT,  
    `c1` varchar(16) DEFAULT NULL,  
    `c2` varchar(16) DEFAULT NULL,  
    `c3` varchar(16) DEFAULT NULL,  
    `c4` varchar(16) DEFAULT NULL,  
    `c5` varchar(16) DEFAULT NULL,  
    `c6` varchar(16) DEFAULT NULL,  
    `c7` varchar(16) DEFAULT NULL,  
    `c8` varchar(16) DEFAULT NULL,  
    `c9` varchar(16) DEFAULT NULL,  
    `c10` varchar(16) DEFAULT NULL,  
    `c11` varchar(16) DEFAULT NULL,  
    `c12` varchar(16) DEFAULT NULL,  
    `c13` varchar(16) DEFAULT NULL,  
    `c14` varchar(16) DEFAULT NULL,  
    `c15` varchar(16) DEFAULT NULL,  
    `c16` varchar(16) DEFAULT NULL,  
    `c17` varchar(16) DEFAULT NULL,
  PRIMARY KEY (`c`),  KEY `idx_18` (`c1`,`c2`,`c3`,`c4`,`c5`,
  `c6`,`c7`,`c8`,`c9`,`c10`,`c11`,`c12`,`c13`,`c14`,`c15`,`c16`)
) ;

1.5.2 唯一索引

1、语法

create unique index 索引名 on 表名 (字段名)

2、场景

用户表，用户手机号码注册注册，手机号码创建唯一索引，重复手机号码新增，提示索引冲突。

1.5.3 组合索引

单个组合索引，mysql的5.7版本innodb引擎，允许最大设置16个列。

1、语法

create table 表名(
    字段名1 int(11) not null,
    字段名2 varchar(10) not null,    index(字段名1,字段名2)
);

2、最左匹配原则

在多个字段上创建的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用。

EXPLAIN SELECT *  FROM test_index WHERE c2='123';

1.6 索引创建规则

1.61 频繁作为查询条件的字段

适合查询频繁，修改较少的场景。

1.6.2 外键建立索引

表关联查询需求多，其他表的外键适合创建索引。

1.6.3 大文本字段

索引应该建在小字段上，对于大的文本字段甚至超长字段，不要建索引。

1.6.4 频繁更新

频繁进行数据操作的表，不要建立太多的索引。

1.6.5 重复值较多的列

性别字段主要就是“男”、“女”;职位字段中也是有限的几个内容。

添加索引也不会显著的增加查询速度，减少用户响应时间。 因为需要占用空间，反而会降低数据库的整体性能。

1.6.6 按范围查询的列，最好建立索引

索引已经排序，其保存的时候指定的范围是连续的，查询可以利用索引的排序，提高查询效率。 示例：年龄14到18的学生。

1.6.7 排序、统计

排序和统计的字段如果通过索引去访问，将大大提高排序速度。

1.6.8 索引不会包含有NULL值的列

只要列中包含有NULL值都将不会被包含在索引中，复合索引中只要有一列含有NULL值，那么这一列对于此复合索引就是无效的。 建议：数据库设计时不要让字段的默认值为NULL。

二 索引的使用分析

CREATE TABLE `user_info` (
    `id` int(11) NOT NULL AUTO_INCREMENT,
    `name` varchar(255) DEFAULT NULL,
    `nick` varchar(255) DEFAULT NULL,
    `sex` tinyint(2) DEFAULT NULL,
    `score` int(3) DEFAULT NULL,
    KEY `idx_id` (`id`),
    KEY `idx_score` (`score`) USING BTREE
);

insert into user_info values (1, '杨过', 'yangguo', '1', 90);
insert into user_info values (2, '小龙女', 'xiaolongnv', '0', 88);
insert into user_info values (3, '黄药师', 'huangyaoshi', '1', 75);
insert into user_info values (4, '郭襄', 'guoxiang', '0', 66);
insert into user_info values (5, '何足道', 'hezudao', '1', 50);
insert into user_info values (6, '独孤求败', 'duguqiubai', '1', 55);
insert into user_info values (7, '方东白', 'fangdongbai', '1', 88);
insert into user_info values (8, '赵敏', 'zhaomin', '0', 75);
insert into user_info values (9, '程灵素', 'chenglingsu','0', 66);

2.1 索引无效场景

2.1.1 字段取值 != 或者 <>

-- 使用了索引
EXPLAIN SELECT *  FROM user_info WHERE score = 55;    

-- 未使用索引
EXPLAIN SELECT *  FROM user_info WHERE score != 55;

2.1.2 字段列与查询数据列类型不一致

字符串未使用引号

  -- 使用了索引
  EXPLAIN SELECT *  FROM user_info WHERE sex = '0';    
  
  -- 未使用索引
  EXPLAIN SELECT *  FROM user_info WHERE sex = 0;

2.1.3 左模糊查询

EXPLAIN SELECT * FROM user_info WHERE score LIKE '5%';

2.1.4 or包含无索引字段

-- 使用了索引
EXPLAIN SELECT *  FROM user_info WHERE score = 55;    

-- 未使用索引
EXPLAIN SELECT * FROM user_info WHERE score = 55 OR nick='yangguo';

2.1.4 运算操作

相减，身份证截取，日期格式化，字符串拼接比较等。

-- 未使用索引
EXPLAIN SELECT * FROM user_info WHERE substr(name, 2, 2) = '灵素';
-- 使用了索引
EXPLAIN SELECT * FROM user_info WHERE name = '程灵素'; 

-- 使用了索引
EXPLAIN SELECT * FROM user_info WHERE score = 75;
-- 未使用索引
EXPLAIN SELECT * FROM user_info WHERE score-1 = 74;

2.1.5 IS NOT NULL

-- 使用索引
EXPLAIN SELECT *  FROM user_info WHERE score IS NULL;

-- 不使用索引
EXPLAIN SELECT *  FROM user_info WHERE score IS NOT NULL;

三 索引类型及原理

3.1 二叉树

3.1.1 左小

若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

3.1.2 右大

若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3.1.3 跟节点居中

左、右子树也分别为二叉树

链表的查找时间复杂度是O(N)，这时候最多需要7次才能查到所需数据。

3.1.4 时间复杂度

二叉搜索树查找数据的时间复杂度是O(logN)，如图所示，最多查找3次就可以查到所需数据。

3.1.5 缺点

极端情况下，二叉查找树可能退化成线性链表 非平衡树，不适合做数据库索引。

代码实现：
https://gitee.com/ischenshuai/demo/tree/master/dataStruct/
tree/binary-tree-demo

3.2 B树

B树是有序数组+平衡多叉树，总体有序。 树的高度越高，查找次数越多，也就是磁盘IO次数越多，耗时越长。 降低树的高度，把二叉树变成N叉树，即B树。

3.2.1 m阶的B树

1、根节点至少有2个子节点

2、每个中间节点都包含k-1个元素和k个子节点，其中 m/2 <= k <= m

3、每个叶子节点都包含k-1个元素，其中 m/2 <= k <= m

4、中间节点的元素按照升序排列

5、所有的叶子结点都位于同一层

3.2.2 树分析

1. 根节点（8）有两个子节点，左子节点（3 5）和右子节点（11 15）。

2. 左子节点（3 5）中有2个元素和3个子节点。

3. 元素是3和5，按照升序排列。

4. 子节点是（1 2）、（4）、（6 7），

5. 而（1 2）中元素小于3，（4）中的元素在3和5中间，（6 7）的元素大于5，符合B树特征。

3.2.3 优点

高度更低，每个节点含有多个元素，查找的时候一次可以把一个节点中的所有元素加载到内存中作比较，两种改进都大大减少了磁盘IO次数。

3.3 红黑树

3.3.1 定义

1、节点要求

节点必须是红色或者黑色

2、根节点要求

根节点必须是黑色

3、叶子节点要求

叶子节点全部为黑色，叶子是NIL结点

4、红节点要求

每个红色结点的两个子结点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色结点）

5、节点路径要求

从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点

3.3.2 红黑树目标要求

1、优点

限制了左右子树的树高，不会相差过大。查询效率高

2、缺点

规则复杂，可能红黑树转化，开销大

3.4 B+ Tree

有序数组链表+平衡多叉树

3.4.1 约定

1、有k个子节点的中间节点就有k个元素（B树中是k-1个元素），也就是子节点数量 = 元素数量。每个元素不保存数据，只用来索引，所有数据都保存在叶子节点上。

2、所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

3、非叶子节点只保存索引，不保存数据。（B树中两者都保存）。

4、叶子结点包含了全部元素的信息，并且叶子结点按照元素大小组成有序列表。

3.4.2 优点

1、每个节点存储的元素更多，看起来比B树更矮胖，导致磁盘IO次数更少。

2、非叶子节点不存储数据，只存储索引，叶子节点存储全部数据。这样设计导致每次查找都会查到叶子节点，效率更稳定，便于做性能优化。

3、叶子节点之间使用有序链表连接。这样设计方便范围查找，只需要遍历链表中相邻元素即可，不再需要二次遍历二叉树。

3.5 hash

3.5.1 hash冲突

将车库中的车牌号按简称排列，重复的简称，可成为hash冲突。 多个不同的值通过算出了同一个hash值被称之为hash冲突。

3.5.2 hash索引使用场景

1、对等比较

等值比较，使用hash索引效率更高。 由于是一次定位数据，不像BTree索引需要从根节点到枝节点，最后才能访问到页节点这样多次IO访问，所以检索效率远高于BTree索引。

3.5.3 hash索引缺点

1、Hash 索引不能进行范围查询

Hash 索引指向的数据是无序的，而 B+ 树的叶子节点是个有序的链表。

2、Hash 索引不支持联合索引的最左侧原则

对于联合索引来说，Hash 索引在计算 Hash 值的时候是将索引键合并后再一起计算 Hash 值，所以不会针对每个索引单独计算 Hash 值。因此如果用到联合索引的一个或者几个索引时，联合索引无法被利用。

3、Hash 索引不支持 ORDER BY 排序

Hash 索引指向的数据是无序的，因此无法起到排序优化的作用，而 B+ 树索引数据是有序的，可以起到对该字段 ORDER BY 排序优化的作用。

4、无法模糊查询

B+ 树使用 LIKE 进行模糊查询的时候，LIKE 后模糊查询的话就可以起到优化作用。

对于等值查询来说，通常 Hash 索引的效率更高，但是，索引列的重复值如果很多，效率就会降低。这是因为遇到 Hash 冲突时，需要遍历桶中的行指针来进行比较，找到查询的关键字，非常耗时。所以，Hash 索引通常不会用到重复值多的列上，比如列为性别、年龄的情况等。

三 索引相关的问题

3.1 锁表问题

3.1.1 更新时锁表

1、使用非索引字段更新，导致锁表。

在 update 语句的 where 条件没有使用索引，就会全表扫描。 使用索引后，使用“行锁”进行udpate，只锁当前行。不影响其他行的查询更新

3.2 不当索引导致性能开销

使用性别等字段，导致数据查询效果性能提升不大，且增加修改成本。