数据结构—B树、B+树、B*树

<!-- more -->

博客阐明

文章所波及的材料来自互联网整顿和集体总结，意在于集体学习和教训汇总，如有什么中央侵权，请分割自己删除，谢谢！

多叉树

多叉树（multiway tree）容许每个节点能够有更多的数据项和更多的子节点

多叉树通过从新组织节点，缩小树的高度，能对二叉树进行优化

文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页(页得大小通常为4k)，这样每个节点只须要一次I/O就能够齐全载入

2-3树

  • 2-3树的所有叶子节点都在同一层.(只有是B树都满足这个条件)
  • 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点.
  • 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点.
  • 2-3树是由二节点和三节点形成的树

插入规定:
  • 2-3树的所有叶子节点都在同一层.(只有是B树都满足这个条件)
  • 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点.
  • 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点
  • 当依照规定插入一个数到某个节点时，不能满足下面三个要求，就须要拆，先向上拆，如果下层满，则拆本层，拆后依然须要满足下面3个条件。
  • 对于三节点的子树的值大小依然恪守(BST 二叉排序树)的规定

B树

  • B树的阶：节点的最多子节点个数。比方2-3树的阶是3，2-3-4树的阶是4
  • B-树的搜寻，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则完结，否则进入查问
  • 关键字所属范畴的儿子结点；反复，直到所对应的儿子指针为空，或曾经是叶子结点
  • 关键字汇合散布在整颗树中, 即叶子节点和非叶子节点都存放数据.
  • 搜寻有可能在非叶子结点完结
  • 其搜寻性能等价于在关键字选集内做一次二分查找

B+树

B+树是B树的变体，也是一种多路搜寻树

  • B+树的搜寻与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树能够在非叶子结点命中），其性能也等价于在关键字选集做一次二分查找
  • 所有关键字都呈现在叶子结点的链表中（即数据只能在叶子节点【也叫浓密索引】），且链表中的关键字(数据)恰好是有序的。
  • 不可能在非叶子结点命中
  • 非叶子结点相当于是叶子结点的索引（稠密索引），叶子结点相当于是存储（关键字）数据的数据层
    更适宜文件索引零碎

B*树

B*树是B+树的变体，在B+树的非根和非叶子结点再减少指向兄弟的指针

  • B树定义了非叶子结点关键字个数至多为(2/3)M，即块的最低使用率为2/3，而B+树的块的最低使用率为B+树的1/2。
  • 从第1个特点咱们能够看出，B*树调配新结点的概率比B+树要低，空间使用率更高

感激

尚硅谷

以及勤奋的本人，集体博客，GitHub