MySQL索引
索引的常见模型？
- 哈希表：只适合等值查询
- 有序数组：查询最快，但更新数据成本太高
- 搜索树
InnoDB的索引为什么选择B+树？
索引需要保存到磁盘上，假设我们使用平衡二叉树来存储，一个100万个节点的二叉树高20，一次查询需要访问20个数据块，机械硬盘随机读取一个数据块大约需要10ms时间，因此单独访问一个行大约需要200ms时间。
为了让一个查询尽量减少读磁盘，就必须让查询过程访问尽量少的数据块，B+树可以很好的配合磁盘的读写特性，减少单次查询访问磁盘的次数。
B+树的叶子结点存储的是？
存储的是页，一个页里面有多个行。当我们通过索引定位页时，然后通过内部的有序数组再借助二分法去定位行。
InnoDB索引模型？
InnoDB中，表都是根据主键顺序以索引的形式存放，这种存储方式称为索引组织表。
InnoDB使用了B+数索引模型，所以数据都是存储在B+树中。
每一个索引在InnoDB中都对应一棵B+树。
create table t(
id int primary key,
name varchar(16),
k int not null,
index (k)
) engine = InnoDB;
insert into t(id, name, k) values
(1, 'Java', 100),
(2, 'Python', 200),
(3, 'Go', 300),
(5, 'MySQL', 500),
(6, 'Spark', 600)
上面我们添加了5行数据，按照ID大小我们可以记为R1~R5。上述语句中有两棵索引数，一棵是主键索引，另一棵为非主键索引。
主键索引和非主键索引的区别？
- 主键索引又称聚簇索引，主键索引的叶子节点存储的是整行数据
- 非主键索引又称二级索引，非主键索引的叶子结点存储的是主键的值
假设我们有以下两个SQL语句：
-- SQL1
select * from t where id = 5;
-- SQL2
select * from t where k = 500;
SQL1只需要搜索主键索引这棵B+树即可获得结果，但是SQL2需要先通过k索引树查到主键值，然后再去主键索引树查找最终的结果。
基于非主键索引的查询可能需要多扫描一棵索引树，因此我们在查询的时候尽量使用主键查询。
索引维护
B+树为了维护索引有序性，在插入新值时必须做必要的维护。当我们插入id为7的行记录时，只需要在R5后面新增一个记录。
但是如果插入id为4的行记录，此时就需要挪动R4及R4后面的数据，空出位置。此时如果R5所在的数据页已经满了，将会更加糟糕，因为此时需要申请一个新的数据页，然后挪动一部分数据过去（页分裂）。
页分裂除了影响性能以外，还会降低数据页的利用率，原本放在一个数据页的数据现在分到两个数据页，整体利用率下降50%。
当然相邻的两个页中间也会因为有些数据被删除，利用率过低以后会进行页合并。
覆盖索引
select id from t where k = 500;
上述语句中我们只需要查询id的值，id的值已经在k索引树上，因此可以直接提供查询结果，所以不需要回表操作。该索引k覆盖了我们的查询需求，因此称之为覆盖索引。
最左前缀原则
B+树索引结构，可以利用索引的最左前缀来定位记录。索引项是按照索引定义里面出现的字段顺序进行排序。
最左前缀可以是联合索引的最左的N个字段，也可以是字符串索引的最左M个字符。
索引下推
索引遍历过程中，会对索引的中包含的字段先进性判断，直接过滤掉不满足条件的记录，减少回表次数。
索引思考
-- 系统中的表如下
CREATE TABLE `t` (
`a` int(11) NOT NULL,
`b` int(11) NOT NULL,
`c` int(11) NOT NULL,
`d` int(11) NOT NULL,
PRIMARY KEY (`a`,`b`),
KEY `c` (`c`),
KEY `ca` (`c`,`a`),
KEY `cb` (`c`,`b`)
) ENGINE=InnoDB;
-- 业务系统中如下的查询语句
select * from t where c=N order by a limit 1;
select * from t where c=N order by b limit 1;
ca和cb这两个索引有必要建立么？
- 如果c列的区分度很高，ca和cb其实都可以不用建立，因为通过索引c查出来的数据量会很少，order by进行排序还是很快的，此时ca和cb都不想要建立
- 如果c列的区分度很低，联合普通索引还是有必要要建立的，因为通过索引查出来的数据量会很大，order by将会很慢，并且很有可能需要借助磁盘临时表进行排序。如果没有cb索引，limi t 1仅仅表示返回给客户端1条数据，起不到限制扫描行数的作用，所以需要加cb索引；但是ca的索引由于满足最左前缀原则，所以不需要加，且c列是固定值，a列又有序，limit 1会只精准扫描一条数据。
limit的操作是在Server层进行完成，引擎每找到一条数据会返回给Server层，Server层进行数据的过滤，过滤完成以后会判断一下够不够limit的数，如果够了就结束循环，否则继续读取下一行。