数据结构简述&mysql索引存储引擎结构分析图解&mysql执行计划&树节点的增删改查图解

0022

0434

性别

比b树要求更加宽松，每个节点的子节点个数可以更多，这样既降低树的高度，又增加了区间，提高的查询效率。树的最底层存放data，上面全是key。最底层的节点通过指针相互连接组成链式还结构，更加方便查询。

index：扫描全索引就能拿到结果，一般是扫描某个二级索引，这种扫描不会从索引树根节点开始快速查找，而是直接对二级索引的叶子节点遍历和扫描，速度还是比较慢的，这种查询一般为使用覆盖索引，二级索引一般比较小，所以这种通常比ALL快一些。

0034      0434

4. type列这一列表示关联类型或访问类型，即MySQL决定如何查找表中的行，查找数据行记录的大概范围。依次从最优到最差分别为：system > const > eq_ref > ref > range > index > ALL一般来说，得保证查询达到range级别，最好达到ref特别：NULL：mysql能够在优化阶段分解查询语句，在执行阶段用不着再访问表或索引。例如：在索引列中选取主键的最小值，可以单独查找索引来完成，不需要在执行时访问表，索引存的就是主键，而且安装b+树的数据存放，就是最小值就是树的最左子层节点。

0043   0044   0054

ALL：即全表扫描，扫描你的聚簇索引的所有叶子节点。通常情况下这需要增加索引来进行优化了。

0044   0054

0034      0044       0434

0034

等值查询，返回结果只有一条

0434          a

0044 

1. id列id列的编号是 select 的序列号，有几个 select 就有几个id，并且id的顺序是按 select 出现的顺序增长的。id列越大执行优先级越高，id相同则从上往下执行，id为NULL最后执行。

0034 

a

a   b

1

地址指针

15

25

压栈出栈先进后出

0054

50

65

WOO

GCC

男

AILI

索引页所在的地址指针

GGI

红黑变色规则

例如删除22

例如删除54

0043

0043    0434

如果被删关键字所在结点的关键字个数n等于( 上取整）[ m/2 ]-1，说明删去该关键字后该结点将不满足B-树的定义，需要调整。分两种情况：

40

44

ad21

22eq

加了平衡算法

依次放入： 22、34、43、434、a、54

mysql索引类型：hash索引和b+树。一般都是使用B树索引，虽然对于等值查询hash索引更快，但是它不支持大于小于之类的范围查询。而B+树，普通的等值查询通过树查询，对于范围查询，比如大于20的元素，先定位到20的元素，再通过叶子节点的双向指针，进行范围查询。

1-30索引页所在的地址指针

30

范围查询

双亲节点的指针指向22的右兄弟节点0043，父节点0034和右兄弟节点0043放在一起

二叉搜索树

 0044 0434

2

10

0x7d

0x71

0043   0044    0054

0043      0054

0043 

3. table列这一列表示 explain 的一行正在访问哪个表。

右侧为未完成部分

树两边基本平衡，可以通过二分查找法来快速查到目标。但是插入时，会因为平衡的最高子树比最低子树个数差最大不能差1倍，从而需要旋转1到n次。

根据地址找到data

插入慢，查询快

YAYA

data和key都在节点上，所有的数据都分布在树的各个节点。

explain查询结果的列

key

EIV

女

28

0x78

0x79

0022        0043 

数据和索引都在.ibd文件

JIJ

KIC

35

被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于（上取整）[m/2]-1。假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针Ai所指，则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字Ki一起，合并到 Ai所指兄弟结点中(若没有右兄弟，则合并至左兄弟结点中)。

叶子节点：也叫终端结点，是度为 0 的结点，即没有子节点的节点；查找数据：B-Trees:是一层层找，找到即返回。每个节点上都带有数据。查找类似于连续内存空间的二分查找，但是增删改要比连续内存空间要快，因为不用移动大量的内存B-Trees：是一直查到最底层，因为上层节点只是用来划定范围的，具体的节点和节点数据都在底层，而且最底层还可以通过节点链接符进行快速定位查询。插入数据：B-Trees：左部放在原来的结点，右部放入新的结点，而中间值则插入到父结点，并且父结点会产生一个新的指针，指向新的结点的位置。删除数据：B-Trees：非叶子节点：

二级索引扫描(就是先通过非主键索引查询整个表。只不过是有索引，通过索引查全表。

加入了平衡算法后

17

20

HERY

FOX

MYISAM存储结构

队列

eq_ref：primary key 或 unique key 索引的所有部分被连接使用 ，最多只会返回一条符合条件的记录。这可能是在 const 之外最好的联接类型了，简单的 select 查询不会出现这种 type。

 0434

先进先出，查询慢，增删快。查询需要一个个依次根据指针找到下一个元素，进行查询。而增删只要找到指定位置后，直接将前后。就是删除之前的查询比较慢。

0044  0434

平衡二叉树

31

37

45

GAN

 b

ref：相比 eq_ref，不使用唯一索引，而是使用普通索引或者唯一性索引的部分前缀，索引要和某个值相比较，可能会找到多个符合条件的行

张三

李四

张闪

李司

32

右兄弟节点中最小关键字a移到到双亲节点，再将双亲节节点中小于a的关键字放到下面被删除的54节点的位置

删除非叶子节点：删除后，将其子节点的最小值放到其原来的位置，再进行平衡

因为22节点下的子节点只有一个，因此要将22再移到到43的位置，这样正好是满足个数等于(m-1)

新增元素：

innodb存储结构

如果根据非主键(二级主键)名字去查询，首先是根据名字自身的索引查到叶子节点，获取叶子节点存的主键信息，再使用主键去主键索引查询到对应该条完整记录。

B+Trees

栈

这样44的下节点就有空的再将44移到下面，最上层的节点空了去除

这样44的下节点就有空的再将44移到下面

删除元素

linklist:源码中remove方法，如果是根据索引进行删除，效率会提高，因为源码里是通过位运算实现二分查找的方式查询的

0044    0434

二叉树

BOB

插入快，但是查询慢。

7. key_len列这一列显示了mysql在索引里使用的字节数，通过这个值可以算出具体使用了索引中的哪些列。 举例来说，film_actor的联合索引 idx_film_actor_id 由 film_id 和 actor_id 两个int列组成，并且每个int是4字节。通过结果中的key_len=4可推断出查询使用了第一个列：film_id列来执行索引查找

ArrayList：增删是直接增删指定位置的元素后，直接在copy数组，更耗资源

1xa4

1xa3

连续的内存空间，查询快，增删满。因为查询可以直接连续内存查询，但是增删中间的元素都需要将这个元素后面的所有元素进行逐一往前挪。

如果被删关键字所在结点的原关键字个数n>=[m/2] ( 上取整），说明删去该关键字后该结点仍满足B-树的定义。这种情况最为简单，只需删除对应的关键字：k和指针：A 即可。

6. key列这一列显示mysql实际采用哪个索引来优化对该表的访问。如果没有使用索引，则该列是 NULL。如果想强制mysql使用或忽视possible_keys列中的索引，在查询中使用 force index、ignore index

name

1、为了减少io次数，读取数据底层是按页读取的，一般是8kb。因此mysql默认是每页是16kb，也就是16*1024=16384b。2、B树是每个节点都放有数据和索引key，比如每条数据占1kb，那每页放16个节点，16的6次方才1600多万，存放2000万的数据就需要17层树。B+树是只有最低层的叶子节点才存放数据，上层的只需要存放主键key，一个key如果是bigint就是8字节，中间存的地址一般占6个字节，那上层每页就可以存放16384/14=1170个节点，最底层叶子节点每页可以存16个。假设每层只有一页，三层就可以存放1170*1170*16=2190万。层数上大大缩减了。3、b树叶子节点没有双向指针，对于范围查询只能一个个节点去查询。而B+树有双向指针，定位到边界的节点，就可以通过双向指针就可以快速查询到结果。

非聚簇索引Myisam

0034   0043 

主键或者唯一索引查询

删除34，先定位到34，然后找到这个节点指向的子节点的最小值，移动到34的位置

聚簇索引innodb

删除叶子节点：分三种情况：

总结：插入新节点必须是红色。父黑不用动。父红看规则：变色规则：父叔都红，父叔变黑爷变红。旋转规则：父红叔黑，看当前节点，当前节点是左就右旋，当前是右就左旋。

2. select_type列select_type 表示对应行是简单还是复杂的查询。1）simple：简单查询。查询不包含子查询和union2）primary：复杂查询中最外层的 select3）subquery：包含在 select 中的子查询（不在 from 子句中）4）derived：包含在 from 子句中的子查询。MySQL会将结果存放在一个临时表中，也称为派生表（derived的英文含义）5）union：在 union 中的第二个和随后的 select

mysql的执行计划

04gf

sa12

B-Trees

mysql为什么选择了B+Tree来作为存储引擎的基础数据结构，而不用btree？

m=3

数组

新添加一个44

B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；

红黑树

范围中 正数是从0开始，故减一，同理，负数不包括零，故不用减一类型        字节数                            范围byte         1                    -128~127(-2的7次方到2的7次方-1)short        2                    -2的15次方到2的15次方-1 int            4                    -2的31次方到2的31次方-1 long         8                    -2的63次方到2的63次方-1）

BTrees

多路搜索树

平衡树B树

0044

拿到主键再去查主键索引树

B+树

非唯一索引，但是条件都是等值查询。比如查询两学生表中name相等的同学。

两者之间进行了权衡。牺牲部分的查询性能，提高插入速度。最高子树比最低子树只要不超过两倍即可。通过红黑的变色完成查询和插入的平衡。

数据在.MYD索引都在.MYI文件

插入快：只按大小比较，在原有的树基础上进行插入元素。查询慢是只能从根节点比较大小一路查下去。

如果与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于( 上取整）[m/2]-1。则可将右兄弟(或左兄弟)结点中最小关键字(或最大的关键字)上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中。

5、possible_keys列这一列显示查询可能使用哪些索引来查找。 explain 时可能出现 possible_keys 有列，而 key 显示 NULL 的情况，这种情况是因为表中数据不多，mysql认为索引对此查询帮助不大，选择了全表查询。 如果该列是NULL，则没有相关的索引。在这种情况下，可以通过检查 where 子句看是否可以创造一个适当的索引来提高查询性能，然后用 explain 查看效果。

0x73

0x75

直接从叶子节点从头到尾查。

平衡后，将最上面的也合并到第二层

表结构都在.frm

非主键索引