数据结构：B-树和B+树的相同点和不同点
前言：其他内容正在学习中…
【答案】
图片来源: link.
一个m阶的B-树和B+的区别，具有如下几个特征：
| 关键词 | B-树 | B+树 | 备注 |
| 最大分支，最小分支 | 每个结点最多有m个分支（子树），最少⌈m/2⌉（中间结点）个分支或者2个分支（是根节点非叶子结点）。 | 同左 | m阶对应的就是就是最大分支 |
| n个关键字与分支的关系 | 分支等于n+1 | 分支等于n | 无 |
| 关键字个数（B+树关键字个数要多） | 大于等于⌈m/2⌉-1小于等于m-1 | 大于等于⌈m/2⌉小于等于m | B+树关键字个数要多，+体现在的地方。 |
| 叶子结点相同点 | 每个节点中的元素互不相等且按照从小到大排列；所有的叶子结点都位于同一层。 | 同左 | 无 |
| 叶子结点不相同 | 不包含信息 | 叶子结点包含信息，指针指向记录。 | 无 |
| 叶子结点之间的关系 | 无 | B+树上有一个指针指向关键字最小的叶子结点，所有叶子节点之间链接成一个线性链表 | 无 |
| 非叶子结点 | 一个关键字对应一个记录的存储地址 | 只起到索引的作用 | 无 |
| 存储结构 | 相同 | 同左 | 无 |
- m阶B-树和B+树都满足：m阶就是结点最大分支m。
- 但是B+树的“+”体现在哪呢：首先，B+树的每个结点内关键字n个数最大值比B-树多1。
- 根据1，2得知：n个关键字与分支的关系：B-树分支为n+1,B-树分支为n。
- 再考虑叶子结点相同点：每个节点中的元素互不相等且按照从小到大排列；所有的叶子结点都位于同一层。
- 再考虑叶子结点不同点：B+树上有一个指针指向关键字最小的叶子结点，所有叶子节点之间链接成一个线性链表。
- 再考虑叶子结点不同点2：B+树结点不包含信息；叶子结点包含信息，指针指向记录。
- 再考虑非叶子结点不同点：B-树非叶子结点一个关键字对应一个记录的存储地址；B+树非叶子结点只起到索引的作用。
【题目拓展】
B+树比B树的优势：
- 单一节点存储更多的元素，使得查询的IO次数更少；
这也使得B+树更加矮胖，
- 所有查询都要查找到叶子节点，查询性能稳定；
任何关键字的查询必须走从根结点到叶子结点，查询路径长度相同
- 所有叶子节点形成有序链表，便于范围查询。