数据结构 八股文

B树和B+树的区别？

• B树

B树是平衡多叉树，每个节点既保存索引又保存数据，搜索时相当二分查找；

• B+树

B+树也是平衡多叉树，但只有叶子节点保存数据，非叶节点只保存索引，搜索时相当于二分查找，同时增加了相邻接点的指向指针；

主要区别：

1. 叶子节点B树不存指针，B+树存双向指针，方便范围查找；
2. B树非叶子节点也存储数据，B+树不存储数据；
3. B树不会有冗余索引，是唯一的，B+树会有冗余索引，存放同样的数据，B树的层级比B+树要高，因为B+树有冗余索引。在相同数据量的情况下，比存储即存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更 矮胖 ，查询底层节点的磁盘 I/O次数会更少。所以数据库用B+树作为索引。

为社么使用B+树作为MySQL的索引？

• B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比存储即存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更 矮胖 ，查询底层节点的磁盘 I/O次数会更少。

• B+ 树有大量的冗余节点（所有非叶子节点都是冗余索引），这些冗余索引让 B+ 树在插入、删除的效率都更高，比如删除根节点的时候，不会像 B 树那样会发生复杂的树的变化；

• B+ 树叶子节点之间用链表连接了起来，有利于范围查询，而 B 树要实现范围查询，因此只能通过树的遍历来完成范围查询，这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。