B树

B 树的阶,指的是 B 树中节点的子节点数目的最大值

B树(英语:B-tree)是一种自平衡的树,能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作,都在对数时间内完成。B树,概括来说是一个一般化的二叉查找树(binary search tree)一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同,B树适用于读写相对大的数据块的存储系统,例如磁盘。B树减少定位记录时所经历的中间过程,从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。

在B树中,内部(非叶子)节点可以拥有可变数量的子节点(数量范围预先定义好)。当数据被插入或从一个节点中移除,它的子节点数量发生变化。为了维持在预先设定的数量范围内,内部节点可能会被合并或者分离。因为子节点数量有一定的允许范围,所以B树不需要像其他自平衡查找树那样频繁地重新保持平衡,但是由于节点没有被完全填充,可能浪费了一些空间。子节点数量的上界和下界依特定的实现而设置。例如,在一个2-3 B树(通常简称2-3树),每一个内部节点只能有2或3个子节点。

https://zh.wikipedia.org/wiki/B树

上一篇:浙江大学数据结构 03-树3 Tree Traversals Again(25 分)


下一篇:1020 Tree Traversals (25分)