InnoDB存储引擎5-索引与算法

发表于   |   分类于   |  

InnoDB存储引擎索引概述

InnoDB常见索引B+树索引、全文索引、哈希索引。
B+树索引并不能找到一个给定键值的具体行。B+树索引能找到的只是被查找数据行所在的页，然后数据库通过把页读入到内存，再在内存中进行查找，最后得到要查找的数据。

数据结构与算法

二分查找法

PageDiretory中槽是按照主键顺序存放的，对于某一条具体记录的查询是通过page directory进行二分查找得到的。（我怀疑B+树也用到了二分查找法）。

二叉查找树和平衡二叉树

B+树

B+树的插入操作

##Ｂ＋树的删除操作

B+树索引

B+索引在数据库中有一个特点是搞扇出性，因此在数据库中，B+树的高度一般都是2~4层，这也就是说查找某一简直的行记录时最多只需要2到4次IO。当前一般的机械磁盘每秒至少可以做10次IO。数据库中B+树索引分为聚集索引和辅助索引。

##　聚集索引
InnoDB存储引擎表示索引组织表，即表中数据按照主键顺序存放。而聚集索引就是按照每张表的主键构造一棵B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。

辅助索引

对于辅助索引，叶子节点并不含行记录的全部数据。叶子节点除了包含键值意外，每个叶子节点中的索引行中还包含了一个书签。该书签来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据

B+树索引的分裂

索引管理

1
2
3
alter table 表名称 add  index|key 索引名 （列名，）
alter table 表名称 drop  index|key 索引名 
create/drop index  on 表名称

Show Index from

Fast Index Creation

Mysql5.5版本之前，DDL操作过程：

  • 首先创建一张新的临时表，表结构为通过命令alter table 新定义的结构。
  • 然后把原表中数据导入到临时表
  • 删除原表 更换表名
    InnoDB1.0开始支持 一种称为fast index creation的索引创建方式。索引创建时会阻塞表上的DML操作。
    对于辅助索引，会对表加上一个s锁。不用重建表，因次速度快很多。删除富足索引操作就更简单了，InnoDB存储引擎只需要更新内部视图，并将辅助索引的空间标记为可用，同时删除mysql数据库内部视图上对该表的索引定义即可。
    FIC常见过程对表上了S锁，因此只能对该表进行读操作，只限定于辅助索引，对于主键的创建和删除同样要创建新表。

    Online Schema Change

    最早由facebook实现的一种在线执行ddl的方式。可以有读写事务对表进行DDL操作。
    OSC是一个php脚本，因此其有一定的局限性。进行修改的表一定要有主键，且表本身不能存在外键和触发器。此外，允许set sql_bin_log = 0,因此所做的操作不会同步slave服务器，可能导致主从不一致的情况。

    Online DDL

    Mysql 5.6开始支持Online DDL。允许辅助索引创建的同事进行诸如Insert、update、delete这类DML操作。此外逼近是辅助索引，以下DDL操作都可以通过在线的方式进行操作
  • 改变自增长值
  • 天剑或删除外键约束
  • 列的重命名
1
2
3
# 新的alter table
alter table tbl_name Add index index_name (index_col_name)
algorithm = {default|inplace|copy} lock = {default|none|shared|exclusive}

algorithm 指定创建和删除索引的算法，cpoy表示按照mysql5.1版本之前的工作模式，即创建临时表的方式。inplace表示不需要创建临时表。default表示根据参数old_alter_table来判断，该参数默认值为off，表示采用inplace的方式。

lock部分为索引创建或删除时对表添加锁的情况，已有的选择为：

  • none：对目标表不添加任何锁
  • share：和fic类似，对目标表加上一个s锁
  • exclusive：对目标添加一个x锁
  • default：一次尝试none、share、exclusive模式

Online DDL的原理是在执行创建或者删除操作的同事，将insert、update、delete这类dml操作日志写入到一个缓存中，待完成索引创建后再将重做应用到表上，一次达到数据的一致性。
由于Online DDL在创建索引完成后再通过重做日志达到数据库的最终一致性，这意味着在索引创建过程中，sql优化器不会选择正在创建中的索引。

5.5 Cardinality

cardinality表示索引中不重复记录数量的预估值。cardinality/表中行数应尽可能的接近1。

##InnoDB存储引擎的cardinality统计
innoDB内部更新cardinality信息的策略为

  • 表中十六之一的数据发生过变化
  • sta_modified_counter>2 000 000 000
    默认InnoDB存储引擎对8个叶子节点进行采样，采样的过程如下：
  • 取得B+树索引中叶子节点的数量，记为A-
  • 随机去个B+树索引中的8个叶子节点，统计每个页不同记录的个数，记为P1，P2…P8
  • 根据采样信息给出cardinality的预估值
    当执行sql语句analyze table show table status、showindex 一集访问information_schema架构下的表tables和statistics会导致存储引擎重新计算索引的cardinality。P214

    5.6 B+树索引的使用

    联合索引

    覆盖索引

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

    没有命中覆盖索引，并且查询的数据量大于表的20%，优化器会选择聚集索引来查找数据。因此对于不能进行索引覆盖的情况，优化器选择辅助索引的情况是，通过辅助所以呢查找的数据是少量的。利用顺序读来替换随机读的查找

    索引提示 index hint

    use index 只是告诉优化器可以选择该索引，实际上优化器还是胡再根据自己判断进行选择。如果使用 force index 一定会使用索引。
    1
    2
    select * form t use index(a) where a =1 and b = 2;
    select * form t force index(a) where a =1 and b = 2;

Multi-Range Read 优化

Mysql5.6版本开始支持。
对于InnoDB和MyISAM存储引擎的范围查询和Join查询操作，MRR的工作方式如下：

  • 将查询得到的辅助索引键值存放于一个缓存中，这是缓存中的数据是根据辅助索引键值排序的。
  • 将缓存中的键值根据RowID进行排序。
  • 根据rowID的排序顺序来访问实际的数据文件
    MRR 优化有一下几个好处
  • MRR使数据访问变得较为顺序。在查询辅助索引时，首先根据得到的查询结果，按照主键进行排序，并按照主键顺序进行书签查找。
  • 减少缓冲池中页被替换的次数
  • 批量处理对键值的操作

Index condition pushdown 优化 P226

Mysql5.6开始支持。之前当进行索引查找时，首先根据索引来查找记录，然后再根据where条件过滤记录。ICP判断是够可以进行where条件的过滤，也就是将where的部分过滤操作放在存储引擎层。

哈希算法

InnoDB存储引擎中哈希算法

自适应hash索引想问见第二章

全文索引

倒排索引

全文检索通常使用代拍索引来实现。它在辅助表中存储了单次与单词自身在一个或多个文档中位置之间的映射。

  • inverted file index ，表现形式为{单次，单次所在文档的id}
  • full inverted index，其变现形式为{单次，（单次所在文档的id，在具体文档中的位置）}

InnoDB全文检索

innoDB存储引擎从1.2开始支持全文检索的技术。InnoDB中环将（documentID，Position）视为一个“ilist”。因此在全文检索表中，有两个列，一个是word字段，另一个是ilist字段，并且在word字段上有索引。此外，由于InnoDB在ilist字段中存放了position信息，故可以进行proximity search。InnoDB会批量对Auxiliary table进行更新，而不是每次插入后更新一次。查询是，首先将FTS index cache 中对应的word字段合并到 辅助表中，然后再进行查询。这个merge操作类似Inser buffer的功能，不同的是 inser buffer 是一个持久的兑现个，并且其是B+树结构。FTS index cache由红黑树排序后批量插入。
当数据库关闭时，cache中的数据会通过到磁盘的辅助表中，然而，数据库发生宕机时，未能将cache同步到磁盘上。那么下次重启数据库时，当用户对表进行全文检索时，InnoDB存储引擎会自动读取未完成的文档，然后进行分词操作，在激情分词的结果放入到FTS index cache。
innoDB存储引擎中，为了支持全文检索，必须有一个列和word进行映射，这个列被命名为为fts_doc_id,类型必须是 bigint unsigned not null，必须加 unique index。上述这些操作都会有innoDB存储引擎自己完成

InnoDB全文检索存在的限制

  • 每张表只能有一个全文检索的索引
  • 由多列组合而成的全文检索索引列必须使用相同的字符集和排序规则
  • 不支持没有单次界定符的预先 如 中文、 日语、韩语。
    不支持中文 还研究个毛