likes
comments
collection
share

InnoDB 存储引擎索引原理解析

作者站长头像
站长
· 阅读数 43

在数据库领域，深入了解 InnoDB 存储引擎的运作机制至关重要。本文以《MySQL 技术内幕 InnoDB 存储引擎》为基础，呈现关键内容，并融入了案例分析，让读者更加直观地理解知识点。

InnoDB 存储引擎索引概述

常见索引类型

  1. B+ 树索引
  2. 全文索引
  3. 哈希索引

B+ 树不能找到给定键值的具体行，B+ 树索引只能找到数据所在的页，通过数据库把页读取到内存中，再在内存中查找到需要的数据

数据结构和算法

二分查找法

二叉查找树和平衡二叉树

B+ 树

B+树插入操作

  1. Leaf Page 未满，Index Page 未满 直接插入到叶子节点
  2. Leaf Page 满， Index Page 未满
    1. 拆分Leaf Page
    2. 将中间节点放入 Index Page
    3. 小于中间节点的放左边
    4. 大于等于中间节点的放右边
  3. Leaf Page满，Index Page满
    1. 拆分Leaf Page
    2. 小于中间节点放左边
    3. 大于等于中间节点放右边
    4. 拆分Index Page
    5. 小于中间节点记录放左边
    6. 大于等于中间节点放右边
    7. 中间节点放上一层 Index Page

特性

  1. B+ 树总会保持平衡，新插入键值可能需要拆分页
  2. B+ 树提供了类似于平衡二叉树的旋转功能

B+ 树的删除操作

B+ 树索引

  1. 聚集索引在页里面不是顺序存储的，而是逻辑顺序的（物理存储的话维护成本很高）
    1. 页通过双向链表链接，页按照主键的顺序排序
    2. 每个页中的记录按照双向链表进行维护，物理存储上可以同样不按照主键存储
  2. MySQL explain 中的 Cardinality 可以通过 analyze table 进行更新

Fast Index Creation

  1. 5.5版本之前（不包括5.5）创建索引等 DDL 步骤
    1. 创建新的临时表
    2. 把原表数据导入临时表
    3. 删除原表
    4. 把临时表重命名为原表
  2. 从 InnoDB 1.0.x 开始支持 Fast Index Creation(FIC)
    1. 对于辅助索引，在创建的过程中对表上了 S 锁，只能对表进行读操作
    2. 对于主键索引仍然需要创建新表
    3. 临时表通过 tmpdir 设置的，需要保证有足够空间存放临时表
  3. Online Schema Change OSC

OSC 操作时允许设置 sql_bin_log=0，所以所做的操作不会同步 slave 服务器，可能导致主从不一致

  1. init 初始化阶段，验证是否含有主键、触发器或者外键
  2. creteCopyTable 创建和原始表结构一样的新表
  3. alterCopyTable 对新表进行 ALTER TABLE 操作，添加索引或者列
  4. createDeltasTable 创建 deltas 表，为下一步创建的触发器所使用。之后对原表的所有 DML 操作会被记录到 creteDeltasTable 中
  5. createTriggers 对原表创建 INSERT UPDATE DELETE 操作的触发器，触发器操作记录被写入到 deltas 表
  6. startSnpshotXact 开始 OSC 操作的事务
  7. selectTableIntoOutfile 将原表数据写入新表。为减少对原表锁定时间，通过分片（chunked）将数据输出到多个外部文件，然后将外部文件的数据导入到 copy 表中。默认 500000
  8. dropNCIndexs 导入到新表前，删除新表中的所有辅助索引
  9. loadCopyTable 将导出的分片文件导入到新表
  10. replayChanges OSC表中原表的 DML 操作记录到 新表中，保存在 deltas 表
  11. recreateNCIndexs 重新创建辅助索引
  12. replayChanges 再次进行 DML 日志的回放操作，是在上述创建辅助索引过程中新产生的日志
  13. swapTables 将原表和新表交换名字（需要锁定两张表）
  14. Online DDL

MySQL 5.6 开始支持 Online DDL（在线数据定义）操作

允许以下几类 DDL 操作

  1. 辅助索引的创建和删除
  2. 改变自增长值
  3. 添加或删除外键约束
  4. 列的重命名
alter table tbl_name
add index idx_test
(t1,t2)
algorithm = {DEFAULT|INPLACE|COPY}
lock = {DEFAULT|NONE|SHARED|EXCLUSIVE}

ALGORITHM 指定了创建或者删除索引的算法

  1. COPY 按照 MySQL 5.1 版本之前的工作模式，创建临时表
  2. INPLACE 表示索引的创建或删除不需要临时表
  3. DEFAULT 表示根据参数 old_alter_table 来判断通过 INPLACE 还是 COPY 的算法（默认为 OFF，表示采用 INPLACE的方式）

LOCK 支持以下模式

  1. NONE 执行索引创建或删除操作时不会加锁，事务可以正常读写
  2. SHARE 和 FIC 类似，对目标表加上一个 S 锁，可以并发读，但不可写入
  3. EXCLUSIVE 对目标表加 X 锁，不可以读写，与 COPY 类似，但是不用创建临时表
  4. DEFAULT 依次判断是否可以使用 NONE SHARE EXCLUSIVE模式

原理

  1. 执行创建或者删除操作时，将 INSERT、UPDATE、DELETE 这类 DML 操作日志写入到缓存中，完成索引创建后再重做到应用表上，以达到数据一致性
  2. 缓存大小由 innodb_online_alter_log_max_size控制（更新数据超过限制时会抛出异常）
  3. Online DDL 索引创建过程中，SQL优化器不会使用创建中的索引

Cardinality 值

什么是 Cardinality

InnoDB 存储引擎的 Cardinality 的统计

Cardinality 在存储引擎层统计

更新策略

  1. 表中 1/16 的数据已经发生过变化
  2. stat_modified_counter > 2 000 000 000

如何统计和更新 默认 InnoDB 存储引擎对 8 个叶子节点（Leaf Page）进行采样

  1. 取得 B+ 树索引中叶子节点的数量，记为 A
  2. 随机取得 B+ 树索引中的 8 个叶子节点。统计每个页不同记录的个数，记为 P1，P2 ... P8
  3. 根据采样信息给出预估值 Cardinality = (P1 + P2 + ... + P8) * A / 8
  4. 即使不进行数据更新，因为每次采样使用的页不同，所以结果可能不同，但是如果页小于等于8个，则每次结果一定相同

相关配置

  1. innodb_stats_persistent 是否将 cardinlity 保存到磁盘，默认 OFF
  2. innodb_stats_on_metadata 使用 SHOW TABLE STATUS，SHOW INDEX 以及访问 INFORMATION_SCHEMA 架构下的表 TABLES 和 STATISTICS 时，是否要重新计算，默认 OFF
  3. innodb_stats_persistent_sample_pages 表示innodb_stats_persistent ON 时每次采样页的数量
  4. innodb_stats_transient_sample_pages 取代之前的 innodb_stats_sample_pages，表示每次采样页数量

B+ 树索引的使用

不同应用中 B+ 树索引的使用

  1. OLTP 中需要查询数据量比较小，使用 B+ 树索引可以只获取少部分数据
  2. OLAP 中需要访问表中大量数据，索引添加应该基于宏观而不是微观

联合索引

联合索引和排序 表有索引 idx(a,b,c)，分别执行如下查询

-- 使用 idx 索引，利用了 a
select * from t1 where a = 'xxx';

-- 使用 idx 索引，并利用了 c的排序
select * from t1 where a = 'xxx' b = 'yyy' order by c limit 3;

-- 使用 idx 索引，没有利用 c 的排序，会有 filesort(文件排序）
select * from t1 where a = 'xxx' order by c limit 3;

覆盖索引

  1. 使用覆盖索引可以减少回表
  2. 进行 count 查询时，MySQL 可能检测到使用索引效率更高而采用辅助索引

不适用索引的情况

样例

如果使用固态硬盘，对于随机读有信心，可以强制使用索引

-- 如果使用 order_id 的索引，需要大量回表，所以走全表扫描
select * from order_details where order_id > 10000 and order_id <102000;

MySQL 成本分析

  1. 根据搜索条件 找出所有可能使用的索引
  2. 计算全表扫描的代价
  3. 计算使用不同索引查询的代价
  4. 对比各种执行方案 找出最优的方案
全表扫描的代价
  1. msyql默认单次读取的数据是一页 一页数据是16k
  2. 一次io成本记作 1, 一次cpu成本记作0.2

将数据从硬盘读取到内存中 可以和cpu并行运行 但是将数据从内存拿到cpu计算 需要消耗cpu

成本计算
  1. 全表扫描

假设总个数为 442486 则页数为 10512768(字节数)/1024(取得KB数)/16(每页16KB) = 1252 页 io成本: 1252 * 1.0 = 1252 cpu成本: 442486 * 0.2 = 88497 成本 为 88497 + 1252 = 89749

# 查看表数据的大小 #data_length
show table status like '表名';
# data_length/1024/16 = 需要取得的次数
  1. 索引扫描

二级索引 + 回表成本 IO成本 100 * 1.0 + 1.0 CPU成本 100 * 0.2(二级索引) + 100 * 0.2 (回表) = 40 总成本 = 101 + 40 = 141

mysql 如果没有执行就知道要执行多少个
  1. 如果查询的首尾节点在同一个父节点下面, 可以直接通过父节点获取到个数
走全表扫描的情况
  1. 检索的结果内容过大 走索引的- IO成本 + CPU成本可能比走全表扫描的成本更高 这时候就会走全表扫描
# explain不够用时, 可以用这个判断是否是当前的
optimizer trace

索引提示

MySQL 支持使用索引提示（INDEX HINT）显示的告诉优化器使用哪个索引

  1. MySQL 数据库优化器错误的使用了某个索引，导致 SQL 语句运行很慢（很少见）
  2. 某个 SQL 语句可以选择的索引很多，选择执行计划的时间可能大于 SQL 本身

语法 select * from t use index(a) where a = 1 and b =2 ;但是实际不一定按照这个来执行，如果使用 force index则一定会使用指定的索引

Multi-Range Read 优化 （MRR优化）

MRR 目的为了减少磁盘速记访问，将随机访问转化为较为顺序的数据访问，对于 IO-bound 类型的 SQL 查询语句可以带来性能极大的提升。可以适用于 range ，ref ，eq_ref 类型的查询

优点

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

工作方式

  1. 将查询到的辅助索引放到一个缓存中，这时缓存中的值是根据赋值索引键值排序的
  2. 将缓存中的键值根据 RowID 进行排序
  3. 根据 RowID 的排序顺序来访问实际的数据文件

启用方式 show variables like 'optimizer_switch' 默认值

index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,engine_condition_pushdown=on,index_condition_pushdown=on,mrr=on,mrr_cost_based=on,block_nested_loop=on,batched_key_access=off,materialization=on,semijoin=on,loosescan=on,firstmatch=on,duplicateweedout=on,subquery_materialization_cost_based=on,use_index_extensions=on,condition_fanout_filter=on,derived_merge=on,use_invisible_indexes=off,skip_scan=on,hash_join=on,subquery_to_derived=off,prefer_ordering_index=on,hypergraph_optimizer=off,derived_condition_pushdown=on

  1. mrr 表示是否启用 Multi-Range Read
  2. mrr_cost_based 表示是否使用 cost based 的方式来选择是否启用 mrr

set @@optimizer_switch='mrr=on,mrr_cost_based=off'; 一直启用 mrr

  1. read_rnd_buffer_size用来控制键值缓冲区的大小，若大于该值，则执行器对已经缓存的数据根据 RowID 进行排序，并通过 RowID 来取得行数据。该值默认为 256K

Index ConditionPushdown（ICP）优化 （索引下推）

Index Condition Pushdown 支持 range、ref、eq_ref、ref_or_null 类型的查询 说明 通常联合索引查询时，如果索引有模糊查询，需要将所有的结果取出来之后再进行筛选，通过索引下推，在索引取出时就会进行 where 条件的过滤，极大地提高查询的效率 样例 通常来说，以下 SQL 需要将 所有 zip_code 为 111000 的结果取出来再进行筛选，通过索引下推，可以在取出 结果时即进行筛选

-- 索引 (zip_code, last_name, address)
select * from t1
wehre zip_code = '111000'
and last_name = like '%aaa%'
and address like '%bbb%';

另外 辅助索引中会包含主键的信息，所以在查询时针对主键的模糊查询也可以走索引下推

哈希算法

哈希算法时间复杂度为 O(1) ，如果要从缓存中得到需要的列可以优先使用哈希算法

哈希表

哈希表由直接寻址表改进而来。 直接寻址表问题

  1. 如果数据很大，直接寻址不现实

InnoDB 中的哈希算法

  1. 使用哈希函数 h(k), 根据关键字 k 计算出索引位置，将关键字域映射到哈希表T[0...m-1]的槽位上
  2. 如果存在哈希碰撞，使用链接法拼接
  3. 哈希函数使用除法散列，h(k) = k mod m
  4. 对于缓冲池页的哈希表，在缓冲池中的页都有一个 chain 指针，指向相同哈希函数值的页
  5. 除法散列，m 取值略大于 2 倍缓冲池页数量的质数。
    1. innodb_buffer_pool_size 为10M，则一共有 640 个 16KB 的页，对于缓冲池内存的哈希表需要分配 640 * 2 = 1280 个槽，取略大的质数为 1399

如何查找 InnoDB 存储引擎表空间有一个 space_id，用户要查找的应该是某个表空间某个连续 16KB 的页，即偏移量 offset。InnoDB 存储引擎将 space_id 左移 20 位，然后加上这个 space_id 的 offset，关键字 K = space_id << 20 + space_id + offset

自适应哈希索引

自适应哈希经哈希函数映射到一个哈希表中，因此对于字典类型的查找非常快速。select * from t1 where c1 = 'xxx'，范围查询不可以使用哈希索引

全文索引

概述

  1. 根据 B+ 树的特点，支持右模糊查询
  2. 对于左模糊的查询，B+ 树索引不能很好的完成工作，（需要全表扫描等）
  3. 全文索引（Full-Text Search）是将存储与数据库中整本书或者整篇文章任意内容查找出来的技术

倒排索引

**全文索引使用倒排索引来实现。**其在辅助表（auxiliary table)中存储了单词与单词自身在一个或多个文档中所在位置之间的映射。这通常利用关联数组实现，拥有两种表现形式

  1. inverted file index，表现形式为 {单词，单词所在文档的ID}
  2. full inverted index，表现形式为 {单词，（单词在文档的ID，在具体文档中的位置）}

InnoDB 全文检索

  1. 从 1.2.x 开始支持全文检索，使用 full inverted index 的方式。
  2. 倒排索引需要将 word 存放到一张表中，称为 Auxiliary Table（辅助表）。为了提高全文索引的并行性能，共有 6 张 Auxilary Table，每张表根据 word 的 Latin 编码进行区分。（Auxilary Table 存放与磁盘上）
  3. FTS Index Cache（全文检索索引缓存） 是一个红黑树，根据 （word，ilist）进行排序。
    1. 可能插入的数据已经更新到了对应的表，但是对全文索引的操作在分词后还在 FTS Index Cache 中，Auxiliary Table 可能还没有更新。
    2. InnoDB 会批量对 Auxiliary Table 进行更新，而不是每次插入后更新一次 Auxiliary Table。
    3. 在对全文索引进行查询时，Auxiliary Table 会首先将 FTS Index Cache 合并到 Auxiliary Table中，然后进行查询，类似于 Insert Buffer 操作。
  4. 可以通过设置查看倒排索引的 Auxiliary Table 中分词的信息
    1. set golbal innodb_ft_aux_table = 'test/fts_a';
    2. select * from information_schema.innodb_ft_index_table; 可以查看 fts_a 表的 Auxiliary Table
-- 添加全文索引
ALTER TABLE biz_order_detail ADD FULLTEXT(form_name, field_value);
-- 执行全文索引查询
explain select * from biz_order_detail WHERE MATCH(form_name, field_value) AGAINST( 'vin');
-- 查看全文索引分词信息
SET GLOBAL innodb_ft_aux_table = 'delta/biz_order_detail';
select * from information_schema.INNODB_FT_INDEX_TABLE;
-- 查看插入到 DELETED 表中的信息
select * from information_schema.INNODB_FT_DELETED;
-- 设置 optimize table 时仅进行 full text 清理
set GLOBAL innodb_optimize_fulltext_only = 1;

OPTIMIZE TABLE delta.biz_order_detail;

select * from information_schema.INNODB_FT_DELETED;
-- 清除完之后会保存到 BEING_DELETED中
select * from information_schema.INNODB_FT_BEING_DELETED;

-- 如果清除全文索引之后，不会再允许插入这个文档ID
  1. 数据库关闭或者宕机时
    1. 数据库关闭时会将数据写入磁盘上的 Auxiliary Table
    2. 数据库宕机后，下次重启之后，用户访问全文索引时会自动读取未完成的文档，然后进行分词操作并写入 FTS Index Cache 中
  2. innodb_ft_cache_size用来控制 FTS Index Cache 大小，默认值为 32M
  3. FTS Document ID，为了支持全文索引，必须要有一个列与 word 进行映射，在 InnoDB 中这个列被命名为 FTS_DOC_ID，类型为 BIGINT UNSIGNED NOT NULL
  4. 对于删除操作，不会删除磁盘 Auxiliary Table 中的记录，而是删除 FTS Index Cace 中的记录，并保存FTS Document ID
  5. optimize table t1
    1. 可以将删除的记录彻底清除
    2. 如果删除的文档非常多， 可能会占用非常多的时间
    3. 可以通过innodb_ft_num_word_optimize来控制每次实际删除的分词数量，默认 2000

stopword 列表

-- 默认的 stopword 列表 （共 36 个） a,about,an,are,as,at,the...
select * from information_schema.INNODB_FT_DEFAULT_STOPWORD;

-- 设置自定义的 stopword 列表
set GLOBAL innodb_ft_server_stopword_table = 'delta/user_stopword';

使用全文索引限制

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

全文检索

Natural Language

全文检索通过 MATCH 函数进行查询，默认采用 Natural Language 模式

select * from fts_a
where match(body) aginst ('Porridge' IN NATURAL LANGUAGE MODE);

-- 统计 MATCH 函数得到的数量
select count(1) from fts_a where 
match(body) against ('Porridge' IN NATURAL LANGUAGE MODE);
-- 或者 使用以下效率可能更高： 不需要进行相关性排序
select 
count(if(match (body) aginst ('Porridge' , 1, NULL)) as count
      from fts_a;

全文检索的结果根据相关性进行排序，相关性计算依据满足以下条件

  1. word 是否再文档中出现
  2. word 在文档中出现的次数
  3. word 在索引列中的数量
  4. 多少个文档包含该 word

对 InnoDB 存储引擎的全文索引，需要考虑以下因素

  1. 查询的 word 在 stopword 中，忽略该字符串的查询（会返回所有的结果 类似于 '%%')
  2. 查询的 word 字符长度是否在区间 **[innodb_ft_min_token_size, innodb_ft_max_token_size] **中,不在范围中则不进行查询，默认[3,84]

Boolean

MySQL 数据库允许使用 IN BOOLEAN MODE 修饰符来进行全文检索。

select * from fts_a
where MATCH(body) AGAINST ('+Pease -hot' IN BOOLEAN MODE);

Boolean 支持以下几种操作符

    • 表示该 word 必须存在
    • 表示该 word 必须被排除
  3. （no operator) 表示该word 是可选的，但是如果出现，相关性更高
  4. @distance 表示查询的多个单词之间的距离是否在 distance 之内，distance 的单位是字节

  5. 表示出现该单词时增加相关性

  6. < 表示出现该单词时降低相关性
  7. ~ 表示允许出现该单词，但是出现时相关性为负
    • 表示以该单词开头的单词， 如 lik* 表示可以时 lik like likes
  9. '' 表示短语

Query Expansion

MySQL 支持全文检索的扩展查询。可以在查询中使用 WITH QUERY EXPANSION 或 IN NATURAL LANGUAGE MODE WITH QUERY EXPANSION 可以开启 blind query expansion（automatic relevance feedback）。查询分为两个阶段

  1. 根据搜索的单词进行全文索引查询
  2. 根据第一阶段的分词再进行一次全文检索的查询
转载自:https://juejin.cn/post/7377062977647149095
评论
请登录