一句话简单的来说，索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。对于数据库的表而言，索引其实就是它的目录。
索引的常见模型
索引的出现是为了提高查询效率，但实现索引的方式却有很多种，所以这里也就引入了索引模型的概念。可以用于提高读写效率的数据结构有很多，这里介绍三种常见、比较简单的数据结构，他们是哈希表、有序数组、和搜索树。
从使用的角度，简单说下三种索引的区别。
哈希表是一种以key-value存储的数据结构。哈希的思路很简单，把value存放在数组里，用一个哈希函数把key换算成一个确定的位置。然后把value存放在数组的这个位置。
需要注意的是，hash的key并不是递增的，这样的好处是增加新的数据时速度会很快，只需要往后追加，缺点是，因为不是有序的，所以哈希索引做区间查询的速度是很慢的。
所以哈希这种结构只适用于只有等值查询的这种场景。
而有序数组在范围查询和等值查询的场景中性能都非常优秀。
如果仅仅看查询效率，有序数组就是最好的数据结构了，但是需要更新数据的时候就麻烦了，你往中间插一个记录就必须的挪动后面所有的记录，成本太高。
所以，有序数组只适用于静态存储引擎，比如你要保存的是2017年所有人口的信息。
二叉搜索树是课本里经典的数据结构了，结构不在赘述。
树可以有二叉，也可以有多叉，二叉树是搜索效率最高的，但实际上大多存储引擎并不使用二叉树，其原因是索引不仅存在内存中，还要写到磁盘上。
你可以想象一下，一颗100万节点的平衡二叉树，树高20，一次查询可能需要访问20个数据块。在机械硬盘的时代，从磁盘随机访问一个数据块大概需要10ms的寻址时间，使用二叉树存储，单独访问一个行可能需要20*10ms的时间。
为了让一个查询尽量的少读磁盘，就必须让查询查询过程访问尽量少的数据块。那么我们就不应该使用二叉树，而是使用“N叉树”，这个N取决于数据块的大小。
InnoDB的索引模型
在InnoDB中，表都是根据主键顺序以索引方式存放的，这种存储的方式表被称为索引组织表。InnoDB使用了B+树存储模型，所以索引都是存储在B+树中的。
每一个索引在DB里面对应一颗B+树。
假设我们有一个主键为ID的表，表中有字段K，并且在K上有索引。
这个表的建表语句是
mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;
从图中不难看出，根据叶子节点的内容，索引类型分为主键索引和非主键索引。
主键索引的叶子节点存的是整行数据。在InnoDB里，主键索引也被称为聚簇索引（clustered index）。
非主键索引叶子节点内容是主键的值，在InnoDB里非主键索性也被称为二级索引。
基于上述结构，我们来讨论一个问题:基于主键索引和非主键索引的查询有什么区别
- 如果语句是
select * from T WHERE ID=500;即主键查询方式，则只需要搜索ID这棵B+树。 - 如果查询语句是
select * from T where k=5;即普通索引查询方式，则需要先搜索K索引树，得到ID的值为500，再到ID索引树搜索一次。这个过程称为回表。
也就是说基于非主键的索引要多扫描一颗索引树。因此，我们在应用中应该尽量使用主键索引。
索引维护
以上面这个图为例，如果新插入的行ID为700，则只需要在R5的后面插入一条新记录;如果新插入的值ID为400，则相对麻烦了，需要逻辑上挪动后面的数据，空出位置。
更糟糕的情况是，如果R5所在的数据页已经满了，这时候就需要申请一个新的数据页，挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能会受到影响。
当然有分裂就会有合并，当相邻两个页由于删除了数据利用率很低后，会将数据页做合并。
基于上面的维护过程，我们来讨论一个问题:
你可能在一些建表规范里见过一些类似描述，要求建表语句里一定要有自增主键。当然事无绝对，我们来分析一下哪些场景下应该使用自增主键，而哪些场景下不应该。
- 自增主键的插入模式，符合了我们前面提到的递增插入场景。不会触发页分裂。而业务逻辑字段作为主键，往往不容易保证由于插入，这样写数据的成本相对较高。
- 除了考虑性能外，我们还可以从存储空间的角度来看。假设你的表中确实有一个唯一字段，比如字符串类型的身份证号，那应该用身份证号做主键，还是用自增主键呢？
由于每个非主键索引叶子节点上都是主键索引的值。如果用身份证号做主键，那么每个二级索引的叶子节点占用约20个字节，而如果用整形做主键，则只需要4个字节。
显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。
所以从性能和存储空间方面考量，自增主键往往是更合理的选择。
有没有什么场景适合用业务字段直接做主键的呢？ 还是有的。比如有些业务场景需求是这样的:
- 只有一个索引;
- 该索引必须是唯一索引。
你也一定看出来了，这就是典型的kv场景。由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小问题。
延伸阅读
了解change buffer作用
感谢以下文章作者:
https://blog.csdn.net/shenjian58/article/details/93691224
https://www.lizenghai.com/archives/43575.html
