4 多路查找树(B 树)

Wu Jun 2019-05-23 19:48:27
01 数据结构与算法 > 数据结构 > 03 查找

多路查找树:每一个结点的孩子数可以多于两个,且每一个结点处可以存储多个元素。

1、2-3 树

2-3 树复杂的地方就在于新结点的插入和已有结点的删除。

插入

删除

2、2-3-4 树

3、B 树

B 树 (B-tree)是一种平衡的多路查找树,2-3 树和 2-3-4 树都是 B 树的特例。

一个 m 阶的 B 树具有如下属性:

查找

在 B 树上查找的过程是一个顺指针查找结点和在结点中查找关键字的交叉过程

插入和删除

B 树的插入和删除,方式是与 2-3 树和 2-3-4 树相类似的,只不过阶数可能会很大而已。

减少内存与外存交换数据次数

对 B 树进行调整,使得 B 树的阶数(或结点的元素)与硬盘存储的页面大小相匹配。

比如说一棵 B 树的阶为 1001 (即 1 个结点包含 1000 个关键字) ,高度为 2 ,它可以储存超过 10 亿个关键字,我们只要让根结点持久地保留在内存中,那么在这棵树上,寻找某一个关键字至多需要两次硬盘的读取即可。

4、B+树

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

一棵 m 阶的 B+树和 m 阶的 B 树的差异在于:

查找

B+树的结构特别适合带有范围的查找。

插入和删除

B+树的插入、删除过程也都与 B 树类似,只不过插入和删除的元素都是在叶子结点上进行而已。