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操作。