章节目标

  • 了解InnoDB存储引擎支持的索引
  • 了解索引内部的机制
  • 掌握哪里可以使用索引

5.1 InnoDB存储引擎索引概述

InnoDB存储引擎支持以下几种常见的索引：

  • B+树索引
    • 最常用和最为有效
    • 类似二叉树，不代表二叉，而是代表平衡
    • 从最早的平衡二叉树演化而来
    • 能找到的只是被查找数据行所在的页
  • 全文索引
  • 哈希索引
    • 自适应
    • 根据表的使用情况自动为表生成哈希索引，不能认你为干预是否在一张表中生成哈希索引

5.2 数据结构与算法

5.2.1 二分查找法

二分查找法也称为折半查找法，用来查找一组有序的记录数组中的某一记录。

  • 将记录按有序化排列，在查找过程中采用跳跃式方式查找
  • 先以有序数列的中点位置为比较对象
  • 要找的元素值小于该中点元素，则将待查序列缩小为左伴部分，否则为右伴部分

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

二叉查找树：

  • 左子树的键值总是小于根的键值
  • 右子树的键值总是大于根的键值
  • 平均查找次数为（3+3+3+2+2+1)/6=2.3次
  • 平均查找次数为（1+2+3+4+5+5)/6=3.16次

以上可以看出，若想最大性能地构造一颗二叉查找树，需要这颗二叉查找树是平衡的，从而引出了定的定义——平衡二叉树

平衡二叉树：（查找性能是比较高的，接近最高性能）

  • 首先符合二叉查找树的定义
  • 必须满足任何节点的两个子树的高度最大差为1

维护一颗平衡二叉树的代价会非常大（多用于内存结构对象中，维护的开销相对较小），需要1次或多次左旋和优选来得到插入或更新后树的平衡性

5.3 B+树

B+树由B树和索引顺序访问方法演化而来

B树：

  • B树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树
  • B树中所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接

5.3.1 B+树的插入操作

B+树总是会保持平衡。尽量减少页的拆分操作。B+树同样提供类似于平衡二叉树的旋转功能。

  • 插入键值70，B+树并不会急于拆分叶子节点
  • 左兄弟会被首先检查用来做旋转操作，去做旋转
  • 同时这颗B+树的高度依然还是2

5.3.2 B+树的删除操作

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

5.4 B+树索引

本质是B+树在数据库中的实现。特点高扇出性，一般都在2~4层。

  • 聚集索引
  • 辅助索引

5.4.1 聚集索引

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

  • 聚集索引能够在B+树索引的叶子节点上直接找到数据

  • 并不是物理上连续而是逻辑上连续的

    • 也通过双向链表链接，页按照主键的顺序排序
    • 每个页中的记录也是通过双向链表进行维护的，物理存储上可以同样不按照逐渐存储

5.4.2 辅助索引

叶子节点并不包含行记录的全部数据。

5.4.3B+树索引的分裂

没理解，待完善

5.4.4 B+树索引的管理

1.索引管理

  • ALTER INDEX
  • CREATE DROP INDEX
  • SHOW INDEX
    • Table：索引所在的表名
    • Non_unique：非唯一的索引，primary key 是0，因为必须是唯一的。
    • Key_name：索引的名字
    • Sql_in_index：索引中该列的位置
    • Column_name：索引列的名字
    • Collation：列以什么方式存储在索引中
    • Cardinality：唯一值的数目估计值，尽可能接近1，如果非常小考虑删除此索引
    • Sub_part：是否是咧的部分被索引
    • Packed：关键字如何被压缩
    • Null：是否索引的列含有Null值
    • Index_type：索引的类型
    • Comment：注释

2.Fast Index Creation

InnoDB1.0.x版本开始支持

  • FIC方式只限定于辅助索引，对于主键的创建和删除同样需要重建一张表

  • 会对创建索引的表加上一个S锁，表只读

  • 删除辅助索引只需更新内部视图，标记辅助索引的空间可用，删除内部视图上对该表的索引定义

3.Online Schema Change（在线架构改变）

实现OSC步骤：

  • init，初始化阶段，会对创建的表做一些验证工作，如检查表是否由主键，是否存在触发器或者外键等
  • createCopyTable：创建和原始表结构一样的新表
  • alterCopyTable：对创建的新表进行Alter Table操作，如添加索引或列等
  • createDeltasTable：创建deltas表，该表的作用式为下一步创建的触发器所使用
  • createTriggers：对原表创建INSERT、UPDATE、DELETE操作的触发器。触发器操作产生的记录被写入到deltas表。
  • startSnpshotXact：开始OSC操作的事务
  • selectTableIntoOutfile：将原表中的数据写入到新表。
  • dropNCindexs：在导入新表前，删除新表中所有的辅助索引
  • loadCopyTable：将导出的分片文件导入到新表
  • replayChanges：将OSC过程中原表DML操作的记录应用到新表中，这些记录被保存在deltas表中
  • recreateNCIndexes：重新创建辅助索引
  • relayChanges：再次进行DML日志的回访操作，这些日志是在上述创建辅助索引过程中新产生的日志。
  • swapTables：将原表和新表交换名字，整个操作需要锁定2张表，不允许新的数据产生。

4.Online DDL

5.6版本开始支持

  • 辅助索引的创建和删除
  • 改变自增长值
  • 添加或删除外键约束
  • 列的重命名

5.5 Cardinality值

5.5.1 什么是Cardinality

表示索引中不重复记录数量的预估值。

故在访问高选择性属性的字段并从表中取出很少一部分数据时，对这个字段添加B+树索引是非常有必要的。

5.5.2 InnoDB存储引擎的Cardinality统计

Where

  • 放在存储引擎层进行的

When

  • 表中1/16的数据已发生过变化
    • 自从上次统计cardinality信息后，表中1/16的数据已经发生过变化
  • stat_modified_counter>2000 000 000
    • 发生变化的次数

How

默认Innodb存储引擎对8个叶子节点进行采用

  • 取得B+树索引中叶子节点的数量，记为A
  • 随机取得B+树索引中的8个叶子节点。统计每个页不同记录的个数，即为P1，P2，。。。P8.
  • 根据采样信息给出Cardinality预估值：Cardinality=（P1+P2+。。。+P8）/*A/8

由于每次随机取得8个叶子节点，每次得到的值可能是不同的。

执行以下SQL语句会导致InnoDB存储引擎去重新计算索引的Cardinality的值：

  • ANALYZE TABLE
  • SHOW TABLE STATUS
  • SHOW INDEX
  • INFORMATION_SCHEMA架构下的表TABLES和STATISTICS

5.6 B+树索引的作用

5.6.1 不同应用中B+树索引的作用

OLTP：B+树索引建立后，对该索引的使用应该只是通过该索引取得表中少部分的数据。

OLAP：宏观的信息，通常会对时间字段进行索引。

5.6.2 联合索引

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

键值都是排序的，通过叶子节点可以逻辑上顺序地读出索引数据。

5.6.3 覆盖索引

  • 从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。

  • 不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的IO操作。

详情案例不记录，查看详情到原文件中

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

1
select * from orderdetails where orderid>10000 and orderid<102000
  • orderdetails有（orderid，productid）联合主键，orderid 单个索引
  • explain查看没有使用orderid上的索引来查找数据

Why

  • 用户要取的是整行信息，orderid索引不能覆盖到我们要查询的信息。

  • orderid查询到指定数据后，还需要再一次书签访问来查找整行数据的信息。

  • 再一次书签查找的数据则是无序的，变成了磁盘上的离散读操作

  • 访问的数据占整个表中数据的蛮大一部分（一般20%左右），优化器会选择通过聚集索引来查找数据

优化器选择辅助索引的情况是：

  • 通过辅助索引查找的数据是少量的。

5.6.5 索引提示

use index只是告诉优化器可以选择某索引，实际上优化器还是会再根据自己的判断进行选择。

5.6.6 Multi-Range Read优化

适用于range,ref,eq_ref

  • 数据访问变得较为顺序
  • 减少缓冲池中页被替换的次数
  • 批量处理对键值的查询操作

详情案例不记录，查看详情到原文件中

范围查询和Join查询操作，MRR的工作方式：

  • 将查询得到的辅助索引键值存放于一个缓冲中，根据辅助索引键值排序的

  • 将缓存中的键值根据RowID进行排序

  • 根据RowID的排序顺序来访问实际的数据文件

开启操作：

1
set @@optimizer_switch='mrr=on,mrr_cost_based=off'
  • read_rmd_buffer_size 用于控制键值的缓冲区大小

5.6.7 Index Condition Pushdown(ICP)优化

  • 会在取出索引的同时，判断是否可以进行WHERE条件的过滤

  • WHERE的部分过滤操作放在了存储引擎层

支持range,ref,eq_ref,ref_or_null

5.7 哈希算法

5.7.1 哈希表

没有理解，待完善

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

没有理解，待完善

5.7.3 自适应哈希索引

数据库自身创建并使用的。

5.8 全文索引

是将存储于数据库中的整本书或整篇文章中的任意内容信息查找出来的技术

InnoDB1.2.x版本开始支持

5.8.2 倒排索引

它在辅助表中存储了单词与单词自身在一个或多个文档中所在位置之间的映射。

  • inverted file index {单词，单词所在文档的ID}
  • full inverted index {单词，（单词所在文档的ID，在具体文档中的位置）}

5.8.3 InnoDB全文索引

  • 每张表只能有一个全文检索的索引
  • 由多列组合而成的全文检索的索引列必须使用相同的字符集与排序规则
  • 不支持没有单词界定符的语言，如中文、日语、韩语等

5.8.4 全文检索

1.Natural Language

2.Boolean

3.Query Expansion