数据结构-B树

从二叉搜索树出发，探讨数据结构中的B树，它是一种多路平衡查找树，每个结点的特性至关重要。

B树以每个结点最多存储m个关键字为特点（阶数m），非空B树需满足以下规则：根节点可有任意数量的子树，但至少有两个；除根外，所有非叶结点至少有m/2个子树（向上取整），保证了非叶结点至少有m-1个关键字；所有叶结点位于同一层，没有数据，是查找失败的标志。

例如，考虑非终端结点，如含有5和11的第二层，划分为三个区间，这就体现了每个结点最多有m个子树的特性。B树对关键字数量的限制，是为了防止树的变细，提高查找效率，避免过多层级查找。

B树保持平衡的目的是为了减少磁盘访问次数，提升查找效率。在构建B树时，要求所有节点的子树高度相同，避免高度差异过大。

关键特性包括：根节点至少有两棵子树，所有叶结点在最底层，且非叶结点包含信息，而叶结点不包含。

对于B树的高度，根节点至少两个分叉，随着递增的分支，每层最多有m/2个子节点。最低高度与满二叉树类似，而最大高度则通过限制分叉数来达到平衡。

插入B树时，关键在于保持关键字分布的平衡，通过定位和调整节点来确保规则的遵守。删除操作则要考虑节点合并或关键字转移，以保持B树的定义和平衡。

B+树是B树的一种变体，强调所有关键字都在叶结点中，非叶结点仅存储索引信息，支持顺序查找。B+树与B树的主要区别在于叶结点和非叶结点中包含信息的差异。