B树为什么具有相同的深度？

B树的分裂行为导致了B树具有相同的深度。不过要清楚的知道这一点&＃xff0c;要从
节点从0到节点变满&＃xff0c;到第一次有分层&＃xff0c;知道深度不断增大的流程开始&＃xff0c;直接上图&＃xff1a;

首先是一个空的根节点&＃xff1a;

然后第一次有了第一个关键字&＃xff1a;

由于其节点元素大小不是我的观察重点&＃xff0c;所以用e代替&＃xff0c;用\代表空

假如我们的B树最小度数为t,那么一直插入关键字的话&＃xff1a;
先根节点称为一个满节点&＃xff1a;

------------------------ 【1-a】 3个关键字&＃xff0c;所有孩子为空--------------------------

------------------------ 【1-b】 2t-2个关键字关键字&＃xff0c;所有孩子为空。--------------
当节点存在2t-2个关键字时&＃xff0c;其处在一个临近分裂的状态&＃xff0c;节点在此环境下&＃xff0c;
再插入一个关键字&＃xff0c;B树为了方便后续插入&＃xff0c;即防止分裂向上传播&＃xff0c;会将其
预分裂。
分裂行为如下&＃xff0c;插入了一个关键字&＃xff0c;节点满了2t-1个。&＃xff08;此节点为合法B树节点&＃xff09;

继续不断地添加节点&＃xff0c;其中只要当第二层的某个节点等于2t-1关键字,其就会给父节点增加一个关键字。&＃xff08;这样做实际上维持了父节点关键字个数n&＃xff0c;具有n&＃43;1孩子的性质&＃xff09;

最终子节点不断增多&＃xff0c;第一层根节点又有2t-1个了&＃xff0c;根节点也要分裂不过这次多少不一样&＃xff0c;它的孩子域下有子代的&＃xff0c;此时的分裂带有子代分裂。

再次观察分裂细节&＃xff08;把上面的根节点放大&＃xff09;&＃xff0c;此时根节点开始分裂&＃xff1a;

其中每个椭圆都是具有t-1个关键字叶子节点。
这种分裂都是按这种方式进行&＃xff0c;其实现在就很好理解为什么叶子节点深度相同。因为B树不像二叉树一样在叶子节点的下面插入&＃xff0c;而是就是插入到叶子节点&＃xff0c;这样叶子节点如果有空间&＃xff0c;就插了&＃xff0c;没有空间&＃xff0c;就分裂成两个相同深度的叶子节点&＃xff0c;如果父节点也满了&＃xff0c;会继续父节点也分裂&＃xff0c;直到满足存储需求&＃xff0c;如果到根节点还没满足&＃xff0c;就新建一个根节点&＃xff0c;将原来父节点分裂&＃xff0c;深度加一层。而原来父节点是两个子代域具有相同深度&＃xff0c;相同深度的两个子代域连接一个父节点&＃xff0c;保证其后叶子节点深度相同。
因此&＃xff0c;空间够不够深度都不变&＃xff0c;一开始深度相同&＃xff0c;那深度就一致相同了。