5 算法和索引

5.1 InnoDB索引

几种常见索引

  1. B+树索引
  2. 全文索引
  3. hash索引（自适应hash索引）

5.2 数据结构与算法

5.2.1 二分查找

5.2.2 二叉查找树和平衡二叉树

B+树是有二叉查找树，再由平衡二叉树（AVL），B树演化而来的

平衡二叉树（AVL)树：首先符合二叉查找书的定义，其次必须满足任何节点的两个子树的高度最大差为1.

5.3 B+树

5.3.1 B+树的插入操作

B+树插入必须保证插入后叶子节点中的记录依然排序，同时需要考虑插入到B+树的三种情况：

mysql ---- innodb2 （索引） - 图1

不管怎么变化，B+树总是平衡的。但是为了保持平衡对于新插入的键值可能需要做大量的查分页操作。因为B+树结构主要用于磁盘，页的拆分意味着磁盘操作，所以应该在可能的情况下减少页的拆分操作。因此B+树也有类似于平衡二叉树的旋转操作。

旋转发生在Leaf page已满，但是其兄弟节点未满的情况下，这是B+树并不会基于拆分操作，而是将记录转移到页的兄弟节点上。

5.3.2 B+树的删除操作

B+树使用填充因子（fill factor）来控制树的删除变化，50%是填充因子可设置的最小值。

B+树的删除操作也有三种情况：

mysql ---- innodb2 （索引） - 图2

5.4 B+树索引

B+树在数据库中有一个特点是高扇出性，因此在数据库中，B+树的高度一般在24次IO。

数据库中的B+数索引可分为聚集索引（clustered index）和辅助索引（secondary index），但是不管是哪种索引，其内部都是B+树，即高度平衡的，叶子节点中存放着所有的数据。聚集索引与辅助索引不同的是，叶子节点存放的是否是一整行的信息。

5.4.1 聚集索引

InnoDB存储引擎表示索引组织表，即表中数据按照主键顺序存放

聚集索引（clustered index）就是按照每张表的主键构造一颗B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。

由于实际的数据页只能按照一颗B+树进行排序，因此每张表只能拥有一个聚集索引。

5.4.2 辅助索引

辅助索引（Secondary Index，也称非聚集索引），叶子节点并不包含记录全部数据。叶子节点中除了包含键值以外，每个叶子节点的索引行中还包含了一个书签（bookmark）。 该书签用来告诉InnoDB引擎哪里可以赵铎与索引相对应的行数据

InnoDB存储引擎的辅助索引的书签就是相应行数据的聚集索引。（即要通过辅助索引查找数据，先找到辅助索引的叶节点，在根据叶节点中的书签找到聚集索引的主键，然后再根据主键从聚集索引中找到叶节点中的行记录）

mysql ---- innodb2 （索引） - 图3

5.4.3 B+树索引的分裂

B+树索引页的分裂并不总是从页的中间记录开始

5.4.4 B+树索引的管理

  1. 索引管理
    索引的创建和删除两种方法：一种是ALTER TABLE，另一种是CREATE/DROP INDEX ```sql — alter alter table tbl_name add [index|key] [index_name];

alter table tbl_name drop primary key; —create create [unique] index index_name [index_type] on tbl_name(index_col_name);

drop index index_name on tbl_name;

  2. 1. 用户可以设置对整个列的数据进行索引，也可以只索引一个列的开头部分数据
  3. ```sql
  4. -- 索引前边100
  5. alter table t add key ind_b (b(100));
  7. -- 查看索引信息
  8. show index from tbl_name;

  1. 如;

    1. create table t (
    2. a varchar(1),
    3. b varchar(8000),
    4. c varchar(2),
    5. primary key a(a),
    6. key b(b(100)),
    7. key c(c),
    8.  key a_c(a,c)
    9. );

  2. 上表使用show index from t， 可以观察到表t有4个索引， 分别为a主键索引、c的辅助索引，b的前100字节的辅助索引，以及a、c的联合辅助索引。show index from t可以观察每列的含义： | Table | 表明 | | —- | —- | | Non_unique | 非唯一索引，0：表示唯一索引， 1表示非唯一索引 | | Key_name | 索引名称 | | Seq_in_index | 该列在索引中的位置，联合索引能够观察的区别 | | Column_name | 该列的名称 | | Collation | 列以什么方式存储在索引中。值可以为A或NULL，B+树的索引总是A，即排序的 | | Cardinality | 非常关键的值，表示索引中唯一值数目的估计值，该值应该尽可能的接近1，如果非常小，需要考虑删除该索引 | | Sub_part | 是否是该列部分索引 | | Packed | 关键值是否被压缩 | | Null | 是否索引的列允许NULL值 | | Index_type | 索引类型，InnoDB引擎总是BTree | | Comment | 注释 |

mysql ---- innodb2 （索引） - 图4

Cardinality值非常关键，优化器会根据这个值来判断是否使用这个索引。但是这个值不是实时更新的。如果需要更新的话使用命令ANALYZE TABLE命令。

  1. Fast Index Creation
    Mysql版本5.5之前，对于添加索引或删除操作，数据库的操作过程为：
    1. 首先创建一张新的临时表，表结构为通过命令ALTER TABLE新定义的结构
    2. 然后把原表中的数据导入到临时表
    3. 接着删除原表
    4. 最后把临时表重命名为原表

这种操作对于原表非常大的情况则需要很长的时间。
InnoDB引擎从1.0.x版本开始支持Fast Index Creation（快速索引创建）的方式—-FIC。对于辅助索引的创建，InnoDB引擎会对创建索引的表加上一个S锁，在创建的过程中不需要重建表。

5.5 Cardinality值

5.5.1 Cardinality

  1. 对于什么时候添加B+树索引，一般经验是，在访问表中很少一部分时使用B+树索引才有意义（区分度大），对于性别地域等不适合建立索引。如一个字段的取值范围非常广，几乎没有重复，属于高选择性，此时使用B+树索引是合适的。
  3. 怎样查看字段是否高选择性？可以通过SHOW INDEX结果列中的Cardinality来观察。这个值应该尽可能的接近1

5.5.2 InnoDB存储引擎的Cardinality统计

在InnoDB引擎中，Cardinality统计信息的更新是发生在两个操作中：INESRT和UPDATE。

InnoDB引擎内部更新Cardinality的侧脸：

  1. 1. 表中1/16的数据已经发生裱花
  2. 2. stat_modified_counter>2 000 000 000

怎样统计Cardinality信息的：即采样过程：

  1. 1. 取得B+树索引中叶子节点的数量，记为A
  2. 2. 随机取得B+树索引中的8个叶子节点。统计每个页不同记录的个数，记为P1，P2,P3.....P8
  3. 3. 根据采用信息给出Cardinality的预估值：Cardinality=(P1+P2+.....+P8) * A / 8

mysql ---- innodb2 （索引） - 图5

5.6 B+树索引的使用

5.6.2 联合索引

联合索引是指对表上的多个列进行索引。例如

  1. create table t (
  2.     a int,
  3.     b int,
  4.     primary key(a),
  5.     key idx_a_b(a,b)
  6. ) engine = innodb

mysql ---- innodb2 （索引） - 图6

上图可以看到多个键值的B+树，键值都是排序的，通过叶子节点可以逻辑上顺序地读出所有数据。

因此对于select * from table where a=xxx and b=xxx,是可以使用到索引的，对于select * from table where a = xxx，也是可以用到索引的，但是select * from table where b=xxx是用不到索引，因为叶子节点的b值1/2/1/4/1/2，显然不是顺序排序的，因此对b列的查询使用不到索引（a，b）的。

  1. 联合索引的第二个好处就是已经对第二个键值进行了排序处理。

5.6.3 覆盖索引

  1. InnoDB存储引擎支持覆盖索引（covering index，或索引覆盖），即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。使用覆盖索引的一个好处就是辅助索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少IO操作。

5.6.4 优化器不适用索引的情况

在某些情况下，优化器并不会选择使用索引，这种情况多数发生于范围查找、join链接操作等情况。

  1. select * from orderdetails where orderid > 10000 and orderid < 102000;

对于上述sql，通过命令show index from orderdetails，可以观察到：

mysql ---- innodb2 （索引） - 图7

orderdetails表有（orderid，productid）的联合主键，此外还有orderid的单个索引，上述sql显然可以通过扫描orderid列上的索引进行数据的查找，然而通过explain命令，实际上并没有使用orderid上的索引来查找的

mysql ---- innodb2 （索引） - 图8

在posable_keys一列可以看到查询可以使用PRIMARY、OrderID、OrdersOrder_details三个索引，但是时间使用的是PRIMARY聚集索引，也就是权标扫描，而非OrderID辅助索引扫描。

这个是因为用户选择的是整行信息，而OrderID索引不能覆盖到我们查询的信息，因此在对OrderID索引查询到指定数据后，还需要一次书签访问来查找整行数据的信息，虽然OrderID是顺序存放的，但是在进行一次书签访问则是无序的，变为了离散读。

5.6.5 索引提示

显示的告诉mysql使用哪个索引：以下情况可以显示可以显示的告诉mysql使用哪个索引

  1. mysql数据的优化器错误的使用了某个索引（发生的情况比较少）
  2. 某sql语句可以选择的索引非常多，优化器选择执行计划的开销可能大于sql语句本身。

例子：

  1. select * from tbl_name force index(a) where ***

5.6.6 Multi-Range Read 优化

mysql5.6版本开始支持Multi-Range Read（MRR）优化，MRR优化的目的就是为了减少磁盘的随机访问，并接将随机访问转化为顺序地数据访问，这对于IO-bound类型的sql查询的性能带来极大的提升。

MRR优化可适用于range，ref，eq_ref类型的查询：

MRR优化好处：

  1. 1. 使数据访问变得较为顺序。在查询辅助索引时，首先根据得到的查询结果，按照主键进行排序，并按照主键排序进行书签查找
  2. 2. 减少缓冲池中页被替换的次数
  3. 3. 批量处理对键值的查询操作

是否启用MRR优化可以设置参数optimizer_switch中的标记（flag）来控制。当mrr为on时，表示启用。mrr_const_based标记设置off，则总是启用mrr优化。

  1. set @@optimizer_switch='mrr=on,mrr_cost_based=off';

5.6.7 Index Condition Pushdown（ICP）优化

该优化也是在mysql5.6开始支持的一种优化方式。

在不支持ICP之前，当进行查询操作时，首先根据索引查找记录，然后再根据where条件进行过滤。

支持ICP之后，mysql数据库会在取出索引的同时，判断是否可以进行where条件的过滤，也就是将where的部分过滤操作放在了存储引擎层。在某些查询下，可以大大减少对记录的获取。

可支持的类型：range、ref、eq_ref、ref_or_null。

5.7 哈希算法

5.7.1 哈希表

又称离散表。哈希表由直接寻址表改进而来的

5.7.2 InnoDB存储引擎中的哈希算法

InnoDB引擎使用哈希算法来对字典进行查找，起冲突机制采用链表方式，hash函数采用除法散列方式。

在缓冲池中的page页都有一个chain指针，它指向相同hash函数值得页。对于除法散列，m的取值为略大于2倍的缓冲池页数量的质数。

例如：当前参数innodb_buffer_pool_size的大小为10M，则共用640个16kb的页，对于缓冲池内存的hash表来说，需要分配640*2=1280个槽，但是由于1280不是质数，则取略大的质数1399.

5.8 全文检索