8.8 B树

8.8 B树

什么是B树?有什么用呢?B树是由什么演变过来的呢?

多路查找树(muitl-way search tree),其每一个节点的孩子数可以多于两个,且每一个节点处可以存储多个元素。主要有4种特殊形式。

1. 2-3 树

1.1 定义

其中的每一个节点都具有两个孩子(称为2节点)或者三个孩子(称为3节点)。
并且2-3树中所有的叶子都在同一层

Qi85LT.png

1.2 2结点

一个2节点包含元素孩子(或者没有孩子)。 左小右大

1.3 3结点

包含一小一大元素孩子(或者没有孩子)。 左中右

1.4 2-3树的插入操作

1.4.1 空树

直接插

1.4.2 插入到2结点的叶子上

将2结点变成3结点

QiGPFH.png

1.4.3 往3结点中插入元素

1.4.3.1 双亲结点是2结点

QiGDpR.md.png

1.4.3.2 双亲结点是3结点,双亲的双亲是2结点

QiGWAe.png

1.4.3.3 双亲结点是3结点,双亲的双亲是3结点

QiJPBT.md.png

1.5 2-3树的删除操作

1.5.1 删除的元素是在3结点的叶子结点

QiJWrV.png

1.5.2 删除的元素是2结点

1.5.2.1 双亲是2结点,右孩子是3结点

QiYaW9.png

删除后左旋

1.5.2.2 双亲是2结点,右孩子是2结点

QiYoef.md.png

方法是将右结点变成3结点

1.5.2.3 双亲是3结点

QitJXt.png

方法是将双亲拆分

1.5.2.4 满二叉树

QitHnx.png

1.5.3 删除的是非叶子结点

重点是找到前驱或者后继

QiNt29.png

2. 2-3-4树

2.1 定义

2-3-4树是2-3树的扩展,包括了4节点的使用,一个4节点包含小中大三个元素四个孩子(或没有孩子)。

QiNLMn.png

3.B树

3.1 定义

B树(B-树)是一种平衡的多路查找树。2-3树和2-3-4树都是B树的特例。节点最大的孩子数组称为B树的(order),因此,2-3树是3阶B树,2-3-4树是4阶B树。

Qiwkss.md.png

3.2 B树的数据结构为内外存的数据交互准备的

当要处理的数据很大时,无法一次全部装入内存。这时对B树调整,使得B树的阶数与硬盘存储的页面大小相匹配。比如说一棵B树的阶为1001(即1个节点包含1000个关键字),高度为2(从0开始),它可以存储超过10亿个关键字(1001x1001x1000+1001x1000+1000),只要让根节点持久的保留在内存中,那么在这颗树上,寻找某一个关键字至多需要两次硬盘的读取即可。

4.B+树

QiB7GT.png

B+树中,出现在分支节点中的元素会被当做他们在该分支节点位置的中序后继者(叶子节点)中再次列出。另外,每一个叶子节点都会保存一个指向后一叶子节点的指针


  目录