关于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