innodb B+树
  1. Q:为什么要有索引?
    1. 当没有索引的时候如何查找数据?
  2. Q:B+树的索引是怎么构建起来的?有什么依据吗?
    1. B+树长什么样?
    2. B+树是如何构建起来的?
  3. Q:B+树有什么特点?
    1. 从构建过程中总结出来的特点:
    2. B+树本身的特点:
  4. Q:除聚簇索引外,还有别的索引吗?
    1. 二级索引
    2. 联合索引
  5. Q:回表的代价
    1. 什么情况下会回表?
    2. 回表的影响
    3. 如何避免回表?
  6. Q:如何使用B+树呢
    1. 索引的代价
    2. 索引的使用
  7. Q:如何挑选索引

Q:为什么要有索引?

当没有索引的时候如何查找数据?

如果查询条件是主键的话,我们可以遍历页目录,使用二分法定位到数据,但如果我们的查询条件不是主键时,那么我们的页目录就用不上了,我们只能遍历所有的页,当数据量十分庞大的时候,查询效率十分低下。

Q:B+树的索引是怎么构建起来的?有什么依据吗?

B+树长什么样?


最后一层存放用户记录,称为叶子节点
除最后一层外的节点用于存放目录项,均称为非叶子节点
通常一颗B+树的层高不会超过4,原因见B+树的构建。

B+树是如何构建起来的?

首先,我们每一个数据页中都会记录该数据页中用户记录最大主键值和最小主键值,如下:

基于数据页中的最大记录和最小记录,我们可以针对数据页形成一个目录:
上边的目录项就是数据页的目录,目录项中记录了对应数据页的最小值,而被目录项组织起来的数据页的主键值必须是依次递增了,也就是说目录项2中所有记录的主键值肯定是要大于目录项1中所有记录的主键值的。
之后,为了使数据页的目录更灵活,MySQL的设计者将这些目录信息存储到了“页”中,存储这些目录信息的页也被称为“索引页”,效果如下:

索引页中的记录有一个特点,就是它们头信息中的record_type为1,代表它们是目录项记录,而我们的普通记录对应的record_type是0。
当我们的数据页特别多的时候,我们需要用来记录页的目录项页就特别多了,那目录页多起来了后,我们为了提高检索效率,还得对目录项页整理目录,如下图:
那么到这里,我们的“树”已经呼之欲出了,这就是“B+”树的形成过程。
这里我们做一个简单计算,来说明为什么B+树不可能超过4层:
假设目录项页中可以记录的记录条数为1000,一个数据页中能记录的用户记录为100条,那4层B+树总共可以记录的信息有:100010001000*100=1000亿条。我们正常一张表是不可能记录这么多数据的。

Q:B+树有什么特点?

从构建过程中总结出来的特点:

  1. 定位一条数据,最多只需要关注4个页,分别是三个目录页,一个数据页
  2. 无论是数据页还是索引页,页和页之间在物理上都不是连续的,而是通过偏移量形成了一个双向链表

B+树本身的特点:

上边描述的B+树我们称之为聚簇索引,因为叶子节点上存储了完整的用户记录,索引即记录。

Q:除聚簇索引外,还有别的索引吗?

二级索引

我们上边描述的索引是基于主键生成的聚簇索引,我们在使用主键检索数据时,该索引效率很高,但是当我们使用非主键进行查找时,该索引就无法使用了,那么为了提高非主键查询时的查询效率,我们可以针对非主键字段建立索引,此类索引称为“二级索引”。
二级索引的特点:

  1. 叶子节点不存储记录所有列的信息,只存储索引对应列的值和主键值
  2. 当需要获取其他字段值时,需要拿着主键回表查询

联合索引

针对多个列建立索引,假如我们对c1和c2列建立联合索引,我们会先根据c1进行排序,当c1值相同时,我们再对c2进行排序。效果图如下:

Q:回表的代价

什么情况下会回表?

查询条件命中了二级索引,但是目标字段却不在二级索引中,此时就需要根据二级索引中记录的主键值回到聚簇索引中查询对应的记录值

回表的影响

回表是随机I/O,通常顺序I/O的性能是要由于随机I/O的,当我们回表次数过多的时候,innodb优化器会选择进行全表扫描

如何避免回表?

  1. 尽可能地限制查询到的数据
  2. 覆盖索引:我们查询的目标列最好是索引中的列

Q:如何使用B+树呢

索引的代价

时间上的代价:每一次增删改的时候,我们都要维护对应的B+树
空间上的代价:每建立一个索引,都会产生一颗B+树

索引的使用

全值匹配:查询条件和列值完全匹配
最左匹配:假设我们针对列a,b,c建立了联合索引idx_a_b_c:

  1. 那么当我们使用条件a,b,c进行查询的时候会先匹配a相等的记录,然后再匹配b,最后是c;
  2. 如果我们的查询条件是b,c,那就无法使用到该联合索引了;
  3. 如果查询条件是a,c,那么只可以使用到a列的索引

匹配列前缀:B+树中对于字符串进行了排序,所以我们使用部分前缀也可以快速地定位到数据,例如

1
select column A from table where A like "As%"

但是如果只给出中间或者末尾的某个字符,该索引就无法使用了,因为innodb并不会为某一列数据中间或末尾几个字符进行排序。
范围查询:当使用范围查询时,只有联合索引做左边的列能够使用到
精确匹配某一列并范围匹配另外一列:对于联合索引来说,如果可以精确匹配第一列,那么第二个条件可以范围匹配
用于排序:通常当我们的sql中包含order by的时候,我们的做法是将数据load到内存中,在内存中对数据进行排序,当我们where条件名字的数据过多时,甚至还可能要使用到磁盘空间来完成排序,那么一但和磁盘沾边,那我们的查询效率就会很低了。但是如果我们的ordey by中使用索引字段来进行排序的话,我们就可以直接从索引里提取数据,再进行一次回表就可以的。
不可以使用索引进行排序的情况:

  1. ASC和DESC混用:因为我们的联合索引在创建的时候会根据A进行排序,A字段一样的记录再根据B字段进行排序,如果我们排序条件时A、B均升序,那么我们从索引最左边读10行就好,如果排序条件是A、B均降序,那么我们从索引最右边向左读10条就好,如果A增B减的话,我们需要先针对A增的情况挑选出10条数据,在根据B减的情况匹配出对应的十条,但是往往我们是无法精确匹配出10条B递减的数据的,于是我们又得重新在A增的情况下多拿出几条,这样会导致我们索引使用的效率特别低
  2. 多个用于排序的列不属于同一个索引
  3. 用于排序的列使用到了复杂表达式:当我们使用索引列进行排序时,必须保证该索引列是单独出现的,不能经过任何加工

用于分组:如果分组条件和我们索引字段一致的话,会提高分组sql语句的效率
覆盖索引:我们查询的目标列最好是索引中的列

Q:如何挑选索引

  1. 只为用于搜索、排序、分组的列创建索引
  2. 考虑列的区分度,越高越值得建立索引
  3. 索引列的类型尽可能地笑
  4. 索引字符串列的前缀