Mysql B+树学习

概述

要描述清楚B+树,得先了解二叉查找数,平衡二叉树.

二叉查找树

这里写图片描述

任意节点,它的左子树如果不为空,那么左子树上所有节点的值都小于根节点的值；

任意节点,他的右子树如果不为空,那么右子树上的所有节点的值大于根节点的值.

这个特性给查找带来了方便,如上图,要找key=3的键值,只要从5这个节点左子树进行递归查找即可,右子树的节点可以完全不理会.

平衡二叉树

二叉查找树有些缺陷,因为它对树的左右子树的高度没有任何限制,极端的情况下会出现如下图的类似链表的情况：

这里写图片描述

这种二叉查找树对查询没任何好处的.所以有必要将树节点的左右子树的高度做一下限制,尽量坚持平衡.

二叉平衡树 图一

这里写图片描述

二叉查找树 图二

这里写图片描述

二叉平衡树要求节点的左右子树的高度不要相差超过1,像图二中的6这个节点,它的左子树的高度是4,右子树的高度是2,相差超过了1,不具备平衡二叉树的特性.

由二叉平衡树的特性可以看到,查询的效率同样很高,同时又避免了二叉查找树出现链表那种极端情况.

B+树

图三

这里写图片描述

B+树有几个特点：

1、是多叉而不是二叉了,使用多叉的目的是降低树的高度;

2、每个节点不再只是存储一个key了,可以存储多个key；

3、非叶子节点存储key,叶子节点存储key和数据.

4、叶子节点两两相连,为顺序查询提供了赞助

Mysql为什么选择B+树

1、B+树的非叶子节点只是存储key,占用空间非常小,因此每一层的节点能索引到的数据范围更加的广.换句话说,每次IO操作可以观看更多的数据；

2、叶子节点两两相连,符合磁盘的预读特性.如图三中存储50和55的叶子节点,它有个指针指向了60和62这个叶子节点,那么当我们从磁盘读取50和55对应的数据的时候,由于磁盘的预读特性,会顺便把60和62对应的数据读取出来.这个时候属于顺序读取,而不是磁盘寻道了,加快了速度.

3、支持范围查询,而且部分范围查询非常高效,原因是数据都是存储在叶子节点这一层,并且有指针指向其他叶子节点,这样范围查询只需要遍历叶子节点这一层,无需整棵树遍历.

Mysql 索引简单描述

innodb存储引擎

自增主键索引

自增主键索引就是使用了B+数,索引文件同时也是数据文件,存储了整张表的数据.也就是说,平时我们执行sql依照主键查询的时候,那么只需要从这个索引文件获取数据即可.这种索引也叫聚集索引 ,原因是所有数据是依照主键聚集的.

辅助索引(非自增主键索引,也可以叫非聚集索引)

这种索引文件的叶子节点存储了键值和书签.键值说的就是列的值,书签就是对应记录的主键的值,如果依照某个辅助索引来查询数据的时候,如果没有用到覆盖索引,那么就得分两步走：

1、先从辅助索引文件中获取到数据对应的主键；

2、根据主键从聚集索引中获取真实数据.

MyISAM存储引擎

MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址.这种称为非聚集索引,这个命名其实是对应上面innodb的叫法罢了.

1、具有1-5工作经验的,面对目前流行的技术不知从何下手,需要突破技术瓶颈的可以加群.

2、在公司待久了,过得很安适,但跳槽时面试碰壁.需要在短时间内进修、跳槽拿高薪的可以加群.

3、如果没有工作经验,但基础非常扎实,对java工作机制,常用设计思想,常用java开发框架掌握熟练的,可以加群.

4、觉得本身很牛B,一般需求都能搞定.但是所学的知识点没有系统化,很难在技术领域继续突破的可以加群.

5. 群号：高级架构群 647631030备注好信息!

6.阿里Java高级架构师直播讲解知识点,分享知识,多年工作经验的梳理和总结,带着大家全面、科学地建立本身的技术体系和技术认知!