索引就像书的目录一样，索引的出现就是为了提高查询效率。
索引的常见模型
你现在维护着一个身份证信息和姓名的表，需要根据**「身份证号」**查找对应的名字
哈希表
哈希表
好处：新增或者等值查询很快
缺点：因为是无序的所以区间查询的速度很慢，不支持范围查询，并且大数据量容易有hash冲突。
适用场景：等值查询，一些nosql的数据库引擎，比如Memcached
有序数组
有序数组
优点：「有序数组在等值查询和范围查询场景中的性能就都非常优秀」。如果仅仅看查询效率，有序数组就是最好的数据结构了
缺点：但是，在需要更新数据的时候就麻烦了，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。
适用场景：「有序数组索引只适用于静态存储引擎」，比如你要保存的是2017年某个城市的所有人口信息，这类不会再修改的数据。
平衡二叉搜索树(AVL)
平衡二叉搜索树(AVL)
好处：搜索效率高
缺点：数据库存储不适用二叉树，数据过多会造成树过高。
「数据库不适用原因」：因为索引不止存在内存中，还要写在磁盘上，为了尽量少地读写磁盘，减少IO次数，所以尽管二叉树的效率很高，大多数数据库不会选择二叉树。
N叉树
N叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。
以InnoDB的一个整数字段索引为例，这个N差不多是1200。这棵树高是4的时候，就可以存1200的3次方个值，这已经17亿了。考虑到树根的数据块总是在内存中的，一个10亿行的表上一个整数字段的索引，查找一个值最多只需要访问3次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。
Innodb的索引模型
在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。
「每一个索引在InnoDB里面对应一棵B+树。」
假设，我们有一个主键列为ID的表，表中有字段k，并且在k上有索引。
这个表的建表语句是：
mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;表中R1~R5的(ID,k)值分别为(100,1)、(200,2)、(300,3)、(500,5)和(600,6)，两棵树的示例示意图如下。
B+树
「主键索引」的叶子节点存的是整行数据。在InnoDB里，主键索引也被称为「聚簇索引」（clustered index）。
「非主键索引」的叶子节点内容是主键的值。在InnoDB里，非主键索引也被称为「二级索引」（secondary index）。
「基于主键索引和普通索引的查询有什么区别？」
如果语句是select * from T where ID=500，即主键查询方式，则只需要搜索ID这棵B+树；
如果语句是select * from T where k=5，即普通索引查询方式，则需要先搜索k索引树，得到ID的值为500，再到ID索引树搜索一次。这个过程称为回表。
索引的维护
B+树为了维护索引有序性，在插入新值的时候需要做必要的维护。
如果插入新记录ID为400，还需要挪动后面的数据，如果R5所在的数据也满了，还需要申请新的数据页，然后挪动部分数据过去，这个过程称为页分裂。
「为什么需要自增主键？」
自增主键是指自增列上定义的主键，在建表语句中一般是这么定义的： NOT NULL PRIMARY KEY AUTO_INCREMENT。
从性能和存储空间方面考量，自增主键往往是更合理的选择。
性能：
自增主键的插入数据模式，正符合了**「递增插入」**的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。
而有业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高。
存储：
由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键，那么每个二级索引的叶子节点占用约20个字节，而如果用整型做主键，则只要4个字节，如果是长整型（bigint）则是8个字节。
「主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。」
「什么时候用业务字段作为主键？？」
只有一个索引。
该索引必须是唯一索引。
你一定看出来了，这就是典型的KV场景。
由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小的问题。
这时候我们就要优先考虑上一段提到的“尽量使用主键查询”原则，直接将这个索引设置为主键，「可以避免每次查询需要搜索两棵树」。
