B树和B+树性质对比
B树和B+树性质对比
通用概念：
阶：所有结点的孩子个数的最大值称为阶。通常用m表示
终端结点：最后一排具有关键字的结点。
叶子结点：也叫失败结点，没有任何信息的一排结点。
B树（B-树）
概念：
也叫作多路平衡查找树、B-树。
注：2-3树、2-3-4树是B树的一种特定情况。而B+树则是B树的变形。
性质（条件）//注意分清子树和结点
B树是一种平衡的多分树，通常我们说m阶的B树，它必须满足如下条件：
- 每个结点最多有m棵子树。
- 具有k个子树的非叶结点包含k -1个键。
- 每个非叶子结点（除了根）具有至少⌈ m/2⌉子树，即最少有⌈ m/2⌉-1个关键字。
- 如果根不是终端结点，则根结点至少有一个关键字，即至少有2棵子树。【根的关键字取值范围是[1，m-1]，子树的取值范围是[2,m]】
- 所有叶子结点都出现在同一水平，没有任何信息（高度一致）。【带有关键字那个叫做终端结点】
关键字：最少⌈ m/2⌉-1，最多m-1
子树：最少⌈ m/2⌉，最多m
其他性质：
B+树
概念：
B+树是应数据库所需要而出现的一种B树的变形树。
性质（条件）//注意分清子树和结点
一棵m阶B+树，它必须满足如下条件：
- 每个结点最多有m棵子树。
- 如果根不是终端结点，则根结点至少有一个关键字，即至少有2棵子树。【根的关键字取值范围是[1，m-1]】
- 每个关键字对应一棵子树（与B树的不同），具有k个子树的非叶结点包含k 个键。
- 每个非叶子结点（除了根）具有至少⌈ m/2⌉子树，即最少有⌈m/2⌉个关键字。
- 终端结点包含全部关键字及相应记录的指针，叶结点中将关键字按大小顺序排序，并且相邻叶结点按大小顺序相互链接起来。
- 所有分支结点（可以视为索引的索引）中金包含他的各个子节点（即下一级的索引块）中关键字最大值，及指向其子结点的指针。
m阶B树和B+树的主要对比：
| B树 | B+树 | |
|---|---|---|
| 关键字 | 最少：⌈m/2⌉-1 最多：m-1 | 最少：⌈m/2⌉ 最多：m |
| 子树 | 非叶根：至少2棵，最多m棵 其他：至少⌈m/2⌉，最多m | 非叶根：至少2棵，最多m棵 其他：至少⌈m/2⌉，最多m |
| key-subtree | k个key有k+1棵tree | k个key有k棵tree |
| 非终端节点 | 包含有用信息 | 只是索引 |
| 终端节点 | 不会出现非终端节点的key | 会出现非终端节点的key |
- 在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶子结点中的每个索引项只是包含了对应子树最大关键字和指向该孩子树的指针，不含有该关键字对应记录的存储地址。
- 在B+树中，终端结点包含全部关键字及相应记录的指针，即非终端结点出现过的关键字也会在这重复出现一次。而B树是不重复的。