B树、B+树、B*树——简单介绍

B树、B+树、B*树——简单介绍
强烈推介IDEA2020.2破解激活,IntelliJ IDEA 注册码,2020.2 IDEA 激活码

一、为什么是有B树


二叉树存在的问题:二叉树的构建是在内存中执行的,需要将磁盘中的文件通过 IO操作进行读取。如果二叉树的节点少,这样也没有问题,但是如果二叉树的节点很多(比如说一个亿),则存在如下问题:
【1】在构建二叉树时,需要多次进行 IO操作(海量数据存储在数据库或者文件中),节点海量,构建二叉树时,速度有影响。
【2】节点海量,也造成了二叉树的高度很高,会降低操作速度。

二、B树(多叉树)


【1】在二叉树中,一个节点最多可以有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点,就是多叉树;
【2】2-3树,2-3-4树就是多叉树,多叉树通过重新组织节点,减少树的高度,能对二叉树进行优化。如下图就是一个2-3树;
  

【3】文件系统及数据库系统的设计者利用磁盘预读(预先读取)原理,将一个节点的大小设置为页<page:数据读取的最小单位>的大小(通常为4k),这样每个节点只需要一次 IO就能载入内存;B树(B+树)广泛应用于文件存储系统及数据库文件系统中。

2-3 树基本介绍:最简单的 B树结构,具有如下特点:
  ■  2-3 树的所有叶子节点都在同一层(只要是B树都满足这一点);
  ■  有两个子节点的叫二节点,二节点要么没有子节点,要么有两个子节点;
  ■  有三个子节点的叫三节点,三节点要么没有子节点,要么有三个子节点;
  ■  2-3 树是由二节点和三节点构成的树;
  ■  当按照规则插入一个数到某个节点时,不能满足上述要求时,就需要拆分。先向上拆,如果上层满了,则拆本层。拆后仍需要满足上述条件;
  ■  对于三节点的子树的值的大小仍然遵循(BST:二叉排序树)的规则;

2-3 树的插入和删除节点案例链接

B-Tree树即B(Balanced:平衡)树,有人将B-Tree 翻译成 B-树,容易让人产生误解,会以为 B-树是一种树。实际上,B-Tree就是B树。

三、B树、B+树、B*树


【1】B树介绍:前面介绍的2-3、2-3-4树就是 B树,在 MySql 中经常听说某种索引是基于 B树、B+树的,如下图:
  

【2】B+树介绍:B+ 树是B树的变体,也是一种多路搜索树,如下图:
 

【3】B* 树介绍:B* 树是B+树的变体,在B+树的非根和非叶子节点增加了指向兄弟的指针,如下图:

本文来源程序猿进阶,由javajgs_com转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/8262

发表评论