平衡查找树之B树

维基百科对B树的定义为“在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同,B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库和文件系统。”
定义
B 树可以看作是对2-3查找树的一种扩展,即他允许每个节点有M-1个子节点。

  • 根节点至少有两个子节点
  • 每个节点有M-1个key,并且以升序排列
  • 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
  • 其它节点至少有M/2个子节点


下图是一个M=4 阶的B树:
290047064066682
可以看到B树是2-3树的一种扩展,他允许一个节点有多于2个的元素。
B树的插入及平衡化操作和2-3树很相似,这里就不介绍了。下面是往B树中依次插入
6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4
的演示动画:
btreebuild

B+树是对B树的一种变形树,它与B树的差异在于:

  • 有k个子结点的结点必然有k个关键码;
  • 非叶结点仅具有索引作用,跟记录有关的信息均存放在叶结点中。
  • 树的所有叶结点构成一个有序链表,可以按照关键码排序的次序遍历全部记录。

如下图,是一个B+树:
290050048129679
下图是B+树的插入动画:

B和B+树的区别在于,B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历。

B+ 树的优点在于:

由于B+树在内部节点上不好含数据信息,因此在内存页中能够存放更多的key。 数据存放的更加紧密,具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
B+树的叶子结点都是相链的,因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好。
但是B树也有优点,其优点在于,由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。

下面是B 树和B+树的区别图:
290050088914733

分析
对B树和B+树的分析和2-3树的分析类似,
对于一颗节点为N度为M的子树,查找和插入需要logM-1N ~ logM/2N次比较。这个很好证明,对于度为M的B树,每一个节点的子节点个数为M/2 到 M-1之间,所以树的高度在logM-1N至logM/2N之间。
这种效率是很高的,对于N=62*1000000000个节点,如果度为1024,则logM/2N <=4,即在620亿个元素中,如果这棵树的度为1024,则只需要小于4次即可定位到该节点,然后再采用二分查找即可找到要找的值。

留下评论