B+树

B+树的性质

一棵m阶的B+树满足如下性质:

  • 每个节点最多有m个关键字
  • 对于非空树,根节点有最少一个关键字
  • 除了根节点,每个节点有最少ceil(m/2)个关键
  • 所有的叶子节点都出现在同一层
  • 有n个关键字的节点,也有n个孩子。关键字有序排列,并且对于非叶子节点:KeyWordi <= Childreni中所有的关键字

在B+树中,所有的关键字都存放在叶子节点。而在B树中,所有的节点都存放关键字。在B+树中,非叶子节点的关键字,只充当索引的作用,所以在搜索的时候,一定要搜索到叶子节点,而在B树中,可能无需搜索至叶子节点就找到关键字了。
在B+树中,所有的叶子节点,都通过指针连接起来。
在B+树中,有两个指针:一个指向根节点,一个指向最左面的叶子节点。
下面是一棵3阶B+树的例子:
b<em>plus</em>tree.jpg


B+树的深度

对于关键字总数为n的m阶B+树而言:

  • 当根节点只有一个元素,其他节点有ceil(m/2)个元素的时候,B+树的深度最大:
    设j = ceil(m/2)、h为B+树的深度,则:
    j + j2 + ... + jh-1 + j = n --->
    j×((1-jh-1)/(1-j)) = n - j --->
    (j-1)×(n-j)/j + 1 = jh-1 --->
    h - 1 = logj((j-1)×(n-j)/j + 1) --->
    h = 1 + logj((j-1)×(n-j)/j + 1)
    增长率是logmn。
  • 当每个节点都有m个关键字时,树的深度最小:
    设h为B+树的深度,则:
    m + m2 + ... + mh = n --->
    m×((1-mh)/(1-m)) = n --->
    h = logm((m×n-n+m)/m)
    增长率是logmn。

B+树的插入、搜索、删除

与B树的区别点主要在于:

  • 插入的时候,如果插入的关键字比根节点最小的关键字还小,那么需要沿路更新非终端节点的索引关键字
  • 删除节点的时候,也可能需要以回溯的方式,更新非终端节点中的索引关键字
  • 删除节点的时候,对于节点的父节点是根节点的情形,需要特殊处理

代码实现

tim-chow的github

感谢浏览tim chow的作品!

如果您喜欢,可以分享到: 更多

如果您有任何疑问或想要与tim chow进行交流

可点此给tim chow发信

如有问题,也可在下面留言: