索引模型

哈希表模型：适用于只有等值查询的场景，不适用于范围查询。
有序数组模型：对于等只查询和范围查询效率都很好，但是更新数据成本太高。所以适用于静态历史数据存储。
搜索树模型：搜索树中二叉树的查询复杂度和更新复杂度都是O(logN)，是搜索效率最高的。但是由于二叉节点相当于多叉节点，会导致树的高度增加，在机械硬盘上树的高度增加，其查询时读取的数据块也会增多，磁盘读取次数多，会成为查询效率的瓶颈。所以为了减少查询时磁盘读取，减少数据块访问，就要使用N叉树，N取决于数据块的大小。InnoDB中整数字段的索引的N差不多是1200.
跳表模型
LSM树模型

索引的维护

页分裂

B+树的索引是有序的，如果向索引插入一个中间值，就需要将这个中间值后面的索引数据向后挪动，以空出位置。如果当前索引使用的数据页已经满了，这时候如果需要向后挪动，就要申请一个新的数据页，然后再挪动部分数据过去，这个过程就是页分裂。页分裂除了影响性能，还对数据页的利用率有影响。
有分裂就有合并，相邻的两个页由于删除了数据，页利用率很低后，还会进行合并。

关于自增主键和业务唯一字段做主键

从性能上看：用自增主键的好处是，由于主键是自增的，也就不会存在向已有主键索引的中间部分插入的情况，而只有追加插入的情况，这样就不会涉及到数据挪动，也不会触发叶子节点的页分裂。这一点比业务唯一字段做索引要好，业务字段往往只会保证唯一而不会保证有序，这样插入的成本相对较高。
从存储空间上看：业务字段做主键时，比如身份证号，那么二级索引的叶子节点存储的就是主键，也就是大约占用20个字节长度。而如果用长整型bigint做主键，也可以表示20位的长度，但是bigint只占用8个字节。显然主键的长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。
这样从性能和存储空间上看，往往是自增主键更为合理。
但也有个别场景适合使用业务字段做主键，比如要求：1）只有一个索引。2）索引必须是唯一索引。这其实就是典型的KV场景，这时按照‘尽量使用主键查询’的原则，直接将业务字段作为主键，可以避免回表查询。

重建索引
删除重建普通索引没有问题。删除或则重建主键索引，会导致将整个表重建。

“N叉树”的N值在MySQL中是可以被人工调整的么？

1， 通过改变key值来调整
N叉树中非叶子节点存放的是索引信息，索引包含Key和Point指针。Point指针固定为6个字节，假如Key为10个字节，那么单个索引就是16个字节。如果B+树中页大小为16K，那么一个页就可以存储1024个索引，此时N就等于1024。我们通过改变Key的大小，就可以改变N的值
2， 改变页的大小
页越大，一页存放的索引就越多，N就越大。
数据页调整后，如果数据页太小层数会太深，数据页太大，加载到内存的时间和单个数据页查询时间会提高，需要达到平衡才行

一条SQL执行几次树的搜索，扫描多少行

mysql> create table T (
ID int primary key,
k int NOT NULL DEFAULT 0,
s varchar(16) NOT NULL DEFAULT ‘’,
index k(k))
engine=InnoDB;

insert into T values(100,1, ‘aa’),(200,2,’bb’),(300,3,’cc’),(500,5,’ee’),(600,6,’ff’),(700,7,’gg’);

sekect * from T where k between 3 and 5;
1)在k索引树上找到k=3的记录，取得id=300；
2）再到id索引树查找id=300对应的row3
3）在k索引树取下一个值k=5，取得id=500；
4）再回到id索引树查到id=500对应的row4
5）在k索引树取下一个值k=6，不满足条件，循环结束。

过程中读了k索引树的3条记录，回表两次。

覆盖索引
覆盖索引可以减少回表，减少索引树的查询次数，因此可以显著的提升性能，也是SQL优化的常用手段。例如，一张市民表，是否有必要在身份证号和姓名上建立索引呢？答案是，如果经常用到身份证号查询姓名的查询，还是建立覆盖索引比较好，可以减少一次回表操作。当然维护索引也有成本，维护成本大小由DBA权衡。

索引下推
MySQL5.6以后，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。
select * from T where name like ‘张%’ and age=10 and ismale=1;