1. B-树的阶,是什么意思?
举个例子: 5阶的B-树, 阶数 m = 5
指的是:
对于非根节点: 每个结点最多5个孩子分支,分支指的是 孩子节点指针,
每个结点最多4个关键字【因为有个内容节点用来存储关键字个数】
【最多 阶数 个分支, 阶数-1 个 关键字】
最少 ceil( m/2) 个分支;最多m个
每个节点 最少 ceil( m/2) -1 个关键字;最多 m-1个
【4阶 B-树, 最少2个分支,5阶树最少3个分支,6阶树最少3个分支】
【4阶 B-树, 最少1个关键字,5阶树最少2个关键字,6阶树最少2个关键字】
对于根节点: 至少有两个分支,1个关键字
最多 5个孩子分支, 4个关键字
思路: 阶数 -> 分支数 -> 关键字个数
2. B-树 的数据结构
相当于 两个长度相同的数组,长度等于 阶数m:
第一个数组,存储的关键字。 第一个元素,存储的是关键字个数,所以最多 m-1关键字。
第二个数组,存储的孩子结点指针。 总共存了 m个 指针,即对应 m个孩子分支。
B-树 是平衡m叉查找树
3. B+树与B树的差异
B+树的数据结构与 B树 基本一样。
B+树 关键字个数 和 分支个数 相同。B-树 关键字个数比分支个数小1.
B+树 非根节点 关键字个数最少 ceil( m/2) , 最多 m个
根节点关键字 个数 最少1 个, 最多 m个
B+树 叶子节点 包含 所有关键字, 每个关键字对应的指针 指向一个记录。
非叶子结点 只相当于 索引,是孩子节点中关键字的最大值。