Skip to content

B树和B+树的区别

B的意思为平衡

B-树,即为B树。因为B树的原英文名称为B-tree,而很多人喜欢把B-tree译作B-树,其实,这很容易让人产生误解。让人们可能会以为B-树是一种树,而B树又是一种树。而事实上是,B-tree就是指的B树

为什么B树会出现

B树的出现是为了弥合不同的存储级别之间的访问速度上的巨大差异,实现高效的 I/O。平衡二叉树的查找效率是非常高的,并可以通过降低树的深度来提高查找的效率。但是当数据量非常大,树的存储的元素数量是有限的,这样会导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁,进而导致查询效率低下。另外数据量过大会导致内存空间不够容纳平衡二叉树所有结点的情况。B树是解决这个问题的很好的结构

概念

B树不要和二叉树混淆,在计算机科学中,B树是一种自平衡树数据结构,它维护有序数据并允许以对数时间进行搜索,顺序访问,插入和删除。B树是二叉搜索树的一般化,因为节点可以有两个以上的子节点,是一颗多路平衡查找树。与其他自平衡二进制搜索树不同,B树非常适合读取和写入相对较大的数据块(如光盘)的存储系统。它通常用于数据库和文件系统。

区别

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

    B+树非叶子节点仅存储key不存储data,这样一个节点就可以存储更多的key,可以使得B+树相对B树来说更矮(IO次数就是树的高度),所以与磁盘交换的IO操作次数更少。

  2. B+树所有叶子节点构成一个有序链表,按主键排序来遍历全部记录,能更好支持范围查找。由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历,相邻的元素可能在内存中不相邻,所以缓存命中率没有B+树好。
  3. B+树所有的查询都要从根节点查找到叶子节点,查询性更稳定;而B树,每个节点都可能查找到数据,需要在叶子节点和内部节点不停的往返移动,所以不稳定。