未加星标

Mysql B+树学习

字体大小 | |
[数据库(mysql) 所属分类 数据库(mysql) | 发布者 店小二03 | 时间 2017 | 作者 红领巾 ] 0人收藏点击收藏
概述

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

二叉查找树
Mysql B+树学习

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

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

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

平衡二叉树

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


Mysql B+树学习

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

二叉平衡树 图一
Mysql B+树学习
二叉查找树 图二
Mysql B+树学习

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

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

B+树 图三
Mysql 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、支持范围查询,而且部分范围查询非常高效,原因是数据都是存储在叶子节点这一层,并且有指针指向其他叶子节点,这样范围查询只需要遍历叶子节点这一层,无需整棵树遍历。

参考的文章

1、 从 MongoDB 及 Mysql 谈B/B+树

2、 MySQL索引背后的数据结构及算法原理

本文数据库(mysql)相关术语:navicat for mysql mysql workbench mysql数据库 mysql 存储过程 mysql安装图解 mysql教程 mysql 管理工具

主题: 数据SQL数据结构MongoDBMySQL算法
分页:12
转载请注明
本文标题:Mysql B+树学习
本站链接:http://www.codesec.net/view/531514.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 数据库(mysql) | 评论(0) | 阅读(53)