文章目录
- 1. 节点结构
- 2. 插入和删除
- 3. 查询
- 4. 性能
- 5. 适用场景
- 6.关于 B树和 B+树的常见问题
- 6.1. B树和B+树的区别是什么？
- 6.2. 什么情况下应该使用 B树？
- 6.3. 什么情况下应该使用 B+树？
B树和B+树都是多路搜索树，它们都用于数据库索引中存储和组织数据。B+树是B树的一种改进，它具有更好的插入和删除性能。
1. 节点结构
B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而B树每个节点 key 和 data 在一起，无法区间查找。
B树：每个节点存储多个关键字和数据指针，关键字之间通过指针连接。
查询节点 key 为 50 的 data，key 为 50 的节点在第一层，B-树只需要一次磁盘 IO 即可完成查找。所以说B-树的查询最好时间复杂度是 O(1)。
B+树：非叶子节点只存储关键字和子节点指针，叶子节点存储关键字和数据。
B+树所有的 data 域都在根节点，查询 key 为 50的节点必须从根节点索引到叶节点，时间复杂度固定为 O(log n)。
B树的由于每个节点都有key和data，所以查询的时候可能不需要O(logn)的复杂度，甚至最好的情况是O(1)就可以找到数据，而B+树由于只有叶子节点保存了data，所以必须经历O(logn)复杂度才能找到数据
2. 插入和删除
B树：插入和删除操作需要在树中找到要插入或删除的关键字，然后进行相应的操作。如果树满了，需要进行分裂操作。
B+树：插入操作总是从叶子节点开始，如果叶子节点满了，则进行分裂操作。删除操作需要从叶子节点开始，如果删除后叶子节点不满足最小度，则进行合并操作。
3. 查询
B树：查询操作需要从根节点开始，逐层向下查找，直到找到要查询的关键字。
B+树：查询操作只需要从根节点开始，逐层向下查找，直到找到要查询的关键字所在的叶子节点。
4. 性能
B树：B树的插入和删除操作的性能较差，因为需要进行分裂或合并操作。
B+树：B+树的插入和删除操作的性能较好，因为只需要在叶子节点进行操作。
5. 适用场景
B树：B树适用于对插入和删除操作要求不高的场景。
B+树：B+树适用于对插入和删除操作要求较高的场景。
B树和B+树都是多路搜索树，它们都用于在数据库索引中存储和组织数据。
6.关于 B树和 B+树的常见问题
6.1. B树和B+树的区别是什么？
B树和B+树的主要区别在于节点结构和插入和删除操作。B树的每个节点都存储关键字和数据指针，而B+树的非叶子节点只存储关键字和子节点指针。B树的插入和删除操作需要在树中找到要插入或删除的关键字，然后进行相应的操作，而B+树的插入操作总是从叶子节点开始，删除操作需要从叶子节点开始。
6.2. 什么情况下应该使用 B树？
B树适用于对插入和删除操作要求不高的场景。例如，可以用于存储用户列表、缓存数据等。
6.3. 什么情况下应该使用 B+树？
B+树适用于对插入和删除操作要求较高的场景。例如，可以用于实现数据库索引。