面试官：请你说说B树、B+树的原理及区别

短命女 2022-09-17 05:16 150阅读 0赞

点击上方“Java基基”，选择“设为星标”

做积极的人，而不是积极废人！

每天 **14:00** 更新文章，每天掉亿点点头发...

源码精品专栏

*  [原创 | Java 2021 超神之路，很肝~][_ Java 2021]  
    
 *  [中文详细注释的开源项目][Link 1]  
    
 *  [RPC 框架 Dubbo 源码解析][RPC _ Dubbo]
 *  [网络应用框架 Netty 源码解析][Netty]
 *  [消息中间件 RocketMQ 源码解析][RocketMQ]  
    
 *  [数据库中间件 Sharding-JDBC 和 MyCAT 源码解析][Sharding-JDBC _ MyCAT]
 *  [作业调度中间件 Elastic-Job 源码解析][Elastic-Job]
 *  [分布式事务中间件 TCC-Transaction 源码解析][TCC-Transaction]
 *  [Eureka 和 Hystrix 源码解析][Eureka _ Hystrix]
 *  [Java 并发源码][Java]

[来源：blog.csdn.net/yu876876/  
article/details/84896789][blog.csdn.net_yu876876_ article_details_84896789]

*  [B树的原理][B]
 *  [辨析1：B树与红黑树的区别][1_B]
 *  [B树的插入操作][B 1]
    
     *  [B树的插入][B]
 *  [B+树的原理][B 2]
 *  [B+树的插入操作][B 3]
    
     *  [B+树插入][B]

[![bc32e6f18366f60e39f7a74f10fc942f.png][]][B]

--------------------

之前在网上看到过一些B树与B+树的区别然后主要是针对定义来陈述，分分钟看的我快要冬眠，然后在一次面试遇到该没问题没回答上来一首凉凉送 给自己，今天老老实实的分享自己对B树，B+树浅显理解，若望指出不足。

## [B树的原理][blog.csdn.net_yu876876_ article_details_84896789] ##

动态查找树主要包括：二叉搜索树，平衡二叉树，红黑树，B树，B-树时间复杂度O(log2N)，通过对树高度的降低可以提升查找效率

尤其是在大量数据进行存储的时候会存储到外部 磁盘，通过对外部磁盘的读取时需要快速的查找到对应的位置，所以需要一种高效的外村数据结构。

B树：就是为了存储设备或者磁盘设计的一种平衡查找树

> 推荐下自己做的 Spring Boot 的实战项目：
> 
> https://github.com/YunaiV/ruoyi-vue-pro

## [辨析1：B树与红黑树的区别][1_B] ##

B树的节点可以有很多孩子节点，红黑树是一种近似平衡的二叉搜索树即每个节点只有两个孩子

一颗含有N个节点的B树和红黑树的高度是一样的O（lgn）。

[![f66b1b9c16ff611817dabedcc64b39ff.png][]][blog.csdn.net_yu876876_ article_details_84896789]

##### [B树的定义][blog.csdn.net_yu876876_ article_details_84896789] #####

对于一颗M阶的B树

> 树中的每个节点最多有m个孩子
> 
> 除了根节点和叶子节点外，其他节点最少含有m/2（取上限）个孩子
> 
> 若根节点不是叶子节点，则根节点最少含有两个孩子
> 
> 所以叶子节点都在同一层，叶子节点不包含任何关键字信息

B树的类型与节点定义

struct BTNode
    {
     int keyNum ; //实际关键字的个数
     PBTNode parent；//指向父亲节点
     PBTNode *ptr ;
     keyType *key ； //关键字向量
    }

> 推荐下自己做的 Spring Cloud 的实战项目：
> 
> https://github.com/YunaiV/onemall

## [B树的插入操作][B 1] ##

### [B树的插入][blog.csdn.net_yu876876_ article_details_84896789] ###

1）若B树中已存在需要插入的键值时，用新的键值替换旧值；2）若B树中不存在这个值，则在叶子节点进行插入操作；具体插入过程如下

> 对于高度为h的m阶B树，新节点一般插在第h层。
> 
> 1）若该节点中关键码个数小于m-1，则直接插入
> 
> 2）若该节点中关键码个数等于m-1，则节点分裂。以中间的关键码为界，将节点一分为二，产生一个新的节点，并将中间关键码插入到父节点中。
> 
> 重复上述过程，最坏情况一直分裂高根节点，则B树就会增加一层。

## [B+树的原理][B 2] ##

**B+树特点**

1）B+树是B树的一种变形，它把数据都存储在叶子节点，内部只存关键字（其中叶子节点的最小值作为索引）和孩子指针，简化了内部节点。2）B+树的遍历高效，将所以叶子节点串联成链表即可从头到尾遍历，

**B+树的定义**

> 1）有n棵子树的结点含有n个关键字，每个关键字都不保存数据，只用来索引，并且所有的数据都存储在叶子节点
> 
> 2）所有叶子结点包含所有关键字信息和指向关键字记录的指针，其中关键字从小到大顺序链接

[![85b2e92ac80358d0e22a43e883559921.png][]][blog.csdn.net_yu876876_ article_details_84896789]

## [B+树的插入操作][B 3] ##

### [B+树插入][blog.csdn.net_yu876876_ article_details_84896789] ###

**1.若为空树直接插入**

**2.对于叶子结点：** 根据key找到叶子结点，对叶子结点进行插入操作。插入后如果当前叶子结点的key值数b不大于m-1,则插入结束。

> 反之，将这个叶子结点分成左右两个叶子结点进行操作，
> 
> 左叶子结点包含前m/2个记录，右叶子结点包含剩下的记录key,
> 
> 将第m/2+1个记录的key进位到父结点中，（父结点必须是索引类型的结点）
> 
> 进位到父结点的key，进位的key左孩子指向左结点，右孩子指向右结点。

**3.对于索引结点：** 如果当前结点的key个数小于等于m-1,插入结束。

> 反之，将这个索引类型的结点分成两个索引结点，
> 
> 左索引结点包含前（m-1)/2个数据，右结点包含m-(m-1)/2个数据
> 
> 将第m/2个key进位到父结点中，进位的key左孩子指向左结点，右孩子指向右结点

**剖析2：为什么B+树比B树更适合做系统的数据库索引和文件索引**

**1）B+树的磁盘读写代价更低**

因为B+树内部结点没有指向关键字具体信息的指针，内部结点相对B树小

**2）B+树的查询更加稳定**

因为非终端结点并不是指向文件内容的结点，仅仅是作为叶子结点的关键字索引，因此所有的关键字查询都会走一条从根节点到叶子结点的路径。即s所有关键字查询的长度是一样的，查询效率稳定。

--------------------

欢迎加入我的知识星球，一起探讨架构，交流源码。加入方式，**长按下方二维码噢**：

![f6e9abca41e6432301a45b202c2ecd3e.png][]

已在知识星球更新源码解析如下：

[![6d3b93768d1ab10a2350bb84c3b7ce76.png][]][_ Java 2021]

[![6eabc21c2760726c431b567b553bdad4.png][]][_ Java 2021]

[![cd39b3f852317156504d2a7c1fa6d069.png][]][_ Java 2021]

[![faf105d5dc83dbd0eaf55ce38a38f690.png][]][_ Java 2021]

最近更新《芋道 SpringBoot 2.X 入门》系列，已经 101 余篇，覆盖了 MyBatis、Redis、MongoDB、ES、分库分表、读写分离、SpringMVC、Webflux、权限、WebSocket、Dubbo、RabbitMQ、RocketMQ、Kafka、性能测试等等内容。

提供近 3W 行代码的 SpringBoot 示例，以及超 6W 行代码的电商微服务项目。

获取方式：点“**在看**”，关注公众号并回复 **666** 领取，更多内容陆续奉上。

文章有帮助的话，在看，转发吧。
    谢谢支持哟 (*^__^*）

[_ Java 2021]: http://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247487551&idx=1&sn=18f64ba49f3f0f9d8be9d1fdef8857d9&chksm=fa496f8ecd3ee698f4954c00efb80fe955ec9198fff3ef4011e331aa37f55a6a17bc8c0335a8&scene=21#wechat_redirect
[Link 1]: https://blog.csdn.net/qq_40831778/article/details/102375778
[RPC _ Dubbo]: https://blog.csdn.net/uoyou138/article/details/107024989
[Netty]: https://blog.csdn.net/shishishilove/article/details/108051416
[RocketMQ]: http://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247486256&idx=1&sn=81daccd3fcd2953456c917630636fb26&chksm=fa497481cd3efd97d9239f5eab060e49dea9876a6046eadba0effb878d2fb51f3ba5733e4c0b&scene=21#wechat_redirect
[Sharding-JDBC _ MyCAT]: http://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247486257&idx=1&sn=4d3c9c675f8833157641a2e0b48e498c&chksm=fa497480cd3efd96fe17975b0b8b141e87fd0a62673e6a30b501460de80b3eb997056f09de08&scene=21#wechat_redirect
[Elastic-Job]: http://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247486258&idx=1&sn=ae5665ae9c3002b53f87cab44948a096&chksm=fa497483cd3efd950514da5a37160e7fd07f0a96f39265cf7ba3721985e5aadbdcbe7aafc34a&scene=21#wechat_redirect
[TCC-Transaction]: http://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247486259&idx=1&sn=b023cf3dbf97e5da59db2f4ee632f5a6&chksm=fa497482cd3efd9402d71469f71863f71a6998b27e12ca2e00446b8178d79dcef0721d8e570a&scene=21#wechat_redirect
[Eureka _ Hystrix]: http://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247486260&idx=1&sn=8f14c0c191d6f8df6eb34202f4ad9708&chksm=fa497485cd3efd93937143a648bc1b530bc7d1f6f8ad4bf2ec112ffe34dee80b474605c22db0&scene=21#wechat_redirect
[Java]: http://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247486261&idx=1&sn=bd69f26aadfc826f6313ffbb95e44ee5&chksm=fa497484cd3efd92352d6fb3d05ccbaebca2fafed6f18edbe5be70c99ba088db5c8a7a8080c1&scene=21#wechat_redirect
[blog.csdn.net_yu876876_ article_details_84896789]: https://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247487551&idx=1&sn=18f64ba49f3f0f9d8be9d1fdef8857d9&scene=21#wechat_redirect
[B]: https://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247487551&idx=1&sn=18f64ba49f3f0f9d8be9d1fdef8857d9&chksm=fa496f8ecd3ee698f4954c00efb80fe955ec9198fff3ef4011e331aa37f55a6a17bc8c0335a8&scene=21&token=899450012&lang=zh_CN#wechat_redirect
[1_B]: https://blog.csdn.net/yu876876/article/details/84896789
[B 1]: https://blog.csdn.net/qq_44654974/article/details/120198638
[B 2]: https://blog.csdn.net/jenie/article/details/106066990
[B 3]: https://blog.csdn.net/yanshuanche3765/article/details/79945254
[bc32e6f18366f60e39f7a74f10fc942f.png]: /images/20220828/a396ff147ce04fb9848b822dccc7451b.png
[f66b1b9c16ff611817dabedcc64b39ff.png]: /images/20220828/5adf8d9ff32745489c30be15609771f2.png
[85b2e92ac80358d0e22a43e883559921.png]: /images/20220828/b468b75ce5ec4e5ca68c53ac7dbbb903.png
[f6e9abca41e6432301a45b202c2ecd3e.png]: /images/20220828/8ba35984b15640b698b3d2039e5422c8.png
[6d3b93768d1ab10a2350bb84c3b7ce76.png]: /images/20220828/dc65fbca6afb4296be4e135ebc8248dc.png
[6eabc21c2760726c431b567b553bdad4.png]: /images/20220828/a8d9823d1fb046a0ab83e4a58e53d998.png
[cd39b3f852317156504d2a7c1fa6d069.png]: /images/20220828/6a8e2db28c1a4f44af24ac98ce83bab7.png
[faf105d5dc83dbd0eaf55ce38a38f690.png]: /images/20220828/583426cc6fde41139baa7abe058d525e.png