MySQL索引底层探究

一、什么是索引？

• 索引是一种特殊的文件(InnoDB数据表上的索引是表空间的一个组成部分)，它们包含着对数据表里所有记录的引用指针。
• 索引是一种数据结构。数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。
• 更通俗的说，索引就相当于目录。为了方便查找书中的内容，通过对内容建立索引形成目录。索引是一个文件，它是要占据物理空间的。

二、索引有哪些优缺点？

1.索引的优点

• 可以大大加快数据的检索速度，这也是创建索引的最主要的原因。
• 通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

2.索引的缺点

• 时间方面：创建索引和维护索引要耗费时间，具体地，当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，会降低增/改/删的执行效率；
• 空间方面：索引需要占物理空间。

3.索引简单使用示例

先插入100万数据(bduser表)
......

-- 查询其中一个用户 
SELECT * from bduser where UserCode  = '50000';

-- 添加索引
ALTER TABLE bduser ADD INDEX index_usercode (UserCode);

-- 删除索引
ALTER TABLE bduser DROP INDEX index_usercode;

三、索引引擎

1.引擎分类

• Innodb引擎：Innodb引擎提供了对数据库ACID事务的支持。并且还提供了行级锁和外键的约束。它的设计的目标就是处理大数据容量的数据库系统。
• MyIASM引擎(原本Mysql的默认引擎)：不提供事务的支持，也不支持行级锁和外键。
• MEMORY引擎：所有的数据都在内存中，数据的处理速度快，但是安全性不高。

2.MyISAM索引与InnoDB索引的区别？

• InnoDB索引是聚簇索引，MyISAM索引是非聚簇索引。
• InnoDB的主键索引的叶子节点存储着行数据，因此主键索引非常高效。
• MyISAM索引的叶子节点存储的是行数据地址，需要再寻址一次才能得到数据。
• InnoDB非主键索引的叶子节点存储的是主键和其他带索引的列数据，因此查询时做到覆盖索引会非常高效。

四、索引底层(Innodb)

1.局部性原理

局部性原理是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。当一个数据被用到时，其附近的数据也通常会马上被使用。

一次性读多少呢？

2.数据页

页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存 储块称为一页（在许多操作系统中，页得大小通常为4kb），主存和磁盘以页为单位交换数据。

Innodb默认情况下，表空间中的页大小都为 16KB，当然也可以通过改变 innodb_page_size 选项对默认大小进行修改，一般都是操作系统的整数倍。
一次最少从磁盘读取16KB内容到内存中，一次最少把内存中16KB内容刷新到磁盘中。

-- 查看Innodb一页最大存储大小
show global status like 'Innodb_page_size';

3.Innodb行格式

create table test（
    c1 varchar(10),
    c2 varchar(10) not null,
    c3 char(10),
    c4 varchar(10),
）

共有四种行格式，分别是：compact、redundant、dynamic、compressed

• 变长字段宽度列表。c1和c2和c4为变长字段，字段的长度是不固定的，所以说我们在每条记录的前面把这些变长字段所占用的字节数给记录下来，这就是变长字段宽度列表的作用。比如我们插入一条记录insert into test(c1,c2,c3,c4) value(a,bb,ccc,dddd)，那么在[变长字段宽度列表]中就会存储c1、c2和c4字段的长度，分别是1，2，4（注意：是逆序存放）
• 空值列表。插入一行数据前，MySQL先检查表的结构，查看哪些列可以为空，然后对这行数据中这些可以为空的列，检查他们的值是否为空，如果为空则用 1 标识，如果不为空则用 0 标识。比如：insert into test(c1,c2) value(a,bb)，这条数据只有c1，c2列不为空，那么在[空值列表]中便会记录011。
• 记录头信息。记录头信息主要记录着这条数据的一些信息，比如最常见的几个delete_flag、record_type、next_record、n_owned。delete_flag 标识该条记录是否已经被删除。record_type 表示该条记录的类型。next_record 表示指向下一条记录的地址指针（innodb中可以通过一条记录找到下一条记录就是通过这个指针实现的）。
• 记录的真实数据。row_id:如果建表时没有指定主键，并且表中又找不出非空且不重复的列的话，那么MySQL会自动为该表生成一个隐藏的有序的列作为主键列，这个列就是row_id，用6个字节表示（所以该ID能表示的范围就是1 ~ 2 ^48 ）。trx_id:记录着最近修改这条数据的事务ID。roll_pointer:主要是为innodb的mvcc生成版本连使用。

4.行溢出数据

我们知道，一页最大为16KB也就是16384字节，而一个varchar类型的列最多可以储存65532字节，这样就可能造成一张数据页放不了一行数据的情况。

一页可能存不下一行数据？

在 Compact 和 Reduntant 行格式中，对于占用存储空间非常大的列，在记录的真实数据处只会存储该列的一部分数据，把剩余的数据分散存储在几个其他的页中，然后 记录的真实数据 处用20个字节存储指向这些页的地址（当然这20个字节中还包括这些分散在其他页面中的数据的占用的字节数），从而可以找到剩余数据所在的页。

对于 Compact 和 Reduntant 行格式来说，如果某一列中的数据非常多的话，在本记录的真实数据处只会存储该列的前 768 个字节的数据和一个指向其他页的地址，然后把剩下的数据存放到其他页中，这个过程也叫做 行溢出 ，存储超出 768 字节的那些页面也被称为 溢出页 。

MySQL 版本 5.7 之后默认行格式是 Dynamic ，这俩行格式和 Compact 行格式挺像，只不过在处理行溢出数据时不同，它们不会在记录的真实数据处存储字段真实数据的前 768 个字节，而是把所有的字节都存储到其他页面中，只在记录的真实数据处存储其他页面的地址。

五、深入理解Innodb B+树算法

-- 创建表 t1
create table t1 (
    a int primary key,
    b int not null,
    c int,
    d int,
    e varchar(20)
) engine=InnoDB;

insert into t1 values (4,3,1,1,'d');
insert into t1 values (1,1,1,1,'a');
insert into t1 values (8,8,8,8,'h');
insert into t1 values (2,2,2,2,'b');
insert into t1 values (5,2,3,5,'3');
insert into t1 values (3,3,2,2,'c');
insert into t1 values (7,4,5,5,'g');
insert into t1 values (6,6,4,4,'f');


-- 创建表t2
create table t2 (
    a int primary key,
    b int not null,
    c int,
    d int,
    e varchar(20)
) engine=MyISAM;

insert into t2 values (4,3,1,1,'d');
insert into t2 values (1,1,1,1,'a');
insert into t2 values (8,8,8,8,'h');
insert into t2 values (2,2,2,2,'b');
insert into t2 values (5,2,3,5,'3');
insert into t2 values (3,3,2,2,'c');
insert into t2 values (7,4,5,5,'g');
insert into t2 values (6,6,4,4,'f');


-- 查询
select * from t1; -- 聚集
select * from t2; -- 堆表

1.主键索引

InnoDB这种存储方式的优点

• 查询便捷，超出数据索引大小时停止查找
• 数据分组，使用Page Directory增加查询速度

最终的大致模型如下：

B+树特点

• 真实完整数据在叶子节点上
• 非叶子节点数据冗余在叶子节点上
• 一个节点存在多个数据
• 节点中的数据顺序排列
• 叶子节点之间有指针

B树是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。

• 特点：
  • 叶节点具有相同的深度，叶节点的指针为空。
  • 所有索引元素不重复；
  • 节点中的数据索引从左到右递增排列。
  • 每个节点都有data。
• 缺点：
  • 如果data过大，一个节点存放的数据少，这样会导致树加深，这样也增加了IO次数。
  • 范围查询支持不好。

B+树的好处：

• 一个节点可以存储多个数据，减少深度，提高查询效率

• where id>2 这种条件，叶子结点有指针，可以直接查询，减少树左右节点的比较及回归。

    那么MyISAM是什么结构呢？
    MyISAM索引也为B+树，只不过叶子节点存放的是不是真实数据，而是真实数据的地址，所以查询的时候还需要一次寻址查询。
  

2.非主键索引

-- 组合索引
create index idx_t1_bcd on t1(b,c,d);

-- 辅助索引查找
explain SELECT * from t1 where b=1 and c=1 and d=1;

-- 创建b字段索引
create index idx_t1_b on t1(b);

特点：

• 组合索引会进行排序，即相邻的两个数据在物理上可能不相邻

• 叶子节点上不存储具体数据，只存储这条数据的主键

• 查到数据，先查找据数据的主键，再从主键索引中查找出具体的数据，被称为 回表

    那什么是全表扫描？即将表中的所有数据一一进行比较。
    explain SELECT * from t1 where c=0;
    索引失效，索引的左匹配原则。
  

六、索引类型

主键索引: 数据列不允许重复，不允许为NULL，一个表只能有一个主键。

唯一索引: 数据列不允许重复，允许为NULL值，一个表允许多个列创建唯一索引。

• 可以通过 ALTER TABLE table_name ADD UNIQUE (column); 创建唯一索引
• 可以通过 ALTER TABLE table_name ADD UNIQUE (column1,column2); 创建唯一组合索引

普通索引: 基本的索引类型，没有唯一性的限制，允许为NULL值。

• 可以通过 ALTER TABLE table_name ADD INDEX index_name (column); 创建普通索引
• 可以通过 ALTER TABLE table_name ADD INDEX index_name(column1, column2, column3); 创建组合索引

全文索引： 是目前搜索引擎使用的一种关键技术。

• 可以通过 ALTER TABLE table_name ADD FULLTEXT (column); 创建全文索引

七、索引创建原则

索引虽好，但也不是无限制的使用，最好符合一下几个原则

• 最左前缀匹配原则，组合索引非常重要的原则，mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，如果建立(a,b,d,c)的索引则都可以用到，a,b,d的顺序可以任意调整。
• 较频繁作为查询条件的字段才去创建索引
• 更新频繁字段不适合创建索引，涉及索引结构变化会耗时
• 若是不能有效区分数据的列不适合做索引列(如性别，男女未知，最多也就三种，区分度实在太低)
• 尽量的扩展索引，不要新建索引。比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可。
• 对于那些查询中很少涉及的列，重复值比较多的列不要建立索引。
• 对于定义为text、image和bit的数据类型的列不要建立索引。

创建索引时需要注意什么？

• 非空字段：应该指定列为NOT NULL，除非你想存储NULL。在mysql中，含有空值的列很难进行查询优化，因为它们使得索引、索引的统计信息以及比较运算更加复杂。你应该用0、一个特殊的值或者一个空串代替空值；
• 取值离散大的字段：（变量各个取值之间的差异程度）的列放到联合索引的前面，可以通过count()函数查看字段的差异值，返回值越大说明字段的唯一值越多字段的离散程度高；
• 索引字段越小越好：数据库的数据存储以页为单位一页存储的数据越多一次IO操作获取的数据越大效率越高。