B树、B+树、B*树的区别

写在前面

B 树、B + 树和 B * 树都是多路平衡查找树，常用于文件系统和数据库系统等场景中，以提高数据的存储和检索效率。

B树

• 定义：B 树是一种平衡的多路查找树，它的每个节点可以包含多个关键字和对应的子节点。
• 特点
• • 节点结构：一个节点包含多个关键字和指向子节点的指针。关键字按照从小到大的顺序排列，子节点的数量取决于关键字的数量。
• • 平衡特性：B 树通过在插入和删除操作时进行节点的分裂和合并，保证树的高度始终保持在对数级别，从而实现高效的查找、插入和删除操作。
• • 数据存储：B 树的每个节点既可以存储关键字，也可以存储对应的数据记录。

B+树

• 定义：B + 树是 B 树的一种变体，它在 B 树的基础上对数据存储和查询方式进行了优化。
• 特点
• • 节点结构：B + 树的内部节点只存储关键字和子节点指针，不存储数据记录。数据记录全部存储在叶子节点中，叶子节点通过指针连接成一个有序的链表。
• • 查询效率：由于所有数据都在叶子节点，因此在进行范围查询时，只需要遍历叶子节点的链表即可，无需像 B 树那样在内部节点和叶子节点之间来回查找，查询效率更高。
• • 磁盘 I/O 优化：B + 树的叶子节点链表可以方便地进行顺序读取，这对于磁盘 I/O 操作非常友好，可以减少磁盘寻道时间，提高数据读取效率。

B*树

• 定义：B * 树是 B + 树的一种改进，它进一步提高了树的空间利用率和查询性能。
• 特点
• • 节点填充率：B树要求每个非叶子节点的关键字数量至少为
    (2/3)∗m
    ，其中
    m
    是节点的最大关键字数量。相比之下，B + 树的节点填充率通常为
    50%
    。这使得 B树的节点更加饱满，减少了树的高度，提高了查询效率。
• • 兄弟节点链接：B * 树在非叶子节点之间增加了指向兄弟节点的指针，这使得在进行范围查询时，可以更快速地定位到相邻的节点，进一步提高了查询性能。
• • 空间利用率：由于节点填充率较高，B * 树在存储相同数据量时，所需的节点数量相对较少，从而提高了空间利用率。

总结

类型	节点结构	数据存储	查询效率	磁盘 I/O 优化	节点填充率
B 树	包含关键字、数据记录和子节点指针	节点中可存储数据记录	对数级	一般	无严格要求
B + 树	内部节点含关键字和子节点指针，叶子节点含数据记录及指向下一叶子节点的指针	数据记录全在叶子节点	范围查询高效	好，叶子节点可顺序读取	一般为 50%
B * 树	在 B + 树基础上，非叶子节点间有兄弟节点指针，且节点填充率更高	同 B + 树	范围查询更高效	更好，结合兄弟节点指针与高填充率	至少为 2/3