当前位置: 首页>数据库>正文

innodb 索引类型 方法怎么选 innodb的索引有几种

索引

对于索引的使用有个误区,并不是越多越好,也不是在有性能问题的时候才想起来要dba加个索引,应该是在最初表设计的时候就考虑到该表的使用场景,设计好索引。

索引的存在就是为了减少磁盘io次数,磁盘io是数据库检索过程中最耗时的部分。

innodb中常见的有三种索引,B+树、倒排索引、哈希索引,其中哈希索引是自适应的,不可人为干预。

 

B+树

B+树是为磁盘或者其他存储辅助设备设计的一种多路平衡查找树,B是balance的意思,目的是为了减少IO。

 

B树

B树是一种平衡的多分树,通常我们说m阶的B树,它必须满足如下条件:

  • 每个节点最多只有m个子节点
  • 每个非叶子节点(除了根)具有至少⌈ m/2⌉子节点
  • 如果根不是叶节点,则根至少有两个子节点
  • 具有k个子节点的非叶节点包含k -1个键
  • 所有叶子都出现在同一层

一个B树的结构如下:

innodb 索引类型 方法怎么选 innodb的索引有几种,innodb 索引类型 方法怎么选 innodb的索引有几种_mysql,第1张

 

B树高度

一棵含有n个总关键字数的m阶(B树中一个节点的子节点数目的最大值称为阶)的B树的最大高度是:

证明过程如下:

innodb 索引类型 方法怎么选 innodb的索引有几种,innodb 索引类型 方法怎么选 innodb的索引有几种_聚簇索引_02,第2张

 

 

B+树

B+树由B树变形而来,是为了满足外存设备的需求。它必须满足以下条件:

  • 有m个子树的中间节点包含有m个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引
  • 所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)
  • 所有的非叶子结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字。 (而B 树的非终节点也包含需要查找的有效信息)

一个B+数的结构如下:

innodb 索引类型 方法怎么选 innodb的索引有几种,innodb 索引类型 方法怎么选 innodb的索引有几种_mysql_03,第3张

 

用B+树做索引的原因

  • B+树索引效率高:B+树非叶子节点不存储实际数据,所以每个节点能存储更多的关键key信息,一次性读入内存的关键key就越多,相当于减少了io次数
  • B+树查询效率稳定:所有数据存储在叶子节点,叶子节点的高度都一样,所以查询耗时均衡,不会像B-树一样因为数据所在节点的高度而影响耗时
  • B+树范围查询更方便:B+树叶子节点构成双向链表,所以仅需要进行链表遍历就可以进行范围查询,而B-树则需要从root节点重新查询

 

在真实的数据库中,数据量几十万和几千万的表,B+树索引层高也就3-4层,所以如果通过B+树索引,几十万的数据量和几千万的数据量查询效率不会相差太大,因为都是3次io

 

聚簇索引

聚簇索引(clustered index)就是按照每张表的主键所建立的一棵B+树,所以每张表只能有一个聚簇索引。

 

查询优化器会尽量选择采用聚簇索引来检索,因为聚簇索引能够在B+树叶子节点直接找到目标数据,由于叶子节点数据之间是靠双链表连接,所以能很方便的进行范围查询。

 

辅助索引

也成为非聚簇索引(secondary index),与聚簇索引最大的不同在于,辅助索引叶子节点保存的是聚簇索引,关系如下:

innodb 索引类型 方法怎么选 innodb的索引有几种,innodb 索引类型 方法怎么选 innodb的索引有几种_mysql_04,第4张

 

所以,如果通过辅助索引来检索,过程就是这样的:先通过辅助索引找到聚簇索引,在通过聚簇索引找到实际数据(这个过程称为回表)。如果辅助索引和聚簇索引层高都是3,那么通过辅助索引检索就需要6次io,而通过聚簇索引,只需要3次,这也是为什么在实际应用中应该多多使用聚簇索引。

 

Cardinality

cardinality的值非常关键,优化器会根据该值来决定是否要走这索引。可以使用show index from table xxx命令来查看。它表示索引中唯一值的估计,它与总行数的比值应该接近于1,如果比值很小,那么应该删除该索引。

 

它的计算方式:随机对8个叶子节点进行分析然后更新。更新cardinality的策略如下:

  • 表1/16分之一的数据已经发生过变化
  • stat_modified_counter(发生变化的次数)> 20亿

也可以手动更新:analyze table xxx,如果表很大,该操作会比较耗时,生产核心库需要谨慎操作。

所以,这个值的并不是特别准确,因为它的计算方式是随机采样的。

 

cardinality指示了哪些列适合建来建B+树索引,那些不重复的、没有范围的、散列的列才适合建索引。工作中经常看到有同事会在enum类型的列上建索引(也不能作为联合索引的第一项),这是不对的,因为这些列的取值是重复的、范围恒定的、聚集的,建的B+树分叉太少,层数太高,长的很像链表,大大加大了io次数,走这些索引会增大耗时,也许超过全表扫描。

 

联合索引

联合索引指的是对表上的多个列进行索引,单个索引只针对于一个列,原理和单个索引一模一样,示例如下:

innodb 索引类型 方法怎么选 innodb的索引有几种,innodb 索引类型 方法怎么选 innodb的索引有几种_聚簇索引_05,第5张

 

联合索引有个好处是:第二个key做了排序处理。所以,如果结果集需要根据第二个key做排序,走联合索引可以减少一次内存排序的操作,可以提升查询效率。

 

索引覆盖

如果能够从辅助索引中就能获取到目标记录,不需要进行回表操作(不需要检索聚簇索引),那么这个行为就称为索引覆盖。

 

索引覆盖有两个好处:

  • 不需要回表:减少了聚簇索引检索的时间
  • 优化统计查询count( ):由于辅助索引保存的是聚簇索引,所以它的大小远远小于聚簇索引,也就是辅助索引一个叶子节点的数据页里保存的行数更多,在进行统计查询时通过辅助索引更能够减少磁盘io。

 

对于统计查询count( )如果不带where条件,myisam的效率远远大于innodb,因为myisam只支持页级锁,所以它有行数计数器,那么它的结果返回速度与表大小无关,查询耗时也可以忽略不计;而innodb支持行锁并且由于MVCC存在,每次count( )都需要对每行进行判断是否对当前事务可见,所以效率很低。

 

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

明明你在某些列上建了索引,并且你的查询条件中也使用了这些列,但是解释器告诉你他走了全表扫描,也就是使用了聚簇索引。这种情形有可能是由以下两种情况引起的:

  • 索引不合理:参考上面分析过的cardinality。
  • 范围查询、join连接:如果要查询的数据量占据总表的20%时,优化器会选择全表扫描。虽然可以通过辅助索引能够顺序的查出聚簇索引,效率很高,但是再根据聚簇索引去查询具体数据时,就变成了随机访问磁盘,通过上面的磁盘分析可以知道该操作会大大降低io效率,所以优化器会选择直接顺序的全表扫描。(这里的顺序依然是逻辑上的顺序,不可能做到全部数据是物理磁盘上的连续。innodb是按照区来分配空间的,每个区1M,一次分配连续的1-5个区,这里的连续是指物理上的连续,但是不可能做到所有数据都是物理上连续的,因为那样做的成本太高了)。

 

索引提示

索引提示的意思就是你显示的告诉优化器使用哪个索引,有两种情况:

  • 在有多个可使用索引的情况下,你认为优化器选择的那个不是最优的,你可以提示或者强制优化器使用某个索引
  • 在可选择的索引非常多的情况下,优化器选择执行计划的耗时可能都比执行脚本本身。这时,dba或者研发需要显示的告诉优化器使用哪个索引

上面两种情况都告诉我们,建太多索引不但不能提升效率,还有可能降低效率,此外,innodb还会花资源来维护索引,进一步降低性能。

 

索引提示有两种语法:

  • select * from table xx use index(xxx) where xx=xx : 这种方式只是提示优化器可以选择该索引,但是优化器有自己的想法,最终的执行计划如何取决于优化器的选择
  • select * from table xx force index(xxx) where xx=xx : 这种方式是告诉优化器把自己的想法收起来,乖乖按照我指定的索引执行,这里的好处是优化器不用在耗费时间去在多个索引中找一个最优的

 

倒排索引

通过上面的分析可以得知,等值查询、范围查询、like的前缀查询(like xxx%)等都可以利用到B+树的高效优点,但是对于like %xxx% 的模糊查询,B+树无能为力。倒排索引(inverted index)的引入就是为了弥补这个innodb在这个场景的不足。

 

数据结构

通过一张辅助表(auxiliary table)来存储关键字和关键字在一个或多个文档中所在位置的映射,有两种表现形式:

  • Inverted file index:(key,key所在文档的id)
  • Full inverted index:(key,(key所在文档的id,在文档中的偏移量))

Full inverted index 不仅存了文档id还存了偏移量,所以它占更多的存储空间,但是能更快的定位实际位置。这两种方式都是将一篇没有结构的文档转换为结构化的数据,相当于为每个词都建立了索引,从而可以做到全文的搜索。

 

全文检索

为了提高并发性,在innodb存储引擎中共有6张auxiliary table,每张表根据key的latin编码进行分区。为了获取key的latin编码,首先需要进行分词,分词的操作是在插入的事务提交后完成的。英文分词很简单,根据空格就可以,而中文分词有较多的算法,并且比较复杂还会有二义性,所以innodb不支持中文的全文检索,不过innodb5.7之后提供了ngram全文检索插件,用来支持中文分词。使用方式如下:

1、在mysql配置文件中设置分词的大小

ngram_token_size=2

分词越小,索引占用空间越大。

2、添加全文索引

alter table xx add fulltext index testfulltext(clumn1,clumn2) with PARSER ngram

 

因为auxiliary table是持久的表,并且存在磁盘上,所以为了提高性能,innodb引入了全文检索索引缓存(FTS index cache),其结构是一个红黑树。由于是内存和磁盘的关系,所以此处会涉及缓存有效及宕机恢复等问题,不做过多介绍,只需知道innodb利用缓存提升了检索性能。

 

innodb的全文检索有以下限制:

  • 每张表只能有一个全文检索索引
  • 由多个列组成的全文检索索引必须使用相同的字符集和排序规则
  • 不支持没有单词界定符(delimiter)的语言,如汉语、日语、韩语等,但可以使用ngram插件来解决

 

检索模式

innodb 使用全文检索的语法为:

select * from xx where match(clumn1,clumn2) against('key' in xxx mode)

 

innodb会将在where 条件中使用match( )函数的查询结果根据相关性进行降序排列,相关性是一个非负浮点数,0表示没有任何相关性,其计算依据如下:

  • key是否在文档中出现
  • key在文档中出现的次数
  • key在索引列中的数量
  • 包含该key的文档的数量

 

innodb支持四种检索模式

  • nature language : innodb默认的全文检索模式。所以查询时候可以省略mode修饰,直接使用select * from xx where match(clumn1,clumn2) against('key')
  • boolean : 更为复杂查询模式,表示待查询key前后的操作符有特殊含义,支持的操作符如下:
  • + : 该key必须存在
  • - : 该key必须不存在
  • (no operator) : 该key是可选的,但是如果出现,相关性会更高
  • @distance : 表示多个查询的key的距离是否在distance范围之内,单位是字节。'"dog cat"@30' IN BOOLEAN MODE表示单词dog和cat之间的距离需要在30个字节之内
  • > : 出现该key时增加相关性
  • < : 出现该key时降低相关性
  • ~ : 出现该key时相关性为负(全文检索允许出现负相关性)
  • * : 出现以该key为前缀的词
  • " : 表示短语
  • query expansion : 全文检索的扩展查询

哈希索引

当服务器内存100多G甚至更大时候,想要找到一个被缓存的页,虽然内存中io速度很快,但也不能每次都要通过遍历的方式来查找,那是憨憨的做法。这时候需要对于字典操作只需要O(1)的哈希算法。

哈希算法

时间复杂度为O(1)的常见的简单的算法,就是将k个关键字映射到m个槽的某一个去,即k mod m,如果产生碰撞就采用链表法拉出一个链表。查询时候如果发现链表就进行遍历,此时遍历的数量会大大降低。

这里的链表法和HashMap的处理碰撞的方式如出一辙,只不过jdk1.8之后,HashMap引入了红黑树,当链表长度大于8后就转换为红黑树,这样再次降低了碰撞后的查询时间复杂度,从O(n)降到O(log n)。不过增加了操作的复杂度,因为增加了红黑数的左旋和右旋,还有链表转红黑树和红黑树转链表。但是总体性能1.8优于1.7。

自适应哈希索引

innodb中的哈希索引由mysql自身创建和管理,dba和研发不能进行干预,所以说它是自适应的。通过命令SHOW ENGINE INNODB STATUS可以看到当前自适应哈希索引的使用状况。


https://www.xamrdz.com/database/66b1921965.html

相关文章: