完整B树算法Java实现代码

完整完整B树算法树算法Java实现代码实现代码

主要为大家详细介绍了完整的B树算法Java实现代码,具有一定的参考价值，感兴趣的小伙伴们可以参考一下

定义定义

在计算机科学中，B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。

为什么要引入为什么要引入B树树?

首先，包括前面我们介绍的红黑树是将输入存入内存内存的一种内部查找树内部查找树。

而B树是前面平衡树算法的扩展，它支持保存在磁盘或者网络磁盘或者网络上的符号表进行外部查找外部查找，这些文件可能比我们以前考虑的输入要大的多（难以存入内存）。

既然内容保存在磁盘中，那么自然会因为树的深度过大而造成磁盘I/O读写过于频繁（磁盘读写速率是有限制的），进而导致查询效率低下。

其他结点为内部结点，保存索引，即其他结点为内部结点，保存索引，即key和和next。

内部结点的关键字key：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

内容结点的指针next：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

例如：（M=3）

查找和插入

为了方便这里用了一个特殊的哨兵键，它小于其他所有键，用*表示。

一开始B树只含有一个根结点，而根结点在初始化时仅含有该哨兵键。

内部结点中的每个键都与一个结点相关联，以此结点为根的子树种，所有的键都大于等于与此结点关联的键，但小于其他所有键。

这些约定在很大程度上能够简化代码。

代码