2.1 索引概述

MySQL索引（index）: 是帮助MySQL高效获取数据的数据结构,所以索引的本质就是数据结构!

在表数据之外，数据库系统还维护者满足特定查找算法的数据结构，这些数据结构以某种方式指向数据， 这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。

如下面的示意图 所示 :

左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找快速获取到相应数据。

一般来说索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上。索引是数据库中用来提高性能的最常用的工具。

2.2 索引优势劣势

2.2.1 优势

1） 类似于书籍的目录索引，提高数据检索的效率，降低数据库的IO成本。2） 通过索引列对数据进行排序，降低数据排序的成本，降低CPU的消耗。

2.2.2 劣势

1） 实际上索引也是一张表，该表中保存了主键与索引字段，并指向实体类的记录，所以索引列也是要占用空间的。2） 虽然索引大大提高了查询效率，同时却也降低更新表的速度，如对表进行INSERT、UPDATE、DELETE。因为更新表时，MySQL 不仅要保存数据，还要保存一下索引文件每次更新添加了索引列的字段，都会调整因为更新所带来的键值变化后的索引信息。

# 1. 索引是什么? 是数据结构
# 2. 索引的优缺点
 a. 好处: 提高查询的效率
 b. 坏处: 降低增删改的效率(索引也是表,也需要维护,增删改数据, 索引也会受到影响,也需要调整)

2.3 索引的结构

索引如果按数据结构划分, 常见的有以下3类:

• BTREE  索引 ：MySQL使用最频繁的一个索引数据结构，是InnoDB和MyISAM存储引擎默认的索引类型,底层基于B+Tree数据结构(mysql5.6默认使用)
• HASH  索引：MySQL中Memory存储引擎默认支持的索引类型 。
• R-tree  索引（空间索引）：空间索引是MyISAM引擎的一个特殊索引类型，主要用于地理空间数据类型，通常使用较少，不做特别介绍。

需要说明的是, 因为MySQL软件可能使用不同的存储引擎(默认使用InnoDB), 每种存储引擎对各种索引的支持可能不一样:

我们平常所说的索引，如果没有特别指明，都是指B+Tree（多路搜索树，并不一定是二叉的）结构组织的索引。

2.3.1 B+Tree的原理

• 索引是在存储引擎中实现的,不同的存储引擎支持的索引也不一样,这里我们主要介绍InnoDB引擎的BTree索引.

• BTree索引类型是基于B+Tree数据结构的, 而B+Tree数据结构又是BTree数据结构的变种. 通常使用在数据库和操作系统中的文件系统, 特点是能够保持数据稳定有序.

# 要理解BTree索引原理,我们需要依次学习
1. 磁盘存储的特点
2. BTree的特点
3. B+Tree的特点

2.3.1.1 磁盘存储的特点

• 系统从磁盘读取数据到内存时是以磁盘块(block)为基本单位的.
• 位于同一个磁盘块的数据会被一次性读取出来,而不是需要什么取什么.
• InnoDB存储引擎中有页(page)的概念,页是磁盘管理的最小单位.InnoDB存储引擎中默认每个也的大小为16KB.
• InnoDB 引擎将若干个地址链接磁盘块,以此来达到页的大小16KB,在查询数据时如果一个页中的每条数据都能有助于定位数据定位的位置,这将会减少I/0次数,提高查询效率.

“

比如上图,我要查询数字5, 系统读取到磁盘块2之后, 将整个磁盘块2的数据都读取出来,而不是只读取一个5. 读取出来之后是(4,5,6),然后再根据条件过滤保留5.

”

2.3.1.2 BTree的图示

在图中，我们可以看出 BTree 树下，这是一个多叉树，并不是单独的二叉树。

每个节点就相当于一个磁盘块。而每个磁盘块 不仅包含key值(上图的id和指针),还有数据.

但是我们如果想要查询数据10，下面来看看查询的过程：

• 1.首先从根节点【磁盘块1】开始，判断10是否大于17，如果小于17，那么则从 c2 指针往下走一个节点
• 2.走到【磁盘块2】查询判断10大于8.小于12，此时将走向 c6 指针，往下走一个节点
• 3.走到【磁盘块6】终于搜索到了 id为10 的数据了。

可以看到整体执行过程中，共总查询了 3 次。

但是【磁盘块1】的 id 17 的数据、【磁盘块2】的 id 8 和 id 12 的数据 也在查询过程中读取出来了，这个读取的过程是浪费的。因为对于想要读取 id 10 的数据来说，真正有作用的只是 指针 和 id 号。

所以为了提升效率，B+Tree 将会去除每个节点中的 id 数据，每个节点只保留 id 和 指针，而数据都保存在 叶子节点中。

2.3.1.3 B+Tree的图示

# 总结
1. BTree数据结构
  每个节点不仅包含key值(上图的id和指针),还有数据.
2. B+Tree数据结构
  a. 非叶子节点只存储key值
  b. 所有数据存储在叶子节点
         c. 叶子节点之间有连接指针, 方便范围查找
3. B+Tree的好处
  a. 查询效率更加稳定:由于数据都保存在叶子节点上,意味着每次查询都要查找到叶子节点,所以相对BTree查询效率更加稳定
  b. 数据结构较小

2.3.2  B+Tree 的 数据结构

2.3.2.1 BTREE 结构

BTree又叫多路平衡搜索树，一颗m叉的BTree特性如下：

• 树中每个节点最多包含 m个孩子。
• 除根节点与叶子节点外，每个节点至少有 [ceil(m/2)]个孩子。
• 若根节点不是叶子节点，则至少有两个孩子。
• 所有的叶子节点都在同一层。
• 每个非叶子节点由 n个key与n+1个指针组成，其中[ceil(m/2)-1] <= n <= m-1

以5叉BTree为例，key的数量：公式推导[ceil(m/2)-1] <= n <= m-1。所以 2 <= n <=4 。当n>4时，中间节点分裂到父节点，两边节点分裂。

插入 3 14 7 1 8 5 11 17 13 6 23 12 20 26 4 16 18 24 25 19 数据为例

演变过程如下：

1). 插入前4个数字 3 14 7 1

2).  插入8，n>4，中间元素7向上分裂到新的节点

3).  插入5，11，17不需要分裂

4).  插入13，中间元素13向上分裂到父节点7

5).  插入6，23，12，20不需要分裂

6).  插入26，中间元素20向上分裂到父节点中

7).  插入4，中间元素4向上分裂到父节点中。然后插入16，18，24，25不需要分裂

8).  最后插入19，14 16 17 18节点n>5，中间节点17向上分裂，但分裂后父节点4  7 13 20的n>5，中间节点13向上分裂

到此，该 BTREE树就已经构建完成了， BTREE树 和 二叉树 相比， 查询数据的效率更高， 因为对于相同的数据量来说，BTREE的层级结构比二叉树小，因此搜索速度快。

2.3.2.2 B+TREE 结构

B+Tree为BTree的变种，B+Tree相对于B-Tree有几点不同：

1. 非叶子节点只存储键值信息。
2. 所有叶子节点之间都有一个链表指针。(MySql对B+Tree的优化, 方便范围查询)
3. 数据记录都存放在叶子节点中。

由于 B+Tree只有叶子节点保存key信息，查询任何key都要从root走到叶子。所以B+Tree的查询效率更加稳定。

2.4 索引的分类

* 主键（约束）索引
  1. 主键约束(唯一不为空)+提高查询效率  
  2. 备注: 在创建主键的时,自动生成
* 唯一（约束）索引
  1. 唯一约束(可为空)+提高查询效率
  2. 备注: 创建唯一约束时,自动生成
* 外键索引
  1. 只有InnoDB引擎支持外键索引,用来保证数据的一致性和完整性以及级联操作.
         2. 备注: 在创建外键时,自动生成  
* 普通索引
  仅提高查询效率
* 组合（联合）索引
  多个字段组成索引
* 全文索引
  快速匹配全部文档的方式,mysql5.6之后才支持全文索引

2.5 索引语法

索引在创建表的时候，可以同时创建， 也可以随时增加新的索引。

2.5.0 准备环境:

create database indxdb;

use indxdb;

-- 创建学生表
CREATE TABLE student(
 id INT,
 `name` VARCHAR(32),
 telephone VARCHAR(11)
);

2.5.1 创建索引

① 直接创建【了解】

-- 创建普通索引
create index 索引名 on 表名(字段);
-- 创建唯一索引
create unique index 索引名 on 表名(字段);
-- 创建普通组合索引
create index 索引名 on 表名(字段1,字段2);
-- 创建唯一组合索引
create unique index 索引名 on 表名(字段1,字段2);

测试执行如下：

-- 1.name字段适合设置什么索引？ 普通索引
CREATE INDEX idx_name ON student(`name`);
-- 执行如下：
mysql> CREATE INDEX idx_name ON student(`name`);
Query OK, 0 rows affected (0.07 sec)
Records: 0  Duplicates: 0  Warnings: 0

-- 2.telephone适合设置什么索引？ 唯一索引
CREATE UNIQUE INDEX idx_uni_telephone ON student(telephone);
-- 执行如下：
mysql> CREATE UNIQUE INDEX idx_uni_telephone ON student(telephone);
Query OK, 0 rows affected (0.01 sec)
Records: 0  Duplicates: 0  Warnings: 0

② 修改表时指定【了解】

-- 添加一个主键，这意味着索引值必须是唯一的，且不能为NULL
alter table 表名 add primary key(字段);  --默认索引名：primary
-- 添加唯一索引（除了NULL外，NULL可能会出现多次）
alter table 表名 add unique 索引名(字段);
-- 添加普通索引，索引值可以出现多次。
alter table 表名 add index 索引名(字段); 

--  该语句指定了索引为FULLTEXT， 用于全文索引(了解)
alter table 表名 add fulltext 索引名(字段);

测试执行如下：

-- 指定id为主键索引
ALTER TABLE student ADD PRIMARY KEY(id);

-- 指定name为普通索引
ALTER TABLE student ADD INDEX idx_name(`name`);

-- 指定telephone为唯一索引
ALTER TABLE student ADD UNIQUE idx_uni_telephone(telephone);

③ 创建表时指定【掌握】

-- 创建教师表
-- 创建教师表
CREATE TABLE teacher(
 id INT PRIMARY KEY AUTO_INCREMENT, -- 主键索引
 `name` VARCHAR(32),
 telephone VARCHAR(11) UNIQUE, -- 唯一索引
 sex VARCHAR(5),
 birthday DATE,
 student_id INT,
 INDEX(`name`), -- 普通索引
 CONSTRAINT fk_01 FOREIGN KEY (student_id) REFERENCES student(id) -- 外键索引   
);

2.5.2 查询索引

show index from 表名; 

show index from teacher; 

#查询结果说明
1. table : 表
2. Non_unique: 是否唯一(0表示true,1表示false)
3. Key_name : 索引的名字
4. Column_name : 索引所在的列
5. Null : 是否允许为空(YES表示允许,什么都没有表示不允许)
6. Index_type: 索引的数据结构类型

2.5.3 删除索引

-- 直接删除
drop index 索引名 on 表名;

-- 修改表时删除 【掌握】
alter table 表名 drop index 索引名;

测试执行如下：

-- 删除name普通索引
DROP INDEX idx_name ON student;

-- 删除telephone唯一索引
ALTER TABLE student DROP INDEX idx_uni_telepphone;

2.6 百万级数据效率演示

2.6.1 准备数据

-- 1. 准备表
CREATE TABLE `user`(
 id INT,
 username VARCHAR(32),
 `password` VARCHAR(32),
 sex VARCHAR(6),
 email VARCHAR(50)
);

-- 2. 创建存储过程，实现批量插入记录
DELIMITER $$ -- 声明存储过程的结束符号为$$
CREATE PROCEDURE auto_insert()
BEGIN
    DECLARE i INT DEFAULT 1;
 START TRANSACTION; -- 开启事务
    WHILE(i<=1000000)DO
        INSERT INTO `user` VALUES(i,CONCAT('jack',i),MD5(i),'male',CONCAT('jack',i,'@qq.com'));
        SET i=i+1;
    END WHILE;
 COMMIT; -- 提交
END$$ -- 声明结束
DELIMITER ; -- 重新声明分号为结束符号

-- 3. 调用存储过程: 耗时比较长，慢慢等待吧
CALL auto_insert();

-- 4. 查看表中数据总量: 100万
select count(*) from user;

执行如下：

2.6.2 先来测试没有索引情况下查询

-- 1.指定id查询
mysql> select * from user where id = 888888;
+--------+------------+----------------------------------+------+-------------------+
| id     | username   | password                         | sex  | email             |
+--------+------------+----------------------------------+------+-------------------+
| 888888 | jack888888 | 21218cca77804d2ba1922c33e0151105 | male | jack888888@qq.com |
+--------+------------+----------------------------------+------+-------------------+
row in set (0.47 sec) -- 执行耗时0.47s

-- 2.指定username精准查询
mysql> select * from user  where username = 'jack123456';
+--------+------------+----------------------------------+------+-------------------+
| id     | username   | password                         | sex  | email             |
+--------+------------+----------------------------------+------+-------------------+
| 123456 | jack123456 | e10adc3949ba59abbe56e057f20f883e | male | jack123456@qq.com |
+--------+------------+----------------------------------+------+-------------------+
row in set (0.61 sec) -- 执行耗时0.61s

-- 3.指定email模糊查询
mysql> select * from user  where email like 'jack123456%';
+--------+------------+----------------------------------+------+-------------------+
| id     | username   | password                         | sex  | email             |
+--------+------------+----------------------------------+------+-------------------+
| 123456 | jack123456 | e10adc3949ba59abbe56e057f20f883e | male | jack123456@qq.com |
+--------+------------+----------------------------------+------+-------------------+
row in set (0.54 sec) -- 执行耗时0.54s 

mysql> 

可以看到在百万数据下，耗时还是比较长的，下面我们来建立索引，看看提升的效率。

2.6.3 给这三个字段添加索引

-- 指定id为主键索引
ALTER TABLE user ADD PRIMARY KEY(id);
-- 指定username为普通索引
ALTER TABLE user ADD INDEX(username);
-- 指定email为唯一索引
ALTER TABLE user ADD UNIQUE(email);

执行如下：

2.6.4 再测试有索引情况下查询

-- 1.指定id查询
select * from user where id = 888888; -- 执行耗时0.02s
-- 2.指定username精准查询
select * from user  where username = 'jack123456'; -- 执行耗时0.01s
-- 3.指定email模糊查询
select * from user  where email like 'jack123456%'; -- 0.00s

执行如下：

2.7 索引的设计原则

# 索引的特点总结
1. 索引本身也是一张表, 也需要存在磁盘上
2. 优点: 减少磁盘IO,提高查询效率
3. 缺点: 索引占用空间,在进行增删改操作时,索引的维护会增加成本,可能降低服务器性能

# 索引的设计原则
1. 对查询频次较高,且数据量比较大的表建立索引
2. 使用唯一索引,区分度越高,使用索引的效率越高(精准查询比模糊查询快)
3. 索引字段的选择,最佳候选列应当从where字句的条件中提取
4. 不要随意创建索引,因为维护索引也需要成本