⭐ 题目日期：

阿里 - 2025/8/19

📝 题解：

在数据库和文件系统中，B树和B+树都是常用的多路平衡查找树，用于高效地存储和检索数据。尽管它们都是为了减少磁盘I/O次数而设计的，但B+树在实际应用中更具优势，主要原因在于其结构特点和查询效率。

1. 节点结构不同：

   • B树：B树的每个节点都存储键（key）和对应的数据（data）。这意味着，无论是在内部节点还是叶子节点，都会包含数据。
   • B+树：B+树的内部节点（非叶子节点）只存储键，不存储数据。数据都存储在叶子节点中。所有叶子节点构成一个有序链表，方便范围查询。

2. 查询效率不同：

   • B树：由于数据可能存在于任何节点，查询时需要从根节点遍历，直到找到目标键或到达叶子节点。如果目标数据在内部节点，查询可能会提前结束。然而，这使得查询路径长度不固定，查询性能不稳定。
   • B+树：所有的数据都集中在叶子节点，因此每次查询都必须从根节点走到叶子节点。这保证了查询路径长度是固定的，查询性能更加稳定。

3. 磁盘I/O和内存利用率：

   • B树：由于内部节点存储了数据，一个节点能存储的键值对数量较少。当需要查找数据时，可能需要加载更多的节点到内存中，导致更多的磁盘I/O操作。
   • B+树：内部节点只存储键，不存储数据。这意味着在同样大小的磁盘块中，B+树的内部节点可以存储更多的键。这使得树的高度更低，查找时需要的磁盘I/O次数更少，查询效率更高。这是B+树优于B树最核心的原因。

4. 范围查询和遍历：

   • B树：不支持高效的范围查询。如果要查询一个范围的数据，找到起始节点后，可能需要再次从根节点出发，或者通过中序遍历来查找后续数据，效率低下。
   • B+树：所有叶子节点形成一个有序链表。进行范围查询时，只需找到起始叶子节点，然后通过链表指针向后遍历即可，非常高效。

---

📝 面试官答案（面试中可以直接表达）

面试官您好，我认为在数据库索引中，B+树相较于B树有显著优势，主要原因有以下几点：

1. 磁盘I/O次数更少：B+树的内部节点只存储键，不存储数据。这使得一个节点能存储更多的键，从而降低了树的高度。在查询时，需要进行的磁盘I/O次数更少，查询效率更高。
2. 查询性能更稳定：B+树的所有数据都存放在叶子节点，任何一次查询都必须从根节点走到叶子节点。这保证了每次查询路径长度相同，查询性能非常稳定。而B树的查询路径长度不固定，性能不稳定。
3. 范围查询更高效：B+树的叶子节点之间通过指针连接，形成一个有序链表。这使得在进行范围查询时，只需找到起始数据，然后沿着链表遍历即可，效率非常高。B树则不具备这个优势。

综上，B+树更适合作为数据库索引，因为它在空间利用率、查询性能和范围查询方面都优于B树。