1.B-树的相关问题

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+树 叶子节点 包含 所有关键字, 每个关键字对应的指针 指向一个记录。

                非叶子结点 只相当于 索引,是孩子节点中关键字的最大值。

     

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容