对于B+树的定义,有两种说法,一种是国内常见且强调的关键字数量和子树数量相同;另一种是国外大多数教程所说的,类似于B树的,关键字数量比子树数量少1。
我现在很好奇,关键字数和子树数量相同的B+树是如何构建的。我查了很多网页和国内的书,往往都是一笔带过,讲不清楚。假设一个场景,一棵最多3个关键字的B+树,根节点已经插入了1,2,3,现在再插入4,他会发生什么?
对于关键字数比子树数量少1的B+树,我已经很了解了。大概如下图
那对于关键字数和子树数相同的B+树,它是如何分裂的呢?
希望有人能解决我的疑惑,在此先谢谢各位。