概述
InnoDB存储引擎支持以下索引:
- B+树索引
B+树索引是传统意义上的索引.B+树索引并不能找到一个给定键值的具体行,只能找到备查找数据行所在的页,然后把页读入内存,再在内存中查找 - 全文索引
- 哈希索引
InnoDB支持的哈希索引是自适应的,InnoDB存储引擎会根据表的使用情况自动为表生产哈希索引,不能人为干预是否在一张表中生成哈希索引
B+树
B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树
B+树的插入操作
| Leaf Page满 | Index Page满 | 操作 |
|---|---|---|
| false | false | 直接将记录插入到叶子节点 |
| true | false | 1. 拆分Leaf Page 2. 将中间的节点放入到Index Page中 3. 小于中间结点的记录放左边 4. 大于或等于中间结点的记录放右边 |
| true | true | 1. 拆分Leaf Page 2. 小于中间节点的记录放左边 3. 大于或等于中间节点的记录放右边 4. 拆分Index Page 5. 小于中间结点的记录放左边 6. 大于中间结点的记录放右边 7. 中间结点放入上一层Index Page |
不管怎么变化,B+树总会保持平衡.但是为了保持平衡对于新插入的键值可能会做大量的拆分页操作.因为B+树结构主要用于磁盘,页的拆分意味着磁盘操作,所以应该在可能的情况下尽量减少页的拆分操作,因此,B+数同样提供了类似平衡二叉树的旋转的功能
B+树索引
B+树做引在数据库中有一个特点是高扇出性,因此在数据库中,B+树高度一般都在2~4层,也就是说查找某一键值记录时最多只需要2~4次磁盘IO
B+树索引可以分为聚集索引和辅助索引.不管是聚集索引还是辅助索引,其内部都是B+树的,即高度平衡,叶子节点存放着所有的数据.聚集索引与辅助索引不同的是,叶子节点存放的是否是一整行的信息
聚集索引
InnoDB存储引擎表是索引组织表,即表中数据按照主键顺序存放,而聚集索引就是按照每张表的主键构造一棵B+树,同时叶子节点存放的即为整张表的行记录数据,也将聚集索引的叶子节点成为数据页.聚集索引的这个特性决定了索引组织表中数据也是索引的一部分
由于实际的数据页只能按照一棵B+树进行排序,因此每张表只能拥有一个聚集索引.
辅助索引
对于辅助索引,叶子节点并不包含行记录的全部数据.叶子节点除了包含键值以外,每个叶子节点中的索引行中还包含了一个书签,该书签告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据.由于InnoDB存储引擎表是索引组织表,因此InnoDB存储引擎的辅助索引的书签就是相应行数据的聚集索引键
辅助索引的存在并不影响数据在聚集索引中的组织,因此每张表上可以有多个辅助索引.当通过辅助索引来寻找数据时,InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获取指向主键索引的主键,然后再通过主键索引来找到一个完整的行记录
Cardinality值
概述
并不是在所有的查询条件中出现的列都需要添加索引.如果某个字段取值范围很窄,则完全没有必要,相反,如果某个字段取值范围很广,几乎没有重复,即属于高选择性,则此时使用B+树索引是最合适的
索引是否有高选择性可以通过SHOW INDEX结果中的列Cardinality值来观察.Cardinality值非常关键,表示索引中不重复记录数量的预估值.在实际应用中,Cardinality/n_rows_in_table应尽可能地接近于1.如果非常小,那么用户需要考虑是否还有创建这个索引的必要.故在访问高选择性属性的字段并从表中取出很少一部分数据时,对这个字段添加B+树索引是非常有必要的.
InnoDB存储引擎的Cardinality统计
数据库对Cardinality值的统计都是通过采样的方法来完成的.
在InnoDB存储引擎中,Cardinality统计信息的更新发生在两个操作中:INSERT和UPDATE.不可能每次发生INSERT和UPDATE时就去更新Cardinality信息,这样会增加数据库系统的负荷.
InnoDB存储引擎内部对更新Cardinality信息的策略为:
- 表中1/16的数据已发生过变化
- stat_modified_counter>2000000000
B+树索引的使用
联合索引
联合索引也是一棵B+树,不同的是联合索引的键值的数量不是1,而是大于等于2.
覆盖索引
优化器选择不适用索引的情况
多发生于范围查找,JOIN链接操作等情况下.
若用户有足够信心使用辅助索引可以带来更好的性能,那么可以使用关键字FORCE INDEX来强制使用某个索引
索引提示
MySQL数据库支持索引提示,显式地告诉优化器使用哪个索引.下面时两种可能需要用到INDEX HINT的情况:
- MySQL数据库的的优化器错误地选择了某个索引,导致SQL语句运行的很慢
- 某SQL语句可以选择的索引非常多,这时优化器选择执行时间的开销可能会大于SQL语句本身的时间开销
Mult-Range Read优化
Multi-Range Read(MRR)优化的目的是为了减少磁盘的随机访问,并且将随机访问转化为较为顺序的数据访问,这对于IO-bound类型的SQL查询语句带来性能极大的提升.MRR优化可适用于range,ref,eq_ref类型的查询
MRR优化有以下好处:
- MRR是数据访问变得较为顺序
在查询辅助索引时,首先根据得到的查询结果按照主键进行排序,并按照主键顺序进行书签查找 - 减少缓冲池中页被替换的次数
- 批量处理对键值的查询操作
对于InnoDB和MyISAM存储引擎的范围查询和JOIN查询操作,MRR的工作方式如下:
- 将查询得到的辅助索引键值存放于一个缓存中,这时缓存中的数据时根据辅助索引键值排序的
- 将缓存中的键值根据RowId进行排序
- 根据RowID的排序顺序来访问实际的数据文件
Index Condition Pushdown(ICP)优化
TODO
哈希算法
哈希表
InnoDB存储引擎中的哈希算法
InnoDB存储引擎使用哈希算法来对字典进行查找,其冲突机制采用链表方式,哈希函数采用除法散列方式.
自适应哈希索引
自适应哈希索引经哈希函数映射到一个哈希表中,因此对于字典类型的查找非常快速.但是范围查找就无能为力了.
全文检索
概述
全文检索是将存储于数据库中的整本书或整篇文章中的任意内容信息查找出来的技术.它可以根据需要获得全文中有关章节段句词等信息,也可以进行各种统计和分析
倒排索引
全文检索通常使用倒排索引来实现.倒排索引同B+树索引一样,也是一种索引结构,它在辅助表中存出来单词与单词自身在一个活多个文档中所在位置之间的映射.这通常利用关联数组实现.
InnoDB全文索引
TODO