一文详解：什么是B树？.pdf详细了解B树的实现机制，深入理解大规模数据存储、索引查询的问题2.1磁

文件名称: 一文详解：什么是B树？.pdf

所属分类: 互联网

开发工具:

文件大小: 547kb

下载次数: 0

上传时间: 2019-10-08

提供者: feige*****

下载 (547kb)

不能下载？报告错误

详细说明：详细了解B树的实现机制，深入理解大规模数据存储、索引查询的问题2.1磁盘的构造磁盘是一个扁平的圆盘(与电唱机的唱片类似)。盘面上有许多称为磁道的圆圈, 数据就记录在这些磁道上。磁盘可以是单片的,也可以是由若干盘片组成的盘组, 每一盘片上有两个面。如下图11.3中所示的6片盘组为例,除去最顶端和最底端的外侧面不存储数据之外,一共有10个面可以用来保存信息。存取装置主轴动臂盘片柱面千专道读写美图11.3活动头盘示意图当磁盘驱动器执行读/写功能时。盘片装在一个主轴上,并绕主轴高速旋转,当磁道在读/写头(又叫磁头)下通过时,就可以进行数据的读/写了一般磁盘分为固定头盘(磁头固定)和活动头盘。固定头盘的每一个磁道上都有独立的磁头,它是固定不动的,专门负责这一磁道上数据的读/写活动头盘(如上图)的磁头是可移动的。每一个盘面上只有一个磁头(磁头是双向的,因此正反盘面都能读写)。它可以从该面的一个磁道移动到另一个磁道。所有磁头都装在同一个动臂上,因此不同盘面上的所有磁头都是同时移动的(行动整齐划一)。当盘片绕主轴旋转的时候,磁头与旋转的盘片形成一个圆柱体。各个盘面上半径相同的磁道组成了一个圆柱面,我们称为柱面。因此,柱面的个数也就是盘面上的磁道数。 2.2磁盘的读/写原理和效率磁盘上数据必须用一个三维地址唯一标示:柱面号、盘面号、块号(磁道上的盘块)。读/写磁盘上某一指定数据需要下面3个步骤 (1)首先移动臂根据柱面号使磁头移动到所需要的柱面上,这一过程被称为定位或查找。 (2)如上图11.3中所示的6盘组示意图中,所有磁头都定位到了10个盘面的 10条磁道上(磁头都是双向的)。这时根据盘面号来确定指定盘面上的磁道。 (3)盘面确定以后,盘片开始旋转,将指定块号的磁道段移动至磁头下。经过上面三个步骤,指定数据的存储位置就被找到。这时就可以开始读/写操作访问某一具体信息,由3部分时间组成查找时间( seek time)Ts:完成上述步骤(1)所需要的时间。这部分时间代价最高,最大可达到0.1s左右 ●等待时间( atency time)T:完成上述步骤(3)所需要的时间。由于盘片绕主轴旋转速度很快,一般为7200转/分(电脑硬盘的性能指标之一,家用的普通硬盘的转速一般有5400rpm(笔记本)、7200rpm几种)。因此一般旋转一圈大约 0.00835。传输时间( transmission time)Tt:数据通过系统总线传送到内存的时间般传输一个字节(byte)大概0.02us=2*10^(-8)s 磁盘读取数据是以盘块( block)为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。而磁盘IO代价主要花费在查找时间Ts上。因此我们应该尽量将相关信息存放在同一盘块,同一磁道中。或者至少放在同一柱面或相邻柱面上,以求在读/写信息时尽量减少磁头来回移动的次数,避免过多的查找时间Ts。所以,在大规模数据存储方面,大量数据存储在外存磁盘中,而在外存磁盘中读取/写入块( block)中某数据时,首先需要定位到磁盘中的某块,如何有效地査找磁盘中的数据,需要一种合理高效的外存数据结构,就是下面所要重点阐述的B tree结构,以及相关的变种结构:B+-tree结构和B*-tree结构 3B树 3.1什么是B树具体讲解之前,有一点,再次强调下:有的文章里面出现的B-树,即为B树。因为B树的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-树,其实,这是个非常不好的直译,很容易让人产生误解。如人们可能会以为B-树是种树,而B树又是一种一种树。而事实上是,B-tree就是指的B树。特此说明我们知道,B树是为了磁盘或其它存储设备而设计的一种多叉(下面你会看到相对于二叉,B树每个内结点有多个分支,即多叉)平衡查找树。与本bog之前介绍的红黑树很相似,但在降低磁盘I0操作方面要更好一些。许多数据库系统都一般使用B树或者B树的各种变形结构,如下文即将要介绍的B+树,B*树来存储信息 B树与红黑树最大的不同在于,B树的结点可以有许多子女,从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样,一棵含n个结点的B 树的高度也为O(lgn),但可能比一棵红黑树的高度小许多,应为它的分支因子比较大。所以,B树可以在O(logn)时间内,实现各种如插入( insert), 删除( delete)等动态集合操作。如下图所示,即是一棵B树,一棵关键字为英语中辅音字母的B树,现在要从树种查找字母R(包含n[x个关键字的内结点ⅹ,ⅹ有n[x]+1]个子女(也就是说,一个内结点ⅹ若含有n[x]个关键字,那么X将含有n[x]+1个子女)。所有的叶结点都处于相同的深度,带阴影的结点为查找字母R时要检查的结点) M Q,7、X B C F G y K L N P R S 相信,从上图你能轻易的看到,一个内结点ⅹ若含有n[x]个关键字,那么ⅹ将含有nx]+1个子女。如含有2个关键字DH的内结点有3个子女,而含有3个关键字QTX的内结点有4个子女。 B树的定义,从下文中,你将看到,或者是用阶,或者是用度,如下段文字所述 Unfortunately, the literature on B-trees is not uniform in its use of terms relating to B-Trees (Folk Zoellick 1992, p. 362)Bayer McCreight(1972), Comer(1979), and others define the order of b-tree as the minimum number of keys in a non-root node. Folk Zoellick(1992) points out that terminology is ambiguous because the maximum number of keys is not clear. An order 3 b-tree might hold a maximum of 6 keys or a maximum of 7 keys (Knuth 1998, TAOCP p 483)avoids the problem by defining the order to be maximum number of children(which is one more than the maximum number of keys) Definition【edit] According to Knuth's definition, a B-tree of order m is a tree which satisfies the following properties 1. Every node has at most m children. 2. Every non-leaf node (except root) has at least 1=21 children. 3. The root has at least two children if it is not a leaf node 4. A non-leaf node with k children contains x-1 keys 5. All leaves appear in the same level, and internal vertices carry no informat ion 用阶定义的B树 B树又叫平衡多路查找树。一棵m阶的B树(注:切勿简单的认为一棵m阶的B树是m叉树虽然存在四叉树,八叉树,KD树,及vp/R树/R*树/R+树/X 树/M树/线段树/希尔伯特R树/优先R树等空间划分树,但与B树完全不等同) 的特性如下 ①树中每个结点最多含有m个孩子(m>=2) ②除根结点和叶子结点外其它每个结点至少有[cei(m/2)个孩子(其中cei(x) 是一个取上限的函数) ③若根结点不是叶子结点,则至少有2个孩子(特殊情况:没有孩子的根结点, 即根结点为叶子结点,整棵树只有一个根节点); ④所有叶子结点都出现在同一层,叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点,实际上这些结点不存在,指向这些结点的指针都为 nul);(读者反馈冷岳:这里有错,叶子节点只是没有孩子和指向孩子的指针, 这些节点也存在也有元素。研究者Juy:其实关键是把什么当做叶子结点, 因为如红黑树中,每一个NULL指针即当做叶子结点,只是没画出来而已)。 ⑤每个非终端结点中包含有n个关键字信息:(n,P0,K1,P1,K2,P2 Kn,Pn)。其中 a)Ki(i=1.n)为关键字,且关键字按顺序升序排序K(i-1)=2)表示。 i)每个非根的内结点至多有m个子女,每个非根的结点必须至少含有m-1个关键字,如果树是非空的,则根结点至少包含一个关键字 i)每个结点可包含至多2m-1个关键字。所以一个内结点至多可有2m个子女。如果一个结点恰好有2m-1个关键字,我们就说这个结点是满的(而稍后介绍的 B*树作为B树的一种常用变形,B*树中要求每个内结点至少为2/3满,而不是像这里的B树所要求的至少半满); i)当关键字数m=2(t=2的意思是,mmin=2,m可以>=2)时的B树是最简单的(有很多人会因此误认为B树就是二叉查找树,但二叉查找树就是二叉查找树,B树就是B树B树是一棵含有m(m>=2)个关键字的平衡多路查找树), 此时,每个内结点可能因此而含有2个、3个或4个子女,亦即一棵2-3-4树, 然而在实际中,通常采用大得多的t值。 B树中的每个结点根据实际情况可以包含大量的关键字信息和分支(当然是不能超过磁盘块的大小,根据磁盘驱动( disk drives)的不同,一般块的大小在1k~4k 左石);这样树的深度降低了,这就意味着查找一个元素只要很少结点从外存磁盘中读入内存,很快访问到要査找的数据。如果你看完上面关于B树定义的介绍,思维感觉不够清晰,请继续参阅下文第6小节、B树的插入、删除操作部分 3.2B树的类型和节点定义 B树的类型和节点定义如下图所示

(系统自动生成,下载前可以参看下载内容)