B树

原创 2018-07-23 17:40 阅读(184)次

大规模数据存储中,实现索引查询是在这样一个实际背景下,树单个节点存储的元素数量是有限的(如果元素数量非常多的话,查找就退化成节点内部的线性查找了),这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁,进而导致查询效率低下(为什么会出现这种情况,因为磁盘的操作费时费资源,如果过于频繁的多次查找势必效率低下,详见磁盘读取数据的原理)。

根据磁盘查找存取的次数往往由树的高度所决定,所以,只要我们通过某种较好的树结构减少树的结构尽量减少树的高度,那么是不是便能有效减少磁盘查找存取的次数呢?那这种有效的树结构是一种怎样的树呢?

在无法减少查询需求(数据量)的情况下,那么如何减少树的深度,一个基本的想法就是:采用多叉树结构,即多路查找树。

1970年,R.Bayer和E.mccreight提出了一种适用于外查找的树,它是一种平衡的多叉树,称为B树(或B-树、B_树)。

B-tree(又叫平衡多路查找树,并不是二叉的)是一种常见的数据结构。使用B-tree结构可以显著减少定位记录时所经历的中间过程,从而加快存取速度。B 通常认为是Balance的简称。与自平衡二叉查找树不同,B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库和文件系统。

注意:B-树,即为B树。因为B树的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-树,其实,这是个非常不好的直译,很容易让人产生误解。如人们可能会以为B-树是一种树,而B树又是一种一种树。而事实上是,B-tree就是指的B树。

B树与红黑树最大的不同在于,B树的结点可以有许多子女,从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样,一棵含n个结点的B树的高度也为O(lgn),但可能比一棵红黑树的高度小许多,应为它的分支因子比较大。所以,B树可以在O(logn)时间内,实现各种如插入(insert),删除(delete)等动态集合操作。

在大规模数据存储操作中,由于无法一次性加载到内存里。所以避免不了发生内外存交换。所以次数越少,效率表现也越高。

如下图:


这是个典型的b树结构,初始因子为1000,高度仅为3的b树,就可以存储1002001000的数据了。

假设要查询最后一个数据:
从硬盘加载根节点搜索,IO一次。
根据根节点的指针信息,去加载第二层的节点, IO一次。
重复2,IO一次。
IO只用了3次,就查询了需要的数据,所以说B树效率是非常高的。
B树的节点,在硬盘里表现为:柱面里的页(page)或盘块(block) ,如果把索引持久化到内存,只需要一次就够了。
B树的高效的前提是数据已排序。


Btree的定义

b-tree分为用“阶”的定义和用“度”的定义,度和阶都是描述子节点的数量的。

用阶定义(m阶的B树)

  1. 树中每个结点最多含有m个孩子(m>=2);
  2. 除根结点和叶子结点外,其它每个结点至少有[ceil(m / 2)]个孩子(其中ceil(x)是一个取上限的函数);
  3. 根结点至少有2个孩子(除非B树只包含一个结点:根结点);
  4. 所有叶子结点都出现在同一层,叶子结点不包含任何关键字信息(可以看做是外部结点或查询失败的结点,指向这些结点的指针都为null);(注:叶子节点只是没有孩子和指向孩子的指针,这些节点也存在,也有元素。类似红黑树中,每一个NULL指针即当做叶子结点,只是没画出来而已)。
  5. 每个非终端结点中包含有n个关键字信息: (n,P0,K1,P1,K2,P2,......,Kn,Pn)。其中:
    a) Ki (i=1...n)为关键字,且关键字按顺序升序排序K(i-1)< Ki。
    b) Pi为指向子树根的结点,且指针P(i-1)指向子树种所有结点的关键字均小于Ki,但都大于K(i-1)。
    c) 关键字的个数n必须满足: [ceil(m / 2)-1]<= n <= m-1。比如有j个孩子的非叶结点恰好有j-1个关键码。

是不是看得头晕。
来看图


这是B树存储在硬盘的逻辑结构图。其中根节点中17,35在称为关键字(key) ,实际中往往附带更多复杂类型数据。

可以看出一个节点包含 keys和ChildNotePointer 两部分信息。


根据这张图介绍下b树的基础定义:

这是颗5阶B树的图,阶简写m。

    1:树中每个结点最多含有m个子节点(m>=2)。 
    2:每个内节点至少 [ceil(m / 2)] 个子节点。  内节点即非根节点非页子节点,也可以叫中间节点。
    3: 关键字key的数量   [ceil(m / 2)-1]<= n <= m-1,关键字按递增排序。
    4: 每个叶节点具有相同的深度,即树的高度h,而且不包含关键字信息。

上图也可称为最小度数为3的b树,(degree) ,简写t。   t其实是上面第二条定义中 [ceil(m / 2)] 的值,即t=[ceil(m/2)], 3=ceil(5/2) 。 

    1:每个非根节点至少有t-1个关键字,非根内节点至少有t个子节点。 t称为度数(degree),t>=2  。
 .  2:每个节点至多有2t-1关键字,每个内节点最多有2t个子节点。
    3:每个叶节点具有相同的深度,即树的高度h,而且不包含关键字信息。



插入

根节点插入,不满直接插入。节点满进行分裂,再满递归分裂。



删除

查询到节点,然后进行删除操作,不满足B数节点的定义则进行节点合并。

更新和删除一样,只是讲key替换掉。

这里还找到一个GIF,很形象展示插入。

下面是往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的演示动画:



B树的缺点

从上面的得知,在查询单条数据是非常快的。但如果范围查的话,b树每次都要从根节点查询一遍。所以在实际应用中,往往采用b树的变形,b+树来存储,只有叶子节点存储数据,每个叶子节点都指向下一个。


参考: http://www.cnblogs.com/mushroom/p/4100087.html

http://www.cnblogs.com/yangecnu/p/Introduce-B-Tree-and-B-Plus-Tree.html

本文完。

本站作品的版权皆为作品作者所有。

本站文字和内容为本站编辑或翻译,部分内容属本站原创,所以转载前务必通知本站并以超链接形式注明内容来自本站,否则以免带来不必要的麻烦。

本站内容欢迎分享,但拒绝有商业目的的转载!