彻底搞懂B树、B+树、B*树、R树

B树、B+树、B*树和R树是四种常见的树状数据结构，广泛应用于数据库和文件系统中。它们的设计初衷是为了解决大规模数据的存储和检索问题，通过平衡树的结构来提高查询效率。
一、B树
B树（Balanced Tree）是一种自平衡的树，能够保持数据有序，从而在插入、删除和查找操作时保持相对稳定的性能。B树的每个内部节点都包含一定数量的关键字，并将数据分割成多个区间。随着数据的插入和删除，B树可能会进行分裂和合并操作以保持平衡。
B树的特点：

1. 内部节点：至少包含m/2个关键字（m为节点容量），至多包含m个关键字。
2. 叶子节点：包含n个关键字和n+1个指针，其中n >= m/2，指针指向对应关键字的记录。
3. 所有叶子节点中的关键字按升序排列，且叶子节点中的指针也按关键字的顺序排列。
4. 非叶子节点：仅保存关键字信息，不保存数据记录，指针指向其子节点的最小（或最大）关键字。
   二、B+树
   B+树是B树的一种变体，它将数据全部存储在叶子节点上，使得非叶子节点仅作为索引使用。B+树的非叶子节点仅保存关键字信息，这些关键字用于指示子节点的范围。此外，B+树的叶子节点之间通过指针相互连接，便于顺序访问。
   B+树的特点：
5. 非叶子节点：仅保存关键字信息，不保存数据记录。
6. 叶子节点：包含所有的数据记录，并按关键字的顺序链接在一起。此外，叶子节点之间通过指针相互连接。
7. 所有叶子节点中的关键字按升序排列，且叶子节点中的指针也按关键字的顺序排列。
8. B+树的非根和非叶子节点不保存数据记录，只保存子树的临界值（最大或最小）。因此，相同大小的节点下，B+树相对于B树能够有更多的分支，使得查询时的IO操作次数更少。
9. B+树的查询效率相对较高，特别是在多数节点存储在磁盘等辅助存储器上时。
   三、B树
   B树是B+树的变种，它在B+树的基础上增加了一个额外的指针指向兄弟节点。这种设计使得B树的非根和非叶子节点也可以进行区间访问，提高了查询效率。同时，由于增加了指向兄弟的指针，结点的最低利用率从1/2提高到了2/3。
   B树的特点：
10. 非叶子节点：仅保存关键字信息，不保存数据记录。非根和非叶子节点增加指向兄弟的指针。
11. 叶子节点：包含所有的数据记录，并按关键字的顺序链接在一起。此外，叶子节点之间通过指针相互连接。
12. 所有叶子节点中的关键字按升序排列，且叶子节点中的指针也按关键字的顺序排列。
13. B*树的非根和非叶子节点可以访问兄弟节点，提高了查询效率。
14. B*树的结点利用率更高，提高了空间利用率和查询效率。
    四、R树
    R树是一种空间索引数据结构，用于处理多维空间数据的存储和检索问题。R树的核心思想是将相近的数据点聚合在一起，并在树结构的上一层将其表示为这些节点的最小外接矩形（MBR）。这种设计使得R树非常适合处理地理信息系统、图像数据库等领域的空间数据检索问题。
    R树的特点：
15. R树将空间划分为多个矩形区域，每个区域包含相近的数据点或几何对象。这些区域在树上表示为一个节点和一个MBR（最小外接矩形）。
16. R树的每个节点可以包含多个子节点，每个子节点代表一个区域并具有相应的MBR。根节点是整个空间区域的MBR，而其他非叶子节点则是其子节点的MBR的交集或并集。
17. R树的查询操作可以通过遍历树结构来实现。通过查找与查询点最接近的MBR来定位相关的数据点或几何对象。然后可以在该MBR对应的子节点中进行进一步查询或检索操作。
18. R树具有较好的动态性，可以适应数据的插入、删除和更新操作而不需要频繁地重建整个树结构。此外，R树还支持范围查询和近邻查询等操作。
    总结：
    B树、B+树、B*树和R树是