B+树的基本概念及性质

B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。

一棵m阶的B+树需满足下列条件:

1、每个分支结点最多有m棵子树。
2、非叶根结点至少有两棵子树,其他每个分支结点至少有⌈m/2⌉棵子树。
3、结点的子树个数与关键字个数相等。
4、所有叶结点包含全部关键字及指向相应记录的指针，而且叶结点中将关键字按大小顺序排列,并且相邻叶结点按大小顺序相互链接起来。
5、所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针。

B树与B+树的区别

1、在B树中，具有n个关键字的结点含有（n+1）棵子树；而在B+树中，具有n个关键字的结点只含有n棵子树,即每个关键字对应一棵子树。
2、在B树中，根结点的关键字个数n的范围是1 <= n <= m-1,非根结点的范围是⌈m/2⌉-1<=n <= m-1；而在B+树中，根结点的关键字个数n的范围是1 <= n <= m,非根结点的范围是⌈m/2⌉<=n <= m。
3、在B+树中，所有非叶结点仅起到索引作用，即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
4、在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的；而在B+树中，叶结点包含了全部关键字，即其他非叶结点中的关键字包含在叶结点中。

例子：4 阶 B+ 树的示例

补充1：通常在 B+树中有两个头指针， 一个是指向根结点，一个是指向关键字最小的叶子结点。

补充2：可以对 B+ 树进行两种查找运算： 一种是从最小关键字开始的顺序查找，一种是从根结点开始，进行多路查找。

补充3： B+ 树在查找过程中，如果非叶子结点上的关键字值等于给定值时并不终止，而是继续向下查找直到叶结点上的该关键字为止。所以在 B+ 树中的查找，无论查找成功与否，每次查找都是从根结点到叶结点的路径。

为什么MySQL要用B+树做索引?

HASH的查找和删除的时间复杂度都是O(1). 但是如果出现HASH碰撞的话, 需要使用扩展链表法(JDK1.8之后, 如果链表长度大于8则转换为红黑树, 如果低于6则,转换为链表). 这样的话如果数据库中存储的数据量比较大, 那么发生HASH碰撞发生的次数就会越来越多. 时间复杂度会越来越高. 而且我们平时查询的时候经常会用到ORDER BY GROUP BY, 在这种排序查询的状态下, 他的时间复杂度就会变成O(N).

使用B+树的话, 因为它只有叶子节点保存数据, 所以可以将索引节点一次加载到内存当中, 而消耗很少的内存量. 同样大小的空间B+树可以比B树, 加载更多的索引节点. 而且B+树由于其叶子节点存储数据的原因, 它的查找每个元素所花费时间的方差也就更低. 这样也更稳定可控.

数据库引擎为InnoDB的时候, 数据库一般的层数为三层, 最多存储数据量为2.1千万. 如果大于这个数据量就需要分库分表, 否则层数大于四层, 会造成查询效率降低.

为什么不使用平衡二叉树/...

课后习题

【2017年真题】下列应用中，适合使用B+树的是（）
A.编译器中的词法分析        B.关系数据库系统中的索引
C.网络中的路由表快速查找        D.操作系统的磁盘空闲块管理

参考答案：B

【2016年真题】B+树不同于B树的特点之一是（）
A.能支持顺序查找
B.结点中含有关键字
C.根结点至少有两个分支
D.所有叶结点都在同一层上

参考答案：A