【MySQL】2. 索引与算法

【MySQL】2. 索引与算法

索引是应用程序设计和开发的一个重要方面。若索引太多,应用程序的性能可能会受到影响。而索引太少,对查询性能又会产生影响。要找到一个合适的平衡点,这对应用程序的性能至关重要。

MySQL 和 InnoDB 的对应关系:

InnoDB 存储引擎支持以下几种常用的索引:B+树索引、哈希索引、全文检索

B+树索引:目前关系型数据库系统中查找最为常用和最为有效的索引,B+树索引构造类似于二叉树,根据键值对快速找到数据。

哈希索引:InnoDB的哈希索引是自适应的,引擎会根据表的使用情况自动生成哈希索引,不能人为干预是否在一张表中生成哈希索引。在聚集索引之上,数据库自己维护的一个表

全文检索:将存储在数据库中的整本书或整篇文章中的任意内容信息查找出来

1 .B+树索引:

B+树索引最为常见,也是在数据库中使用最频繁的一种索引。了解B+树之前,先了解 二分查找树、二叉查找树、平衡二叉树、B树:

二分查找法:也称为折半查找法,用来查找一组有序的记录数组中的某一记录。
二叉查找树:有序数组的 中序树,左节点小于根,右节点大于根。
平衡二叉树:在满足二叉查找树的基础上,满足任何节点的两个子树高度最大差为1.平衡二叉树在插入新的节点之后,需要通过左旋或者右旋恢复到 平衡二叉树
左旋示意图:以 privot + Y 为轴
B树:平衡多路查找树,(一颗m阶的B树(m叉树))
1. B树中所有节点的孩子节点数中最大值 称为B树的阶,记为M
2. 树中每个节点至多有M棵子树,如果定义了M,B树任何节点的子节点数量都不超过M
3. 若根节点不是终端节点,则至少有两个子树
4. 除根节点和叶节点外,所有点至少有m/2棵子树(上溢)
5. 所有的叶子节点都位于同一层

B+树由B树和索引顺序访问方法(ISAM,来自于MyISAM)演化过来。B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。

在B+树中,所有记录节点都是按键值的大小顺序存放在同一层的叶子节点中,由各叶子节点指针进行连接。

B+树插入,通过 拆分 leaf page 和 index page来实现平衡,但B+树是磁盘存储,拆分page,会带来资源消耗,一般优先通过旋转来实现平衡,旋转不能实现时,通过拆分page实现。

B+树删除,使用填充因子控制树的删除变化,50% 是填充因子的可设最小值。B+树的删除操作同样必须保证删除后叶子节点中的记录依然排序。

1.1 InnoDB中的 B+树索引:

B+树索引的实质就是B+树在数据库中的实现。但是B+索引在数据库中 高扇出。因此在数据库中,B+树的高度一般都在2~4层。一般的机械磁盘每秒做100次IO,2~4次的IO意味着查询时间只需要0.02~0.04秒、

B+ 树索引并不能找到一个给定键值的具体行。B+树索引能找到的只是被查找数据行所在的页。然后把页读入到内存,再在内存中进行二叉查找,最后得到要查找的数据。

注意:B+树中的B不是代表二叉(binary),而是代表平衡(balance),因为B+树是从最早的平衡二叉树演化而来,但是B+树不是一个二叉树。

数据库的B+ 树索引可以分为聚集索引(clustered index)和辅助索引(secondary index),不管是聚集索引还是辅助索引,内部都是B+树的,及高度平衡的,非叶子节点记录下一个叶子的位置,叶子节点存放着数据。

聚集索引和辅助索引不同的是,叶子结点存放着是否是一整行的信息。

1.1.1 聚集索引:

InnoDB存储引擎表是索引组织表,即表中数据按照主键顺序存放。

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

实际的数据只能按照一颗 B+树进行排序,因此每张表只能拥有一个聚集索引。
在多数情况下,查询优化器倾向于采用聚集索引。因为聚集索引能够在B+树索引的叶子节点上直接找到数据。查询器能够快速的发现某一范围的数据页需要扫描。

聚集索引的存储并不是物理上连续的,而是逻辑上连续的,主要是因为:
1. 页 和 每个页中的记录都是通过双向链表连接,不需要物理存储

聚集索引的另一个好处:对于主键的排序查找和范围查找速度非常快。叶子节点的数据就是用户所要查询的数据.

1.1.2 辅助索引:

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

InnoDB 存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键。然后再通过主键索引来找到一个完整的行记录。

辅助索引可以有多个。

1.1.3 B+树索引的管理:

0 . 索引管理:

索引的创建和删除可以通过两种方法:
Create/Drop Index index_id on table_name (id);
Create/Drop unique index index_id on table_name (id);

Alter Table t add key idx_id (id);
用户可以设置对整个列进行索引,也可以之所以部分前缀数据。。b(100)

可以通过Show index from table; 查看某个表上的索引情况。
Cardinality :非常关键的值,表示索引中唯一值的数目的估计值,如果与实际的行数差很多,那么用户需要考虑是否可以删除此索引、
$$优化器会根据这个值来判断是否使用这个索引,但是这个值并不是实时更新的,并非每次索引的更新都会更新该值,因为代价太大了。因此,该值是一个大概的值。

1 .B+树索引的分裂:

1. 若插入是随机的,则取页的中间记录作为分裂点的记录。
2. 若往同一方向插入的记录数量为5,并且目前一定定位到的记录(InnoDB 插入之前,先做定位,定位到的记录为待插入记录的前一条记录)之后还有3条记录,则分裂点的记录为定位到的记录后的第三条记录,  *否则*分裂点记录就是待插入的记录。???、

2 . Fast Index Creation:

MySQL 5.5 版本之前,MySQL 数据库对于索引的添加和删除这类的DDL操作,都需要迁表:
1. 首先,创建一个新的临时表,表结构为通过命令 ALTER TABLE 新定义的结构
2. 然后把原表的数据导入到临时表
3. 删除原表
4. 最后把临时表重命名为原来的表名
这个操作对于数据量较大的表是非常不友好的,而且影响使用。
注意:临时表的创建路径是通过参数 temdir 设置的,必须保证有足够的空间存放临时表。

InnoDB在 1.0.x版本开始支持 Fast Index Creation(FIC,快速索引创建)
对于辅助索引,
创建索引的时候,直接在表上添加一个S锁,
删除索引的时候,更新内部视图,将辅助索引的空间标记为可用,删除内部视图对索引定义。

FIC 方式只限定于辅助索引,对于主键的创建和删除同样需要重建一张表。

3 . Online Scheme Change (OSC在线架构改变):

由Facebook实现的一种在线执行DDL的方式,在事务的创建过程中,可以有读写事务对表进行操作,这提高了原有MySQL数据库在DDL操作时的并发性。

4 . Online DDL:

MySQL 5.6版本开始支持 Online DDL(在线数据定义)操作。其允许在辅助索引创建的同时,还允许其他诸如 insert、update、delete这类的DML操作,这极大地提高了MySQL数据库在生产环境中的可用性。
此外,不仅是辅助索引,以下的几类DDL操作都可以通过“在线”的方式操作:
1. 辅助索引的创建和删除
2. 改变自增长值
3. 添加和删除外键约束
4. 列的重命名

5. Cardinality 值:

什么时候需要添加B+树索引?
在访问高选择性的字段并从表中取出很少数据时,使用索引更合适

如果某个字段的取值范围很广,几乎没有重复,及属于高选择性,怎么确定索引的列是不是高选择性呢?
1. 对数据表的内容有认知,比如:性别列就是低选择的,身份证就是高选择的。
2. 通过Show Index 结果中的 Cardinality 查看,Cardinality 是一个预估值,表示索引列中不重复记录数量。 0 < Cardinality/n_rows_int_tabls < 1,在实际应用中,Cardinality 应该跟 n_rows_in_table 越接近越好。

在InnoDB中,数据库对于Cardinality 的统计通过采样(sample)方法完成。
更新的策略:表中1/16的数据发生了变化 / stat_modified_counter>2 000 000 000
默认InnoDB 对8个leaf Page进行采样:()
Cardinality = 叶子节点数量* (A1+A2+...+A8)/ 8


在数据库运行一段时间之后,可能Cardinality 为NULL,可能是建立了索引但是没有用到 或者 对两条基本一样的语句执行Explain,最终结果不一样,一个使用索引,一个使用全表扫描,这样,全表扫描的数据时正确的,说明索引数据有问题。这时应该做一次 Analyze table 的操作, 有时候对应用程序的核心表做 Analyze table操作,可以使优化器和索引更好的为你工作。

1.1.4 B+树索引的使用

应用场景:

OLTP(在线事务处理)和OLAP(在线分析处理)是我们常用的两种应用场景。

OLTP中,查询操作只查询小部分数据,而且业务总是查询、插入、更新、删除。这种情况下,建立B+树索引是合适的。
OLAP中,主要是查询表中的大量数据,根据结果分析,依赖于CPU性能,对于OLAP的复杂查询,涉及到多张表之间的连接操作,索引也是合适的,但是如果连接使用的是 Hash join 那么索引就不太重要了。不过在OLAP中,经常有对于时间字段进行索引的处理。
MySQL 从8.x只有开始使支持 Hash join,在之前都是使用 Nested Loop Join (NLJ,嵌套循环)实现。
NLJ是通过两层循环,用第一张表做Outter Loop,第二张表做Inner Loop,Outter Loop的每一条记录跟Inner Loop的记录作比较,符合条件的就输出。

NKJ 分为 SNLJ、INLJ、BNLJ:
SNLJ(Simple...):两层循环全量扫描两张表,笛卡尔积,次数是R * S,暴力/耗时
INLJ(Index...):在Inner Loop中扫描索引而不去扫描数据本身,但辅助索引要回表
BNLJ(Blocking...):使用了join buffer,提前读取Inner Loop所需要的记录到buffer

Hash join:分为构建阶段(build)、探测阶段(probe)  不使用索引
1.构建阶段:选择join连接中,空间小的表(不是行少,而是占用内存少),对join的值做hash 存储到内存中
2. 探测阶段:对另一个表每行的join字段做hash,与内存中的hash table做匹配

分析:每张表只扫描一次,匹配的时间是恒定的,非常高效,但是需要占用内存。
如果需要加载到内存中的表太大了,会使用磁盘空间,因为处理都是根据join列的哈希值判断的,所以可以一块一块的处理,在内存装不下的时候,A表的部分先加载到 Hash Table,然后通过对B表数据处理匹配,处理完成之后,再取A表的一部分处理,以为都是 hash,所以A 和 B 的是对应的关系。

联合索引:(覆盖索引、回表操作)

联合索引:对表上的多个列进行索引。
覆盖索引:从辅助索引中就可以查询到记录,而不需要查询聚集索引中的记录,好处是辅助索引不包含整行记录的所有信息,故其大小要远小于聚集索引,减少IO操作。Mysql5.0+
使用的场景:
1. 联合索引 (key1,key2,key3)
select key2 from table where key1 = xxx;
2. 统计数据量,不会再次查询聚集索引
3. 通过辅助索引查询到主键值

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

不使用索引的情况多发生在:范围查找(非聚集索引)、Join链接操作

范围查找:用户要选择的数据是整行信息,而辅助索引只能找到聚集索引,通过聚集索引在去找每一记录的信息,是离散读。如果访问的数据很小,可能会使用辅助索引,要是反问的数据较多(一般20%左右),就会使用聚集索引全表扫描、主要是因为IO操作较慢,所以会不使用辅助索引,如果有强制要求,可以通过 force index 来强制使用。

索引提示:(Index hint)语法: Use index

MySQL支持索引提示,显式的告诉优化器使用哪个索引。主要有两种场景可以需要:
1. 优化器错误选择了某个索引,一般不会出现
2. SQL可以选择的索引太多,优化器执行计划时间的开销可能大于 SQL 语句本身
如果用户明确知道 SQL 应该使用的索引,应该使用 force index 强制选择,而不是让优化器自己选(除非用户不确定)

Multi-Range Read 优化:

MySQL 从5.6开始支持 Mrr 优化,主要支持:range、ref、eq_ref。目的:
1. 将随机访问转化为较为顺序的数据访问,查询辅助索引将结果按主键排序
2. 减少缓冲池中页被替换的次数
3. 批量处理对键值的查询操作
4. 对于范围查询,拆分处理

对于 InnoDB 和 MyISAM存储引擎的范围查找和JOIN查询,MRR 的工作方式:
1. 将查询得到的辅助索引键值存放在一个缓存中,这时,缓存中的数据按照辅助索引排序
2. 将缓冲中的键值根据RowID进行排序
3. 根据RowID的排序顺序访问实际的数据文件(防止不断的扇出内存,缓冲池替换)

在对于多条件范围查找时,之前都是先按照A条件处理,然后从A条件得到的数据,再按照B条件处理,在使用MRR之后,对查询条件进行拆分,再进行查询(主要影响联合索引)

Multi-Range Read 在实际使用中,查询性能提升明显

ICP(Index Condition Pushdown)优化

MySQL 从5.6开始支持的一种根据索引进行查询的优化方式。(比如:联合索引)
不支持的情况:通过索引查询记录,再根据where条件过滤
支持之后:在通过索引查询记录的同时,通过where条件过滤,将where的处理放在了存储引擎层,减少了上层SQL层对记录的索取(fetch)

ICP优化支持 range、ref、eq_ref、ref_or_null类型的查询,当使用InnoDB和MyISAM存储引擎时,优化器选择 ICP 时,可以在执行计划列 Extra 中看到 Using index condition提示

2 . 哈希索引:

哈希算法是一种常见算法,时间复杂度为O(1),且不只存在于索引中,每个数据库应用中都存在该数据库结构。

2.1 哈希表

哈希表(Hash Table)也称为散列表,由直接寻址表改进而来。

直接寻址表:关键字 和 数据内容,一对一存储,占用太多内存
哈希表:hash + 关键字,通过对关键字做 hash 操作,得到哈希值,存储到一个哈希表上,发生哈希碰撞的时候,将同一个槽中的所有元素放到一个链表中.

哈希碰撞之后,怎么判断不一致?
在查询的时候,先通过哈希获得存储数据库的槽,然后获取链表,遍历equals得到正确的结果

在哈希函数的除法散列法中,通过取 k 除以 m 的余数,将关键字 k 映射到 m 个槽的某一个去, h(k) = k mod m

2.2 InnoDB中的哈希算法:

InnoDB 存储引擎使用哈希算法对字典进行查找,冲突使用链表方式,哈希函数采用除法散列方式。
对于缓冲池的哈希表来说,在缓冲池中的Page也都有一个chain指针,它指向相同哈希函数值的也。对于除法散列,槽的数量取值为略大于2倍的缓冲池页数量的质数。比如 innodb_buffer_pool_size 为10M,共有 640个16KB 的页,对于缓冲池内存的哈希表来说,应该分配640*2=1280个槽,但是由于1280不是质数,会选择 1399,在启动的时候分配1399个槽。
个人理解,不一定完全正确
InnoDB 存储引擎的缓冲池怎么查找其中的页呢?
InnoDB 存储引擎的表空间都有一个space_id,用户所以查询的应该是 某个表空间的某个连续的16KB 的页,即偏移量offset,InnoDB存储引擎将 space_id 左移20位,然后加上space_id 和 offset ,即 K= space_id << 20 +space_id +offset,然后通过除法散列到各个槽中???

2.3 自适应哈希索引:

自适应哈希索引采用哈希表实现,由数据库自身创建并使用。自适应哈希索引经哈希函数映射到一个表中。
对于字典类型的查找非常快,对于范围查找无能为力。

由 InnoDB 存储引擎控制,通过参数 innoDB_adapitive_hash_index禁用和启用,默认开启

3 . 全文检索:

全文检索(Full-Text Search) 是将存储在数据库中的整本书或整篇文章中的任意内容信息查找出来的技术。
之前的MySQL中,InnoDB不支持全文检索技术,MyISAM支持全文检索。InnoDB 从1.2.x 开始,开始支持全文检索,其支持MyISAM存储引擎的全部功能,并且还支持其他的一些特性。

全文检索通常使用倒排索引(inverted index)来实现,倒排索引也是一种索引结构。它在辅助表中存储了单词和单词自身在一个或多个文档中所在位置之间的映射,通常有两种表现形式:
inverted file index, 表现形式为 { 单词,单词所在的文档的 ID }
full inverted index, 表现形式为 { 单词,(单词所有的文档ID,文档中的位置)}

通过单词就能查询到有该单词的多个文档。

3.1 InnoDB全文索引:

InnoDB 存储引擎从1.2.x版本开始支持全文检索技术,采用 full inverted index的方式。在InnoDB中,将(DocumentId,Position)视为一个“ilist”。因此在全文检索的表中,有两个列,word 和 ilist。并且在 word上设有索引。由于ilist 字段存放了 Position 信息,故可以进行 Proximity Search (临近搜索),而 MyISAM 不支持该特性

当前的 InnoDB 存储引擎的全文检索还存在以下的限制:
1. 每张表(文档表)只能有一个全文检索的索引
2. 由多列组合而成的全文检索的索引列必须使用相同的字符集和排序规则
3. 不支持没有单词界定符(delimiter)的语言,如中文、日语、韩语等

3.2 全文检索:

MySQL 数据库支持全文检索(Full-Text Search)的查询。
通过Match()...Against()语法支持全文检索的查询,Match 指定了需要被查询的列,Against指定了使用何种方法查询。
1. Natural Language : 默认模式,使用倒排索引,match通过相关性降序排序。
     stopword 不查询,经常出现的词,比如 the  a  的 是 等。
     word 的长度应该大于 3 小于 84
2. Boolean : 允许使用 in boolean mode 修饰符来进行全文检索,当使用修饰符时,查询字符串的前后字符有特殊的含义。
    +word 表示单词必须出现  -word 表示单词不能出现   " 表示短语
3. Query Expansion :支持全文检索的扩展查询,通常出现在 查询的关键词太短的时候

参考书籍:
MySQL技术内幕InnoDB存储引擎第2版.pdf   姜承尧
0 0 vote
Article Rating
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments