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

Johngo学长 MySQL 90

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

为什么不是一般二叉树?

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

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

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

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

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

回复

我来回复
  • 暂无回复内容

免费咨询
免费咨询
扫码关注
扫码关注
联系站长

站长Johngo!

大数据和算法重度研究者!

持续产出大数据、算法、LeetCode干货,以及业界好资源!

2022012703491714

微信来撩,免费咨询:xiaozhu_tec

分享本页
返回顶部