B+树的简单介绍

女爷i 2022-06-18 02:41 150阅读 0赞

*前言*

博客编写人：Willam
    博客编写时间：2017/3/28
    博主邮箱：2930526477@qq.com（有志同道合之人，可以加qq交流交流编程心得）

## 1、B+树的介绍 ##

B+树是B-树的变体，也是一种多路搜索树：  
其定义基本与B-树同，除了：

1.  有n颗子树的结点中含有n个关键字
2.  所有的叶子结点中包含了全部关键字的信息，以及指向包含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接
3.  所有的非终端结点可以看成索引部分，结点中仅含有其子树（根结点）中最大（或最小）关键字。

如下图所示，就是一个B+树  
![这里写图片描述][SouthEast]

1.  根结点只有1个，分支数量范围\[2,m\]。
2.  除根以外的非叶子结点，每个结点包含分支数范围\[\[m/2\],m\]，其中\[m/2\]表示取大于m/2的最小整数。
3.  所有非叶子节点的关键字数目等于它的分支数量
4.  所有叶子节点都在同一层，且关键字数目范围是\[\[m/2\],m\]，其中\[m/2\]表示取大于m/2的最小整数。
5.  所有非叶子节点的关键字可以看成是索引部分，这些索引等于其子树（根结点）中的最大（或最小）关键  
    字。例如一个非叶子节点包含信息: (n，A0,K0, A1,K1,……,Kn,An)，其中Ki为关键字，Ai为指向子树根结点的指针，n表示关键字个数。即Ai所指子树中的关键字均小于或等于Ki，而Ai+1所指的关键字均大于Ki（i=1，2，……，n）。
6.  叶子节点包含全部关键字的信息(非叶子节点只包含索引)，且叶子结点中的所有关键字依照大小顺序链接(所以一个B+树通常有两个头指针，一个是指向根节点的root，另一个是指向最小关键字的sqt)。

。

## 2、B+树比B-树的优势 ##

下面是B+树和B-树的一个对比截图：（来自：[参考文件][Link 1]）  
![这里写图片描述][SouthEast 1]

**为什么说B+-tree比B 树更适合实际应用中操作系统的文件索引和数据库索引？（摘抄自：[参考文件][Link 2]）**

（1）B+-tree的磁盘读写代价更低

B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关
    键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相
    对来说IO读写次数也就降低了。
        举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵
        9阶B-tree ( 一个结点最多8个关键字) 的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把
        内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

（2）B+-tree的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从
    根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

好的博客推荐：  
[https://www.phpsong.com/752.html][https_www.phpsong.com_752.html]  
[https://yq.aliyun.com/articles/9280][https_yq.aliyun.com_articles_9280]  
[http://blog.csdn.net/qq\_23217629/article/details/52512041?locationNum=9&fps=1][http_blog.csdn.net_qq_23217629_article_details_52512041_locationNum_9_fps_1]

[SouthEast]: /images/20220618/1a4804ffa7f741f980dc205ee35b4690.png
[Link 1]: http://www.jianshu.com/p/ea8d0418d4ed
[SouthEast 1]: /images/20220618/54d97b2c6dd04436b7743caf3d8a658d.png
[Link 2]: http://blog.csdn.net/v_JULY_v/article/details/6530142
[https_www.phpsong.com_752.html]: https://www.phpsong.com/752.html
[https_yq.aliyun.com_articles_9280]: https://yq.aliyun.com/articles/9280
[http_blog.csdn.net_qq_23217629_article_details_52512041_locationNum_9_fps_1]: http://blog.csdn.net/qq_23217629/article/details/52512041?locationNum=9&fps=1