移动数据库作业教程.docx

嵌入式数据库Ｂ+ 树索引机制改进 谭平飞 摘要:针对嵌入式数据库中Ｂ+ 树索引机制的空间利用率低下及面对庞杂数据的处理能力不足,提出了一种改进的Ｂ+ 树索引机制,使用这种索引机制能较好地解决在存储容量受限的嵌入式系统中提高数据空间利用率和处理庞杂数据能力的问题。 关键词:嵌入式数据库;索引机制;改进的Ｂ+ 树索引 Research and Improvement of B+_trees Method in Embedded Database Tanpingfei Abstract: This paper is due to B+_trees shirting of low storage utilization and its weak processing ability of mass data in embedded database presents an improved B+_trees method to guarantee high storage utilization and its strong processing ability of mass data in limited storage embedded system. Keywords: Embedded database; Index method; Improved B+_trees method 0　引　言 当前嵌入式系统已无处不在,从手机、家电到各类仪器设备都有嵌入式系统隐身其中,它的价值已得到了广泛的认可。同时,随着Ｉｎｔｅｒｎｅｔ和电子商务的迅猛发展,大量的嵌入式设备需要具备高效的数据处理能力。目前,嵌入式系统数据库关键技术的研究[1]已经是嵌入式系统研究与开发的一大热点。由于嵌入式系统没有充足的内存和磁盘资源,嵌入式数据库管理系统被要求占用尽可能小的内存和磁盘空间。为了在资源有限的嵌入式设备上实现嵌入式数据库的快速查找及高效的数据管理,并尽可能地提高数据库的空间利用率,必须找到一种合适的索引机制。本文针对Ｂ+ 树索引机制[2]的空间利用率低下以及面对庞杂数据的处理能力不足,提出了一种改进Ｂ+ 树索引机制,这种索引机制继承了Ｂ+ 树的很多优点,它能同时适应随机查找和顺序查找,并且,改进的Ｂ+ 树最突出的优点在于它可以大大地提高嵌入式数据库的空间利用率和处理庞杂数据的能力,有助于嵌入式数据库在资源有限的嵌入式系统上表现出最佳性能。 1　Ｂ+ 树基本知识 1.1Ｂ+ 树基本概念 Ｂ+ 树是应文件系统所需而提出的一种Ｂ-树索引[3]的变形树,目的是能适应随机和顺序查找,且具有较高的存取效率。Ｂ+ 树的基本特点如下: (1)有ｎ棵子树的结点中含有ｎ个关键字。 (2)把Ｂ+ 树中所有的索引项(Ｖ,Ｐ),按递增次序一律安排在叶结点中,即所有的叶子结点中包含了全部关键字Ｖ的信息以及指向含这些关键字记录的指针Ｐ,且叶子结点本身依关键字的大小自小而大顺序链接。 (3)所有的非终端结点可以看成是索引部分,结点中仅含有其子树中的最大或最小关键字。 Ｂ+ 树索引由两部分组成,如图1所示,上面是Ｂ+ 树索引,下面是顺序集,真实的记录索引都在叶结点中,而Ｂ+ 树仅起路标的作用。在Ｂ+ 树中的索引记录项可能实际并不存在,这点是Ｂ+ 树索引与Ｂ-树最大的不同。因此,查找时在非叶结点找到了要找的关键字值,仍应该继续向下查找直至叶结点[4-5]。顺序集一般组织成稠密索引,指针指向记录地址;而Ｂ+ 树的指针是稀疏索引指向块号。顺序查找时,从顺序集链头开始前进,便能按序读出各个有序的记录;而随机查找是从Ｂ+ 树的根开始有哪些信誉好的足球投注网站的。 图1　Ｂ+ 树结构图 1.2Ｂ+ 树的定义 (1)每个结点至多有ｎ个子结点。 (2)根结点至少有2个子结点,其余每个结点至少有[ｎ/2](向上取整)个子结点,这至少保证有50%的覆盖率。 (3)所有的叶子结点都在同一层上。如图2所示是一棵三阶的Ｂ+ 树,其所有关键字均出现在叶结点中。上面各层结点中的关键字均是下一层相应结点中最大关键字的复写。Ｂ+ 树的构造是由下而上的,ｎ限定了结点大小。 图2　一棵3阶的Ｂ+ 树 通常Ｂ+ 树有两个头指针,一个指向根结点,另一个指向关键字最小的叶子结点。Ｂ+ 树有两种查找运算:一种是从最小关键字起顺序查找;另一种是从根结点开始进行随机查找。 2　Ｂ+ 树的基本操作算法 2.1Ｂ+ 树的查找算法 Ｂ+ 树的随机查找类似于Ｂ-树。但在Ｂ+ 树上进行随机查找时,若非叶子结点的关键字等于查找的关键字,查找不能终止,还要继续向下查找,一直查到叶子结点上相对应的这个关键字。另外Ｂ+ 树还可以由叶子结点构成的链表进行顺序查找。Ｂ+ 树随机查找关键字ｋ的算法如下。 (1)若ｋ=Ｋｉ(1ｉｊ),则判断Ｋｉ所在的结点是否为叶结点