（计算机应用技术专业论文）数据库系统索引结构实现研究.pdf

中文摘要 本文研究基于u n i x 的数据库系统的各种索引结构设计方法，并具体实现了 基于h a s h 表的索引结构。基于h a s h 表的索引结构是当前各种主流关系数据库管 理系统所使用的基本索引结构之一，能较好的支持等值检索。 建立数据库系统索引结构的目的在于加快记录数据的检索速度，但同时在修 改记录数据时会增加索引维护的成本，对索引结构的取舍需要在这两方面进行权 衡。另外，不同的索引结构适用于不同的检索条件，如基于h a s h 表的索引适合 等值检索，而基于b 树的索引则更适合范围检索，两者各有优势。本文设计了一 种关系数据库索引结构的实现方案，将h a s h 表与b 树结合起来，能满足各种不 同检索条件的要求。从整体上看，b 树实现页面级的索引导航，而h a s h 表则用 于页面内的索引。本文详细阐述了基于h a s h 表的索引结构； 数据库中的索引处于高度动态的工作环境，有着频繁的随机修改，如何提高 索引在高度动态环境下的并发能力成为了提高数据库系统性能的重要课题。 p h i l i pl l e 删和s b i n gy a o 提出了经典的b - l i n k 树结构，比较好的解决了 查询进程和插入进程的并发，但是b - l i n k 树的删除算法造成了磁盘空间的浪费， 而且当频繁对同一个页面进行操作时，造成大量时间的浪费。本文针对这两个问 题，给出了较好的解决方案。 关键词：索引h a s hb 树x m l 面向对象数据库 a b s t r a c t t h i sp a p e rd i s c u s s e st h ed e s i g no fu n i x - b a s e di n d e xs t r u c t u r eo fd a t a b a s e s y s t e ma n di m p l e m e n to fi n d e xs t r u c t u r et h a tb a s e do nh a s ht a b l e h a s ht a b l e - b a s e d i n d e xs t r u c t u r ei so n eo fi n d e xs t r u c t u r e su s e db yc u r r e n ts e v e r a lm a i nr e l a t i o n a l d a t a b a s es y s t e m s ，w h i c hi sv e r ys u i t a b l ef o re q u i v a l e n c eq u e r y t h em a i np u r p o s eo f i n d e xs t r u c t u r eo f d a t a b a s es y s t e mi st oi m p r o v et h eq u e r y s p e e do fr e c o r d s ，b u ta tt h es a l n et i m e ，i ti sa tt h ec o s to fi n c r e a s ei ni n d e x m a i n t e n a n c e , s ot r a d e o f fs h o u l db em a d ei no r d e rt od e c i d ew h e t h e ra d o p ti n d e xo r n o t m o r e o 吼as p e c i a lk i n do fi n d e xs t r u c t u r ei ss u i t a b l ef o ras p e c i a lq u e r y c o n d i t i o n , f o re x a m p l e , h a s ht a b l e - b a s e di n d e xs t r u c t u r ei ss u i t a b l ef o re q u i v a l e n c e q u e r y , w h i l ebt r y - b a s e di n d e xs t r u c t u r ei sm o r es u i t a b l ef o rr a n g eq u e r y , e a c ho f w h i c hh a si t sm e r i t t h ep a p e rg i v e sa l li m p l e m e n t a t i o ns o l u t i o no fi n d e xs t r u c t u r ei n r e l a t i o n a ld a t a b a s es y s t e m , t h em a i ni d e ao fw h i c hi st oc o m b i n eh a s ht a b l ea n db t r e es oa st om e e td i f f e r e n tq u e r yc o n d i t i o n s i ng e n e r a l ，bt r e ei su s e df o ri n d e xo f p a g el e v e l ，w h i l eh a s ht a b l ei s u s e df o ri n d e xo fc o n t e n tw i t h i np a g e d e t a i l d e s c r i p t i o na b o u ti m p l e m e n t a t i o no f h a s ht a b l e - b a s e di n d e xs t r u c t u r ei sp r o v i d e d t h ei n d e xs t r u c t u r ei nt h ed a t a b a s ei sr u n n i n gu n d e rv e r yd y n a m i ce n v i r o n m e n t ， i tw i l lb em o d i f i e dv e r yf r e q u e n t l ya n dr a n d o m l y , h o wt oi m p r o v et h ec o n c u r r e n t a b i l i t yo ft h ei n d e xs t r u c t u r eb e c o m eo n eo ft h ek e y st oi m p r o v et h ed b m s s p e r f o r m a n c e p h i l i pl l e h m a na n ds b i n gy a og i v et h ec l a s s i cd a t as t r u c t u r e b - l i n kt r e ew h i c h p e r f e c t l ys o l v et h ec o n e n l t e n tp r o b l e mb e t w e e nr e a d e rp r o c e s sa n d t h ei n s e r t e rp r o c e s s b u ti tc 棚l s ct h ew a s t eo ft i m ew h e nf r e q u e n t l yo p e r a t i o n sa f eo n t h es a m ep a g e , a n di t sd e l e t ea l g o r i t h mc a u s et h ew a s t eo fd i s ks p a c e t h i sp a p e r g i v e se f f i c i e n ts o l u t i o n st os o l v et h et w op r o b l e m sa b o v e k e y w o r d s ：i n d e x ，h a s h , bt r e e , x m l ，o b j e c t - o r i e n t e dd a t a b a s e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘茔或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：汪超 签字日期：2 。年2 月2 口日 学位论文版权使用授权书 本学位论文作者完全了解鑫姿盘堂有关保留、使用学位论文的规定。 特授权盘生盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：证毒己 签字日期：扣o 年二月z 口日 导师签名： 签字日期： 天津大学硕士学位论文 第一章绪论 1 1 数据库系统的发展历史 第一章绪论 数据库是现代计算机信息系统和计算机应用系统的基础和核心技术。数据库 技术最初产生于2 0 世纪6 0 年代中期，根据数据模型的发展，可以划分为三个阶 段：第一代是网状和层次数据库系统；第二代是关系数据库系统；第三代是以面 向对象模型为主要特征的数据库系统。 第一代数据库的代表是1 9 6 9 年i b m 公司研制的层次模型的数据库管理系统 i m s 和7 0 年代美国数据库系统语言协会c o d a s y l 下属数据库任务组d b t g 提议的 网状模型。层次数据库的数据模型是有根的定向有序树，网状模型对应的是有向 图。这两种数据库奠定了现代数据库发展的基础。这两种数据库具有如下共同点： 1 、支持三级模式( 外模式、模式、内模式) 。保证数据库系统具有与程序的物理 独立性和一定的逻辑独立性；2 、用存取路径来表示数据之间的联系；3 、有独立 的数据定义语言；4 、导航式的数据操纵语言。 第二代数据库的主要特征是支持关系数据模型( 数据结构、关系操作、数据 完整性) 。关系模型具有以下特点：1 、关系模型的概念单一，实体和实体之间的 连接用关系来表示；2 、以关系代数为基础；3 、数据的物理存储和存取路径对用 户是透明的；4 、关系数据库语言是非过程化的。 1 9 7 3 年i b m 研究中心开始了一个大的关系型数据库系统研究项目s y s t e m r ， 探讨并验证在多用户与大数据量下关系型数据库的实际可行性。s y s t e m r 的一 个研究小组发明了一套比关系微积分与关系代数更适合最终用户使用的非程序 化查询语言s q l 。从此，基于s o l 的关系型数据库逐渐成为数据库管理系统的主 流。目前所有的关系型数据库厂家的产品都遵循这一标准。 第三代数据库产生于8 0 年代，随着科学技术的不断进步，各个行业领域对 数据库技术提出了更多的需求，关系型数据库已经不能完全满足这些需求，于是 产生了第三代数据库。主要有以下特征：1 、支持数据管理、对象管理和知识管 理；2 、保持和继承了第二代数据库系统的技术；3 、对其它系统开放，支持数据 库语言标准，支持标准网络协议，有良好的可移植性、可连接性、可扩展性和互 操作性等。第三代数据库支持多种数据模型( 比如关系模型和面向对象的模型) ， 并和诸多新技术相结合( 比如分布式处理技术、并行计算技术、人工智能技术、 多媒体技术、模糊技术) ，广泛应用于多个领域( 商业管理、g i s 、计划统计等) ， 由此也衍生出多种新的数据库技术。 天津大学硕+ 学位论文第一章绪论 分布式数据库允许用户开发的应用程序把多个物理分开的、通过网络互联的 数据库当作一个完整的数据库看待，具体可以通过客户服务器模型 8 来实现分 布式数据库。并行数据库通过c l u s t e r 技术把一个大的事务分散到c l u s t e r 中的 多个节点去执行，提高了数据库的吞吐和容错性。多媒体数据库提供了一系列用 来存储图象、音频和视频对象类型，更好地对多媒体数据进行存储、管理、查询。 模糊数据库是存储、组织、管理和操纵模糊数据的数据库，可以用于模糊知识处 理。 随着科学技术的发展，计算机技术不断应用到各行各业，数据存储不断膨胀 的需要，对未来的数据库技术将会有更高的要求。 1 2 数据库系统的研究目的和意义 掌握核心软件技术，开发自主知识产权的系统软件一直是我国软件产业发展 的目标。作为信息处理的核心软件之一，数据库系统是除操作系统之外最重要的 核心软件，也是我国信息化建设中需求量最大、应用最广泛的基础性软件。然而 中国数据库软件市场主导者一直是国外厂商，我国信息化建设的深入，w $ o 的加 入都迫切需要中国人在数据库软件上有所作为。 数据库软件处于软件产业链的上游，是数据处理的核心，因此无论是从发展 民族软件产业角度还是从保障国家信息安全的角度，发展国产数据库软件一直都 是我国科研技术人员的梦想。目前，基于i n t e r n e t 的一大批新一代数据库应用 应运而生，如支持高层决策的数据仓库、数字图书馆、电子图书馆、电子出版物、 电子商务等的信息管理与检索等，数据库软件需求十分庞大。与此同时，公安、 国防、政府、金融等要害部门对自主、安全的数据库管理系统提出了非常迫切的 要求。 在此背景下，发展国产数据库系统，将对我国软件产业及相关产业发挥重大 影响： 1 )发展国产数据库系统，掌握数据库核心技术对提升整个中国软件业 的技术水平、摆脱应用软件市场的被动局面、推动基础软件的规模 化、产业化进程具有十分重要的意义。 2 ) 发展适合国情的国产数据库基础性软件，利用我们开发成本低和售 后服务更方便、快捷的优势，对推动我国信息化建设具有重要的作 用。国家每年在国外数据库软件的投入是2 0 0 多个亿，如果采用国 产软件，将节省大量的资金。 3 ) 发展国产数据库系统对保证国家信息安全具有重要意义。信息化涉 及到国家政治、经济、军事、安全等要害领域，因此拥有自主知识 2 天津大学硕士学位论文第一章绪论 产权的国产数据库对保证国家信息安全具有重要的意义。信息安全 首先是系统的安全，在操作系统掌握于他人的情况下，数据库系统 的安全为数据安全提供了更可靠的保证。 1 3 研究内容及本文结构 研究数据库技术，开发基于u n i x 系统的关系数据库管理系统是提出本研究 课题的基本出发点。数据库管理系统( d a t a b a s em a n a g e m e n ts y s t e m ，d b m s ) 涉及 到多方面的技术知识，但最基础的功能就是对数据的存储和检索，而索引结构的 设计则是与之相应的最关键的技术，也是d b m s 最核心的技术之一。 经过3 0 多年的发展，关系d b m s 的索引技术已经相对比较成熟。但国产数据 库起步较晚，在开发拥有自主知识产权的d b m s 时，研究如何将成熟的索引技术 理论应用到产品开发实现中，甚至对已有的技术进行改进，都是很有意义的。 为基于u n i x 系统的关系d b m s 设计并开发实现相应的索引结构，就是本文主要研 究和讨论的话题。以下章节是这样安排的：第二章介绍常用的索引结构；第三章 给出索引结构的总体设计方案并对涉及到的关键技术问题进行探讨；在第三章的 基础上，针对页内部分，第四章详细介绍基于h a s h 表的索引结构的设计与实现； 最后在第五章对研究做出总结，并展望数据库领域以后的发展趋势。 3 天津大学硕士学位论文第二章常用的索引结构 第二章常用的索引结构 数据库管理系统的目的就是对大量数据的有效存储和快速检索。索引结构的 优劣对关系数据库管理系统的查询速度起着至关重要的作用。比如一条简单的 s q l 语句： s e l e c t + f r o me v e t o p a p pw h e r ep r o e e s s l d = 1 3 5 2( 1 ) 其中e v e t o p a p p 中的记录条数为1 0 5 ，6 3 4 ，3 6 9 。在没有为e v e t o p a p p 建任 何索引的条件下，在某个计算环境下语句( 1 ) 执行了9 6 秒，而当在p r o c 宅s s l d 上 建了一个非聚集索引后，在同样的计算环境下语句( 1 ) 执行的时间就缩短到了 5 9 秒，可见，建立索引可以明显提高检索的性能。 具体来说，索引使我们只需查看所有记录中的一小部分就能找到所需的记 录。目前已有多种不同的数据结构可用做索引 3 ，4 】。在本章中，我们只介绍下面 几种设计和实现索引的方法： 1 排序文件上的简单索引。 2 b 树，一种可在任何文件上建立索引的常用方法。 3 哈希表( 散列表) ，另一种重要并常用索引结构。 4 多维索引和位图索引。 在详细介绍之前，先定义几个名词： 鹈理勋红存放数据记录的文件。 索罗及，毵存放索引记录的文件，由键指针对组成。 查找绝建立索引的字段( 组合) 称为查找键，简称键。 存缮獒：操作系统最基本的i 0 单位，也称为页面，或简称页。 2 1 顺序文件上的索引 一种最简单的索引结构要求文件按索引的属性排序，这样的文件称为顺序文 件。当查找键是关系的主键时这种结构特别有用，当然对关系的其它属性也可使 用这种结构。 1 稠密索引 。 。 稠密索引文件的索引块中只存放记录的键以及指向数据记录本身的指针，并 且保持键的顺序与数据文件中的排序顺序一致。这里说索引是“稠密的”，是因 为数据文件中每个键在索引中都被表示出来。一般情况下，查找键和指针所占存 储空间远小于记录本身，所以存储索引文件比存储数据文件所需的存储块要少得 多。当内存容纳不下数据文件但能容纳下索引文件时，索引的优势尤为明显。这 4 天津大学硕十学位论文 第二章常用的索引结构 时，通过使用索引文件，我们每次查询只用一次i o 操作就能找到给定键值的记 录。 稠密索引支持按给定键值查找相应记录的查询。给定一个键值k ，先在索引 块中查找k ，当找到k 后，按照k 所对应的指针到数据文件中寻找相应的记录。 似乎在找到k 之前需要检索索引文件中的每个存储块，或者平均一半的存储块。 然而，由于有下面几个因素，基于索引的查找比它看起来更有为有效： 1 ) 索引块数量通常比数据块数量少。 2 ) 由于键被排序，可以使用二分查找法来查找k 。若有n 个索引块，只需 查找l o g m 个块。 3 ) 索引文件可能足够小，以致可以永久地存放在主存缓冲区中。要是这样 的话，查找键k 时就只涉及主存访问而不需执行i 0 操作。 2 稀疏索引 与稠密索引相对，稀疏索引只将数据文件中的某些记录在索引文件中表示 出来，通常为每个数据块在索引文件中设一个索引项，也即只为每个数据存储块 设一个键一指针对，键值是每个数据块中第一个记录的对应值。很明显，稀疏索引 节省了存储空间，但查找给定值的记录需要更多的时间。 在稀疏索引的情况下，要找出键值为k 的记录，先得在索引中查找键值小 于或等于k 的最大键值。由于索引文件已按键排序，可以使用二分查找法来定位 这个索引项，然后根据它的指针找到相应的数据块。接着必须搜索这个数据块以 找到键值为k 的记录。 3 多级索引 索引文件本身可能占据多个存储块，即使使用二分查找法找到所需的索引 项，仍可能需要执行多次i o 操作才能找到所需的记录，这时就需要多级索引。 通过在索引上再建索引，能够使第一级索引更为有效。按照同样的想法，可以在 二级索引的基础上建立三级索引，等等。 图2 - 1 就是一个多级索引的例子。在这个例子中，一级索引是稠密的，二 级索引是稀疏的，也可以选择稀疏索引来作为一级索引。但是，二级和更高级的 索引必须是稀疏的，因为一个索引上的稠密索引将需要和其前一级索引同样多的 键一指针对，因而也就需要同样的存储空间。也就是说，二级稠密索引只是增加 额外的结构，而不会带来任何好处。 5 天津大学硕士学位论文第二章常用的索引结构 图2 1 多级索引 4 数据修改期间的索引维护 假定数据文件和索引文件由一些连续的、装满某种类型的记录的存储块组 成。由于随着时间的推移数据会发生变化，需要对记录进行插入、删除和更新。 这势必引起像顺序文件这样的文件组织发生变化，以至于曾经能容纳于块中的记 录不再被容纳，这时需要重新组织数据文件。一般采用下面三种做法： 1 )当需要额外的存储空间时，创建溢出块；或当溢出块中记录被删除 后不再需要该存储空间时，删除溢出块。溢出块在稀疏索引中没有 索引项而应该被看作是基本存储块的补充。 2 )若不用溢出块，可以按序插入新的存储块。要是这样做，那么新的 存储块就需要在稀疏索引中设索引项。在索引文件中索引项的变动 会引起和数据文件的插入与删除同样的问题。要是创建新索引块， 那么这些索引块必须能以某种方法定位，例如像图2 - 1 那样使用另 一级索引。 3 ) 当块中没有空间可以插入元组时，有时可移动一些元组到相邻块； 相反，当相邻块元组太少时，可以合并它们。 然而，当数据文件发生变化后，通常必须对索引进行调整以适应数据文件 的变化。具体的方法依赖于索引是稠密还是稀疏的。不过，索引文件也是顺序文 6 天津大学硕士学位论文第二章常用的索引结构 件，键一指针对可以看作是按查找键排序的记录，因此，数据文件修改过程中用 来维护数据记录的那些策略同样适用于索引文件。 2 2 树结构索引 i b + 树结构 被广泛使用的b + 树是一种平衡的多路查找树，它在文件系统中很有用。它 的内结点用于指导搜索，叶子结点包含数据目录项。 一棵m 阶的b + 树，或为空树，或为满足下列特征的m 叉树： 1 ) 树中每个结点至多有i l l 棵子树； 2 ) 若根结点不是叶子结点，则至少有两棵子树； 3 ) 除根结点之外的所有非终端结点至少有r 加2 1 ( 对m 2 向上取 整) 棵子树，也即结点要满足5 0 的占有率； 4 ) 所有的非终端结点中包含下列信息数据 ( a 0 ，k l ，a i ，k 2 ，a 2 ，k n ，a n ) 其中：k i ( i = 1 ，2 ，n ) 为关键字，且k i k i + l ( i = l ，n 一1 ) ；a i ( i = o ，1 ，n ) 为指向子树根结点的指针，且指针a i 一1 所指子树中 所有结点的关键字均小于k i ( i = 1 ，2 ，r 1 ) ，a n 所指子树中所有 结点的关键字均大于k n 。 5 ) 所有的叶子结点都出现在同一层次上，包含了全部关键字的信 息，以及指向含这些关键字记录的指针，且叶子结点本身依关键 字的大小升序链接。 b + 树包含索引目录项与数据目录项，这两部分组成完整的索引文件 1 4 ， 整体结构如图2 2 所示： 蚓骞最壤 赢接搜索) l l l 索剖文件 l 数据瞬录颈 l ( 腰序纂) j 图2 - 2b + 树总体结构 典型的b + 树内结点，也即索引目录项中的结点如图2 - 3 所示： 7 天津大学硕士学位论文第二章常用的索引结构 指向键值指肉链值指向键僮指翔链毽 k 岱7 5 托k 8 ，8 1 _ ot h e n r e g i s t e r ( a ，d e l t i m e s ) ： c o 咖i t t r a n s 0 ： u n l o c k ( c u r r e n t ) ： e x i t e n d e l s ei fai ss p l i t e dt h e n b e g i n u a l l o c a t e ( 1n e wp a g ef o rb ) ： ( 1 i n kp t ro fa ，l i n kp t ro fb ) 一( u ，1 i n kp t ro fo l da ) ： p u t ( b ，u ) ： p u t ( a ，c u r r e n t ) ： i n s e r t ( ”i n s ”，u ，m a x v a l u eo fa ，q u e u eo fp a r e n t ) ： r e s e t ( q u e u e ) ： c o n i t t r a n s 0 ； u n l o c k ( c u r r e n t ) ： e x i t ： e n de l s e b e g i n 26 天津大学硕士学位论文第三章索引结构的总体设计 p u t ( a ，c u r r e n t ) ： i o ： i fd e l t i m e s ot h e n r e g i s t e r ( d e l t i m e s ) ： e 1 s e d e l t i m e s 一0 ： e n d 从上面的算法中可以看出，当对结点进行了删除操作，就在删除登记表中 ( 表3 - 1 ) 登记，由于删除操作引起的磁盘空间浪费等问题由删除“善后处理” 进程去处理。然而，不是每次一执行到删除操作就在删除登记表中登记，而是每 执行一个完整的事务后，检查该事务中绝对删除数( 删除次数减去插入次数) ， 如果大于零，就进行登记，反之就不登记。这样，就将代理进程与删除“善后处 理”进程有机地结合起来了。 当频繁地在数据库上的进行各种操作时，上面的算法就能显现出优势。例 如，当连续地向同一结点中插入i 条记录，按照以前的插入算法处理，则需要i 次i o 操作，即对同一物理页面读写i 次；而新算法只需要1 次i o 操作，再加 上启动代理进程以及销毁代理进程的时间。再例如，连续地向同一结点中插入i 条记录，然后又删除j 条记录，假设经过前i 次插入操作，将超过结点的键值容 量，但如果将i 次插入操作与j 次删除操作结合起来作为一个整体进行，抵消后 不会超过结点的容量。如果按照以前的插入算法，不仅要进行多次i o 操作，而 且还会导致磁盘上结点的分裂，而按新算法处理，只需要1 次i o 操作，加上启 动代理进程以及销毁代理进程的时间。由此可见，上面的算法特别适合数据库上 操作特别频繁的o l t p 系统，例如股票数据库系统等。 2 7 天律大学硕士学位论文第四章基于h a s h 表的索引结构设计与实现 第四章基于h a s h 表的索引结构设计与实现 从总体上来说，数据库上的索引结构分为页间索引与页内索引两部分( 参 考3 1 节) 。页问索引一般采用b + 树或其各种变体，现在主流的数据库( o r a c l e 、 d b 2 ) 都采用3 2 节介绍的b - l i n k 树结构。而页内索引则有较多的选择，每种选 择都有其优缺点。本章以h a s h 表索引结构为重点，设计并实现了基于h a s h 表的 数据库索引结构。 4 1h a s h 表概述 哈希表是一种高效的数据结构，它的最大优点在于把数据的存储和查找消 耗的时间大大降低，几乎可以看成是常数时间，而代价仅仅是消耗比较多的内存。 然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外， 编码比较容易也是它的特点。 具体来说 1 ，在记录的存储位置和它的关键字之间建立一个确定的对应关 系f ，使每个关键字和结构中一个唯一的存储位置相对应。因而在查找时，只要 根据这个对应关系f 就可以找到给定值k 的像f ( k ) 。若结构中存在关键字和k 相同的记录，则必定在f ( k ) 的存储位置上，由此，不需要进行比较便可直接取 得所查记录。在此，我们称这个对应关系f 为哈希( h a s h ) 函数，按这个思想建立 的表为哈希表( h a s ht a b l e ) 。 基于h a s h 的索引能根据给出的键值快速的检索到对应的数据记录，非常适 合等值查询的情况。 4 2 基于h a s h 表的索引结构总体设计 完整的索引结构由页间索引结构与页内索引结构构成，两者是不可分割的。 所以这里不刻意区分页间索引与页内索引，整个数据库文件( 也称为表文件) 都 采用 i a s h 表建立索引。 在介绍总体设计结构之前，先定义两个概念： 1 粗锁 对整个表文件锁定的锁称为粗锁。比如，可以认为一个进程对数据库文件( 也 即是表文件) 的0 字节加了读锁后，才能获得读数据库文件的权利。一个进程对 数据库文件的0 字节加了写锁后，才获得修改数据库文件的权利。 显然，使用粗锁时每次只能有一个读进程和写进程访问数据库文件，不允 28 天津大学硕士学位论文第四章基于h a s h 表的索引结构设计与实现 许对数据库文件并发操作。 2 细锁 可以用细锁来提高并发度。我们要求一个读进程或写进程在操作一条记录 前必须先获得此记录所在散列链( 具体含义见4 2 1 节中的讲述) 的读锁或写锁。 允许对一条散列链同时可以有多个读进程，而只能有一个写进程。 当数据库文件包含多个散列链时，则同时可以多个读进程和写进程访问数 据库文件，所以说细锁支持并发访问。 4 2 1 总体设计结构 1 表文件的整体存储结构 数据库一般都是由二维表组成的，如果表之间没有外键约束，则所有表都 是独立的。本文假设每个表都是一个独立的文件，称为表文件。我们设计的表文 件的整体存储结构分成四个部分：文件头部、散列表( 哈希表) 、索引记录区( k e y 区) 、数据区( d a t a 区) ，如图4 - 1 所示。 ， 图4 1 整体存储结构 表由一行行记录组成，我们将记录的关键字( k e y ) 单独集中存放在索引记 录区，即k e y 区，而实际的记录数据存放在数据区，即d a t a 区。创建表文件的 时候，分别给这两个区预分配一定的空间。在使用过程中，当这两个区溢出的时 候，再分别给这两个区分配额外的页面( p a g e ) ，这些额外的页面通过链表分别 组织起来，如图4 一l 所示。k e y 区中的索引记录与d a t a 区中的实际数据记录是 29 天津大学硕十学位论文 第四章基于h a s h 表的索引结构设计与实现 有联系的，具体见图4 2 。 在使用表文件的过程中，可能会删除一些记录，这样在k e y 区以及d a t a 区 就会出现一些空闲记录，所以我们单独设置一条空闲链表来维护这些空闲记录。 在k e y 区的开始保存有f r e ep t r 和t a i lp t r 两个值，f r e ep t r 就是当前k e y 区中空闲索引记录链表的头指针，t a i lp t r 是当前k e y 区中已使用部分的尾地 址，也就是未使用部分的首地址。当k e y 区用完时，分配一个新页面，在k e y 区的最后有一个指针域，就是指向新分配页面的首地址。d a t a 区和k e y 区结构 基本相同，唯一区别就是d a t a 区的开始部分没有f r e ep t r 值。 表文件头部包含k e y 区首地址、d a t a 区首地址、当前索引页面编号、当前 数据页面编号四个值。k e y 区首地址与d a t a 区首地址是两个指针，分别指向k e y 区的首地址和d a t a 区的首地址。当前索引页面编号是指向溢出索引页面中当前 正使用中的页面，一般是页面链表中最后一个页面。同样，当前数据页面指向溢 出数据页面中当前正使用中的页面，一般是页面链表中最后一个页面。 紧接着文件头部的是散列表，散列表包含n 个头指针，参数n 是在创建表 文件的时候指定的。这n 个指针就是h a s h 结构中n 个桶( b u c k e t ) 的首指针。 每个桶中存放的就是索引记录的集合，而这些索引记录实际都是存放在k e y 区中 的。 2 索引结构设计 正如在上文中所讲的，我们将记录的关键字( k e y ) 单独集中存放在k e y 区， 而实际的记录数据存放在d a t a 区。在k e y 区中，我们为每个k e y 增加一些附属 信息，包装成一条索引记录，通过链表将这些索引记录组织起来。k e y 区中的每 条索引记录对应d a t a 区中的一条数据记录。索引记录的详细格式以及索引记录 与数据记录之间的关系如图4 - 2 所示。 在图4 2 所示的索引记录中，c h a i np t r 是该散列链表中下一条索引记录的 指针，i d xl e n 是该条索引记录的长度( 不包括c h a i np t r 与i d xl e n 的长度) ， k e y 是记录的关键字，s e p 是分隔符，d a to f f 是该索引记录所指向的相应数据 记录的指针，d a tl e n 是数据记录的长度。 我们把所有的索引记录存放在散列表的桶中，组织成链表结构。链表的数 目( 也就是桶的数目) 由参数n 指定。在散列表中的n 个指针域，是n 个索引记 录链表的头指针。 当要对某一条记录操作时，先用该记录的关键字为参数，调用某一散列算 法，计算出该记录所属的散列链表( 以下称为桶) ，然后进行相应的操作。我们 设置了1 3 7 个固定的桶。 因为散列函数要反复使用，所以散列函数应该容易计算，而且尽量避免发 3o 天津大学硕士学位论文 第四章基于h a s h 表的索引结构设计与实现 生冲突 2 0 。散列函数一般有两种选择方法： 1 当键为整数时，散列函数的一种常见选择是计算k b 的余数，其中 k 是键值，b 是桶的数目。通常，b 选为一个素数。 2 当键为字符串时，我们可以把每个字符看作一个整数来处理，把它 们累加起来，并将总和除以b ，然后取其余数。 这里我们选用2 作为散列函数。 一条索引记录 散列表 引记 卜孟五：- 叫 图4 - 2 索引记录与数据记录 3 散列链表的维护 为了简单实用起见，散列链表以及空闲索引链表都采用栈的方式进行管理。 当插入记录时，先利用散列函数计算出该记录应该插入哪个桶。接着搜索k e y 区以及溢出索引页面中的空闲链表，查看是否有合适的索引记录，如果有，则将 新记录内容写入该记录，如果没有合适的记录，则在“当前索引页面编号”指定 的索引页面中t a i lp t r 指针所指向的地址处分配新索引记录所需的存储空间， 然后将新索引记录加入到桶的顶部( 因为散列表按照栈式管理) ，最后将新的记 录数据按照索引记录中指定的地址与长度插入到相应的d a t a 区中即可。插入新 记录的详细流程如图4 3 所示。 31 天津大学硕十学位论文第四章基于h a s h 表的索引结构设计与实现 k 翌， l v j 用散列函数计算小 新让采应该插入的桶 渤 兰y j ，l 窄c 1 4 链袋l f j 墩 j 案 l 记 录，并生成新的索引记录 t a i lp t r 指向的未1 j 区域的人小足够分配 、新记录吗2 y 分配 个新的索引页 匝f 井在新蜓嘶r i 为新 索引记录分配空柳 在t a i lp t r 指向的， 使并i 区域中为新索 引记驶分配窀问 将新的索引畦驶加 入剑相应桶的头部 将靳数撕记采按照索引 己采中 指定的地址和t 。窿插入剑d a t a 区或溢出页| 直r l t 相应位簧 结束 图4 - 3 插入记录的流程 查询、修改、删除等操作也类似，一般