B 树性质

传统的二叉搜索树有一些不尽人意的局限性。引入B树，一种通用的数据结构，可以轻松处理海量数据。传统的二叉搜索树由于其糟糕的速度和高内存利用率，在存储和搜索大量数据时变得不可行。B树，通常被称为平衡树或B-树，是一种自平衡树，其创建目的就是为了克服这些限制。

B树，也被称为“大键”树，与传统的二叉搜索树的区别在于它们可以在单个节点中容纳大量键。

B树的每个节点可以有多个键，这增加了分支因子并降低了树的高度。由于这种降低的高度减少了磁盘I/O，搜索和插入操作完成得更快。硬盘、闪存和CD-ROM等存储设备最受益于B树，因为它们的数据访问缓慢而笨拙。

B树中的每个节点必须包含最小数量的键，以保持树的平衡。无论树最初的形状如何，这种平衡确保了插入、删除和搜索等操作的时间复杂度始终为O(log n)。

B树时间复杂度

这里，“n”是B树中元素的总数。

B树特性

• B树的所有叶子节点都在同一层。
• B树由最小度数“t”定义。磁盘块的大小决定了“t”的值。
• 除了根节点外，每个节点必须至少有t-1个键。根节点可以至少有一个键。
• 包括根节点在内的任何节点最多可以有(2*t - 1)个键。
• 一个节点中的子节点数量与键的数量相同，再加上一个。
• 节点的键按升序排列。k1和k2之间的子节点包含k1和k2之间的每个键。
• 与二叉搜索树不同，B树从根节点开始扩展和收缩。
• 与其它平衡二叉搜索树一样，搜索、插入和删除的时间复杂度均为O(log n)。
• B树中只能在叶子节点插入节点。

注意

当有n个节点且m个子节点（一个节点可以拥有的最大子节点数）时，B树的最小可能高度为

当有n个节点且t为非根节点可拥有的最小子节点数时，B树的最大高度为

B树的起源

• 当被加载到主内存（或RAM）中时，以块形式存储在磁盘上的数据被称为数据结构。
• 由于数据量大且磁盘访问频繁，在大容量数据中搜索单个记录需要读取整个容量。
• 为了解决这个问题，建立了索引表，根据记录所在的块存储记录引用。时间和内存消耗显著减少。
• 由于数据量大，我们可以开发多级索引表。
• B树可以用于创建多级索引，以自平衡的方式保持数据排序。
• B树遍历与中序二叉树遍历在遍历方面相似。从最左边的子节点开始，我们递归地打印该子节点，然后对键和剩余的子节点执行相同的操作。最后，递归地打印右边的子节点。二叉搜索树和B树都使用相似的搜索方法。可搜索的键应该是k。
• 从根节点开始，递归地向上遍历树。
• 如果非叶子节点包含该键，我们只需返回已访问的每个节点中的该键。
• 如果不是，我们返回到节点的适当子节点（位于第一个更大键之前的子节点）。
• 如果到达叶子节点且k不存在，则返回NULL。
• 二叉树搜索与B树搜索相似。该算法使用递归并且具有可比性。每个级别的搜索都经过优化，如果键值不在父节点的范围内，则它位于不同的分支中。这些数字也被称为限制值或分离值，因为它们限制了搜索。如果我们到达叶子节点并且找不到所需的键，它将显示NULL。

为什么需要B树数据结构？

对物理存储介质（如硬盘）更快访问的需求导致了B树的开发。二级存储设备的容量更大，但速度较慢。需要这些能够减少磁盘访问的数据结构。

一个键只能存储在其他数据结构（如二叉搜索树、AVL树、红黑树等）的一个节点中。如果需要存储大量键，此类树的高度会变得非常大，并且访问时间会增加。

B树则可以包含多个子节点，并且可以在单个节点中存储多个键。这使得高度急剧下降，从而实现更快的磁盘访问。