B+树索引
B+树索引类型
聚簇索引
InnoDB存储引擎表是索引组织表,即表中数据按照主键顺序存放。
聚集索引( clustered index)就是按照每张表的主键构造一棵B+树,同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。
每个数据页都通过一个双向链表来进行链接。
数据页上存放的是完整的每行的记录,索引页存放的仅仅是键值及指向数据页的偏移量,而不是一个完整的行记录。
聚集索引的存储并不是物理上连续的,而是逻辑上连续的，组织方式如下（物理存储上可以同样不按照主键存储。）
- 页通过双向链表链接,页按照主键的顺序排序
- 每个页中的记录也是通过双向链表进行维护的
二级索引/辅助索引
辅助索引( Secondary Index,也称非聚集索引),叶子节点并不包含行记录的全部数据。
辅助索引的叶子节点内容是主键的值。
什么是回表？
先搜索辅助索引树，得到ID的值为500，再到聚簇索引树搜索一次，获取这一行全部的数据，这个过程称为回表。
B+树索引的页分裂
对B+树节点进行更新或插入的时候，会导致页分裂。
更新聚簇索引列的代价很高，因为会强制InnoDB将每个被更新的行移动到新的位置。
当行的主键值要求必须将这一行插入到某个已满的页中时，存储引擎会将该页分裂成两个页面来容纳该行，这就是一次分裂操作。
基于聚簇索引的表插入新行，或者主键被更新导致需要移动行的时候，可能面临”页分裂（page split)“的问题。页分裂会导致表占用更多的磁盘空间。
索引的创建
mysql数据库对于索引的添加或者删除的这类DDL操作, MySQL数据库的操作过程为:
- 首先创建一张新的临时表,表结构为通过命令 ALTER TABLE新定义的结构。
- 然后把原表中数据导入到临时表。
- 接着删除原表。
- 最后把临时表重名为原来的表名。
若用户对于一张大表进行索引的添加和删除操作,那么这会需要很长的
时间。更关键的是,若有大量事务需要访问正在被修改的表,这意味着数据库服务不可用。
Fast Index Creation
InnoDB存储引擎从 InnoDB1.0x版本开始支持一种称为 Fast Index creation(快速索引创建)的索引创建方式——简称FIC。
对于辅助索引的创建, InnoDB存储引擎会对创建索引的表加上一个S锁。在创建的过程中,不需要重建表,因此速度较之前提高很多,并且数据库的可用性也得到了提高。
缺点：
- 由于FIC在索引的创建的过程中对表加上了S锁,因此在创建的过程中只能对该表进行读操作,此时数据库无法进行写操作。
- FIC方式只限定于辅助索引,对于主键的创建和删除同样需要重建一张表。
双写创建索引(Online Schema Change)
创建一个新表，把对旧表的更新插入操作也更新到新表，同时把旧表的数据进行迁移，实现方式可以是代码或者触发器，参考Online Schema Change
Online DDL
mysql5.6版本开始支持Online DDL，其允许辅助索引创建的同时,还允许其他诸如 INSERT、 UPDATE、DELETE这类DML操作。支持的操作如下：
- 辅助索引的创建与删除
- 改变自增长值
- 添加或删除外键约束
- 列的重命名
B+树索引的使用
联合索引
联合索引是指对表上的多个列进行索引。
用联合索引可以避免多一次的排序操作,因为索引本身在叶子节点已
经排序了。
最左前缀原则
B+树这种索引结构，可以利用索引的“最左前缀”，来定位记录。
最左前缀可以是联合索引的最左N个字段，也可以是字符串索引的最左M个字符。
前缀索引
InnoDB的索引会限制单独Key的最大长度为 767字节，超过这个长度必须建立小于等于 767 字节的前缀索引。
MySQL前缀索引能有效减小索引文件的大小，提高索引的速度。但是前缀索引也有它的坏处：MySQL不能在 ORDER BY 或 GROUP BY 中使用前缀索引，也不能把它们用作覆盖索引(Covering Index)。
需要再字符串列(varchar,char,text等)上进行查询的时候，需要进行全字段匹配或者前匹配,也就是=‘xxx’ 或者 like ‘xxx%’,想要提升查询效率需要建立前缀索引。
前缀索引选择性 以及如何确定前缀索引长度?
//todo
整理在sql优化中
覆盖索引
InnoDB存储引擎支持覆盖索引(covering index,或称索引覆盖),即从辅助索引中就可以得到查询的记录,而不需要查询聚集索引中的记录。
使用覆盖索引的一个好处是辅助索引不包含整行记录的所有信息,故其大小要远小于聚集索引,因此可以减少大量的IO操作。
优化器不选择辅助索引的情况
如果要求访问的数据量很小,则优化器还是会选择辅助索引,但是当访问的数据占整个表中数据的蛮大一部分时(一般是20%左右),优化器会选择通过聚集索引来查找数据。
因为顺序读要远远快于离散读。
ps 辅助索引的回表操作时离散的
对于不能进行索引覆盖的情况,优化器选择辅助索引的情况是,通过辅助索引
查找的数据是少量的。
这是由当前传统机械硬盘的特性所决定的,即利用顺序读来替换随机读的查找。
若用户使用的磁盘是固态硬盘,随机读操作非常快,同时有足够的自信来确认使用辅助索引可以带来更好的性能,那么可以使用关键字FORCE INDEX来强制使用某个索引。
1 | SELECT * FROM order_detail FORCE INDEX (order_id) |
索引下推(Index Condition Pushdown)
MySQL5.6开始支持的索引下推。
支持ICP之前，当进行索引查询时,首先根据索引来查找记录,然后再根据 WHERE条件来过滤记录。
支持ICP之后，MySQL数据库会在取出索引的同时,判断是否可以进行WHERE条件的过滤,也就是将WHERE的部分过滤操作放在了存储引擎层。
Multi-Range Read优化
MySQL56版本开始支持Multi-Range Read(MRR)优化。
Multi-Range Read优化的目的就是为了减少磁盘的随机访问,并且将随机访问转化为较为顺序的数据访问。
在查询辅助索引时,首先根据得到的查询结果,按照主键进行排序,并按照主键排序的顺序进行查找。
哈希索引
InnodB存储引擎使用哈希算法来对字典进行查找,其冲突机制采用链表方式。
自适应哈希索引
自适应哈希索引采用哈希表的方式实现。不同的是,这仅是数据库自
身创建并使用的,DBA本身并不能对其进行干预。
Innodb存储引擎会监控对表上二级索引的查找，如果发现某二级索引被频繁访问，二级索引成为热数据，建立哈希索引可以带来速度的提升。
倒排索引(全文检索)
1 | SELECT * FROM blog WHERE content like '%xxx%' |
根据B+树索引的特性,上述SQL语句即便添加了B+树索引也是需要进行索引的扫描来得到结果。类似这样的需求在互联网应用中还有很多。例如,搜索引擎需要根据用户输入的关键字进行全文查找,电子商务网站需要根据用户的查询条件,在可能需要在商品的详细介绍中进行查找,这些都不是B+树索引所能很好地完成的工作。
**全文检索是将存储于数据库中的整本书或整篇文章中的任意内容信息査找出来的技术。**它可以根据需要获得全文中有关章、节、段、句、词等信息,也可以进行各种统计和分析。
从 InnoDB1.2.x版本开始, InnoDB存储引擎开始支持全文检索。
倒排索引
全文检索通常使用倒排索引(inverted index)来实现。
倒排索引同B+树索引一样也是一种索引结构。它在辅助表( auxiliary table)中存储了单词与单词自身在一个或多个文档中所在位置之间的映射。这通常利用关联数组实现,其拥有两种表现形式:
- inverted file index,其表现形式为{单词,单词所在文档的ID}
- full inverted index,其表现形式为{单词,(单词所在文档的ID,在具体文档中的位置}
全文检索需要特殊的语法去查询，不能直接用like ‘%xxx%’