InnoDB----第五章 索引与算法

第5章 索引与算法

---

​ 索引是应用程序设计和开发的一个重要方面.如果索引太多,程序的性能可能会受到影响.而索引太少,对查询性能会产生影响.

​ 以下分别是使用聚集索引,不使用索引,使用辅助索引对查询的响应时间对比:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-au4YRkjT-1575942237207)(http://benjaminlee.cn:8989/hello/images/1573546172190.png)]

1. InnoDB存储引擎索引概述

InnoDB支持以下常见索引:

• B+树索引
• 全文索引
• 哈希索引

​ InnoDB存储引擎支持的哈希索引是自适应的,InnoDB存储引擎会根据表的使用情况自动为表生成哈希索引,不能人为干预是否在一张表中生成哈希索引.

​ B+树索引就是传统意义上的索引,这是目前关系型数据库中查找最为常用和最为有效的索引.B+树索引的构造类似于二叉树,根据键值快速找到数据.B+树的B代表的是平衡而不是二叉.

2. 数据结构与算法

(1). 二分查找法

(2). 二叉查找树和平衡二叉树(avl树)

​ 这里只看avl树,另外两个是非常基础的数据结构和算法.

C语言实现:

//AVL平衡树 
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define MALLOC(node, type) 	if(!(node = (type *)malloc(sizeof(type)))){		\
								printf("Can\'t malloc!\n");					\
								return NULL;								\
							}
#define MAX(x, y) (((x) > (y))?(x):(y))

typedef struct node{
	int data;
	int height;
	struct node *left ;
	struct node *right;
}avltree;

//高度
int height(avltree *root){
	if(root == NULL)
		return -1;
	else
		return root->height;
}

// 右旋转
// 就是旋转后以左子树为根
// 先将左子树的右节点作为当前根的左节点
// 然后以左子树为根,将原先的根填入刚刚空出来的右节点
avltree *rotate_r(avltree *root){
	avltree *root1 = root->left;
	root->left = root1->right;
	root1->right = root;
	root->height = MAX(height(root->left), height(root->right)) + 1;
	root1->height = MAX(height(root1->left), height(root1->right)) + 1;
	return root1;
} 

// 左旋转
avltree *rotate_l(avltree *root){
	avltree *root1 = root->right;
	root->right = root1->left;
	root1->left = root;
	root->height = MAX(height(root->left), height(root->right)) + 1;
	root1->height = MAX(height(root1->left), height(root1->right)) + 1;
	return root1;
} 

//左右旋转
avltree *rotate_lr(avltree *root){
	root->right = rotate_l(root->right);
	return rotate_r(root);
} 

//右左旋转
avltree *rotate_rl(avltree *root){
	root->left = rotate_r(root->left);
	return rotate_l(root);
} 

//插入
avltree *tree_insert(avltree *root, int data){
	if(root == NULL){
        // 插入节点的逻辑
		MALLOC(root, avltree);
		root->data = data;
		root->left = root->right = NULL;
	}else if(data == root->data){
        // 不允许重入插入相同的节点
		printf("Find a same node in this avltree!\n");
	}else if(data < root->data){
        // 向左寻找空位
		root->left = tree_insert(root->left, data);
		// 插入过后检查左右子树的高度
        // 高度差大于1时,进行旋转的判断
		if(height(root->left) - height(root->right) == 2){
            // 如果插入的节点是高的一侧子树(左子树)的最对侧子节点(左子树的右子树的右节点),进行一次复合旋转(先对左子树进行左旋,然后对根进行又算)
            // 否则进行单次旋转(右旋)
			if(data < root->left->data){
				root = rotate_r(root);
			}else if(data > root->left->data){
				root = rotate_lr(root);
			}
		}
	}else if(data > root->data){
		root->right = tree_insert(root->right, data);
		
		if(height(root->right) - height(root->left) == 2){
			if(data > root->right->data){
				root = rotate_l(root);
			}else if(data < root->right->data){
				root = rotate_rl(root);
			}
		}
	}
	root->height = MAX(height(root->left), height(root->right)) + 1;
	return root;
}

​ 平衡二叉树多用于内存结构对象中.

3. B+树

参考博客:【数据结构】初入数据结构中的B类树（B Tree , B+ Tree）

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

​ 内部节点并不存储真正的信息，而是保存其叶子节点的最小值作为索引。每次插入删除都进行更新(此时用到parent指针)，保持最新状态。

​ 简单解释一下插入时的情况，根据插入值的大小，逐步向下直到对应的叶子节点。如果叶子节点关键字个数小于2t，则直接插入值或者更新卫星数据；如果插入之前叶子节点已经满了，则分裂该叶子节点成两半，并把中间值提上到父节点的关键字中，如果这导致父节点满了的话，则把该父节点分裂，如此递归向上。所以树高是一层层的增加的，叶子节点永远都在同一深度。

​ 插入过程中,一层插满才会进行分裂.也就是说如果插入节点没有空闲位置,但是相邻节点有,那么会进行类似旋转的操作.尽可能减少页的拆分和尽可能降低树的层数.

(1). B树

一个m阶的B树要有以下几个特征:

1. 根节点至少有两个子女(本身节点存储数据,如果存储不下分为两个子节点,分别和根节点连接)
2. 每个中间节点至少有 m/2 个孩子,至多有 m 个()
3. 每一个叶子节点都有 m/2-1 到 m-1 个元素
4. 所有叶子节点在同一层(平衡,旋转操作来保证)
5. 叶节点中的元素是顺序的,父节点索引域分割了子树,并且父节点中存储了数据域,数量较索引域小一

(2). B+树

B+树是B树的变种，其定义基本与B树相同,但有以下不同点:

• 非叶子节点的字数指针和索引数相同,而B树要多一
• 子树指针指向的子树中所有数据域或者索引域都要大于当前指针对应的索引,小于下一个索引
• 所有非叶子节点的索引域都来自子节点的数据域或者索引域,是其中的最大值或者最小值
• 所有非叶子节点都只被用来充当索引,数据都被保存在叶子节点中
• 所有叶子节点上的数据都有两个链指针,分别指向上一个和下一个数据,构成双向链表

(3). B+树小特性

​ 因为B+树的定义中，所有的非叶子结点的关键字，都会继承至其中孩子结点中，是其孩子结点元素的最大值或最小值，所以就造成了一个特性，根结点的最小值，可能是整棵树的最小值。根结点的最大值可能是整棵树的最大值

(4). 文件系统中B+树较B树的优点

• B+树的磁盘读写代价更低:B+树中非叶子节点不存储数据,只存储其子节点的指针和索引,所以同一个节点中B+树能容纳更多的关键字,所以树更矮胖,查询时需要的访问次数就更少
• B+树查询效率稳定:B+树中所有数据都保存在叶子节点中,属于同一层,每一次查询都是从根节点遍历到叶子节点的过程.
• B+树更利于对数据的扫描:B+树中叶子节点中存在双向链表,遍历时不需要进行对树的中序遍历.

(5). B+树的插入

B+树的插入分为以下的三种情况:

叶子节点是否满	索引节点是否满	进行的操作
no	no	直接插入
yes	no	拆分叶子节点,取中间数据放入上一层充当索引
yes	yes	拆分叶子节点,并向上拆分索引节点

​ 当叶子节点满,但是相邻节点未满的情况下,为了避免破坏B+树的平衡,会将记录转移到所在页的兄弟节点上.

(6). B+树的删除

分以下三种情况(填充因子为叶子节点中数据域占比,通常为50%):

叶子节点小于填充因子	中间节点小于填充因子	进行的操作
no	no	直接删除记录
yes	no	合并叶子节点和它的兄弟节点,更新索引节点
yes	yes	合并叶子节点和兄弟节点,并且合并其父节点的兄弟节点

4. B+树索引

​ B+树索引的本质就是B+树在数据库中的实现,在数据库中B+树的高度通常都在2~4层.

​ B+树索引还可以分为聚集索引和辅助索引,但其内部都是B+树的,即高度平衡,叶子节点存放所有数据.不同点在于其叶子节点是否存放的是一整行信息(辅助索引只存储索引列,聚集索引存储完整的行信息,这里讨论的是存储的内容,按逻辑上还有数据域是否连续的区别).

(1). 聚集索引

​ InnoDB存储引擎表是索引组织表,即表中的数据按照主键的顺序存放.而聚集索引就是按照每张表的主键构造一颗B+树,同时叶子节点存放正行的数据,所以也将聚集索引的叶子节点成为数据页.

​ 聚集索引的这个特性决定了索引组织表的数据本身也是索引的一部分(这个索引就是主键索引).

​ 每张表只能有一个聚集索引,是因为实际的数据只能按照一个B+树进行排序,所以主键只能有一个.

​ 查询优化器倾向于使用聚集索引,因为可以直接得到数据,并且对于范围查询效率非常高(在磁盘中数据按逻辑值顺序存储,所以找到范围的边界,访问边界内部的页即可,这里页的存储在物理上并不一定是连续的).

聚集索引的存储并不是物理上连续的,而是逻辑上连续的.有两点:

1. 页之间通过双向链表连接,并且按主键顺序排序
2. 页内部的每一行数据也是通过双向链表进行维护的

​ 通过这两点,就可以实现物理上的不连续,范围查找只需要查找边界,然后按链表访问下一个边界,中间遍历到的数据都是范围内的.而不是直接确定整块的磁盘空间,这样的实现方式太过难以维护.

​ 聚集索引的一个好处就是,对于主键的排序查找和范围查找速度非常快.

(2). 辅助索引

​ 叶子节点不包括行记录的全部数据,除了包含索引列的值以外,还存储了主键值.其中索引列按逻辑顺序排列,主键值离散.

​ 辅助索引的存在不影响数据中聚集索引的组织,所以一张表上可以有多个辅助索引.当通过辅助索引来寻找数据时,InnoDB存储引擎会遍历辅助索引并通过叶子节点中存储的对应的主键访问主键索引来得到完整的行记录.

(3). B+树的分裂

​ B+树的分裂不总是从页的中间记录开始的,而是取决于当前索引的插入方式.

​ 例如,主键通常都是自增长插入的,那么可能会出现1,2,3,4,5,6,7这样的一个叶子节点,当插入8时,会分裂为1,2,3,4—5,6,7,8.那么继续插入9,10,就会发现左边的叶子节点没有被插入,总是会通过旋转来填充.会比较耗时.

​ InnoDB存储引擎的Page Header中有以下几个部分保存插入的顺序信息:PAGE_LAST_INSERT,PAGE_DIRECTION,和PAGE_N_DIRECTION.通过这些信息,InnoDB存储引擎会决定是向左还是向右分裂,同时决定将分裂点设置为哪一个.

​ 如果插入是随机的,那么和之前了解的分裂方式无二.

(4). B+树索引的管理

1). 索引管理

​ 索引的创建和删除可以通过两种方法,一种是ALTER TABLE,另一种是CREATE/DROP INDEX.

-- alter table方式的创建和删除索引
alter table 表名
add 索引类型 索引名
(索引列[,索引列2]);

alter table 表名
drop primary key  |  index 索引名;

-- create/drop index
create 索引类型 索引名
on 表名 (索引列[,索引列2]);

drop index 索引名
on 表名;

​ 用户可以设置对整个列的数据进行索引,也可以只索引一个列的开头部分数据.

-- 对b列的前100行添加名为index_a的索引
alter table t
add key index_a (b(100))

2). Fast Index Creation

MySQL 5.5之前,要给MySQL数据库中的表添加或者删除索引这类DDl操作步骤如下:

1. 创建一张新的临时表,和原表结构一样,添加了索引(添加了要添加的结构)
2. 将原表中的数据导入新表
3. 将原表删除
4. 重命名新表

​ InnoDB存储引擎从InnoDB 1.0.x版本开始支持Fast Index Creation(快速索引创建),对于索引的创建,会在表上加一个S锁.对于创建操作,不需要重建表,变得更快,而对于删除操作,只需要将索引的空间标记为可用,同时删除对该表索引的定义即可.

​ 由于加了S锁,所以在索引的创建过程中只能进行表的查询,不能进行写操作.

3). Online Schema Change

​ Online Schema Change,在线架构改变,最早由Facebook实现.

​ 是指在DDL过程中,可以有读写事务对表进行操作,提高了原有MySQL数据库在DDL是的并发性.

​ Facebook采用PHP脚本实现OSC,而不是修改InnoDB存储引擎源码.

4). Online DDL

​ MySQL 5.6版本开始支持Online DDL(在线数据定义)操作,其允许辅助索引创建的同事,还允许其他DML操作执行.极大地提高了MySQL数据库在生产环境中的可用性.

alter table 表名
add 索引类型 索引名
(索引列[,索引列2])
algorithm = copy|default|inplace
lock = default|none|shared|exclusive

​ 上面代码为SQL格式,其中algorithm指定了创建或者删除索引的算法.copy表示复制方式创建,inplace表示不需要创建临时表,default表示根据参数选择方法,默认就是启用inplace.

​ lock部分为索引创建或删除时加锁的情况.none即为在线.share表示加写锁.exclusive表示加读写锁.default表示自动判断前三种.

​ Online DDL具体实现的原理是在执行创建或者删除操作是,将insert,update,delete这类DML操作日志写入一个缓存中,索引创建完成后,在重做到应用表上.

5. Cardinality值

(1). 什么是Cardinality

​ 如何判断一个索引是由最合适.评判的标准就是这个列的值中不重复的值的数量.这个数量就是Cardinality值(索引才有).

​ Cardinality/n_rows_in_table就是不重复的值所占比例,这个值越接近1,索引越有高选择性.

(2). InnoDB存储引擎中的Cardinality统计

​ 因为MySQL数据库中各个存储引擎对索引的实现不同,所以对Cardinality的统计是放在存储引擎层处理的.但是都是通过采样完成统计的.

​ InnoDB存储引擎更新Cardinality的条件为:表中1/16的数据发生过变化,表变更过20亿次.所以InnoDB存储引擎内部有一个计数器用来表示变更次数.

​ InnoDB存储引擎内部对Cardinality统计的具体实现:随机取得内部的8个叶子节点(页),统计其中的不同记录的个数,求平均值,然后当做全局的平均值使用,乘以整张表的页个数.得到整张表不同记录的记录估计值.

​ 可以看出,Cardinality不是一个精确值,并且没发生任何变化,Cardinality也可能是不同的.

6. B+数索引的使用

(1). 不同应用中B+树索引的使用

​ 对于OLTP应用(高并发但是查询内容并不多,游戏)的查询语句,索引应该只是获取表中的一小部分数据,否则优化器也不会选择所用索引.

​ 对于OLAP应用(统计类,每次查询大量数据)的查询语句,因为包含复杂的连接查询,添加索引也是很有必要的.通常会对时间字段进行索引,因为大多数统计都会与时间有关.

(2). 联合索引

​ 联合索引是指对表上的多个列进行索引,会对多个键值按优先级进行排序,然后插入B+树.通常用于**多层次查询**(这里层次非常重要,索引的优先级一定要和查询的层次相同,否则不会选择使用索引).

(3). 覆盖索引

​ InnoDB支持覆盖索引,也就是在索引中已经包含的信息(索引列值,主键值)可以直接拿出去直接使用,不需要在根据主键值访问聚集索引.

​ 另一个好处是类似count(*)这样的统计类,也不会进行访问聚集索引,以为没必要.

(4). 优化器不选择使用索引的情况

• 范围查找:取决于数据量的大小,一般情况下大量的操作即使查询到了一些列主键值,但是还需要对聚集索引进行大量的离散访问,如果查询到的数据足够少,还是会启用索引.另外固态硬盘这种访问速度非常快的情况下如果足够自信可以使用force index强制启用索引
• join链接操作:链接操作会先进行笛卡尔积…

(5). 索引提示

​ MySQL数据库支持索引提示(index hint),显示的告诉优化器使用哪一个索引.当优化器错误选择索引或者优化器进行选择占用的时间太久,可以进行索引提示的优化.

​ 使用 use + 索引名 显示声明使用那个索引.

select * from table_t use index(a) where ind = 1;

(6). Multi-Range Read优化

​ MySQL 5.6版本开始支持Multi-Range Read(MRR)优化.大致含义就是将辅助索引条件查询出的主键值排序,顺序访问从而尽可能减少对主键的离散访问导致的缓存的频繁替换.目的就是为了减少磁盘的访问次数.

Multi-Range Read的几个有点:

• 使数据的访问变得顺序
• 减少缓存池中页的替换次数
• 批量处理对键值的查询操作

​ 实现原理是通过缓存查询到的主键,排序后顺序访问,

7. 哈希算法

(1). 哈希表

​ 数据库中一般使用链地址法解决哈希冲突.

​ 哈希函数必须可以很好的进行散列,要尽可能的减少哈希冲突.

(2). InnoDB存储引擎中的哈希算法

​ 页在内存中不是连续的,页的id和内存中的位置是通过哈希连接起来的.

​ 哈希表的长度(数组)为略大于二倍页数的一个质数(这里就是为了减少哈希冲突).

​ 具体的函数为:K = space_id << 20 + space_id + offset(space_id是表空间id, offset是页在表空间内的偏移量)

​ K对应的是页,具体的数据通过取余法散列到页中的每个槽(页中每条记录的相对位置)中去.

(3). 自适应哈希索引

​ 跟前面将的哈希算法类似,不用的是仅仅由数据库创建并使用,用户不能进行干预.

​ 对字典类型查找非常快速,但是对范围查找就无能为力了.所以只能用于搜索等值的查询.

8. 全文检索

(1). 概述

​ B+树索引可以通过索引字段前缀进行查找,但是对于关键字搜索这类的与内容有关的查找,使用B+树索引是不现实的.

​ 出现了全文检索技术.将存储与数据库中的整篇文章的任意内容查找出来的技术.

​ 从InnoDB 1.2.x版本开始,InnoDB开始支持全文检索.

(2). 倒排索引

​ 全文检索通常使用倒排索引实现.倒排索引重存储了(单词,(单词出现的文章id, 单词在文章中的位置).

有两种表现形式:

• inverted file index:

  Number	Text	Documents
  单词编号	单词内容	单词出现的文章编号列表

• full inverted index:

  Number	Text	Documents
  单词编号	单词内容	(出现的文章id : 出现位置0,出现位置1)列表

  (3). InnoDB全文检索

  ​ InnoDB存储引擎从1.2.x版本支持全文检索技术,采用full inverted index的方式.

  ​ 在InnoDB存储引擎中,将(Documents(文章id),Position(单词出现位置))视为一个ilist.因此在全文检索表中,一列是word字段,一列是ilist字段.在word字段上设置索引.

  ​ 由于在ilist字段中放置了Position信息,所以可以进行邻近搜索(proximity search).