自主知识产权数据库物理层索引技术的探索与实现
摘
要 索引顺序法是一种将大文件细分子堆集的组织方法,这种组织方式的查找效率容易受到内存限制的影响。一种很好的解决方案就是将地址块数组存放在磁盘的数据块中,在需要时,DBMS按页将之调入内存。这种方案需要的辅助文件就是索引文件,可以通过对索引文件进行组织使开销极小化。本文主要对稠密层次索引的一般表现形式B树进行了初步探讨,根据数据结构知识中关于B+树的定义和维护B+树平衡结构的算法,为自主知识产权数据库索引文件的实现设计了一种B+树的结点结构,同时编程实现了维护B+树平衡结构的算法。
关键词 索引文件;B+树;实现;算法
The Research and Implement of the Independent
Intellectual Property Right Database Physical Layer Index
Technology
Zhang
jin
ming
(Dept.
of Computer and Information Science, Southwest Forestry College, Kunming, Yunan, 650224, China)
Abstract:
The
organization methods of dividing big files into small molecules
include index sequencing and hashing, …………………
目
录
1 引言. 1
1.1 研究背景. 1
1.2 研究目的及意义. 2
1.3 国内外研究技术概述. 2
1.3.1 国外数据库技术发展观. 2
2 正文. 4
2.1 相关技术介绍. 4
2.1.1 稀疏层次索引. 4
2.1.2 稠密索引. 4
2.1.3 B树的介绍. 5
2.1.4 B树的查找范围. 6
2.1.5
B+树的特性定义. 7
2.2 研究内容与方法. 错误!未定义书签。
2.2.1在插入期间维护B+树的平衡. 错误!未定义书签。
2.2.2在删除期间维护B+树的平衡. 错误!未定义书签。
2.3 n阶B+树设计与实现(以四阶B+树为例) 错误!未定义书签。
2.3.1 四阶B+树的结点结构. 错误!未定义书签。
2.3.2 四阶B+树的类结构. 错误!未定义书签。
2.3.3 四阶B+树插入和删除关键字算法的实现. 错误!未定义书签。
2.4 遇到的困难和解决方法. 错误!未定义书签。
2.5 优化改进工作. 错误!未定义书签。
3 结束语. 错误!未定义书签。
致谢. 错误!未定义书签。
参考文献. 错误!未定义书签。
数据库技术从诞生到现在,在不到半个世纪的时间里,形成了坚实的理论基础、成熟的商业产品和广泛的应用领域,吸引越来越多的研究者加入。数据库的诞生和发展给计算机信息管理带来了一场巨大的革命。三十多年来,国内外已经开发建设了成千上万个数据库,它已成为企业、部门乃至个人日常工作、生产和生活的基础设施。同时,随着应用的扩展与深入,数据库的数量和规模越来越大,数据库的研究领域也已经大大地拓广和深化了。30年间数据库领域获得了三次计算机图灵奖(C.W. Bachman, E.F.Codd,
J.Gray),更加充分地说明了数据库是一个充满活力和创新精神的领域(萨师煊,2000)。
数据库技术是当今信息管理的最新技术,其核心就是数据库管理系统(简称DBMS)。DBMS是各类管理信息系统的支撑平台,也是信息化建设中需求量最大、应用最广泛的基础性软件。2003年,全球数据库软件市场达到70.6亿美元。而根据市场调研机构IDC预测,全球数据库市场规模到2006年将达到200亿美元。在国内,2000年我国数据库管理系统DBMS市场额为32亿元人民币,2001年为38亿元人民币,2002年为45亿人民币,2003年为54亿元人民币,平均每年以20%左右的速度增长。目前,中国的数据库市场虽大,但主要被国外主流数据库厂商如微软公司(SQL sever)、SYBASE公司(Sybase)、ORACLE公司(Oracle)和IBM公司(DB2)等垄断,他们占据了96.4%以上的市场,而国外的软件价格昂贵,让我国政府和企业不堪重负。
同时,数据库软件处于软件产业的上游,是数据处理的核心,因此无论是发展民族软件产业角度还是保障国家信息安全的角度,发展国产数据库软件一直都是我国科研技术人员的梦想。目前,基于网络的一大批新一代数据库应用应运而生,如支持高层决策的数据仓库、数字图书馆、电子出版物、电子商务等的信息管理与检索等,数据库软件需求十分庞大。与此同时,公安、国防、政府、金融等要害部门对自主、安全的数据库管理系统提出了非常迫切的要求。
在此背景下,发展国产数据库系统,将对我国软件产业及相关产业发挥重大影响。
发展国产数据库系统,掌握数据库核心技术对提升整个中国软件业的技术水平、摆脱应用软件市场的被动局面、推动基础软件的规模化、产业化进程具有十分重要的意义。研制适合国情的国产数据库基础性软件,利用我们开发成本低和售后服务更方便、快捷优势,对推动我国信息化建设具有重要的作用。国家每年在国外数据库软件的投入是200多个亿,如果采用国产软件,在节约开支方面也是一比重大的贡献。同时,当今社会的信息化涉及到国家政治、经济、军事、安全等要害领域,拥有自主知识产权的国产数据库对保证国家信息安全同样具有重要的意义。
1.3.1
1.3.1国外数据库技术发展观
数据库技术的发展,已经成为先进信息技术的重要组成部分,是现代计算机信息系统和计算机应用系统的基础和核心。数据库技术最初产生于20世纪60年代中期,根据数据模型的发展,可以划分为三个阶段:第一代的网状、层次数据库系统;第二代的关系数据库系统;第三代的以面向对象模型为主要特征的数据库系统(王能斌,2000)。
第一代数据库的代表是1969年IBM公司研制的层次模型的数据库管理系统IMS和70年代美国数据库系统语言协商CODASYL下属数据库任务组DBTG提议的网状模型。层次数据库的数据模型是有根的定向有序树,网状模型对应的是有向图。这两种数据库奠定了现代数据库发展的基础。这两种数据库具有如下共同点:支持三级模式(外模式、模式、内模式)。保证数据库系统具有数据与程序的物理独立性和一定的逻辑独立性;用存取路径来表示数据之间的联系;有独立的数据定义语言;导航式的数据操纵语言。