InnoDB存储引擎索引之 B+树索引

目前InnoDB 存储引擎的使用广泛，这里深入解析索引，通过了解索引内部原理来指导我们使用索引。B+树索引最常见也是 DB 中使用最频繁的一种，暂不讨论 InnoDB 的全文索引和哈希索引。不作特殊说明InnoDB指InnoDB存储引擎。

注意B+树索引并不能找到给定键值的指定行，而是指向行所在页，然后通过 DB 把页读入内存后，在从内存中查到行数据。

DB 中B+树具有高扇出性（需要了解B+树用到的数据结构和算法即：二分查找法，二叉查找树和平衡二叉树等），所以 DB 中B+树高度一般在2~4层，即查找一行数据最多需要2~4次IO，按机械盘100次/s IO的性能，查询一次只需0.02~0.04s（SSD 就更好了）

B+树可以分为聚集索引（clustered index）和二级索引（secondary index，又称辅助索引）。

聚集索引

InnoDB 表是索引组织表，即表中数据按照主键顺序存放，属于聚集索引，按照每张表的主键构造一棵B+树，叶子节点为数据页，数据页通过双向链表进行链接（聚集索引的存储并不是物理上连续的，而是逻辑上连续）。数据页只能按照一棵B+树排序，因此每张表只能有一个聚集索引（查询优化器当前倾向采用聚集索引）。

二级索引

通过上面介绍可知，一个表中的所有索引除了聚集索引，其他的都是二级索引（secondary index），其叶子节点并不包含行记录的全部数据，叶子结点除了包含键值以外，每个叶子结点中的索引行还包含了一个书签，该书签用来告诉存储引擎可以在哪找到相应的数据行，由于innodb引擎表是索引组织表，因此innodb存储引擎的辅助索引的书签就是相应行数据的聚集索引键。

我们现在了解了InnoDB 存储引擎中B+树索引原理包括两种索引，以及索引对应存储的内容，接下来我们聊一下索引的使用。

Cardinality值

并不是在所有的查询条件中出现的列都需要添加索引。什么是有添加呢，根据经验，在访问表中很少一部分数据时使用B+树索引才有意义。比如用户数据中，对于性别，地区，类型字段，即低选择性，他们取值范围小。如：

SELECT * FROM user WHERE sex =‘M’

按照性别查询，只有 M，F。假设男女比例1：1，上述 SQL 语句将覆盖50%的数据，这时添加B+树索引就完全没必要了。同理可证，相反某字段选择范围广，几乎没有重复，即高选择性，使用B+树索引最合适，例如根据用户名查询，应用中基本上用户名不允许重复的。

界定是否具有高选择性的？这个时候Cardinality值来了，可以通过SHOW INDEX 结果中的列 Cardinality 观察，如：

SHOW INDEX FROM user

此值表示索引中不重复记录数量的预估值（不是准确值），Cardinality/n_rows_in_talbe 应尽可能的接近1.如果非常小，那么用户需要考虑是否有必要创建这个索引.

联合索引

联合索引是对表中的多列进行索引。创建方法和单个索引一样，不同之处在于使用多个索引列，如创建一张表 order.

CREATE TABLE order(
  userid INT UNSIGNED NOT NULL,
  buy_date DATE,
  KEY idx_userid (userid),
  KEY idx_userid2 (userid, buy_date)
)ENGINE=INNODB;

上面可以看出，索引 idx_userid2为联合索引，联合的列为（userid,buy_date），那么什么情况下会使用到这个索引呢：

SELECT * FROM order where userid=1 ORDER BY buy_date desc LIMIT 3

以上优化器会使用idx_userid2 而非 idx_userid，因为在idx_userid2这个联合索引中 buy_date 已经排好序了。联合索引是“最左前缀”的，建立了联合索引相当于建立了多个索引，如联合索引(a,b,c)，相当于是建立了 (a)、(a,b)、(a, b, c)三个索引，

SELECT * FROM table WHERE a=1;

SELECT * FROM table WHERE a=1 AND b=2;

SELECT * FROM table WHERE a=1 AND b=2AND c=3;

以上 sql 均可受益于联合索引(a,b,c)。

覆盖索引

covering index 或称索引覆盖，即从辅助索引中就可以得到查询的记录，从而不需要再查询聚集索引中的记录。前面讨论了辅助索引不包含整行记录所有信息，大小将远小于聚集索引，因此可减少大量 IO 操作。

SELECT COUNT(*) FROM order;

这里有有个误区，很多同学以为 InnoDB 会选择查询聚集索引来进行统计。其实不然，order 表中还有idx_userid2这个辅助索引，二辅助索引远小于聚集索引，所以优化器，会选择辅助索引可减少 IO 操作。

扇入和扇出的概念

这里通过在软件设计中的概念来解释较易理解，扇入和扇出的指应用程序模块之间的层次调用情况。

按照结构化设计方法，一个应用程序是由多个功能相对独立的模块所组成。

扇入：是指直接调用该模块的上级模块的个数。扇入大表示模块的复用程度高。

扇出：是指该模块直接调用的下级模块的个数。扇出大表示模块的复杂度高，需要控制和协调过多的下级模块；但扇出过小（例如总是1）也不好。扇出过大一般是因为缺乏中间层次，应该适当增加中间层次的模块。扇出太小时可以把下级模块进一步分解成若干个子功能模块，或者合并到它的上级模块中去。

参考书目：

MySQL技术内幕：InnoDB存储引擎（第2版）机械工业出版社