转载

B+树

B+ 树是一种树数据结构,通常用于数据库操作系统的文件系统中。

  • B+ 树的特点是能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。
  • B+ 树元素自底向上插入,这与二叉树恰好相反。

B+ 树在节点访问时间远远超过节点内部访问时间的时候,即可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度,平衡操作不经常发生,而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。

节点结构

  • 在 B+ 树中的节点通常被表示为一组有序的元素和子指针。
  • 如果此B+树的序数(order)是m ,则除了根之外的每个节点都包含最少m/2(向下取整)个元素最多 m-1 个元素,对于任意的节点有最多 m 个子指针。
  • 对于所有内部节点,子指针的数目总是比元素的数目多一个。因为所有叶子都在相同的高度上,节点通常不包含确定它们是叶子还是内部节点的方式。
  • 每个内部节点的元素充当分开它的子树的分离值。例如,如果内部节点有三个子节点(或子树)则它必须有两个分离值或元素 a1 和 a2。在最左子树中所有的值都小于 a1,在中间子树中所有的值都在 a1 和 a2 之间,而在最右子树中所有的值都大于 a2。
正文到此结束
本文目录