B树概念

来源:转载

简介

B树是一种为辅助存储设计的一种数据结构,在1970年由R.Bayer和E.mccreight提出。在文件系统和数据库中为了减少IO操作大量被应用。遗憾的是,他们并没有说明为什么取名为B树,但按照B树的性质来说B通常被解释为Balance。在国内通常有说是B-树,其实并不存在B-树,只是由英文B-Tree直译成了B-树。


一个典型的 B树如图1所示。



图1.一个典型的B树

符合如下特征的树才可以称为B树:

根节点如果不是叶节点,则至少需要两颗子树
每个节点中有N个元素,和N+1个指针。每个节点中的元素不得小于最大节点容量的1/2
所有的叶子位于同一层级(这也是为什么叫平衡树)
父节点元素向左的指针必须小于节点元素,向右的指针必须大于节点元素,比如图1中Q的左指针必须小于Q,右指针必须大于Q
为什么要使用B树

在计算机系统中,存储设备一般分为两种,一种为主存(比如说CPU二级缓存,内存等),主存一般由硅制成,速度非常快,但每一个字节的成本往往高于辅助存储设备很多。还有一类是辅助存储(比如硬盘,磁盘等),这种设备通常容量会很大,成本也会低很多,但是存取速度非常的慢,下面我们来看一下最常见的辅存--硬盘。


硬盘作为主机中除了唯一的一个机械存储设备,速度远远落后于CPU和内存。图2是一个典型的磁盘驱动器。



图2.典型的磁盘驱动器工作原理

一个驱动器包含若干盘片,以一定的速度绕着主轴旋转(比如PC常见的转速是7200RPM,服务器级别的有10000RPM和15000RPM的),每个盘片表面覆盖一个可磁化的物质.每个盘片利用摇臂末端的磁头进行读写。摇臂是物理连接在一起的,通过移动远离或贴近主轴。


因为有机械移动的部分,所以磁盘的速度相比内存而言是非常的慢。这个机械移动包括两个部分:盘旋转和磁臂移动。仅仅对于盘旋转来说,比如常见的7200RPM的硬盘,转一圈需要60/7200≈8.33ms,换句话说,让磁盘完整的旋转一圈找到所需要的数据需要8.33ms,这比内存常见的100ns慢100000倍左右,这还不包括移动摇臂的时间。


因为机械移动如此的花时间,磁盘会每次读取多个数据项。一般来说最小单位为簇。而对于SQL Server来说,则为一页(8K)。


但由于要查找的数据往往很大,不能全部装入主存。需要磁盘来辅助存储。而读取磁盘则是占处理时间最重要的一部分,所以如果我们尽可能的减少对磁盘的IO操作,则会大大加快速度。这也是B树设计的初衷。


B树通过将根节点放入主存,其它所有节点放入辅存来大大减少对于辅存IO的操作。比如图1中,我如果想查找元素Y,仅仅需要从主存中取得根节点,再根据根节点的右指针做一次IO读,再根据这个节点最右的指针做一次IO读,就可以找到元素Y。相比其他数据结构,仅仅做两次辅存IO读大大减少了查找的时间。

B树的高度

根据上面的例子我们可以看出,对于辅存做IO读的次数取决于B树的高度。而B树的高度由什么决定的呢?


根据B树的高度公式:


其中T为度数(每个节点包含的元素个数),N为总元素个数.


我们可以看出T对于树的高度有决定性的影响。因此如果每个节点包含更多的元素个数,在元素个数相同的情况下,则更有可能减少B树的高度。这也是为什么SQL Server中需要尽量以窄键建立聚集索引。因为SQL Server中每个节点的大小为8092字节,如果减少键的大小,则可以容纳更多的元素,从而减少了B树的高度,提升了查询的性能。


上面B树高度的公式也可以进行推导得出,将每一层级的的元素个数加起来,比如度为T的节点,根为1个节点,第二层至少为2个节点,第三层至少为2t个节点,第四层至少为2t*t个节点。将所有最小节点相加,从而得到节点个数N的公式:



两边取对数,则可以得到树的高度公式。


这也是为什么开篇所说每个节点必须至少有两个子元素,因为根据高度公式,如果每个节点只有一个元素,也就是T=1的话,那么高度将会趋于正无穷。

转帖:http://www.cnblogs.com/CareySon/archive/2012/04/06/Imple-BTree-With-CSharp.html

分享给朋友:
您可能感兴趣的文章:
随机阅读: