为什么 InnoDB 存储引擎选用 B+ 树而不是 B 树呢?

用 B+ 树不用 B 树考虑的是 IO 对性能的影响,B 树的每个节点都存储数据,而 B+ 树只有叶子节点才存储数据,所以查找相同数据量的情况下,B 树的高度更高,IO 更频繁。数据库索引是存储在磁盘上的,当数据量大时,就不能把整个索引全部加载到内存了,只能逐一加载每一个磁盘页(对应索引树的节点)。

发表回复

后才能评论

评论(3)

  • mpweixin用户 2023年3月10日 上午10:21

    1)B树的每个结点都存储了key和data,B+树的data存储在叶子节点上。

    节点不存储data,这样一个节点就可以存储更多的key。可以使得树更矮,所以IO操作次数更少。

    2)B+树的所有叶结点构成一个有序链表,可以按照关键码排序的次序遍历全部记录

    由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好

  • mpweixin用户 2022年10月20日 下午2:04

    B+树稳定性更高

  • mpweixin用户 2022年3月8日 下午12:02

    B树和B+树对于查询速度也有一些不同