Mysql Index、B Tree、B+ Tree、SQL Optimization

Mysql Index、B Tree、B+ Tree、SQL Optimization

catalog

1. 引言
2. Mysql索引
3. Mysql B/B+ Tree
4. Mysql SQL Optimization
5. MySQL Query Execution Process

1. 引言

在入侵检测(IDS)、流量检测(Traffic Detection System)、主动防御系统中,常常会需要使用到规则解析判断引擎,安全人员需要根据产品特性、暴露给用户态的接口、规则格式定义一些列的形式化规则(或者正则规则)。这会带来一个问题

当规则条目不断增加时,如果采取从上至下逐条解析并执行判断的逻辑的话,规则的判断延时会呈线性(甚至2次方增加),在一些串行实时的Hook引擎上这个情况更加不可接受。这造成了延时的同时,也在一定程度上制约了制定规则的安全人员的能力

为了解决这个问题,首先要考虑的是如何实现一种高效的规则解析、判断机制,即使在万这个数量级的规则条数下,也能保持较好的处理性能

1. 采用多模匹配算法,典型地如Aho-Corasick算法
Snort流量入侵检测就是采用了类似这种规则解析判断思想,这种算法将所有的输入规则进行一次"预处理",生成了一副状态机,在解析请求到达时,一次性对所有的规则同时进行基于状态机的判断,这种算法在规则条数增加时,消耗的时间并不会明显增加
2. 采用内存型数据库SQLite对规则进行cache、检索
对于多条规则的匹配来说,我们可以进行抽象,它从本质上还是一个"判读元素在集合中是否命中"的过程,这正好契合了数据库的SQL查询过程,而数据库的B+树存储结构、SQL查询优化可以帮助我们加快这个检索判断过程
//本质上来说,SQL的查询过程,就是一种基于树的多模匹配过程

2. Mysql索引

官方介绍索引是帮助MySQL高效获取数据的数据结构。我们可以理解索引相当于一本书的目录,通过目录就知道要的资料在哪里,不用一页一页查阅找出需要的资料。关键字index

0x1: 唯一索引

强调唯一,就是索引值必须唯一,关键字unique index

1. 创建索引
1) create unique index 索引名 on 表名(列名);
2) alter table 表名 add unique index 索引名 (列名);

2. 删除索引
1) drop index 索引名 on 表名;
2) alter table 表名 drop index 索引名;

0x2: 主键

主键就是唯一索引的一种,主键要求建表时指定,一般用auto_increatment列,关键字是primary key

1. 主键创建
creat table test2 (id int not null

0x3: 全文索引

InnoDB不支持,Myisam支持性能比较好,一般在 CHAR、VARCHAR 或 TEXT 列上创建

Create table 表名( id int not null primary anto_increment,title varchar(100),FULLTEXT(title))type=myisam

0x4: 单列索引与多列索引

索引可以是单列索引也可以是多列索引(也叫复合索引)

create table test3 (id int not null primary key auto_increment,uname char(8) not null default '',password char(12) not null,INDEX(uname,password))type=myisam;
//INDEX(a, b, c)可以当做a或(a, b)的索引来使用,但和b、c或(b,c)的索引来使用这是一个最左前缀的优化方法

0x5: 聚集索引

一种索引,该索引中键值的逻辑顺序决定了表中相应行的物理顺序。聚集索引确定表中数据的物理顺序。Mysql中myisam表是没有聚集索引的,innodb有(主键就是聚集索引)

0x6: MyisAM索引结构

MyisAM索引用的B+tree来储存数据,MyisAM索引的指针指向的是键值的地址,地址存储的是数据

上图3阶树,主键是Col2,Col值就是该行数据保存的物理地址,其中红色部分是说明标注 
1. 1标注,因为B+tree的所以叶子节点包含所有关键字且是按照升序排列(主键索引唯一,辅助索引可以不唯一),所以等于关键字的数据值在右子树
2. 2标注,对应相应关键字存储对应数据的物理地址,注意这也是之后和InnoDB索引不同的地方之一
3. 2标注也说明MyISAM表的索引和数据是分离的,索引保存在"表名.MYI"文件内,而数据保存在"表名.MYD"文件内,2标注的物理地址就是"表名.MYD"文件内相应数据的物理地址。(InnoDB表的索引文件和数据文件在一起)
4. 对于MyISAM来说,辅助索引和主键索引没什么大的区别,辅助索引的索引值是可以重复的(但InnoDB辅助索引和主键索引有很明显的区别)

0x7: InnoDB索引结构

首先有一个表,内容和主键索引结构如下两图

Mysql Index、B Tree、B+ Tree、SQL Optimization

结构上:由上图可以看出InnoDB的索引结构很MyisAM的有很明显的区别
1. MyisAM表的索引和数据是分开的,用指针指向数据的物理地址,而InnoDB表中索引和数据是储存在一起。看红框1可一看出一行数据都保存了。
2. 注意到InnoDB的上图多了三行的隐藏数据列(虚线表),这是因为MyisAM不支持事务,InnoDB处理事务在性能上并发控制上比较好,看图中的红框2中的
1) DB_TRX_ID是事务ID,自动增长
2) db_roll_ptr是回滚指针,用于事务出错时数据回滚恢复
3) db_row_id是记录行号,这个值其实在主键索引中就是主键值,如果没有设置主键索引(辅助索引),db_row_id会找表中unique的列作为值,若没有unique列则系统自动创建一个
3. 但辅助索引查找数据事要检索两次,先找到相应的主键索引值然后在去检索主键索引找到对应的数据。这也是网上很多mysql性能优化时提到的“主键尽可能简短”的原因,主键越长辅助索引也就越大,当然主键索引也越大

0x8: MyisAM索引与InnoDB索引相比较

1. MyisAM支持全文索引(FULLTEXT)、压缩索引,InnoDB不支持
2. InnoDB支持事务,MyisAM不支持
3. MyisAM顺序储存数据,索引叶子节点保存对应数据行地址,辅助索引很主键索引相差无几;InnoDB主键节点同时保存数据行,其他辅助索引保存的是主键索引的值
4. MyisAM键值分离,索引载入内存(key_buffer_size),数据缓存依赖操作系统;InnoDB键值一起保存,索引与数据一起载入InnoDB缓冲池
5. MyisAM主键(唯一)索引按升序来存储存储,InnoDB则不一定
6. MyisAM索引的基数值(Cardinality,show index 命令可以看见)是精确的,InnoDB则是估计值。这里涉及到信息统计的知识,MyisAM统计信息是保存磁盘中,在alter表或Analyze table操作更新此信息,而InnoDB则是在表第一次打开的时候估计值保存在缓存区内
7. MyisAM处理字符串索引时用增量保存的方式,如第一个索引是‘preform’,第二个是‘preformence’,则第二个保存是‘7,ance‘,这个明显的好处是缩短索引,但是缺陷就是不支持倒序提取索引,必须顺序遍历获取索引

Relevant Link:

http://blogread.cn/it/article/6087?f=wb2

3. Mysql B/B+ Tree

0x1: B-tree结构视图

Mysql Index、B Tree、B+ Tree、SQL Optimization

一棵m阶的B-tree树,则有以下性质

1. Ki表示关键字值,上图中,k1<k2<…<ki<k0<Kn(可以看出,一个节点的左子节点关键字值<该关键字值<右子节点关键字值)
2. Pi表示指向子节点的指针,左指针指向左子节点,右指针指向右子节点。即是:p1[指向值]<k1<p2[指向值]<k2……
3. 所有关键字必须唯一值(这也是创建myisam 和innodb表必须要主键的原因),每个节点包含一个说明该节点多少个关键字,如上图第二行的i和n
4. 节点
l) 每个节点最可以有m个子节点
2) 根节点若非叶子节点,至少2个子节点,最多m个子节点
3) 每个非根,非叶子节点至少[m/2]子节点或叫子树([]表示向上取整),最多m个子节点
5. 关键字
l) 根节点的关键字个数1~m-1
l) 非根非叶子节点的关键字个数[m/2]-1~m-1,如m=3,则该类节点关键字个数:2-1~2
6. 关键字数k和指向子节点个数指针p的关系:
l) k+1=p,根据储存数据的具体需求,左右指针为空时要有标志位表示没有

0x2: B+tree结构示意图如下

Mysql Index、B Tree、B+ Tree、SQL Optimization

B+树是B-树的变体,也是一种多路搜索树 
1. 非叶子结点的子树指针与关键字个数相同
2. 为所有叶子结点增加一个链指针(红点标志的箭头)

4. Mysql SQL Optimization
Relevant Link:

https://dev.mysql.com/doc/refman/5.6/en/statement-optimization.html
http://beginner-sql-tutorial.com/sql-query-tuning.htm

5. MySQL Query Execution Process

Mysql Index、B Tree、B+ Tree、SQL Optimization

1. 查询缓存,判断sql语句是否完全匹配,再判断是否有权限,两个判断为假则到解析器解析语句,为真则提取数据结果返回给用户 
2. 解析器解析。解析器先词法分析,语法分析,检查错误比如引号有没闭合等,然后生成解析树
3. 预处理。预处理解决解析器无法决解的语义,如检查表和列是否存在,别名是否有错,生成新的解析树
4. 优化器做大量的优化操作
5. 生成执行计划
6. 查询执行引擎,负责调度引擎获取相应数据
7. 返回结果

Relevant Link:

http://blogread.cn/it/article/6087?f=wb2

Copyright (c) 2015 LittleHann All rights reserved