InnoDB存储引擎B+树索引简述

索引是一种数据结构，旨在帮助数据库更高效的获取数据。B+树索引是B+树在数据库中的实现，可以划分为聚集索引和辅助索引，其在数据库中有一个特点是高扇出性，因此B+树的高度一般在2~4层，即查找某一个键值最多需要2至4次IO。

1. 聚集索引

聚集索引是按照每个表的主键构建的一颗B+树，所以其对于主键的排序查找和范围查找的速度非常快。聚集索引的叶子节点为数据页，数据页中包含着多条完整的行记录数据，每个数据页都通过一个双向链表进行链接。叶子节点存放的是完整的每行记录，非叶子节点存放的是键值及指向数据页的偏移量，如下图所示。

• 聚集索引B+树的存储记录数计算
  InnoDB存储引擎最小的存储单位为页，默认大小为16K（16384）。B+树索引的叶子节点存储的是完整的行记录，假设一条行记录的大小为1KB，则一个叶子节点（数据页）可以存储16条记录。非叶子节点存储的是主键值及指向叶子节点的指针，假设主键值为bigint类型，长度为8字节，InnoDB中指针的大小为6字节，这样一个非叶子节点可以存储16384/14=1170个单位。
  所以一个高度为2的B+树索引，能存放117016=18720条记录
  高度为3的B+树索引，能存放11701170*16=21902400条记录

2. 辅助索引

辅助索引与聚集索引不同，其叶子节点不包含行记录的所有数据，只包含了键值和书签，该书签为相应行数据的聚集索引键。因此，当通过辅助索引来查找数据时，InnoDB存储引擎会遍历辅助索引，找到对应的叶指针，从而获得指向主键索引的主键，再通过主键索引来获取一个完整的行记录。

3.B+树索引的使用

• 选择建立B+树索引
  当访问表中很少一部分数据的时候，即当某个字段的取值很广，几乎没有重复，选择性高的时候，使用B+树索引才有意义。

• 联合索引
  联合索引是指对表上的多个列进行索引。假设一个表table有a，b两列，对列a建立索引index1，对列a，b建立联合索引index2。

  • 当使用语句select * from table where a = xxx既可以使用index1，也可以使用index2，但是查询优化器最终会选择index1，因为其叶子节点只包含单个键值，所以一个页存放的的记录更多。
  • 当使用语句select * from table where a = xxx order by b desc limit 10时，则会选择index2，因为联合索引中已经对b进行排序了，无需再进行一次额外的排序操作

• 覆盖索引操作
  覆盖索引是指不需要通过查询聚集索引中，而是从辅助索引就可以得到查询的记录。如使用语句select count(*) from table进行查询时，就会进行覆盖索引操作。由于辅助索引不包含整行记录的所有信息，大小远小于聚集索引，所以可以减少大量的IO操作。