基于MySQL InnoDB

索引对查询的速度有着至关重要的的影响，理解索引也是进行数据库性能调优的起点。
索引就是提高数据查询的效率的一种数据结构。

MySQL索引原理

索引目的

索引的目的在于提高查询效率。

可以类比字典，如果要查“mysql”这个单词，我们肯定需要定位到m字母，然后从下往下找到y字母，再找到剩下的sql。
如果没有索引，那么你可能需要把所有单词看一遍才能找到你想要的，如果我想找到m开头的单词呢？或者ze开头的单词呢？是不是觉得如果没有索引，这个事情根本无法完成？

索引原理

除了词典，生活中随处可见索引的例子，如火车站的车次表、图书的目录等。
它们的原理都是一样的，通过不断的缩小想要获得数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是我们总是通过同一种查找方式来锁定数据。

数据库也是一样，但显然要复杂许多，因为不仅面临着等值查询，还有范围查询(>、<、between、in)、模糊查询(like)、并集查询(or)等等。

数据库应该选择怎么样的方式来应对所有的问题呢？
我们回想字典的例子，能不能把数据分成段，然后分段查询呢？
最简单的如果1000条数据，1到100分成第一段，101到200分成第二段，201到300分成第三段……这样查第250条数据，只要找第三段就可以了，一下子去除了90%的无效数据。
但如果是1千万的记录呢，分成几段比较好？稍有算法基础的同学会想到搜索树，其平均复杂度是lgN，具有不错的查询性能。

但这里我们忽略了一个关键的问题，复杂度模型是基于每次相同的操作成本来考虑的，数据库实现比较复杂，数据保存在磁盘上，而为了提高性能，每次又可以把部分数据读入内存来计算，因为我们知道访问磁盘的成本大概是访问内存的十万倍左右，所以简单的搜索树难以满足复杂的应用场景。

磁盘IO与预读

前面提到了访问磁盘，那么这里先简单介绍一下磁盘IO和预读。

磁盘读取数据靠的是机械运动，每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分。
寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下；
旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120/2 = 4.17ms；
传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。

那么访问一次磁盘的时间，即一次磁盘IO的时间约等于5+4.17 = 9ms左右，听起来还挺不错的，但要知道一台500 -MIPS的机器每秒可以执行5亿条指令，因为指令依靠的是电的性质，换句话说执行一次IO的时间可以执行40万条指令，数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难。

下图是计算机硬件延迟的对比图，供大家参考：

考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。
每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助。

索引的数据结构

每次查找数据时把磁盘IO次数控制在一个很小的数量级，最好是常数数量级。
那么我们就想到如果一个高度可控的多路搜索树是否能满足需求呢？
就这样，b+树应运而生。

MySQL为什么使用B+TRee

文件系统及数据库系统普通采用B-/+Tree作为索引结构。
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上。
这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。
换句话说，索引的结构要尽量减少查找过程中磁盘I/O的存取次数。

B树 VS B+树

  • B树
    1. 所有键值分布在整颗树中（索引值和具体data都在每个节点里）；
    2. 任何一个关键字出现且只出现在一个结点中；
    3. 搜索有可能在非叶子结点结束（最好情况O(1)就能找到数据）；
    4. 在关键字全集内做一次查找,性能逼近二分查找；
  • B+树
    1. 所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data)。B+树只有叶子节点保存了data，时间复杂度固定为 O(log n)。
    2. 为所有叶子结点增加了一个链指针

InnoDB B+树的存储结构

B+树的叶子节点和非叶子节点的大小为一页，16K。

  • 叶子节点存放数据，非叶子节点存放指针和键值
  • 主键索引：叶子节点存放真正的数据
  • 二级索引：叶子节点存放主键索引的值

B+树如何检索记录

  • 首先找到根页，你怎么知道一张表的根页在哪呢？
  • 其实每张表的根页位置在表空间文件中是固定的，即上图中page number=3的页
  • 找到根页后通过二分查找法，定位到id=5的数据应该在指针P5指向的页中
  • 然后再去page number=5的页中查找，同样通过二分查询法即可找到id=5的记录

索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中，进而在去数据页中查找到需要的数据。

MySQL InnoDB存储引擎中B+树一个节点有多大？一千万条数据，B+树多高？

存储单元

  1. 数据持久化存储磁盘里，磁盘的最小单元是扇区，一个扇区的大小是 512个字节
  2. 文件系统的最小单元是块，一个块的大小是 4K
  3. InnoDB存储引擎，有自己的最小单元，称之为页，一个页的大小是 16K

InnoDB引擎的页大小

InnoDB存储引擎的最小存储单位是页，页的大小为16K = 16384Byte

1
show variables like 'innodb_page_size';

叶子节点可以存放多少行数据

单个叶子节点（也就是一页）的大小为16K。
一行记录的数据大小为数据表各字段的大小的和，假设为1K，叶子结点一页可以存放16行记录。

非叶子节点可以存放多少指针

单个非叶子节点的大小也为一页，16K。
非叶子节点存储指针和键值，假设主键为bigint类型，长度为8字节，指针大小在InnoDB中的大小为6字节，指针+键值一共14字节。
一个页中能够存放16384 / 14 = 1170个单元，这也是指针的个数。

一颗B+树可以存放多少行记录

假设树高为k，B+树可存储的记录行数 = （非叶子节点的指针个数）的k-1次方 * 叶子节点的记录行数。

一行记录的数据大小为数据表各字段的大小的和，假设为1K；主键类型假设为bigint，长度为8字节。
三层高的B+树可以存储的记录行数为1170 * 1170 * 16 = 21902400，千万级。

索引分类

主键索引 VS 唯一索引 VS 普通索引

同一个叶子节点(大小为一个内存页或磁盘页，MySQL一页16KB)内的各条数据记录按主键顺序存放，因此每当有一条新的记录插入时，MySQL会根据其主键将其插入适当的节点和位置，如果页面达到装载因子(InnoDB默认为15/16)，则开辟一个新的页(节点)。

  • 如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。
    这样就会形成一个紧凑的索引结构，近似顺序填满。
    由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。

  • 如果使用非自增主键(如果身份证号或uuid等)，由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页的中间某个位置
    此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，
    同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，
    后续不得不通过OPTIMIZE TABLE语句来重建表并优化填充页面。因此，只要可以，请尽量在InnoDB上采用自增字段做主键。

聚簇索引 VS 非聚簇索引

联合索引

索引覆盖

当某个索引的索引列覆盖了select的所有字段时，会使用到覆盖索引。
覆盖索引能够只通过索引就获取到所需要的数据而不需要在回表一条条的查询，同时由于索引是有顺序的，这样对于I/O密集型的范围查询效率也很高。

但是，往往我们很少能够遇到覆盖索引的情况，一般情况都是select的列会多于索引列，这样就无法使用到覆盖索引。

索引下推

索引条件下推（Index Condition Pushdown，ICP），就是过滤的动作由下层的存储引擎层通过使用索引来完成，而不需要上推到Server层进行处理。
ICP是在 MySQL5.6 之后完善的功能，它能减少回表查询次数，提高查询效率。

MySQL Server层负责SQL语法解析、生成执行计划等，并调用存储引擎层去执行数据的存储和检索。
索引下推的下推其实就是指将部分上层（服务层）负责的事情，交给了下层（引擎层）去处理。

索引下推一定是在联合索引的情况下，根据联合索引本身就有的数据直接做一次过滤，而不用再进行多次无用的回表再到Server层进行过滤。

慢查询优化

建索引的原则

  1. 最左前缀匹配原则
    mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配。
    比如a = 1 and b = 2 and c > 3 and d = 4，如果建立(a,b,c,d)顺序的索引，d是用不到索引的，如果建立(a,b,d,c)的索引则都可以用到，a,b,d的顺序可以任意调整。
  2. =和in可以乱序
    比如a = 1 and b = 2 and c = 3，建立(a,b,c)索引可以任意顺序，mysql的查询优化器会帮你优化成索引可以识别的形式。
  3. 尽量选择区分度高的列作为索引
    区分度的公式是count(distinct col)/count(*)，表示字段不重复的比例，比例越大我们扫描的记录数越少。
    唯一键的区分度是1，而一些状态、性别字段可能在大数据面前区分度就是0。
    那可能有人会问，这个比例有什么经验值吗？使用场景不同，这个值也很难确定，一般需要join的字段我们都要求是0.1以上，即平均1条扫描10条记录。
  4. 索引列不能参与计算，保持列“干净”
    比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引，原因很简单，b+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，显然成本太大。所以语句应该写成create_time = unix_timestamp(’2014-05-29’)。
  5. 尽量的扩展索引，不要新建索引
    比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可。

索引失效

  • or会导致索引失效，但是单列索引是有效的
  • 不符合左前缀原则会失效
  • 模糊查询%开头会导致失效
  • 隐式类型转换会导致失效
  • 条件中使用函数会失效
  • IN肯定会走索引，但是当IN的取值范围较大时会导致索引失效，走全表扫描

如何定位并优化慢查询sql

  • 第一步根据慢日志定位慢查询sql。慢日志是用来记录执行比较慢的sql。
  • 第二步使用explain等工具分析sql。
    explain关键字段：rows、type、extra
  • 第三步修改sql或者尽量让sql走索引。

explain

  • id
    select查询的序列号，包含一组数字，表示查询中执行select子句或者操作表的顺序：
    • 如果id相同，那么执行顺序从上到下
    • 如果id不同，id值越大优先级越高，越先被执行
  • select_type
    主要用来分辨查询的类型，是普通查询还是联合查询还是子查询
    • SIMPLE 简单的 select 查询,查询中不包含子查询或者UNION
    • PRIMARY 查询中若包含任何复杂的子部分，最外层查询则被标记为Primary
    • SUBQUERY 在SELECT或WHERE列表中包含了子查询
    • DERIVED 在FROM列表中包含的子查询被标记为DERIVED(衍生);MySQL会递归执行这些子查询, 把结果放在临时表里。
    • UNION 若第二个SELECT出现在UNION之后，则被标记为UNION；若UNION包含在FROM子句的子查询中,外层SELECT将被标记为：DERIVED
    • UNION RESULT 从UNION表获取结果的SELECT
    • DEPENDENT SUBQUERY 在SELECT或WHERE列表中包含了子查询,子查询基于外层
    • UNCACHEABLE SUBQUREY 无法被缓存的子查询
  • table
    对应行正在访问哪一个表，表名或者别名，可能是临时表或者union合并结果集
    • 如果是具体的表名，则表明从实际的物理表中获取数据
    • 表名是derivedN的形式，表示使用了id为N的查询产生的衍生表
    • 当有union result的时候，表名是union n1,n2等的形式，n1,n2表示参与union的id
  • partitions
  • type （2）
    访问类型表示我是以何种方式去访问我们的数据，最容易想的是全表扫描，直接暴力的遍历一张表去寻找需要的数据，效率非常低下。
    访问的类型有很多，效率从最好到最坏依次是：
    system > const > eq_ref > ref > fulltext > ref_or_null > index_merge > unique_subquery > index_subquery > range > index > ALL
    必须记住const > ref > range > index > all。
    一般情况下，得保证查询至少达到range级别，最好能达到ref。
    • ALL 全表扫描
    • index 索引树全扫描
    • range 索引范围扫描，常用语<,<=,>=,between等操作
    • ref 使用非唯一索引扫描或唯一索引前缀扫描，返回单条记录，常出现在关联查询中
    • eq_ref 类似ref，区别在于使用的是唯一索引，使用主键的关联查询
    • const/system 单条记录，系统会把匹配行中的其他列作为常数处理，如主键或唯一索引查询
    • null MySQL不访问任何表或索引，直接返回结果
  • possible_keys
    显示可能应用在这张表中的索引，一个或多个，查询涉及到的字段上若存在索引，则该索引将被列出，但不一定被查询实际使用
  • key （4）
    实际使用的索引。
    如果为null，则没有使用索引，查询中若使用了覆盖索引，则该索引和查询的select字段重叠。
  • key_len
    表示索引中使用的字节数，可以通过key_len计算查询中使用的索引长度，在不损失精度的情况下长度越短越好。
  • ref
    显示索引的哪一列被使用了，如果可能的话，是一个常数
  • rows （1）
    根据表的统计信息及索引使用情况，大致估算出找出所需记录需要读取的行数，此参数很重要，直接反应的sql找了多少数据，在完成目的的情况下越少越好。
    rows是核心指标，绝大部分rows小的语句执行一定很快，所以优化语句基本上都是在优化rows。
  • filtered
  • extra （3）
    包含额外的信息。