数据结构：B-树和B+树的相同点和不同点

曾经终败给现在 2023-05-28 11:11 2阅读 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>

==回答思路==：

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+树更加矮胖，

1.  所有查询都要查找到叶子节点，查询性能稳定；

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

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

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