数据库索引的原理,为什么要用 B+树,为什么不用二叉树?

mysql 2022年12月23日 666

可以从几个维度去看这个问题,查询是否够快,效率是否稳定,存储数据多少,以及查找 磁盘次数,为什么不是二叉树,为什么不是平衡二叉树,为什么不是 B 树,而偏偏是 B+树呢?

为什么不是一般二叉树?

如果二叉树特殊化为一个链表,相当于全表扫描。平衡二叉树相比于二叉查找树来说,查找效率更稳定,总体的查找速度也更快。

为什么不是平衡二叉树呢?

我们知道,在内存比在磁盘的数据,查询效率快得多。如果树这种数据结构作为索引,那我们每查找一次数据就需要从磁盘中读取一个节点,也就是我们说的一个磁盘块,但是平 衡二叉树可是每个节点只存储一个键值和数据的,如果是 B 树,可以存储更多的节点数 据,树的高度也会降低,因此读取磁盘的次数就降下来啦,查询效率就快啦。

为什么不是 B 树而是 B+树呢?

  1. B+树非叶子节点上是不存储数据的,仅存储键值,而 B 树节点中不仅存储键值,也会存储数据。innodb 中页的默认大小是 16KB,如果不存储数据,那么就会存储更多的键值,相应的树的阶数(节点的子节点树)就会更大,树就会更矮更胖,如此一来我们查找 数据进行磁盘的 IO 次数有会再次减少,数据查询的效率也会更快。
  2. B+树索引的所有数据均存储在叶子节点,而且数据是按照顺序排列的,链表连着的。 那么 B+树使得范围查找,排序查找,分组查找以及去重查找变得异常简单。


关注微信公众号『PHP学习网

第一时间了解最新网络动态
关注博主不迷路~

PHP学习网:站内收集的部分资源来源于网络,若侵犯了您的合法权益,请联系我们删除!
分享到:
赞(0)

文章评论

您需要之后才可以评论

PHP学习网

PHP学习网