⭐⭐⭐ Spring Boot 项目实战	⭐⭐⭐ Spring Cloud 项目实战
《Dubbo 实现原理与源码解析 —— 精品合集》	《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》	《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》	《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》	《Java 面试题 + Java 学习指南》

摘要: 原创出处 blog.csdn.net/yu876876/article/details/84896789 「海马HiMark」欢迎转载，保留摘要，谢谢！

🙂🙂🙂关注**微信公众号：【芋道源码】**有福利：

RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表

RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址

您对于源码的疑问每条留言都将得到认真回复。甚至不知道如何读源码也可以请教噢。

新的源码解析文章实时收到通知。每周更新一篇左右。

认真的源码交流微信群。

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

B树的原理

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

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

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

辨析1：B树与红黑树的区别

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

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

B树的定义

对于一颗M阶的B树

树中的每个节点最多有m个孩子

除了根节点和叶子节点外，其他节点最少含有m/2（取上限）个孩子

若根节点不是叶子节点，则根节点最少含有两个孩子

所以叶子节点都在同一层，叶子节点不包含任何关键字信息

B树的类型与节点定义

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

B树的插入操作

B树的插入

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

对于高度为h的m阶B树，新节点一般插在第h层。

1）若该节点中关键码个数小于m-1，则直接插入

2）若该节点中关键码个数等于m-1，则节点分裂。以中间的关键码为界，将节点一分为二，产生一个新的节点，并将中间关键码插入到父节点中。

重复上述过程，最坏情况一直分裂高根节点，则B树就会增加一层。

B+树的原理

B+树特点

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

B+树的定义

1）有n棵子树的结点含有n个关键字，每个关键字都不保存数据，只用来索引，并且所有的数据都存储在叶子节点

2）所有叶子结点包含所有关键字信息和指向关键字记录的指针，其中关键字从小到大顺序链接

B+树的插入操作

B+树插入

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所有关键字查询的长度是一样的，查询效率稳定。

芋道源码 —— 纯源码解析博客

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