为什么要用 B+树,为什么不用二叉树

作者:guoxj
浏览:467

可以从几个维度去看这个问题,查询是否够快,效率是否稳定,存储数据多少,以及查找磁盘次数,为什么不是二叉树,为什么不是平衡二叉树,为什么不是 B 树,而偏偏是 B+树呢?
为什么不是一般二叉树?
如果二叉树特殊化为一个链表,相当于全表扫描。平衡二叉树相比于二叉查找树来说,查找效率更稳定,总体的查找速度也更快。
为什么不是平衡二叉树呢?
我们知道,在内存比在磁盘的数据,查询效率快得多。如果树这种数据结构作为索引,那我们每查找一次数据就需要从磁盘中读取一个节点,也就是我们说的一个磁盘块,但是平衡二叉树可是每个节点只存储一个键值和数据的,如果是 B 树,可以存储更多的节点数据,树的高度也会降低,因此读取磁盘的次数就降下来啦,查询效率就快啦。
那为什么不是 B 树而是 B+树呢?
  1. B+树非叶子节点上是不存储数据的,仅存储键值,而 B 树节点中不仅存储键值,也会存储数据。innodb 中页的默认大小是 16KB,如果不存储数据,那么就会存储更多的键值,相应的树的阶数(节点的子节点树)就会更大,树就会更矮更胖,如此一来我们查找数据进行磁盘的 IO 次数有会再次减少,数据查询的效率也会更快。
  2. B+树索引的所有数据均存储在叶子节点,而且数据是按照顺序排列的,链表连着的。那么 B+树使得范围查找,排序查找,分组查找以及去重查找变得异常简单。




登录后回复

共有0条评论