首页 > 数据库技术 > 详细

SQL学习笔记之B+树

时间:2018-07-31 18:29:09      阅读:260      评论:0      收藏:0      [点我收藏+]

标签:csdn   这一   带来   都是   树遍历   sam   div   一个   sql   

 

0x00 概述

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

 

0x01 二叉查找树

技术分享图片

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

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

 

0x02 平衡二叉树

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

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

 二叉平衡树 图一

 技术分享图片

二叉查找树 图二

 技术分享图片

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

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

 

 0x03 B+树

技术分享图片

B+树有几个特点:
1、是多叉而不是二叉了,使用多叉的目的是降低树的高度;
2、每个节点不再只是存储一个key了,可以存储多个key;
3、非叶子节点存储key,叶子节点存储key和数据。
4、叶子节点两两相连,为顺序查询提供了帮助

 

0x04 Mysql为什么选择B+树

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

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

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

0x05 Mysql 索引简单描述

innodb存储引擎

自增主键索引

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

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

这种索引文件的叶子节点存储了键值和书签。键值说的就是列的值,书签就是对应记录的主键的值,如果按照某个辅助索引来查询数据的时候,如果没有用到覆盖索引,那么就得分两步走:
1、先从辅助索引文件中获取到数据对应的主键;
2、根据主键从聚集索引中获取真实数据。

 

MyISAM存储引擎

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

 

 参考

 

SQL学习笔记之B+树

标签:csdn   这一   带来   都是   树遍历   sam   div   一个   sql   

原文:https://www.cnblogs.com/JetpropelledSnake/p/9397033.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号