B+树（B+ Tree）

B+树（B+ Tree）是一种对B树（B-Tree）的改进版本，它在数据库系统和文件系统中作为索引结构得到了广泛的应用，特别是在磁盘存储的场景下。B+树保留了B树的基本特征，如自平衡、多路分支等，但对其结构进行了优化，以更好地服务于大规模数据的高效检索。B+树的主要特点如下：

1. 内部节点仅存储键值，不存储数据：与B树不同，B+树的内部节点（非叶子节点）只存储关键字和指向子节点的指针，不存储实际的数据记录。这些关键字用于确定子节点范围，且按升序排列。

2. 叶子节点包含全部键值和数据，并通过指针链接成链表：所有数据记录都存储在叶子节点中，每个叶子节点不仅包含一个关键字及其对应的记录，而且还包含指向下一个叶子节点的指针，形成了一个有序链表。这样，遍历所有数据只需沿着叶子节点的链表进行。

3. 叶节点包含所有键：B+树要求所有内部节点的关键字也同时出现在叶子节点中，确保叶子节点包含了全部数据的键，且这些键在叶子节点间有序。

4. 分支因子更高：相比于B树，B+树的分支因子（每个节点的孩子数量）通常更大，这意味着在同样的空间内，B+树可以存储更多的关键字，进一步降低树的高度，提高查询效率。

5. 查询操作：

   • 点查询：查找特定关键字的过程与B树类似，从根节点开始，通过比较关键字选择合适的子节点，直到抵达包含目标关键字的叶子节点。
   • 范围查询：由于叶子节点构成了一个有序链表，对某个范围内的所有记录进行查询时，只需定位到范围起点的叶子节点，然后沿着链表顺序扫描即可。这种特性使得B+树非常适合于范围查询和全表扫描。

B+树相对于B树的优势主要体现在以下几个方面：

• 查询效率更稳定：由于数据只存储在叶子节点，且所有查询最终都会到达叶子节点，B+树的所有查询（包括点查询和范围查询）的时间复杂度均为O(logn)，而B树的非叶子节点查询可能需要回溯到叶子节点获取数据，效率略逊一筹。

• 缓存友好：由于数据集中在叶子节点，且叶子节点间有指针相连，当数据量远大于内存大小时，缓存局部性更好。一次磁盘I/O可以加载多个连续的叶子节点到内存中，后续查询可能只需内存操作，无需额外磁盘I/O。

• 更适合磁盘存储：B+树的结构特性使得范围查询更加高效，无需像B树那样进行大量的中序遍历跳转，减少了磁盘I/O次数，极大地提高了在磁盘等外存设备上的检索速度。

B+树在数据库索引、文件系统、以及任何需要处理大规模、持久化数据并支持高效检索的场景中，是一个理想的选择。