B树的基本概念是什么？

本文共计2760个文字，预计阅读时间需要12分钟。

在计算机科学中，B+树是一种自平衡的树，能保持数据有序。适用于读写大量数据的存储系统，如磁盘，常作为数据库索引结构。理解B+树的概念，树是一种自平衡的数据结构。

在计算机科学中，B 树是一种自平衡的树，能够保持数据有序。其适用于读写相对大的数据块的存储系统，例如磁盘，因此也常作为数据库系统的索引结构。 理解 B 树的概念

B 树是一种自平衡的查找树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除数据的动作，都能在对数时间内完成。

同一般的二叉查找树不同，B 树是一棵多路平衡查找树，其特性是：结点的孩子结点数可以多于两个，且每一个结点处可以存储多个元素。

在 B 树中，非叶子结点可以拥有可变数量的子结点，为了维持在预先设定的数量范围内，通常是对非叶子结点进行合并和分离。其优势是不需要像其他自平衡查找树那样频繁地重新保持平衡，其劣势是结点未被完全填充时会浪费一些空间。

特性

通常，我们会在 B 树的名称前添加阶数以示说明，如 m 阶 B 树。一个 m 阶的 B 树具有以下特性：

• 任意结点最多有 m 个孩子结点
• 任意除根结点以外的非叶子结点最少有 \(\frac{m}{2}\) 个子结点
• 如果根结点不是叶子结点，那么它至少有 2 个孩子结点
• 有 k 个孩子结点的非叶子结点有 k-1 个键
• 所有的叶子结点都在同一层，B 树也是通过此约束来保持树的平衡

下述展示的是一个 3 阶 B 树：

变体

B 树可以指一个特定的树形结构，也可以指大体上的一类树形结构。