ITPub博客

首页 > Linux操作系统 > Linux操作系统 > B-tree/B+tree/B*tree

B-tree/B+tree/B*tree

原创 Linux操作系统 作者:ziling2011 时间:2012-11-21 10:58:49 0 删除 编辑

1.前言:

动态查找树主要有:二叉查找树(Binary Search Tree),平衡二叉查找树(Balanced Binary Search Tree),红黑树 (Red-Black Tree )B-tree/B+-tree/ B*-tree (B~Tree)。前三者是典型的二叉查找树结构,其查找的时间复杂度O(log2N)与树的深度相关,那么降低树的深度自然对查找效率是有所提高的;还有一个实际问题:就是大规模数据存储中,实现索引查询这样一个实际背景下,树节点存储的元素数量是有限的(如果元素数量非常多的话,查找就退化成节点内部的线性查找了),这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁,进而导致查询效率低下(为什么会出现这种情况,待会在外部存储器-磁盘中有所解释),那么如何减少树的深度(当然是不能减少查询的数据量),一个基本的想法就是:采用多叉树结构(由于树节点元素数量是有限的,自然该节点的子树数量也就是有限的)。

这样我们就提出了一个新的查找树结构——多路查找树。根据平衡二叉树的启发,自然就想到平衡多路查找树结构,也就是这篇文章所要阐述的主题B~tree(B树结构)B-tree这棵神奇的树是在Rudolf BayerEdward M. McCreight(1970)写的一篇论文《Organization and Maintenance of Large Ordered Indices》中首次提出。具体介绍可以参考wikipedia中的介绍:http://en.wikipedia.org/wiki/B-tree,其中还阐述了B-tree名字来源以及相关的开源地址。

在开始介绍B~tree之前,先了解下相关的硬件知识,才能很好的了解为什么需要B~tree这种外存数据结构。

2.外存储器磁盘

计算机存储设备一般分为两种内存储器(main memory)和外存储器(external memory) 内存存取速度快,但容量小,价格昂贵,而且不能长期保存数据(在不通电情况下数据会消失)

外存储器—磁盘是一种直接存取的存储设备(DASD)。它是以存取时间变化不大为特征的。可以直接存取任何字符组,且容量大、速度较其它外存设备更快。

2.1磁盘的构造

磁盘时一个扁平的圆盘(与电唱机的唱片类似)。盘面上有许多称为磁道的圆圈,数据就记录在这些磁道上。磁盘可以是单片的,也可以是由若干盘片组成的盘组,每一盘片上有两个面。如下图6片盘组为例,除去最顶端和最底端的外侧面不存储数据之外,一共有10个面可以用来保存信息。

                           

 

当磁盘驱动器执行读/写功能时。盘片装在一个主轴上,并绕主轴高速旋转,当磁道在读/写头(又叫磁头) 下通过时,就可以进行数据的读 / 写了。

一般磁盘分为固定头盘(磁头固定)和活动头盘。固定头盘的每一个磁道上都有独立的磁头,它是固定不动的,专门负责这一磁道上数据的读/写。

活动头盘 (如上图)的磁头是可移动的。每一个盘面上只有一个磁头(磁头是双向的,因此正反盘面都能读写)。它可以从该面的一个磁道移动到另一个磁道。所有磁头都装在同一个动臂上,因此不同盘面上的所有磁头都是同时移动的(行动整齐划一)。当盘片绕主轴旋转的时候,磁头与旋转的盘片形成一个圆柱体。各个盘面上半径相同的磁道组成了一个圆柱面,我们称为柱面 。因此,柱面的个数也就是盘面上的磁道数。

2.2磁盘的读/写原理和效率

磁盘上数据必须用一个三维地址唯一标示:柱面号、盘面号、块号(磁道上的盘块)

/写磁盘上某一指定数据需要下面3个步骤:

(1)  首先移动臂根据柱面号使磁头移动到所需要的柱面上,这一过程被称为定位或查找

(2)  如上图6盘组示意图中,所有磁头都定位到了10个盘面的10条磁道上(磁头都是双向的)。这时根据盘面号来确定指定盘面上的磁道。

(3) 盘面确定以后,盘片开始旋转,将指定块号的磁道段移动至磁头下。

经过上面三个步骤,指定数据的存储位置就被找到。这时就可以开始读/写操作了。

访问某一具体信息,由3部分时间组成:

查找时间(seek time) Ts: 完成上述步骤(1)所需要的时间。这部分时间代价最高,最大可达到0.1s左右。

等待时间(latency time) Tl: 完成上述步骤(3)所需要的时间。由于盘片绕主轴旋转速度很快,一般为7200/(电脑硬盘的性能指标之一, 家用的普通硬盘的转速一般有5400rpm(笔记本)7200rpm几种)因此一般旋转一圈大约0.0083s

传输时间(transmission time) Tt: 数据通过系统总线传送到内存的时间,一般传输一个字节(byte)大概0.02us=2*10^(-8)s

磁盘读取数据是以盘块(block)为基本单位的位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘IO代价主要花费在查找时间Ts上。因此我们应该尽量将相关信息存放在同一盘块,同一磁道中。或者至少放在同一柱面或相邻柱面上,以求在读/写信息时尽量减少磁头来回移动的次数,避免过多的查找时间Ts

所以,在大规模数据存储方面,大量数据存储在外存磁盘中,而在外存磁盘中读取/写入块(block)中某数据时,首先需要定位到磁盘中的某块,如何有效地查找磁盘中的数据,需要一种合理高效的外存数据结构,就是下面所要重点阐述的B-tree结构,以及相关的变种结构:B+-tree结构和B*-tree结构。

3.B-tree

 

B-tree又叫平衡多路查找树。一棵m阶的B-tree (m叉树)的特性如下:

(其中ceil(x)是一个取上限的函数)

1)  树中每个结点至多有m个孩子;

2)  除根结点和叶子结点外,其它每个结点至少有有ceil(m / 2)个孩子;

3)  若根结点不是叶子结点,则至少有2个孩子(特殊情况:没有孩子的根结点,即根结点为叶子结点,整棵树只有一个根节点);

4)  所有叶子结点都出现在同一层,叶子结点不包含任何关键字信息(可以看做是外部结点或查询失败的结点,实际上这些结点不存在,指向这些结点的指针都为null)

5)  每个非终端结点中包含有n个关键字信息: (nP0K1P1K2P2......KnPn)。其中:

             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

B-tree中的每个结点根据实际情况可以包含大量的关键字信息和分支(当然是不能超过磁盘块的大小,根据磁盘驱动(disk drives)的不同,一般块的大小在1k~4k左右);这样树的深度降低了,这就意味着查找一个元素只要很少结点从外存磁盘中读入内存,很快访问到要查找的数据。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/25989950/viewspace-749640/,如需转载,请注明出处,否则将追究法律责任。

上一篇: 插入排序
下一篇: 没有了~
请登录后发表评论 登录
全部评论

注册时间:2011-07-18

  • 博文量
    52
  • 访问量
    115156