B-树和B+树区别

客官°小女子只卖身不卖艺 2023-03-06 08:13 43阅读 0赞

图片来源: [link][].

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzUxODAzOA_size_16_color_FFFFFF_t_70]  
一个m阶的B-树和B+的区别，具有如下几个特征：

<table> 
 <tbody> 
  <tr> 
   <td> 关键词 </td> 
   <td> B-树 </td> 
   <td> B+树 </td> 
   <td> 备注 </td> 
  </tr> 
  <tr> 
   <td> 最大分支，最小分支 </td> 
   <td> 每个结点最多有m个分支（子树），最少⌈m/2⌉（中间结点）个分支或者2个分支（是根节点非叶子结点）。 </td> 
   <td> 同左 </td> 
   <td> m阶对应的就是就是最大分支 </td> 
  </tr> 
  <tr> 
   <td> n个关键字与分支的关系 </td> 
   <td> 分支等于n+1 </td> 
   <td> 分支等于n </td> 
   <td> 无 </td> 
  </tr> 
  <tr> 
   <td> 关键字个数（B+树关键字个数要多） </td> 
   <td> 大于等于⌈m/2⌉-1小于等于m-1 </td> 
   <td> 大于等于⌈m/2⌉小于等于m </td> 
   <td> B+树关键字个数要多，+体现在的地方。 </td> 
  </tr> 
  <tr> 
   <td> 叶子结点相同点 </td> 
   <td> 每个节点中的元素互不相等且按照从小到大排列；所有的叶子结点都位于同一层。 </td> 
   <td> 同左 </td> 
   <td> 无 </td> 
  </tr> 
  <tr> 
   <td> 叶子结点不相同 </td> 
   <td> 不包含信息 </td> 
   <td> 叶子结点包含信息，指针指向记录。 </td> 
   <td> 无 </td> 
  </tr> 
  <tr> 
   <td> 叶子结点之间的关系 </td> 
   <td> 无 </td> 
   <td> B+树上有一个指针指向关键字最小的叶子结点，所有叶子节点之间链接成一个线性链表 </td> 
   <td> 无 </td> 
  </tr> 
  <tr> 
   <td> 非叶子结点 </td> 
   <td> 一个关键字对应一个记录的存储地址 </td> 
   <td> 只起到索引的作用 </td> 
   <td> 无 </td> 
  </tr> 
  <tr> 
   <td> 存储结构 </td> 
   <td> 相同 </td> 
   <td> 同左 </td> 
   <td> 无 </td> 
  </tr> 
 </tbody> 
</table>

**B+树是B-树的一种变体，而B-树是二叉排序树的一种升级。二排序树是二路查找，而b+树树多路查找，一个m阶的b+树每个节点最多有m个分支，节点最多会有m个关键字，是有序排列的，每个关键字的左分支节点的内关键字都比它的值小，而有分支节点内的关键字都比他大。**

回答思路：

1.  m阶B-树和B+树都满足\*\*：m阶就是结点最大分支m\*\*。
2.  但是B+树的“+”体现在哪呢：首先，**B+树的每个结点内关键字n个数最大值比B-树多1**。
3.  根据1，2得知\*\*：n个关键字与分支的关系：B-树分支为n+1,B-树分支为n\*\*。
4.  再考虑叶子结点相同点\*\*：每个节点中的元素互不相等且按照从小到大排列；所有的叶子结点都位于同一层\*\*。
5.  再考虑叶子结点不同点\*\*：B+树上有一个指针指向关键字最小的叶子结点，所有叶子节点之间链接成一个线性链表\*\*。
6.  再考虑叶子结点不同点2\*\*：B+树结点不包含信息；叶子结点包含信息，指针指向记录\*\*。
7.  再考虑非叶子结点不同点\*\*：B-树非叶子结点一个关键字对应一个记录的存储地址；B+树非叶子结点只起到索引的作用\*\*。

**【题目拓展：B+树比B树的优势】**

1.  单一节点存储更多的元素，使得查询的IO次数更少；

> 这也使得B+树相对于二叉查找树和b-树，都更加矮胖，

1.  所有查询都要查找到叶子节点，每次查询IO次数相同，查询性能稳定；

> 任何关键字的查询必须走从根结点到叶子结点，查询路径长度相同

1.  所有叶子节点形成有序链表，便于范围查询。

##### 浅析Mysql索引数据结构演变 #####

https://blog.csdn.net/weixin\_34019144/article/details/93181425

[link]: https://www.jianshu.com/p/71700a464e97
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzUxODAzOA_size_16_color_FFFFFF_t_70]: /images/20230208/df746c9feb8a43539b0d03530ba74d68.png