参考文献

  • <<MySQL是怎样运行的>> 小孩子4919

第六章 快速查询的秘籍-B+树索引

总结

InnoDB存储引擎的索引是一棵B+树,完整的用户记录都存储在B+树第0层的叶子节点;其他层次的节点都属于内节点,内节点中存储的是目录项记录.

InnoDB的索引分为两种:

  • 聚簇索引: 以主键值的大小作为页和记录的排序规则,在叶子节点处存储的记录包含了表中所有的列
  • 二级索引: 以索引列的大小作为页和记录的排序规则,在叶子节点处存储的记录内容是索引列+主键

InnoDB存储引擎的B+树根节点自创建之日起就不在移动(即根节点所在的页号不会改变).

  • 树的根始终在一个固定的位置,方便快速定位

在二级索引的B+树内节点中,目录项记录有索引列的值,主键值和页号组成.

一个数据页至少可以容纳2条记录.

MyISAM存储引擎的数据和索引分开存储,这种存储引擎的索引全部都是二级索引,在叶子节点处存储的是列+行号(对于定长记录格式的记录来说)

  • 每个索引都对应一棵B+树.B+树分为好多层,最下边一层是叶子节点,其余的是内节点.所有用户记录都存储在B+树的叶子节点,所有目录项记录都存储在内节点.
  • InnoDB存储引擎会自动为主键建立聚簇索引(如果没有显式指定主键或者没有声明不允许存储NULL的UNIQUE键,它会自动添加主键),聚簇索引的叶子节点包含完整的用户记录.
  • 我们可以为感兴趣的列建立二级索引,二级索引的叶子节点包含的用户记录由索引列和主键组成.如果想要通过二级索引索引查找完整的用户记录,需要执行回表操作,也就是通过二级索引找到主键值之后,再到聚簇索引中查找完整的用户记录.
  • B+树中每层节点都按照索引列的值从小到大的顺序排序组成了双向链表,而且每个页内的记录(无论是用户记录还是目录项记录)都按照索引列的值从小到大的顺序形成一个单向链表.如果是联合索引,则页面和记录先按照索引列中前面的列的值排序;如果该列的值相同,再按照索引列中后面的列的值排序.比如我们对列c2和c3建立了联合索引idex_c2_c3(c2,c3),那么该索引中的页面和记录就先按照c2列的值进行排序;如果c2列的值相同,再按照c3的值排序.
  • 通过索引查找记录时,是从B+树的根节点开始一层一层向下搜索,由于每个页面(无论是内节点页面还是叶子节点页面)中记录都划分成了若干个组,每个组中索引列值最大的记录在页内的偏移量会被当做槽一次存放在页目录中(当然,规定Supermum记录比任何用户记录都大),因此可以在页目录中通过二分法快速定位索引列等于某个值的记录.

第七章 B+树索引的使用

7.3.1 扫描区间和边界条件

针对获取到的每一条二级索引记录,如果没有开启索引条件下推特性,则必须先执行回表操作,在获取到完整的用户记录后再判断key_part3 = 'c'条件是否成立,如果开启了索引条件下推特性,可以立即判断二级索引记录是否符合key_part3 = 'c'条件.如果符合该条件,则再执行回表操作;如果不符合则不执行回表操作,直接跳到下一条二级索引记录.索引条件下推特性是在MySQL5.6中引入的,且默认是开启的.

7.3.2 索引用于排序

我们在编写查询语句时,经常需要使用ORDER BY子句对查询出来的记录按照某种规则进行排序.在一般情况下,我们只能把记录加载到内存中,然后再用一些排序算法在内存中对这些记录进行排序.有时查询的结果集可能太大以至于无法在内存中进行排序,此时就需要暂时借助磁盘的空间来存放中间结果,在排序操作完成后再把排好序的结果集返回客户端.

在MySQL中,这种在内存或者磁盘中进行排序的方式统称为文件排序 (fìlesort).但是,如果ORDER BY子句中使用了索引列,就有可能省去在内存或磁盘中排序的步骤.

使用联合索引进行排序时的注意事项

在使用联合索引时,需要注意一点:ORDER BY子句后面的列的顺序也必须按照索引列的顺序给出;如果给出ORDER BY key_part3,key_part2,key_part1的顺序,则无法使用B+树索引.之所以颠倒排序列顺序就不能使用索引,原因还是联合索引中页面和记录的排序规则是固定的,也就是先按照key_part1值排序;如果记录的key_part1值相同,再按照key_part2值排序;如果记录的key_part1和key_part2值都相同,再按照key_part3值排序.如果ORDER BY子句的内容是ORDER BY key_part3,key_part2,key_part1,那就要按照key_part3值排序;如果key_part3相同在按照key_part2值排序,如果记录的key_part3和key_part2都相同,再按照key_part1排序.这显然是冲突的.

同理,ORDER BY key_part1和ORDER BY key_part1,key_part2这些仅对联合索引的索引列中左边连续的列进行排序的形式,也是可以利用B+树索引的.另外,当联合索引的索引列左边连续的列为常量时,也可以使用联合索引对右边的列进行排序.

1
select * from single_table where key_part1 = 'a' and key_part2 = 'b' order by key_part3 limit 10;
不可以使用索引迸行排序的几种情况

  1. ASC,DESC混用

    1
    2
    -- index(key_part1,key_part2,key_part3)
    select * from single_table order by key_part1, key_part2 desc limit 10;

  2. 排序列包含非同一个索引的列

    1
    2
    3
    -- index(key_part1,key_part2,key_part3)
    -- index(key_part4)
    select * from single_table order by key_part1, key_part4 limit 10;

  3. 排序列是某个联合索引的索引列,但是这些排序列在联合索引中并不连续

    1
    2
    -- index(key_part1,key_part2,key_part3)
    select * from single_table order by key_part1, key_part3 limit 10;

  4. 用来形成扫描区间的索引列与排序列不同

    1
    2
    3
    -- index(key_part1,key_part2,key_part3)
    -- index(key1)
    select * from single_table where key1 = 'a' order by key_part1limit 10;

  5. 排序列不是以单独列名的形式出现在ORDER BY子句中

    1
    2
    -- index(key_part1,key_part2,key_part3)
    select * from single_table order by UPPER(key_part1) limit 10;