• Mysql 索引
  • InnoDB的索引模型
    • 一个简单的设计方案
      • 案例
      • 迭代一次：目录项记录的页(目录页)
      • 迭代2次：目录项记录的多个页
      • 迭代3次:目录项记录页的目录页
    • 聚簇索引
    • 二级索引(辅助索引、非聚簇索引)
    • InnoDB的B+树索引的注意事项
    • MyISAM与InnoDB的对比
      • 为什么不适用Hash结构？

Mysql 索引

索引是帮助MySQL高效获取数据的数据结构，，排好序的快速查找数据结构
目的：减少磁盘I/O的次数，加快查询速度

索引主要影响两个位置：

• 快速查找(提高数据查询效率):影响where后面的查找
• 排好序:order by

索引是在存储引擎中实现的

优点
1.提高数据检索的效率，降低数据库的IO成本
2.创建唯一索引，保证数据库表中每一行数据的唯一性
3.在使用分组和排序子句进行数据查询时，可以减少查询中分组和排序的时间，降低CPU的消耗

缺点
1.创建索引和维护索引要耗费时间，并且随着数据量增加，所耗费的时间也会增加。
2.索引需要磁盘空间，一般索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘中。
3.降低更新表的速度，当对表中的数据进行增加、删除和修改时，索引也要动态维护，这样就降低了数据的维护速度

索引可以提高查询的速度，但是会影响插入记录的速度。这种情况下，最好的办法是先删除表中的索引，然后插入数据，插入完成后再创建索引。

InnoDB的索引模型

一个简单的设计方案

CREATE TABLE index_demo(
	c1 INT,
	c2 INT,
	c3 CHAR(1),
	PRIMARY KEY(c1)
)ROW_FORMAT = Compact # 行格式表示每个记录的格式ROW_FORMAT

Compact

record_type：
0 普通记录
1 目录项记录
2 最小记录
3 最大记录

案例

假设每个数据页最多存放3条记录

INSER INTO index_demo VALUES(1,4,'u'),(5,3,'y'),(3,9,'d')

按主键从小到大的顺序排列

此时数据页10已经有三条记录了，假设现在再插入一条记录，那么需要再分配一个数据页

INSERT INTO index_deomo VALUES(4,4,'a')

假设现在需要查询一条记录，由于数据页的编号可能是不连续的，所以查询的时候可能需要每个数据页都进去查看一遍，效率是非常低的。

给每个页建立一个目录项

先在目录项上查找，然后再进入具体的数据页查找，这样可以提高查询效率

迭代一次：目录项记录的页(目录页)

上述目录项采用物理上连续的空间存储(如数组)
1.如果当目录项个数很多时，可能并没有足够多的连续空间
2.当发生增删改目录项时，为了维持key有序，是非常麻烦的

目录项也采用单项链表上连接，此时目录项也构成了一个页，称为目录页

目录项记录和普通的用户记录的异同点

相同点
都会为主键值生成Page Directory页目录，目的是为了使用二分法来加快查询速度。

假设要查询主键为20的记录
1.先再目录页通过二分法查找页目录，12<20<209，定位到记录在页9
2.到页9的页目录中采用二分法快速找到主键值为20的用户记录

只有2次IO操作

迭代2次：目录项记录的多个页

假设一个目录页已经记录完了，就需要再分配一个新的存储目录项记录的页

如果要查找某个记录，就需要先使用二分法在页30的目录页查找，如果没找到需要去页32的页目录查找

迭代3次:目录项记录页的目录页

如果需要查找的记录在目录页的很后面，那需要多次的IO访问

由于页是不连续的，为了快速定位，我们需要在套一层目录。这样可以稳定IO访问次数

B+ 树能够很好地配合磁盘的读写特性，减少的磁盘I/O操作的次数。
这个数据结构就是B+树
1.只有叶子节点存储数据
2.每一个父节点的元素都出现在子元素中，是子节点的最大(小)元素
3.叶子节点之间通过链表连接，

假设一个数据页可以存放100条用户记录,一个目录页可以存放1000条目录项记录
B+树有一层，可以存放100条记录
B+树有两层，可以存放1000*100 = 10,0000条数据
B+树有三层，可以存放1000*1000*100=1,0000,0000条数据
....

一般情况下，用到的B+树都不会超过4层
1.已经可以存储相当多的数据了
2.层数越低，访问IO的次数越少

聚簇索引

索引分为：

• 聚簇索引：由主键构建，聚簇表示记录和目录存储在一起
• 非聚簇索引/二级索引/辅助索引：由非主键构建，非聚簇是不存储真正的数据的

所有完整的用户记录(包括隐藏列)都存放在聚簇索引的叶子节点处。InnoDB中不需要显示的使用INDEX语句去创建聚簇索引，InnoDB存储引擎会自动为我们创建聚簇索引

优点
1.访问速度更快
2.聚簇索引对主键的排序查找和范围查找速度非常快
3.按照聚簇索引排列顺序，查询一定范围数据的时候，由于数据都是紧密相连的，数据库不用从多个数据块中提取数据，所以节省了IO操作

缺点
1.插入速度严重依赖插入顺序，对于InnoDB表，我们一般会定义自增的ID列为主键
2.更新主键的代价很高，因为会导致主键被更新后行移动，对于InnoDB，我们一般定义主键不可更新
3.二级索引访问需要两次索引查找，第一次查找主键值，第二次根据主键值查找行数据

尽量使用自增主键
NOT NULL PRIMARY KEY AUTO_INCREMENT
每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。
如果使用业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高。

限制
1.MySQL数据库中只有InnoDB数据引擎支持聚簇索引，而MyISAM并不支持聚簇索引
2.由于数据物理存储方式只有一种，所以每个MySQL的表只能有一个聚簇索引
3.如果没有定义主键，Innodb会选择非空的唯一索引代替，如果没有，Innodb会隐式定义一个索引来作为聚簇索引

二级索引(辅助索引、非聚簇索引)

假设c2列为索引，则叶子节点记录c2的值和对应的主键值

每个索引对应一个B+树
假设需要找c2=4的记录，先在这颗B+树上找到对应的主键为1，在去主键B+树去找主键为1的记录,这个过程称为回表。

联合索引

联合索引同时为多个列建立索引，假设我们想让B+树按照c2和c3列的大小排序。会先按照c2进行排序，如果c2相同会按照c3列进行排序

InnoDB的B+树索引的注意事项

• 1 跟页面位置万年不动
• 2 内节点中目录项记录的唯一性
• 3 一个页面最少存储2条记录

1 跟页面位置万年不动

为某个表创建一个B+树索引(聚簇索引不是人为创建的，默认就有)的流程

1.为这个索引创建一个根节点页面。最开始表中没有数据的时候，每个B+树索引对应的根节点中既没有用户记录，也没有目录项记录
2.向表中插入用户记录时，先把用户记录存储到这个根节点中
3.当根节点中的空间用完时，继续插入记录，会将根节点的所有记录复制到一个新分配的页a，然后对新页面进行页分裂操作，得到一个新页b。新记录根据键值的大小会分配到页a或页b中，而根节点便升为目录页
4.当跟节点空间用完时，继续插入记录，会将跟节点的所有记录复制到一个新分配的页C，然后对新页面进行页分裂操作，得到一个新页d，根节点便升为目录页的目录页

2 内节点中目录项记录的唯一性
主要针对二级索引

B+树中目录项记录的内容是索引列+列号，对于二级索引来说不严谨。假设表中的数据是

保证B+树的同一层内节点的目录项记录（除页号，页号肯定是不一样的）是唯一的

所以对于二级索引的内节点的目录项记录的内容是由三个部分构成

• 索引列的值
• 主键值，保证唯一性
• 页号

二级索引的内节点的目录项也保留了主键值

MyISAM与InnoDB的对比

主键索引和二级索引的结构都一样

为什么不适用Hash结构？

1.Hash索引仅满足(=<>IN)查询，进行范围查询的速度很慢，因为数据的存储是无序的，如果在ORDER BY的情况下，还需要对数据重新排序

2.对应联合索引，Hash值是将联合索引键合并一起来计算，无法对单独的一个键或几个键进行查询

3.对于等值查询，通常Hash索引效率更高，但是查询的Hash冲突的值过多时，效率回下降。

InnoDB本身不支持Hash索引，但是提供自适应Hash索引，如果某个数据经常被访问，就会将这个数据页的地址放到Hash表中，下次查询时就可以直接找到这个页面的所在位置。
采用自适应Hash索引可以根据SQL的查询条件快速定位到叶子节点，尤其当B+树比较深的时候，通过自适应Hash索引可以明显提高数据的检索效率。

通过innodb_adaptive_hash_index变量查询是否开启自适应Hashshow variables like'%adaptive_hash_index',默认时开启的