乐趣区

关于java:数据结构B树B树B树

数据结构—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

退出移动版