美文网首页
5-索引与算法

5-索引与算法

作者: 加夕 | 来源:发表于2019-03-21 18:03 被阅读0次

1.InnoDB存储引擎索引概述

InnoDB支持以下几种常见的索引:

  • B+树索引:传统意义上的索引,目前关系型数据库系统中查找最为常用和最为有效的索引。B+树索引并不能找到一个给定键值的具体行,只能找到数据行所在的页,然后通过把页读入到内存,再在内存中进行查找,最后得到要查找的数据。
  • 全文索引
  • 哈希索引:自适应的,InnoDB会根据表的使用情况自动为表生成哈希索引,不能人为干预是否在一张表中生成哈希索引。

2.数据结构预算法

①二分查找法(binary search)

也称为折半查找法,基本思想是:将记录按有序化(递增或递减)排列,在查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要的元素值小于该中点元素,则将待查序列缩小为左半部分,否则为右半部分。通过一次比较,将查找区间缩小一半。

每页Page Directory中的槽是按照主键的顺序存放的,对于某一条具体记录的查询,是通过对Page Directory进行二分查找得到的。

②二叉查找树和平衡二叉树

B+树是通过二叉查找树,再由平衡二叉树,B树演化而来。

二叉查找树:左子树的键值总是小于跟的键值,右子树的键值总是大于根的键值。

若想最大性能地构造一颗二叉查找树,需要这棵二叉查找树是平衡的,从而引出新的定义——平衡二叉树,或称为AVL树。

平衡二叉树:首先符合二叉查找树的定义,其次必须满足任何节点的两个子树的高度最大差为1.

对一颗平衡树的维护是有一定开销的,不过平衡二叉树多用于内存结构对象中,因此维护的开销相对较小。

3.B+树

B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在B+树中,所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上,由各叶子节点指针进行连接。

例:B+树高度为2,每页可存放4条记录,扇出(fan out)为5

①B+树的插入操作

基础:

依次插入:28、70、95

可以看到,不管怎么变化,B+树总是会保持平衡。但是为了保持平衡对于新插入的键值可能需要做大量的拆分页操作。因为B+树结构主要用于磁盘,页的拆分意味着磁盘的操作,所以应该在可能的情况下尽量减少页的拆分操作,因此,B+树同样提供了类似于平衡二叉树的旋转功能。

如插入70时,实际是如下情况:

②B+树的删除操作

填充因子:50%是填充因子可设的最小值

基础:

依次删除:70、25、60

4.B+树索引

B+树索引的本质是B+树在数据库中的实现。但是B+索引在数据库中有一个特点是高扇出性,因此在数据库中,B+树的高度一般都在2~4层,也就是说查找某一键值的行记录时最多只需要2到4次IO。

B+树索引分为聚集索引和辅助索引,内部都是B+树的,叶子节点存放着所有的数据。聚集索引和辅助索引不同的是,叶子节点存放的是否是一整行的信息。

①聚集索引(clustered index)

聚集索引就是按照每张表的主键构造一棵B+树,同时叶子节点中存放的即为整张表的行记录数据,也将聚集索引的叶子节点称为数据页。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同B+树结构一样,每个数据页都通过一个双向链表来进行链接。

由于实际的数据页只能按照一棵B+树进行排序,因此每张表只能拥有一个聚集索引。

②辅助索引(secondary index)

也称为非聚集索引。叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外,每个叶子节点中的索引行中还包含了一个书签,该书签用来告诉InnoDB哪里可以找到与索引相对应的行数据。由于InnoDB表是索引组织表,因此InnoDB的辅助索引的书签就是相应行数据的聚集索引键。

辅助索引的存在并不影响数据在聚集索引中的组织,因此每张表上可以有多个辅助索引。

当通过辅助索引寻找数据时,假设辅助索引树的高度为3,聚集索引树的高度同样为3,查找一个完整行数据所在的页需要6次逻辑IO访问。(先遍历辅助索引树找到指定主键,再通过主键对聚集索引树查找)

5.Cardinality值

并不是在所有的查询条件中出现的列都需要添加索引。对于生命时候添加B+树索引,一般经验是,在访问表中很少一部分时使用B+树索引才有意义。

对于性别字段、地区字段、类型字段,它们可取值的范围很小,称为低选择性。按性别查询时,得到的结果可能是该表50%的数据,这时添加B+树索引是完全没有必要的。相反如果某个字段的取值范围很广,几乎没有重复,即属于高选择性,则此时使用B+树索引是最适合的。例如,对于姓名字段。

怎样查看索引是否是高选择性的呢?可以通过show index from table结果中的列Cardinality来观察。Cardinality表示索引中不重复记录数量的预估值,注意这不是一个准确值。实际应用中,Cardinality/n_rows_in_table应尽可能地接近1.如果非常小,那么用户需要考虑是否还有必要创建这个索引。

6.B+树索引的使用

①联合索引

联合索引本质上来说也是一棵B+树,不同的是联合索引的键值的数量不是1,而是大于等于2。

如鉴定两个整型的列a、b组成联合索引:

B+树索引先按第一个列a来排序,列a相同的再按列b来排序。所以where a=xx and b=xxx和where a= xx 都可以使用(a,b)联合索引,但是where b=xxx就不可以使用这棵B+树索引了。

联合索引的好处是已经对第二个键值进行了排序处理。

联合索引(a,b,c)

可以直接通过联合索引得到结果:

select ... from table where a=xxx order by b

select ... from table where a=xxx and b=xxx order by c

联合索引不能直接得到结果,还需要执行一次filesort排序操作,因为索引a,c并未排序:

select ... from table where a=xxx order by c

②覆盖索引

或称为索引覆盖,即从辅助索引中就可以得到查询的记录,而不需要查询聚集索引中的记录。(查询的列都是辅助索引列)

使用覆盖索引的好处:辅助索引不包含整行记录的所有信息,故其大小要远小于聚集索引,因此可以减少大量的IO操作。

辅助索引包含了主键信息,因此其叶子节点存放数据为(primary key1,primary key2,...,key1,key2,...)。下列语句都可以仅使用一次辅助联合索引来完成查询:

select key2 from table where key1=xxx;

select primary key2,key2 from table where key1=xxx;

select primary key1,key2 from table where key1=xxx;

select primary key1,primary key2,key2 from table where key1=xxx;

覆盖索引另一个好处是对某些统计问题而言的。

例:buy_log,辅助索引userId:userId, userId_2: (userId, buy_date)

select count(*) from buy_log;//使用userId索引

select count(*) from buy_log where buy_date>='2011-01-01' and buy_date<'2011-02-01';//使用userId_2索引

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

用辅助索引范围查询,且数据量占整个表蛮大一部分时(20%左右),优化器会通过聚集索引来查找数据(表扫描)。

因为辅助索引上没有整行数据,如果对辅助索引查询到指定主键后,还需要一次查聚集索引来查找整行数据的信息。虽然辅助索引中数据是顺序存放的,但再一次进行书签查找的数据则是无序的,因此变为了磁盘上的离散读操作。但是离散读是远远慢于顺序读的。

可以强制使用 force index 来强制使用某个索引,如果认为使用辅助索引可以带来更好的性能,可以使用force index。

如:select * from orderDetails force index(orderId) where orderId > 10000 and orderId < 102000;

7.全文检索

B+树索引对于 like ‘xxx%’是支持的,但是对于 like ‘%xxx%’就需要进行索引的扫描来得到结果了。

全文检索是将存储于数据库中的整本书或整篇文章的任意内容信息查找出来的技术,它可以根据需要获得全文中有关文章、节、段、句、词等信息,也可以进行各种统计和分析。

InnoDB 1.2x版本开始,InnoDB存储引擎开始支持全文索引,其支持MyISAM存储引擎的全部功能,并且还支持其他的一些特性。

①倒排索引(inverted index)

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

  • inverted file index,其表现形式为{单词,单词所在文档的ID}
  • full inverted index,其表现形式为{单词,(单词所在文档的ID,在具体文档中的位置)}

如:


②InnoDB全文检索

InnoDB采用 full inverted index的方式。

示例:

create table fts_a(FTS_DOC_ID bigint unsigned auto_increment not null, body text, primary key(FTS_DOC_ID));

插入数据

create fulltext index idx_fts on fts_a(body);

set global innodb_ft_aux_table='cs/fts_a';

select * from information_schema.INNODB_FT_INDEX_TABLE;

当前InnoDB存储引擎的全文检索还存在以下的限制:

  • 每张表只能有一个全文检索的索引
  • 由多列组合而成的全文检索的索引列必须使用相同的字符集与排序规则
  • 不支持没有单词界定符的语言,如中文、日语、汉语等。

③全文检索

MySQL数据库支持全文检索(full-text-search)的查询,语法为:

相关文章

网友评论

      本文标题:5-索引与算法

      本文链接:https://www.haomeiwen.com/subject/eficvqtx.html