索引是在存储引擎层实现的，下面主要说说 InnoDB 引擎的索引。

索引模型

在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表，每一个索引对应一个 B+ 树。

为了让一个查询尽量少的读磁盘，就得让查询过程访问尽量少的数据块，所以索引采用了 n 叉树，n 取决于数据块的大小。

以 InnoDB 一个整型字段索引为例，n 差不多是 1200，当树高是 4 的时候，就可以存 1200 的 3 次方个值，已经是 17 亿了。考虑到树根的数据块总是在内存中，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘，树的第二层也有很大概率在内存中，那访问磁盘的平均次数就更少了。

所以 B+ 树能够很好的配合磁盘的读写特性，减少单次查询的磁盘访问次数。

乱入：B+ 树和 B 树的区别

B+ 树中的节点不存储数据，只是索引，而B树中的节点存储数据
B 树中的叶子结点不需要链表来串联

假设有个表 T，主键为 id，字段 k 上有索引，建表语句如下：

create table T(
  id int(11) not null primary key,
  k int(11) not null,
  name varchar(16),
  index (k)
) engine=InnoDB;

表中 R1～R5 的 (id,k) 值分别为 (100,1)、(200,2)、(300,3)、(400,4)、(500,5)，两棵树的图如下：

InnoDB 索引组织结构.png

如图，根据叶子节点的内容，索引类型分为主键索引和非主键索引。
主键索引也叫聚簇索引，它的叶子节点的内容是整行数据。
非主键索引也叫二级索引，它的叶子节点的内容是主键的值。
索引上的一个叶子节点就是一页，一页里存有多行数据。

基于主键索引和普通索引的查询有什么区别？

如果语句是 select * from T where id = 1，即主键查询方式，只需要搜索 id 这棵树。
如果语句是 select * from T where k = 1，即普通索引查询方式，得先搜索 k 树，得到 id 值为 500，再去 id 树搜索一次，这个过程称为回表。

所以基于非主键索引的查询需要多扫描一棵索引树（当然覆盖索引除外）。

索引维护

B+树为了维护索引的有序性，在插入新值的时候需要做必要的维护。

已上图 id 索引树为例，如果插入新行的 id 值为 700，只需在 R5 后面插入新纪录。如果插入新行 id 值为 400，需要逻辑上挪动后面的数据，空出位置。

更糟糕的是，如果如果 R5 所在的数据页已满，根据 B+ 树的算法，需要申请一个新的数据页，然后挪动部分数据过去，这个过程叫页分裂，这种情况下性能当然会受到影响。
除了性能外，页分裂操作还影响了数据页的利用率，原本在一页的数据，现在分到两个页中，整体空间利用率大概降低 50%。
当相邻的两个页由于删除数据，利用率很低之后，会将数据页合并，这个过程叫页合并。页分裂和页合并都会影响性能。

自增主键

你可能在建表规范里见过这样的描述：要求建表语句一定要有自增主键。那哪些情况应该使用自增主键，哪些情况可以不用呢？

自增主键是指自增列上定义的主键，插入新纪录时，可以不指定 id 的值，系统会获取当前最大 id 值加一作为下一条记录的 id 值。

所以自增主键的插入模式，就是递增插入，每次插入新纪录，都是追加操作，不涉及挪动其他记录，也不会出发页分裂。如果用业务逻辑的字段做主键，往往不容易保证有序插入，这样写数据的成本相对较高。

除了性能外，还可以从存储空间的角度考虑。主键长度越小，普通索引的叶子结点就越小，普通索引占用的空间就越小。所以从性能和存储空间方面考虑，自增主键往往是更合理的选择。

那有没有适合直接用业务字段做主键的场景呢？下面的场景就是：

只有一个索引
该索引必须是唯一索引

由于没有其他索引，所以不必考虑普通索引叶子结点大小问题，直接作为主键，也避免每次查询都要搜索两棵树。

覆盖索引

普通索引已经覆盖了所有查询字段和查询条件字段。这样可以避免回表，减少树搜索次数。

最左前缀原则

联合索引的最左 n 个字段、或字符串索引最左 m 个字符，只要满足最左前缀，就可以利用索引加速检索。

建立联合索引的时候，如何安排索引内的字段顺序？
第一原则是，如果通过调整顺序，可以少维护一个索引，那这个顺序就是需要优先考虑的。
当索引不能减少时，就要从存储空间角度考虑。

索引下推

如果用到了联合索引，在满足最左前缀原则的时候，剩下右边那些用不到的索引字段怎么办呢？
以下面的查询语句为例：

select * from users where name like '张%' and age = 10;

假设有个 (name, age) 的联合索引，在搜索索引树的时候，只能用 ‘张’ 找到第一个满足条件的记录，然后再判断其他条件是否满足。

在 MySQL 5.6 版本之前，并不会看 age 的值，只能一条一条的回表，去主键索引树找到对应的数据行，判断 age 是不是 10。5.6 版本引入了索引下推优化（index condition pushdown），可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

覆盖索引、最左前缀、索引下推，从这些概念中可以看出，在满足语句要需求的情况下，尽量少的访问资源，是数据库设计的重要原则之一。

MySQL 索引