字节跳动C++面试题及参考答案（下）

说说B 树 b + 树

B 树：

B 树是一种平衡的多路查找树，它的设计目的是为了减少磁盘 I/O 操作，适用于存储大量的数据并进行高效的查找、插入和删除操作。B 树的节点可以有多个子节点（通常称为多路），每个节点包含多个关键字，关键字之间是有序的。

B 树的结构特点包括：根节点至少有两个子节点；除根节点外，每个非叶子节点至少有个子节点，其中是 B 树的阶数，表示节点的最大子节点数；所有叶子节点都在同一层。

在 B 树中查找数据时，从根节点开始，将目标关键字与节点中的关键字进行比较。如果目标关键字小于节点中的某个关键字，就沿着对应的左子树继续查找；如果大于某个关键字，就沿着右子树查找；如果相等，就找到了目标数据。插入和删除操作相对复杂，因为需要考虑节点的分裂和合并，以保持 B 树的平衡和性质。例如，当插入一个关键字时，如果插入后节点的关键字数量超过了（阶数限制），就需要将节点分裂成两个节点，并将中间的关键字提升到父节点中。

B 树在数据库索引和文件系统等领域应用广泛。在数据库中，数据存储在磁盘上，B 树的多层结构可以有效地减少磁盘 I/O 次数