B+树

与B树的区别：

• 有k个子结点就有k个关键字 | B树只有k-1个关键字

  • B树根结点关键字个数$\in [1,m-1]$$\in [1,m-1]$,B+树$\in [1,m]$$\in [1,m]$
  • B树分支结点关键字个数$\in [\lceil m/2-1\rceil ,m-1]$$\in [\lceil m/2 - 1 \rceil,m - 1]$ ,B+树$\in [\lceil m/2\rceil ,m]$$\in [\lceil m/2 \rceil, m]$

• 所有数据均放在叶子结点中，分支结点还有根结点仅仅是作为索引 | B树的分支结点也会有数据

  • B+树分支结点因为是索引，用来表示子树最大值，所以可以有重复
  • B树分支结点有数据，数据不重复所以没有重复
  • B+树所有数据都在最底层，所以查找速度“稳定”，不管成功还是失败都会走到最下边一层
  • B树如果查找数据位于根结点速度就会非常快，而查不到数据时就会非常慢，所以查找速度“不稳定”

• B+树的所有叶子结点构成一个有序链表，可以按关键字的顺序遍历全部记录 | B树有些数据都在分支结点上当然不能这样搞

m阶B+树特点：

• 每个分支结点最多有m棵子树（孩子结点）

• 非叶根结点至少有两棵子树，其他每个分支结点至少有$\lceil m/2\rceil$$\lceil m/2 \rceil$ 棵子树

• 结点的子树个数与关键字个数相等

• 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶子结点按大小顺序相互连接起来（值此顺序查找）

  • 非叶子结点不含有关键字对应记录的存储地址，可以使一个磁盘块包含更多关键字，使得B+树的阶更大，树高更矮，读磁盘次数更少，查找更快

• 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针

查找

与B树相似

不同的是，如果在分支结点找到相等的值也不能直接返回，需要继续查找下一层，直到找到叶子结点的目标

也可以像链表一样从子结点最左边开始一个个找