本章是mysql技术内幕这本书的读书笔记。可以点击超链接查看所有的读书笔记。

1. B+树与索引

B+树就是指一个多路平衡树,只不过记录都存放在叶子节点,其他节点都是索引节点。

1.1 B+树插入

扇出的值是固定的。在数据库里面B+树索引的层数一般都比较低,位2-4层,这样经过2-4次IO就可以取到数据。

推荐看下书上p188-p199的例子,演示了B+树上插入操作的进行过程。B+树插入操作分情况主要依据叶子节点和索引节点是否插满了数据

对于插入操作注意以下知识点:

  1. 优先进行树的旋转避免插入时的页拆分。在某个叶子节点满,但是其兄弟节点没有满的情况下优先进行树的旋转(其实就是移动下叶子节点的数据)
  2. 如果索引节点和叶子节点都放满数据了,则需要拆分节点。
  3. 插入后必须保证叶子节点内记录必须仍然是有序的。

B+树进行插入有三种情况,见书本P188页

PS:B+树上如果进行太多无规则的插入,会造成过多的节点拆分,影响性能。

1.2 B+树删除

B+树的删除主要是根据叶子节点和索引节点是否达到填充因子来判断的。填充因子是个百分比,指节点内存放的数据占总容量的百分比。

删除的三种情况见P190页的表格

1.3 聚集索引(重要)

聚集索引用一个B+树实现,叶子节点是数据节点。关于MYSQL的聚集索引,以下几点需要引起注意;

  1. 聚集索引并不意味着一定按照物理地址连续存储数据。聚集索引意味着磁盘上记录的存储顺序与聚集索引索引列的逻辑排序顺序是一致的。对于聚集索引来说,索引列查找键顺序与物理顺序一致,对性能是有帮助的,磁盘上读取可以按顺序读取,不使用随机读取。
  2. 排序查找(order by)和范围查找速度很快。

PS: 对于离散查找的情况可以使用预读

1.4 辅助索引(重要)

辅助索引(也称为二级索引),B+树叶子节点顺序存储索引列的查找键。辅助索引的查找键顺序与物理上的存储顺序不一定一致。

在Innodb中,辅助索引的叶子节点保存了辅助索引索引列的查找键、聚集索引的查找键(在innodb中就是主键)。因此,辅助索引能根据聚集索引的查找键,再去真正从磁盘上查找到记录。也就是说,在innodb当中,辅助索引是作为一个二级索引存在的。innodb当中辅助索引的叶子节点通过书签(bookmark)来保存聚集索引的查找键。

1.5 索引组织表(Index organized table, IOT)

IOT可以省去主键索引的开销,因为数据就是按顺序存储的,可以当做聚簇索引使。换句话说,如果你只会通过一个表的主键来访问这个表,这个表就适合创建成索引组织表。

在InnoDB存储引擎中,所有的表都是索引组织表。也就是说都是在主键上建立了聚簇索引。索引组织表,可以节约聚簇索引的开销。

2. Mysql中B+树的管理

2.1 查看表的索引:

show index from tableName

关于每一列说明:
1.Table:表的名称。
2.Non_unique :如果索引不能包括重复词,则为0。如果可以,则为1。
3.Key_name :索引的名称。
4.Seq_in_index :索引中的列序列号,从1开始。
5.Column_name :列名称。
6.Collation :列以什么方式存储在索引中。在MySQL中,有值‘A’(升序)或NULL(无分类)。
7.Cardinality :索引中唯一值的数目的估计值。通过运行ANALYZE TABLE或myisamchk -a可以更新。基数根据被存储为整数的统计数据来计数,所以即使对于小型表,该值也没有必要是精确的。基数越大,当进行联合时,MySQL使用该索引的机会就越大。
8.Sub_part :如果列只是被部分地编入索引,则为被编入索引的字符的数目。如果整列被编入索引,则为NULL。
9.Packed :指示关键字如何被压缩。如果没有被压缩,则为NULL。
10.Null :如果列含有NULL,则含有YES。如果没有,则该列含有NO。
11.Index_type :用过的索引方法(BTREE, FULLTEXT, HASH, RTREE)。
12.Comment :多种评注。

2.2 Fast Index Creation

索引添加时可以不重建表,加个S锁即可。索引删除只要更新内部视图,将辅助索引空间标记为可用即可。

2.3 Cardinality值

该值表示表中不重复记录的预估值。 Cardinality除以行记录总数应该尽可能等于1才比较适合建索引。太多重复记录使用索引效率比较低。优化器也会判断这个值来决定是否使用索引。

3. B+树索引的使用

3.1 联合索引

联合索引保存的时一个组合值,例如(a,b,c)一起作为联合索引。联合索引按照联合索引中第一个值来排序。

以(a,b,c)这个联合索引为例,以下两个SQL可以直接使用联合索引:

/*以下SQL可以使用联合索引*/
 select ... from table where a=xxx order by b
 select ... from table where a=xxx and b=xxx order by c
 ```
 
 下面这个SQL例子无法直接使用联合索引,需要进行一次filesort排序(对b这一列排序)
 
```sql
select ... from table where a=xxx order by c

3.2 覆盖索引

如果一个查询,仅仅依靠辅助索引或者聚簇索引的查找键就可以返回查询结果。那么这个索引可以称之为覆盖索引。覆盖索引是对于某个查询来说的。一般来说可以通过建立联合查询来构造一个覆盖索引。

例如有张学生表。主键是学号id这一列,此外还有一列是姓名name。那么我可以建立一个联合索引(id,name)。那么针对select name where id=3这种姓名和ID相关的查询,该联合索引就是一个覆盖索引。

可见建立覆盖索引,避免了回表操作。回表操作会带来额外的IO开销。应该尽量避免。

3.3 回表(索引回表)

索引回表:简单的说就是当你使用的sql查询条件和select返回的列没有完全包含在索引列中时就会发生回表。也就是说利用现有的索引不能查找到所有的数据,那就不得不利用索引中保存的聚簇索引的索引列(在innodb当中,就指的是主键)去扫描原表中的数据。这样显然会引入了更多的IO,应该避免这种情况。

在innodb当中,书签查找,也就意味着回表了。

3.4 优化器选择不使用索引的情况

有时候发现优化器直接通过扫描聚集索引全表扫描来得到数据,没有使用辅助索引。

这里的重点是:

  1. 如果要求访问的数据量很小,则优化器还是会选择辅助索引,但是当访问的数据占整个表中数据的蛮大一部分时候(20%左右),优化器会选择通过聚集索引来查找数据。因为顺序读(因为聚集索引上的数据页都用链表串起来了)要远远快于离散读。

3.5 索引提示

可以通过INDEX HINT强制优化器使用哪个索引。一般以下情况会用:

  1. 有经验DBA发现MYSQL错误选择了索引导致SQL语句缓慢(这个概率很低。。)
  2. SQL语句可选择索引太多,选择执行计划耗时开销大于SQL语句本身时

4. 索引优化技术

4.1 Multi-Range Read(多范围读,缩写为MRR)

MRR技术是为了将随机访问转化为顺序访问,对IO密集型的SQL查询语句有非常大的性能提升。MRR专门来优化二级索引的范围扫描并且需要回表的情况。它的原理是,将多个需要回表的二级索引根据主键进行排序,然后一起回表,将原来的回表时进行的随机IO,转变成顺序IO。

MRR原理:查询辅助索引得到批量的KEY值,对其进行排序,然后批量按KEY查询。

优点:

  1. MRR显著减少了离散查询,利用顺序查询性能好。
  2. MRR由于顺序批量查询,相比离散查询减少了缓冲池中叶被替换的次数。
  3. MRR可以将范围查询拆分为键值对,在拆分过程中尽早过滤不符合查询的数据,减少IO开销。

使用MRR的例子:P224

PS: 不需要回表的情况,MRR则不会生效。

4.2 Index Condition Pushdown(索引条件下推,ICP)

ICP核心优化原理,就是在存储层,提前执行where条件的过滤,避免读取无用的记录,减少了IO开销。

优化器不使用ICP时,索引操作过程:根据索引列查找键从磁盘上取出记录,然后根据where条件做过滤。

优化器使用ICP之后的索引操作过程: 存储引擎会在从磁盘上读取记录之前,先对where过滤条件做判断,如果发现查找键不符合where条件,则不会从磁盘上读取记录。

例子见书P226

PS: %XXX 这样的LIKE语句是不会使用索引的。使用索引的一些建议见文章建立索引的一些优化建议的2.5节

建议ICP、MRR都开启,极大提升性能。

5. MYSQL 三大特性

有人说InnoDB有三大特性,我们再回顾下:

5.1 插入缓冲

插入缓冲: 当一个表有非聚集索引时,对于非聚集索引的叶子节点的插入不是物理有序的,这时候需要离散的访问物理上的数据页,性能就在这里降低了。插入缓存就是用来解决这个问题的。对于非聚集索引的插入和更新操作,不是每一次都直接插入索引页,而是先判断插入的非聚集索引页是否在缓存中,如果在就直接插入(避免了磁盘上数据页的离散访问),如果不在就放入到一个插入缓冲区中,之后再以一定的频率将插入缓存的数据和非聚集索引页字节点进行合并操作,合并成一个插入操作。本质即减少插入操作的次数来降低离散访问的次数,减少了开销。

简单来说:插入缓存合并了对辅助索引索引页的插入,通过减少随机IO的次数来降低随机写IO的开销。

5.2 两次写

两次写:主要应付partial write的问题。重做日志没法恢复一个损坏的mysql数据页。重做日志记录的是完整页的物理操作,例如偏移量800,写'a'记录。重做日志无法识别只写了部分的数据页。如果数据页本身损坏,重做日志是重做也是无效的。必须先恢复损坏的数据页。这个就依靠两次写来保障数据页可靠性。oracle没这样的问题是因为oracle有lgwr线程把1个数据页的变动也写入了redo log。也就是意味着oracle的redo log是能恢复损坏的页的。

5.3 自适应哈希索引

第三个就是我们现在要讨论的AHI。AHI采用哈希索引,自适应意味着MYSQL自己会判断何时会使用AHI。例如数据字典的查询、等值查询很多都会使用AHI。

6. 全文检索(使用倒排索引)

用MATCH()和AGAINST()语法支持全文搜索的查询。关于全文索引的使用参考书本吧。

倒排索引在搜索引擎里面也大量使用。主要思想就是一般根据ID查找记录,倒排索引根据属性来查找符合条件的ID的记录。InnoDB实现倒排索引利用了一些辅助表来存储word信息,还利用了一个基于红黑树实现的全文检索索引缓存来加速检索性能。