1.b-树索引
索引首先要回顾一下b树b+树的特点和区别，数据库引擎用b+树的好处有查询时间比较稳定，b+树比较适合范围查询,b+树比较矮胖，b树的高度代表随机io的次数，相对的查询时间会比较短。
如图是索引的一般设计
非叶子也拥有指向叶子页的指针，叶子页之间也存在指针。
文中说道:逻辑页依赖于不同的存储引擎，对于InnoDB为16k。对此“页”的概念做一些资料查找。
页是innodb存储引擎的最小存储单位，有数据页,undo页，系统页，事务处理页。默认的页是16kb,每个页上至少有2条以上的记录。
b-树适合的查询类型
- 全键值
- 键值范围
- 键值前缀(最左前缀)
其中具体包含如下(索引为lastname,firstname,birthday)
- 全部键值 查找lastname=Allen,firstname=Cuba,birthday='1960-01-01'
- 匹配最左前缀 查找lastname=Allen
- 匹配列前缀 查找lastname like"A%"
- 匹配范围值 查找lastname>'A' and lastname<'D'
- 精确匹配某一列并范围匹配另一列 lastname='Allen' and firstname like "f%"
- 覆盖索引的查询
orderBy是否能用到索引的条件和查询是否能用到索引的条件一致
不能使用索引的限制
- 不是从最左开始 查找 firstname='Cuba'
- 不能跳过索引中的列 查找 lastname='Allen' and birthday='2019-01-01'
- 查询中某一列用了范围查询，右边的所有列无法用索引再优化 查找 lastname='A' and firstname like "A%" and birthday = '2019-01-01'
2.哈希索引
哈希索引基于哈希表实现，只有精确匹配索引所有列才有效。对于每一行数据，对所有索引列计算哈希码，哈希索引将哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。
Memory引擎显示支持哈希索引，同时也支持B-tree索引。而且Memory引擎支持非唯一哈希索引，索引会以链表的方式存在同一条哈希条目中。
哈希索引速度非常快，但是限制如下:
- 哈希索引只包含哈希值和行指针，不能在索引中直接查到数据行(对速度影响较小)。
- 哈希索引不是按照索引值顺序排序的，无法用于排序。
- 不支持单个索引列查找，只有部分列是无法使用索引的
- 只支持等值查询，不支持范围查询
- 哈希冲突时查询速度会变慢
innodb有个特殊功能叫"自适应哈希索引(adaptive hash index)",当Innodb注意到某些索引值使用非常频繁的时候，会在内存基于B-tree索引之上创建一个哈希索引，让B-Tree索引具有哈希索引的优点，这个功能是完全自动的，内部行为，用户无法控制或者配置。
这里有个扩展知识就是在平时使用Mysql时我们对一个字段添加了hash索引的话，重新show INDEXES from tableA 会发现的index_type还是BTREE，这个就是上面所说的自适应哈希，其实还是在BTREE的基础上做了哈希索引。
在InnoDB中如何优化如下查询
select id from url where url = "http://www.mysql.com";
可以在该数据库手动建立一个哈希索引列，基于这一列来查询会更快
select id from url where url = "http://www.mysql.com" and url_crc=CRC32("http://www.mysql.com")
这种方案麻烦的地方在于需要手动维护url_crc
全文索引
更类似于搜索引擎做的事情，不是简单的where匹配，全文索引适用于match against操作。
索引的优点
- 减少服务器需要扫描的数据量
- 帮助服务器避免排序和临时表
- 索引可以将随机IO变为顺序IO
如何才能使用到索引
1.独立的列
索引列不能是表达式的一部分，也不能是函数的参数
select * from where To_DAYS(current_date) < 10
2.前缀索引和索引选择性
索引选择性就是说用了这个索引可以筛选多少行，可以过滤多少行，不重复的索引值越多，选择性越大。
文中的例子是对city这个地段做索引，可以用这个公式来测算索引选择性
select count(distinct city)/count(*) from city_demo
计算前缀索引长度的一个建议就是计算完整列的选择性，使得前缀的选择接近于完整列。
select count(distinct left(city,3))/count(*) as sel3,
count(distinct left(city,4))/count(*) as sel4 from city_demo
当索引字节增加，索引选择性没有太大变化时，即认为当前长度足够了。
alter table city_demo add key (city(7));
3.多列索引
4.B—tree索引选择合适的索引列顺序
确定索引列的顺序的其中一个原则是将选择性最高的列放在最前面。
以下面查询为例
select * from payment where staff_id = 2 and customer_id = 584;
是应该创建(staff_id,customer_id)的索引还是颠倒下顺序。
实际上如果staff_id和customer_id的组合数接近总行数，那就说明数据没什么区分度
select count(distinct staff_id,customer_id)/count(*) 比值非常小，说明staff_id,customer_id的组合重复非常多的时候
那么这个联合索引就没啥用，反而如果customer_id的区分度很高，只用customer_id做索引会是查询效率提高很多
聚簇索引
聚簇索引是一种数据存储方式，当表有聚簇索引时，数据行实际存放在索引的叶子页。属于聚簇表示数据行和相邻的键值紧凑地存储在一起。因为无法把数据行放在两个不同的地方，所以一个表只能有一个聚簇索引。
聚簇索引实际上是b-tree+数据行
Mysql的内建存储引擎都不支持服务器选择哪个索引作为聚簇索引，InnoDB通过主键聚集数据，即上图中被索引的列是主键列。
聚簇索引的优点：
- 可以把相关数据保存在一起，例如根据用户id来查找用户的邮件，如果没有使用聚簇索引，可能每封邮件都需要一次IO。（读到这里我是有疑问的，前面说innodb聚簇索引是主键，那主键做索引查邮件只可能是一次IO,一个用户id就一行数据。这里我认为应该是我的误解，这个说法是针对所有聚簇索引的，而不是单指innodb，而innodb是基于主键的)
- 数据访问更快，索引中直接包含数据，比普通索引更快
- 使用覆盖索引扫描的查询可以直接使用页节点的值
聚簇索引的缺点
- 聚簇索引是最大限度提高了IO密集型应用的性能，但是如果数据都在内存里，访问顺序就不重要了，聚簇索引也没什么优势。
- 插入速度依赖于插入顺序，innodb是主键做聚簇索引，索引按照主键顺序插入是最快的
- 更新聚簇索引列代价比较高。 比如Innodb中的主键
- 基于聚簇索引插入行，会面临"页分裂"问题，当主键插入一个已经满了的页中，存储引擎会将该页分为两个页面，会造成占用更多的磁盘空间。
- 聚簇索引导致全表扫描变慢，由于页存储不连续的时候。
- 非聚簇索引会比较大，因为二级索引包含引用行的主键列
- 二级索引访问需要两次索引查找(innodb一次b-tree，找到主键后查找聚簇索引的b-tree,对于innodb，自适应哈希能够减少这种重复工作)
下面看下MyISAM和Innodb对于索引实现的区别，创建如下的数据表,插入10000行数据
create table layout_test(
col1 int not null,
clo2 int not null,
PRIMARY KEY(col1),
KEY(col2)
)
对于MyISAM引擎，如下:
数据列如下
主键索引如下
col2索引如下
可以看到主键索引和普通索引没有什么区别，叶子页都存放的是行号，用来索引到具体的数据行。
对于Innodb引擎，聚簇索引如下:
可以看到innodb主键索引的叶子节点存放的就是行数据。每个叶子节点都包含了主键值，事务ID,用于事务和MVCC的回滚的指针，以及剩余的列。
还有一个MyISAM和Innodb的二级索引和聚簇索引很不相同。Innodb的二级索引的叶子节点不是行指针，而是主键值，并用主键值当做行指针，这样就减少了当前行移动或者数据页分裂时二级索引的维护工作。innodb在移动行时不需要更新二级索引上的指针。
二级索引列的数据如下：
下图可以清楚看出MyISAM和Innodb的区别
一个问题:在InnoDB表中按主键顺序插入行的两种方案，一种主键是递增的id,一种主键是uuid，哪种插入速度会比较快?
两者的区别如下
顺序：
uuid:
- 写入的目标页可能已经刷到磁盘并从缓存删除，Innodb在插入前不得不找到并且从目标页存到内存中，这会导致大量随机IO。
- 插入是乱序的，Innodb会不得不频繁地做页分裂操作，为新的行分配空间，一次插入最少修改三个页而不是一个页。
- 频繁的页分离会造成页变得稀疏，最终会有碎片。
所以当随机值加入后，需要做一次OPTIMIZE TABLE来重新建表并优化页的填充
覆盖索引
如果索引的叶子节点就包含所有要查询的数据，就称改索引为"覆盖索引"。例如对表中某两个字段(A,B)做了联合索引，则如果一个Sql语句是查询A,B两个字段，那就可以用到覆盖索引。
覆盖索引的好处:
- 索引条目远小于数据行大小，用覆盖索引会极大减小数据访问量。
- 索引是顺序存储的，查询的IO会比从磁盘读小很多
- MyISAM这种数据内存中只缓存索引，如果调用数据需要系统调用，会有很大的损耗，直接查索引可以减小很多开销。
- InnoDB是聚簇索引，覆盖索引可以避免对主键索引的二次查询。
覆盖索引必须要存索引列的值，这个在MySQL只能用B-Tree,哈希全文空间都不行。
在使用覆盖索引时，explain时会看到extra有"Using index"
如果想查一个表的所有数据，但是又想用到覆盖索引，可以用延迟关联的方法
innodb所有二级索引都包含主键，所以本来用到覆盖索引的再增加主键值，依然可以用到覆盖索引。
使用索引做排序
在rental表添加一个包含三个列的索引(rental_date,inventory_id,customer_id)
如下语句可以用到索引
select * from rental where rental_date='2019-01-01' order by inventory_id,customer_id
下面这个也可以，满足了最左前缀的要求
select * from rental where rental_date='2019-01-01' order by inventory_id desc
下面这个也可以，因为orderBy使用的也是最左前缀
select * from rental where rental_date>'2019-01-01' order by rental_date,inventory_id desc
下面这个不能用，因为orderBy的排序方向不同，索引列都是正向排序的
select * from rental where rental_date>'2019-01-01' order by inventory_id desc,customer_id ASC
这个也不行，用到了一个非索引的列
select * from rental where rental_date>'2019-01-01' order by inventory_id ,staff_id
这个也不行，无法组成最左前缀
select * from rental where rental_date>'2019-01-01' order by customer_id
这个也不行，第一列是范围查询
select * from rental where rental_date>'2019-01-01' order by inventory_id desc,customer_id
这个也不行，也是一种范围查询
select * from rental where rental_date='2019-01-01' and inventory_id in (1,2) order by inventory_id desc,customer_id
压缩索引
MyIsam用前缀压缩减小索引大小，从而让更多索引放入内存
冗余和重复索引
Mysql可以对相同列创建多个索引，主键、唯一键也是通过索引实现的。
例如(A,B)和A这种索引就是冗余索引，因为对于(A,B)只查A也走索引
另外一种情况是(A,ID)也是冗余的，因为InnoDB主键列在二级索引中。
索引和锁
InnoDB只有在访问行的时候会对其加锁，但是这个只有在InnoDB在存储引擎层能过滤掉所有不需要的行时才有效。在InnoDB检索到数据行返回给服务层，MySQL服务器才能应用Where子句。这时候很多行已经被锁住，直到服务器过滤掉行之后才释放。
set autocommit=0;
begin;
select actor_id from actor where actor_id<5 and actor_id <>1 for update
只返回3行记录，但是实际上会锁住1-4这四行。通过explain可以看出Extra有"UsingWhere"，说明MysSQL是InnoDB将行返回再应用where条件过滤。
set autocommit=0;
begin;
select actor_id from actor where actor_id=1 for update
这个程序会挂起，直到第一个事务释放了锁。
如果说查询根本没用到索引，情况会更糟糕，Innodb会全表扫描并锁住所有的行，这个在生产环境是很危险的。所以写for update语句一定要看看有没有用到索引。
一个很少人知道的细节：InnoDB在二级索引上使用读锁，在访问主键索引需要排他锁，这消除了使用覆盖索引的可能性，并且使得select for update 比 lock in share mode 慢很多
总结
Mysql大多数情况下都会使用B-Tree索引，其他索引都只是适用于特殊目的。
选择索引和编写索引的查询时，有以下三条原则:
- 单行访问是很慢的，如果访问数据页的某一块只为获得某一行，那就浪费了很多IO的工作。
- 顺序访问数据很快，1不需要多次磁盘寻道，所以比随机IO快，尤其机械硬盘2其次是无需额外的排序操作。
- 索引覆盖查询非常快，避免了单行访问，减少了IO的次数。
祝大家编码愉快，工作愉快，欢迎关注我的公众号，一起分享交流
