B 树、B+ 树、B* 树

6个月前 阅读 154 评论 0 赞 0

B 树

为了磁盘或其它存储设备而设计的一种平衡多路查找树

特性

  • 树中每个结点最多含有 m 个孩子(m>=2)
  • 除根结点和叶子结点外,其它每个结点至少有 [ceil(m / 2)] 个孩子
  • 若根结点不是叶子结点,则至少有 2 个孩子
  • 所有叶子节点均在同一层
  • 如果一个非叶子节点有 N 个子节点,则该节点的关键字数等于 N-1
  • 除根结点,其它每个节点个数需满足 [ceil(m / 2)-1]<= n <= m-1
  • 每个节点至多有 m 颗子树

插入(均以 5 叉树为例)

未满直接插入,满了分裂

删除

  • 删除元素后仍能满足下限,直接删除,剩余元素向前移动
  • 父节点删除元素后未满足下限,不能上移子节点就下移祖父节点
  • 叶子节点删除元素后未满足下限:
    • 若兄弟节点丰满,从父节点下移一个元素,上移兄弟节点元素
    • 否则,下移父节点的一个元素,合并父节点和祖父节点

B+ 树

  • 磁盘读写代价更低
    B+ 树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对 B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说 IO 读写次数也就降低了

  • 查询效率更加稳定
    由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当

B 树和 B+ 树的区别

  • B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历
  • 由于B+树在内部节点上不好含数据信息,因此在内存页中能够存放更多的key。 数据存放的更加紧密,具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率
  • B树优点在于由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速

B* 树

相对于B+树他们的不同之处如下:

  • 关键字个数限制:B+ 树初始化的关键字初始化个数是cei(m/2),b树的初始化个数为(cei(2/3m))

  • B+ 树节点满时就会分裂,而 B* 树节点满时会检查兄弟节点是否满(因为每个节点都有指向兄弟的指针),如果兄弟节点未满则向兄弟节点转移关键字,如果兄弟节点已满,则从当前节点和兄弟节点各拿出 1/3 的数据创建一个新的节点出来

特点

在B+树的基础上因其初始化的容量变大,使得节点空间使用率更高,而又存有兄弟节点的指针,可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少

总结

从平衡二叉树、B树、B+树、B*树总体来看它们的贯彻的思想是相同的,都是采用二分法和数据平衡策略来提升查找数据的速度。不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理进行一步步的演变,每一次演变都是为了让节点的空间更合理的运用起来,从而使树的层级减少达到快速查找数据的目的

R 树

采用了B树分割空间的思想

用来存储高维数据的平衡树,最佳应用范围是处理2至6维的数据

采用了一种称为MBR(Minimal Bounding Rectangle)的方法

性质

  1. 除非它是根结点之外,所有叶子结点包含有m至M个记录索引(条目)。作为根结点的叶子结点所具有的记录个数可以少于m。通常,m=M/2

  2. 对于所有在叶子中存储的记录(条目),I是最小的可以在空间中完全覆盖这些记录所代表的点的矩形(注意:此处所说的“矩形”是可以扩展到高维空间的)

  3. 每一个非叶子结点拥有m至M个孩子结点,除非它是根结点

  4. 对于在非叶子结点上的每一个条目,i是最小的可以在空间上完全覆盖这些条目所代表的店的矩形(同性质2)

  5. 所有叶子结点都位于同一层,因此R树为平衡树

你的支持将鼓励作者继续创作

评论(0)

(无)