广告区

广告区


本站消息

站长简介/公众号

关注本站官方公众号:程序员总部,领取三大福利!
福利一:python和前端辅导
福利二:进程序员交流微信群,专属于程序员的圈子
福利三:领取全套零基础视频教程(python,java,前端,php)

  价值13000svip视频教程,python大神匠心打造,零基础python开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2021-07(1)

2021-08(9)

树(四)详解B+树与B树索引

发布于2020-03-07 19:04     阅读(1869)     评论(0)     点赞(22)     收藏(1)



目录

1 从B树说起

1.1 B树的特点

1.2 一棵五叉B树会有哪些特点

2 构造一棵B树

2.1 准备数据

2.2 插入前四个元素

2.3 插入第五个元素

2.4 插入第六至第八的元素

2.5 插入第九个元素

2.6 插入第十至十三的元素

2.7 插入第十四元素

2.8 插入第十五个元素

2.9 插入第十六个元素

2.10 插入第十七个元素

2.11 插入最后两个元素

3 B+树

3.1 B+树的特点

3.2 构造一棵B+树

3.2 为什么Mysql使用B+树作为索引


1 从B树说起

        Mysql有两种类型的索引,一种是HASH,一种是BTREE,大多数时候我们都选择BTREE索引。BTREE索引实际上是一个B+树,对于B+树的描述,先从B树说起。

1.1 B树的特点

        在写B+树之前先说B树。首先,B树不属于二叉树,它的节点可以拥有大于2的子节点。

        B树是一种平衡的多叉树,也称为多路平衡搜索树,一棵m叉的B树具有如下特点。

      (1)树中的每一个节点最多包含m个子节点;

      (2)所有的叶子节点处于同一层;

      (3)除根节点与叶子节点外,每个节点至少包含ceil(m/2)个子节点,这里ceil表示向上取整(比如一个7叉B树,每个节点至少包含ceil(7/2) = 4个子节点);

      (4)当根节点不是叶子节点时,根节点至少要有2个子节点;

      (5)每个非叶子节点由n个key与n+1个指针组成,其中ceil(m/2)-1 <= n <= m-1。

1.2 一棵五叉B树会有哪些特点

        这里以一棵5叉B树举例。对于5叉B树,根据上面的定义,它会具有以下性质。

      (1)树中的每一个节点最多包含5个子节点;

      (2)所有的叶子节点处于同一层;

      (3)除根节点与叶子节点外,每个节点至少包含3个子节点;

      (4)当根节点不是叶子节点时,根节点至少要有2个子节点;

      (5)每个非叶子节点由n个key与n+1个指针组成,这里的指针指向子节点,并且2 <= n <= 4。

 

2 构造一棵B树

        B树的构造与平衡二叉树不一样,平衡二叉树向下插入子节点并通过旋转等操作保持平衡,而B树以向上分裂的方式构造。

2.1 准备数据

        这里准备了19个元素元素,会以顺序插入的方式构造一棵5叉B树,数据如下。

2, 13, 6, 1, 7, 4, 10, 16, 12, 5, 14, 17, 11, 15, 3, 8, 9, 18, 19

2.2 插入前四个元素

        在插入前四个元素[2, 13 , 6, 1]后这棵树只有一个节点,在这个节点上有4个key,5个指针,4个key为一个节点的最大容量,下面为图示。

2.3 插入第五个元素

        上面的节点中已经有了四个元素,此时插入第五个元素[7],发生向上分裂。以目前的[1, 2, 6, 7, 13]的中间元素向上分裂重写构造,比[6]小的元素作为左子树节点中的元素,比[6]大的元素作为右子树节点中的元素,下面为图示。

2.4 插入第六至第八的元素

        接着插入第六至第八的元素[4, 10, 16],此时根节点的右子树会达到单个节点的最大元素数量4个,下面为图示。

2.5 插入第九个元素

        插入第九个元素,也就是[12],此时根节点的右子树节点向上分裂,将中间元素[12]放入根节点,并将[7, 10]两个元素放到同一个节点,[13, 16]放到另一个节点中,下面为图示。

2.6 插入第十至十三的元素

        插入第十至十三的元素[5, 14, 17, 11]四个元素,这四个元素插入后,依然是一棵B树,不会发生向上分裂,下面为图示。

2.7 插入第十四元素

        插入第十四个元素[15],此时发生向上分裂,[15]这一个元素正好是[13, 14, 15, 16, 17]的中间元素。向上分裂之后,根节点的元素为[6, 12, 15],该节点有四个子节点,下面为图示。

2.8 插入第十五个元素

        插入第十五个元素[8],此时再次向上分裂,[1, 2, 3, 4, 5]的中间元素为[3],因此将[3]拿到根节点,[1, 2]作为单独一个节点, [4, 5]为另一个节点,以下为图示。

2.9 插入第十六个元素

        插入第十六个元素[8],不发生分裂,下面为图示。

2.10 插入第十七个元素

        插入第十七个元素[9],[7, 8, 9, 10, 11]这个节点达到了五个元素向上分裂,取中间元素[9]向上分裂,此时[3, 6, 9, 12, 15]这个节点,也就是根节点元素数量到达五,需要将[9]这一个元素向上分裂,作为根节点,图示如下。

 

2.11 插入最后两个元素

        插入最后两个元素,此时不发生分裂,完成B树的构造,下面为图示。

 

3 B+树

        从上面对B树的构造过程可以看到,B树的层级少,所以它的查询效率是比较高的;另外,在插入与删除数据的时候对于整棵树的结构影响较小,这也是它的优点。

        接下来说B+树。

3.1 B+树的特点

        B+树衍生自B树,它的特点如下:

      (1)一棵m叉B树的每个节点最多是有m-1个key,而B+树每个节点最多可以有m个key;

      (2)B树的key在树中有序排列在每一个节点中,而B+树的所有key都在叶子节点中有序排列;

      (3)B+树的所有非叶子节点都是为了查找到叶子节点。

      (4)B+树的叶子节点处于同一层,并且相邻的叶子节点互相连接,使所有叶子节点形成一个链表。

3.2 构造一棵B+树

        这里我画了一棵四叉B+树,直接上图。

         在这棵树中,可以通过索引(非叶子节点)找到叶子节点,叶子节点包含了这棵树的所有key,并且是有序的;另外,在每一个叶子节点也可以通过链表找到其他的叶子节点。

3.2 为什么Mysql使用B+树作为索引

        (1)选用B+树作为索引稳定且效率高,这是由于B+树所有数据都在叶子节点中,并且所有叶子节点处于同一层;

        (2)B+树对于新增与修改节点的效率也是比较高的,这与B树相同;

        (3)在叶子节点引入了链表,增加范围查询的效率,比如我要查询上图四叉B+树中[11]到[24]的数据,那么在根据索引(非叶子节点)找到[11]所在的叶子节点后,也可以根据链表找到其他叶子节点。

原文链接:https://blog.csdn.net/y506798278/article/details/104638155







所属网站分类: 技术文章 > 博客

作者:32738ew

链接:https://www.pythonheidong.com/blog/article/246893/e7ec52809d91b8884bd9/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

22 0
收藏该文
已收藏

评论内容:(最多支持255个字符)