第6章 DB的存储结构.

Presentation on theme: "第6章 DB的存储结构."— Presentation transcript:

1 第6章 DB的存储结构

2 第6章 数据库的存储结构 6.1 文件组织 6.2 文件结构 6.3 索引技术 6.4 散列技术 6.5 多键访问 6.6 小结

3 前 言 前面几章，主要强调数据库的逻辑结构。在关系模型中，我们把数据库看成关系的汇集。数据库系统的一个目标是使用户能简单、方便、容易地存取数据库中的数据。用户访问数据库，不必关心数据库的存储结构和具体的实现方式。但是，用户如能了解数据库的存储结构，那么对于数据库就会有一个比较完整的了解，拓宽知识面。 本章先介绍文件组织形式，然后介绍以及常用的索引组织和散列组织。

4 6.1 文件组织 定长记录 变长记录 在外存中，数据库以文件形式组织，而文件由记录组成。文件结构由操作系统的文件系统提供和管理。那么逻辑文件中的记录在物理文件中将如何实现。这是本节所讨论的问题。 一般，文件组织有两种方式，一种是把记录设计成定长格式，另一种是变长格式，下面分别讨论。

5 6.1.1 定长记录（1） 为关系模式EMP（ENAME，ENO，SALARY）可以设计一个文件，记录格式如下：
定长记录（1） 为关系模式EMP（ENAME，ENO，SALARY）可以设计一个文件，记录格式如下： TYPE EMP_TYPE = RECORD ENAME：CHAR(10)； ENO：CHAR(10)； SALARY：REAL； END 假设一个实数占8个字节，那么每个记录占28个字节。可以像图6.1那样把记录依次组织起来。一个职工可以为几个部门工作，因此可以有几个工号。

6 6.1.1 定长记录（2） 图6.1 定长记录的文件 在系统运行时，有两个问题需考虑：
定长记录（2） 在系统运行时，有两个问题需考虑： ●如果要删除一个记录，那么必须在被删位置上填补一个记录，或者设法使文件忽略该位置。 ●除非每块的大小恰好是28的倍数，否则可能有的记录横跨两个块。读 / 写这样的记录就要访问两个块。 记录0 LIU A-102 600 记录1 WEN B-306 700 记录2 HE F-257 800 记录3 ZHANG A-214 记录4 ZHOU C-343 750 记录5 B-215 记录6 LOU B-428 850 记录7 B-467 记录8 C-333 400 图6.1 定长记录的文件

7 6.1.1 定长记录（3） 图6.2 把被删记录后的 记录依次移上来 记录0 LIU A-102 600 记录1 WEN B-306 700
定长记录（3） 记录0 LIU A-102 600 记录1 WEN B-306 700 记录3 ZHANG A-214 记录4 ZHOU C-343 750 记录5 B-215 800 记录6 LOU B-428 850 记录7 B-467 记录8 C-333 400 1．删除操作时的考虑 删除一个记录，可采用下面三种方法之一实现： （1） 把被删记录后的记录一次移上来 例如在图6.1中，要删除记录2，那么要把记录3～8依次移上来，如图6.2所示。这时删除一个记录平均要移动文件中的一半记录。 图6.2 把被删记录后的 记录依次移上来

8 6.1.1 定长记录（4） （2） 把文件中最后一个记录填补到被删记录位置，如图6.3所示。
定长记录（4） （2） 把文件中最后一个记录填补到被删记录位置，如图6.3所示。 这两种方法都要移动结点，操作不灵活。由于数据库中删除操作总是少于插入操作，因此我们可以采用下面方式实现。 记录0 LIU A-102 600 记录1 WEN B-306 700 记录8 C-333 400 记录3 ZHANG A-214 记录4 ZHOU C-343 750 记录5 B-215 800 记录6 LOU B-428 850 记录7 B-467 图6.3 把最后一个记录填补到被删记录位置

9 6.1.1 定长记录（5） 图6.4 删除记录1、4、6后的文件结构 文件 首部 记录0 LIU A-102 600 记录1 记录2 HE
定长记录（5） 文件 首部 记录0 LIU A-102 600 记录1 记录2 HE F-257 800 记录3 ZHANG A-214 记录4 记录5 B-215 记录6 记录7 B-467 记录8 C-333 400 （3） 把被删结点用指针链接起来 在每个记录中增加一个指针，在文件中增设一个文件首部。文件如图6.4所示。 这种方式较好。但要注意，是否还有指针指向被删记录。在DB中，被指针指向的记录称为“被拴记录”。如果不小心把被拴记录删掉，那么指向该记录的指针成了“悬挂指针”。悬挂指针指向的空间称为“垃圾”，即该空间别人无法使用而又被空闲着。 图6.4 删除记录1、4、6后的文件结构

10 6.1.1 定长记录（6） 2．插入操作时的考虑 如果采用把被删记录链接起来的方法，那么插入操作可采用下列方法：
定长记录（6） 2．插入操作时的考虑 如果采用把被删记录链接起来的方法，那么插入操作可采用下列方法： 在空闲记录链表的第一个空闲记录中，填上插入记录的值，同时使首部指针指向下一个空闲记录；如果空闲记录链表为空，那么只能把新记录插到文件尾。 定长记录文件的插入操作比较简单，因为插入记录的长度与被删记录的长度是相等的。在变长记录文件中操作就复杂了。

11 6.1.2 变长记录（1） 在DBS中，有时需要文件中的记录是变长格式。
变长记录（1） 在DBS中，有时需要文件中的记录是变长格式。 例如，一个文件存储了多种不同的记录类型记录；文件中允许记录类型的记录是变长的；允许记录中某个字段可以出现重复组等等。 例如图6.1的文件也可以设计成变长记录格式： TYPE EMP_LIST=RECORD ENAME：CHAR（10）； ENO_INFO：ARRAY[1..∞] OF RECORD ENO：CHAR（10）； SALARY：REAL； END 此处定义（ENO，SALARY）作为成分元素组成一个数组，成分具体个数视实际情况而定。

12 6.1.2 变长记录（2） 图6.5 变长记录的字节串表示形式 变长记录的表示有字节串形式和定长形式两种。 1．变长记录的字节串表示形式
变长记录（2） 变长记录的表示有字节串形式和定长形式两种。 1．变长记录的字节串表示形式 这种形式是把每个记录看成连续的字节串，然后在每个记录的尾部附加“记录尾标识符”（⊥）。图6.1的定长记录文件可以用图6.5的格式表示。 LIU A-102 600 B-215 800 C-333 400 ⊥ 1 WEN B-306 700 2 HE F-257 3 ZHANG A-214 B-467 4 ZHOU C-343 750 5 LOU B-428 850 图6.5 变长记录的字节串表示形式

13 6.1.2 变长记录（3） 字节串表现形式的另一种方式是在记录的开始加一个记录长度的字段来实现，而不是使用在记录尾加标志符的方法。
变长记录（3） 字节串表现形式的另一种方式是在记录的开始加一个记录长度的字段来实现，而不是使用在记录尾加标志符的方法。 字节串表示形式有两个缺点： （1） 由于各记录的长度不一，因此被删记录的位置难以重新使用。既使制订许多技术规则，仍然会导致磁盘中出现大量小的空间（即“碎片”）浪费了。 （2） 如果文件中的记录要伸长，很难实现。必须要把记录移到他处才能伸长。如果要伸长的记录是“被拴记录”，那么移动的代价是很大的。 由于上述两个缺点，现在一般不使用字节串表现形式。在实际中，往往使用的是一种改进的字节串表现形式，称为“分槽式页结构”（slotted – page structure），如图6.6所示。

14 6.1.2 变长记录（4） 图6.6 分槽式页结构 在每块的开始处设置一个“块首部”，其中包括下列信息： ① 块中记录数目
变长记录（4） 在每块的开始处设置一个“块首部”，其中包括下列信息： ① 块中记录数目 ② 指向块中自由空间尾部的指针 ③ 登记每个记录的开始位置和大小的信息 块首部 记录大小 记录数目 自由空间…… 记录位置 自由空间尾部 图6.6 分槽式页结构

15 变长记录（5） 在块中实际记录紧连着，并靠近块尾部存放。块中自由空间也紧连着，在块的中间。插入总是从自由空间尾部开始，并在块首部登录其插入记录的开始位置和大小。 记录删除时只要在块首部该记录的大小登记处改为-1即可。更进一步，可以把被删记录左边的记录移过来填补，使实际记录仍然紧连着。当然此时块首部记录的信息也要修改。记录的伸缩也可使用这样的方法。在块中移动记录的代价也不太高，这是因为一块的大小最多只有4KB。 在分槽式页结构中，要求其它指针不能直接指向记录本身，而是指向块首部中的记录信息登记项，这样块中记录的移动就独立与外界因素了。

16 变长记录（6） 2．变长记录的定长表示形式 在文件系统中往往是使用一个或多个定长记录来表示变长记录的方法。具体实现时有两种技术：预留空间和指针技术。 （1） 预留空间的方法 取所有变长记录中最长的一个记录的长度作为存储空间的记录长度，来存储变长记录。如果变长记录短于存储记录长度，那么在多余空间处填上某个特定的空值或记录尾标志符。例如图6.5的字节串表现形式可以用图6.7的预留空间方法实现。这方法一般使用在大多数记录的长度接近最大长度时才使用，否则使用时空间浪费很大。

17 6.1.2 变长记录（7） 图6.7 变长记录 的预留空间 表示形式 LIU A-102 600 B-215 800 C-333 400 1
变长记录（7） LIU A-102 600 B-215 800 C-333 400 1 WEN B-306 700 ⊥ 2 HE F-257 3 ZHANG A-214 B-467 4 ZHOU C-343 750 5 LOU B-428 850 图6.7 变长记录 的预留空间 表示形式 （2） 指针形式 如果记录的长度相差很大，那么可用指针形式实现变长记录的定长表示形式。在每个记录后加一个指针字段，图6.5的文件可以用图6.8来表示。 使用改进的指针形式，在一个文件中使用两种块，固定块和溢出块。图6.9表示文件的固定块和溢出块结构。

18 6.1.2 变长记录（8） 图6.8 变长记录的 图6.9 固定块和 指针表示方式 溢出块的结构 LIU A-102 600 1 WEN
变长记录（8） LIU A-102 600 1 WEN B-306 700 2 HE F-257 800 3 ZHANG A-214 4 ZHOU C-343 750 5 B-215 6 LOU B-428 850 7 B-467 8 C-333 400 固 定 块 LIU A-102 600 WEN B-306 700 HE F-257 800 ZHANG A-214 ZHOU C-343 750 LOU B-428 850 B-215 C-333 400 B-467 溢出块 图6.8 变长记录的 指针表示方式 图6.9 固定块和 溢出块的结构

19 6.2 文件结构 四种文件结构 顺序文件 聚集文件

20 6.2.1 四种文件结构 文件结构主要有下列四种形式： （1）堆文件（heap file）
四种文件结构 文件结构主要有下列四种形式： （1）堆文件（heap file） 记录可以放在文件的任何位置上。一般，以输入顺序为序。记录的存储顺序与关键码没有直接的联系。删除操作只是加个删除标志，新插入记录总是在文件尾。 （2）顺序文件（sequential file） 记录是按查找键值升序或降序的顺序存储的。 （3）散列文件（hashing file） 据记录的某个属性值通过散列函数求得的值作为记录的存储地址（即“块号”）。这个技术通常与索引技术连用。 （4）聚集文件（clustering file） 一个文件可以存储多个关系的记录。不同关系中有联系的记录存储在同一块内，可以提高查找速度和I / O速度。 本节介绍顺序文件和聚集文件，散列文件在6.4节中介绍。

21 顺序文件（1） 根据查找键的值的顺序存储记录的文件称为顺序文件。在文件中，每个记录增加一个指针字段，根据查找键值的大小用指针把记录链接起来。 文件初始建立时，存储记录尽可能使物理顺序和查找键值的顺序一致。 图6.10是顺序文件的例子，记录按ENAME值升序排列。顺序文件可以很方便地按查找键的值的大小顺序读出所有的记录。 HE F-257 800 LIU A-102 600 B-215 C-333 400 LOU B-428 850 WEN B-306 700 ZHANG A-214 B-467 ZHOU C-343 750 图6.10 顺序文件

22 顺序文件（2） 删除操作可以通过修改指针实现，被删记录链接成一个自由空间，以便插入时使用。 插入操作包括定位和插入两步： （1）定位：在指针链中，找到插入的位置，即插入记录应插在哪个记录的前面。 （2）插入：在找到记录的块内，如果有空闲记录，那么在该位置插入新记录，并加入到指针链中；如果无空闲记录，那么就只能插入到溢出块中。 在图6.10中，插入一个新记录（MA，B-547，500），就得到图6.11。 HE F-257 800 LIU A-102 600 B-215 C-333 400 LOU B-428 850 WEN B-306 700 ZHANG A-214 B-467 ZHOU C-343 750 MA B-547 500 图6.11 插入一个记录 后的顺序文件

23 聚集文件（1） 在小型DBS中，数据量小，每个关系处理成一个文件。这种文件称为单记录类型文件，文件中每个记录都是定长的。文件之间是分离的，没有联系。 随着数据量的增大，系统的性能和查询速度日益下降。此时应采用新的文件结构，称为“聚集文件”。这种变化允许一个文件由多个关系的记录组成，即多记录类型文件。聚集文件的管理由DBS实现。 例如教学数据库中关系S（SNO，SNAME，AGE，SEX）和SC（SNO，CNO，SCORE），如果将每个关系组织成一个文件，那么查找学生的成绩，就要做连接操作： SELECT S.SNO，SNAME，CNO，GRADE FROM S，SC WHERE S.SNO = SC.SNO；

24 聚集文件（2） 在图6.12中，关系S和SC如图（a）、（b）所示，S和SC的元组混合放在一起，如图（c）所示。即使一个学生的成绩信息很多，一块访不下，那么也是放在相邻的块内。为了进一步提高查询速度，我们可以在文件中建立以查询学生信息为主的链表，在图6.12的（c）中已表示。 S1 WANG 20 M C1 80 S2 LIU 21 F C2 70 S3 CHEN 22 90 85 C3 95 （a）关系S （b）关系SC （c）聚集文件 图6.12 聚集文件例子

25 6.3 索引技术 6.3.1 索引机制 6.3.2 有序索引的分类 6.3.3 主索引 6.3.4 辅助索引 6.3.5 B+树索引文件
6.3 索引技术 索引机制 有序索引的分类 主索引 辅助索引 B+树索引文件 B树索引文件

26 6.3.1 索引机制 根据记录中某种排序顺序建立的索引，称为有序索引。 在索引技术中，用户可根据下面五个方面选择各种实现方法：
索引机制 根据记录中某种排序顺序建立的索引，称为有序索引。 在索引技术中，用户可根据下面五个方面选择各种实现方法： ① 存取类型：用户是根据属性值找记录，还是根据属性值的范围找记录。 ② 存取时间；查找记录所花费的时间。 ③ 插入时间；插入新记录所花费的时间，应包括两部份，找到正确的位置插入新记录所花时间和修改索引结构所花时间。 ④ 删除时间；也应包括两部分，找到被删记录删除所花时间和修改索引结构所花时间。 ⑤ 索引空间开销。 在索引中，用于找记录的属性集称为查找键。应注意，查找键不一定是主键（候选键、超键），前者的值允许重复，而后者的值不允许重复。

27 有序索引的分类 索引文件由两个部分组成：索引和主文件。由于主文件记录多、数据量大并且占据大量物理块，因此在主文件中查找，速度是很慢的。如果对记录建立索引，那么相对主文件而言，索引空间小，因而查找速度就快。 这里考虑的主文件是指顺序文件，文件按某个属性值大小的顺序排列。对主文件可以建立几套不同的索引。 如果索引的查找键值的顺序与主文件的顺序一致，那么这种索引称为主索引，也称为聚集索引。一般，主索引的查找键往往是文件的主键。 如果查找键的值的顺序与主文件的顺序不一致，那么这种索引称为辅助索引，或非聚集索引。

28 主索引（1） 当索引查找键值的顺序与主文件顺序一致时，这种索引文件称为“索引顺序文件”。这种文件既适用随机处理，也适用顺序处理。下面以图6.10的顺序文件为例介绍主索引以及稠密索引、稀疏索引和多级索引三种实现方法。 1．稠密索引和稀疏索引 对于主索引，可以采用下面两种实现方法： （1） 稠密索引（dense index）：对于主文件中每一个查找键值建立一个索引记录（索引项），索引记录包括查找键值和指向具有该值的记录链表中第一个记录的指针。这种索引称为“稠密索引”。读者应注意，在有些教材中稠密索引定义为对主文件中每个记录建立一个索引记录，与我们的提法有区别。 图6.13是为图6.10的顺序文件建立的稠密索引。

29 6.3.3 主索引（2） 图6.13 稠密索引 HE LIU LOU WEN ZHANG ZHOU HE F-257 800 LIU
主索引（2） HE LIU LOU WEN ZHANG ZHOU HE F-257 800 LIU A-102 600 B-215 C-333 400 LOU B-428 850 WEN B-306 700 ZHANG A-214 B-467 ZHOU C-343 750 图6.13 稠密索引

30 主索引（3） （2） 稀疏索引（sparse index）：在主文件中，对若干个查找键值才建立一个索引记录，此时索引记录的内容仍和稠密索引一样。这种索引称为“稀疏索引”。 图6.14为图6.10的顺序文件建立的稀疏索引。 HE LOU ZHANG HE F-257 800 LIU A-102 600 B-215 C-333 400 LOU B-428 850 WEN B-306 700 ZHANG A-214 B-467 ZHOU C-343 750 图6.14 稀疏索引

31 主索引（4） 相比之下，在带稠密索引的主文件中，查找速度较快；而带稀疏索引的文件中查找较慢，但稀疏索引的空间较小，因此插入、删除操作时指针的维护量相对要少些。 系统设计者应在存取时间和空间开销方面权衡，选择何种索引。有一个折衷的办法，可把两种索引结合起来。 首先为顺序文件的每一块建立一个索引记录，得到一个以块为基本单位的稠密索引，然后再在稠密索引基础上建立一个稀疏索引。查找时，先在稀疏索引中找到记录所在的范围，然后在稠密索引中确定记录在哪一块，最后在主文件的块中顺序查找，找到所在的主记录。这种方法实际已是二级索引了。

32 6.3.3 主索引（5） 2．多级索引 即使采用稀疏索引，可能建成的索引还是很大，以至于查询效率不高。
主索引（5） 2．多级索引 即使采用稀疏索引，可能建成的索引还是很大，以至于查询效率不高。 解决这个问题的方法是对主索引再建立一级稀疏索引。即对每个索引块建立一个索引记录（如图6.15所示）。 图6.15是一个二级索引例子。此时外层索引块可常驻内存，在找记录时内层索引块只要读1次就行。如果外层索引块的数目太多，不能全部进内存，那么可对最外层索引再往外建一层索引。这就形成了多级索引技术。

33 主索引（6） 外层索引 内层索引 索引块0 数据块0 索引块1 … 数据块1 … … … 图 二级稀疏索引

34 6.3.3 主索引（7） 3．索引的更新：在索引文件中，主记录的插入或删除可能会引起索引的修改。在只有一级的索引中索引的修改算法如下所述。
主索引（7） 3．索引的更新：在索引文件中，主记录的插入或删除可能会引起索引的修改。在只有一级的索引中索引的修改算法如下所述。 （1） 删除操作 ●为了在主文件中删除一个记录，首先要找到被删记录，才能执行删除操作。 ●如果符合查找键值的记录在文件中只有一个，那么被删记录删除后，肯定要修改索引。 ●如果要修改索引，对于稠密索引，要从索引中删除被删记录相应的索引记录；对于稀疏索引，如果被删记录的查找键值在索引块中出现，那么用主文件中被删记录的下一个主记录的查找键值A替换，如果A已在索引块中出现，那么被删记录的相应索引记录应从索引块中删除。

35 6.3.3 主索引（8） （2） 插入操作 ●首先，用插入记录的查找键值找到插入位置。
主索引（8） （2） 插入操作 ●首先，用插入记录的查找键值找到插入位置。 ●如果是稠密索引并且查找键值在索引块中未出现过，那么要把插入记录的查找键值插入到索引块中。 ●如果是稀疏索引，每一个数据块对应一个索引记录，那么在数据块能放得下新记录时，不必修改索引。如果要加入新的数据块，那么插入记录的查找键值将成为新数据块的第一个查找键值，并将在索引块中插入一个新的索引记录。 在多级索引时,可以采取类似的办法。在插入、删除主记录时，最低一级索引的修改方法如上所述。如果第二级索引（外层）要修改，那么把第一级索引（内层）看成顺序文件。在第一级索引中插入或删除一个索引记录时，第二级索引的修改也像上面叙述的方法一样。以此类推。

36 辅助索引（1） 在主索引中，我们可以方便、快速地根据某个查找键值找记录。如果我们要根据另一个查找键值寻找主文件的记录，那么可以用辅助索引方法实现。 在主索引中，具有相同查找键值的记录在同一块中或相邻的块中，因而查找速度较快。而在辅助索引中，具有相同查找键值的记录将分散在文件的各处，因而查找速度较慢，并且查找时无法利用主文件中按主索引键值建立的指针链。 辅助索引可采用下面的方法实现：仍然为每个查找键值建立一个索引记录，内容包括查找键值和一个指针。但这个指针不指向主文件中的记录，而是指向一个桶（bucket），桶内存放指向具有同一查找键值的主记录的指针。例如在图6.10的顺序文件中，可以对属性SALARY建立一个辅助索引，其结构如图6.16所示。

37 6.3.4 辅助索引（2） 图6.16 辅助索引例子 HE F-257 800 LIU A-102 600 B-215 C-333 400
辅助索引（2） HE F-257 800 LIU A-102 600 B-215 C-333 400 LOU B-428 850 WEN B-306 700 ZHANG A-214 B-467 ZHOU C-343 750 400 600 700 750 800 850 图6.16 辅助索引例子

38 辅助索引（3） 在主索引中可以采取顺序查找方法。在辅助索引中，由于同一个查找键值的记录分散在文件的各处，因此以辅助索引查找键顺序扫描文件是行不通的，每读一个记录几乎都要执行读一块到内存的操作。 辅助索引都是稠密索引，不可能是稀疏索引结构。在主记录插入或删除时，都要修改辅助索引，修改的方法与主索引的方法类似。 辅助索引机制曾在20世纪60年代中期广泛流行，倒排文件系统就是建立了许多辅助索引的文件系统。辅助索引改善了系统的查询效率和查询方式，但是也给系统带来很大的负担。数据库应用设计者应在查询效率和修改的代价方面作出权衡，以选择合适的索引结构。

39 B+树索引文件（1） 1．平衡树的概念 为了改善索引结构的性能，可以采用多级索引，目前广泛流行的一种技术，称为平衡树（Balanced tree）技术。数据库技术中平衡树的形式定义如下所述。 定义6.1 一棵m阶平衡树或者为空，或者满足以下条件： ① 每个结点至多有m棵子树； ② 根结点或为叶结点，或至少有两棵子树； ③ 每个非叶结点至少有⌈m/2⌉棵子树； ④ 从根结点到叶结点的每一条路径都有同样的长度，即 叶结点在同一层次上。 平衡树又分为两类：B+树和B树。下面先介绍B+树。

40 6.3.5 B+树索引文件（2） 图6.17 B+树的结点结构 2．B+树的结构 在实际使用中，B+树有很多形式，下面介绍其中的一种。
一棵m阶B+树是平衡树，按下列方式组织： （1） 每个结点中至多有m-1个查找键值K1，K2，…，Km-1， m个指针P1，P2，…，Pm，如图6.17所示。 P1 K1 P2 …… Pm-1 Km-1 Pm 图6.17 B+树的结点结构

41 B+树索引文件（3） （2） 叶结点的组织方式 叶结点中的指针（1≤i≤m-1）指向主文件中的记录。譬如指针Pi指向查找键值为Ki的主记录。 如果查找键恰好是主文件的主键，那么叶结点中的指针直接指向主文件中的记录。如果查找键不是主文件的主键，并且查找键值的顺序也不是主文件的顺序，那么叶结点中的指针指向一个桶，桶中存放指向具有该查找键值的主记录的指针。 每个叶结点中至少应有⌈（m-1）/2⌉个查找键，至多有m-1个查找键，并且查找键值不允许重复。如果B+树索引是稠密索引，那么每个查找键值必须在某个叶结点中出现。 叶结点中最后一个指针Pm，指向下一个叶结点（按查找键值顺序）。这样可以很方便地在主文件进行顺序访问。 图6.18表示3阶B+树的叶结点结构。

42 6.3.5 B+树索引文件（4） 图6.18 3阶B+树的 叶结点结构 下一个叶结点 叶结点 HE LIU 主文件 HE F-257 800
A-102 600 B-215 C-333 400 … 图 阶B+树的 叶结点结构 （3） 非叶结点的组织方式 B+树中的非叶结点形成了叶结点上的一个多级稀疏索引。每个非叶结点（不包括根结点）中至少有⌈m/2⌉个指针，至多有m个指针。指针的数目称为结点的“扇出端数”（fanout）。图6.19是一个完整的3阶B+树索引。图6.20是一个5阶B+树索引的例子。

43 6.3.5 B+树索引文件（5） 图6.19 3阶B+树索引 图6.20 5阶B+树索引 ZHANG LOU WEN HE LIU ZHOU

44 B+树索引文件（6） 3．B+树的查询 如果用户要检索查找键值为K的所有记录，那么首先在根结点中找大于K的最小查找键值（设为Ki），然后沿着Ki左边的指针Pi到达第二层的结点。如果根结点中有n个指针，并且K＞Kn-1，那么就沿着指针Pn到达第二层的结点。在第二层的结点，用类似的方法找到一个指针，进入第三层的结点……一直到进入B+树的叶结点，找到一个指针直接指向主文件的记录，或指向一个桶（存放指向主文件记录的指针）。最后把所需记录找到。 如果文件中查找键值有W个值，那么对于m阶B+树而言，从根结点到叶结点的路径长度不超过⌈log⌈m/2⌉（W）⌉。

45 6.3.5 B+树索引文件（7） 例6.2 讨论B+树索引查询中查询次数与文件的存储块数的关系。
如果在B+树索引中，每块存储一个结点，占4096字节。如果查找键的长度为32字节，指针仍为8字节，那么每块大约可存储100个查找键值和指针，即m约为100。 在m为100时，如果文件中查找键有100万个值，那么一次查找需读索引块的数目为 ⌈log50（ ）⌉=4。如果B+树索引的根结点常驻内存，那么查找时只需再读三个索引块即可。 B+树的结构与内存中普遍使用的二叉排序树的主要区别是结点的大小以及树的高度。在二叉排序树中，每个结点很小，只有一个键值和两个指针。而B+树中，每个结点很大，可以是磁盘上的一个块，包含更多查找键值和指针。二叉排序树显得瘦而高，而B+树显得胖而矮。

46 B+树索引文件（8） 4．B+树的更新 在B+树索引文件中插入主记录时，有可能叶结点要分裂，并引起上层结点的分裂和B+树层数的增加。在删除主记录时，这有可能出现相反的现象。下面就是否出现分裂与合并情况分别讨论。 （1）不引起索引结点分裂的插入操作 首先使用查找方法，从根结点出发直到在叶结点中找到某个查找键值K1。如果插入记录的查找键值K0已在叶结点出现，那么在主文件中插入记录即可，不必修改索引。 如果K0在叶结点中不存在，那么在叶结点中K1之前插入K0值（此时假设叶结点中存在空闲空间），并把K1及K1后的值往后移动，使叶结点中查找键值仍然保持排序。然后插入新记录到主文件中去。

47 6.3.5 B+树索引文件（9） （2）不引起索引结点合并的删除操作 首先使用查找方法在主文件中找到被删记录，删除之。
如果主文件中还存在具有被删记录查找键值的记录，那么不必修改索引；否则应该从叶结点中删除该查找键值和相应的指针。此时假定叶结点中中查找键值的数目仍然不小于⌈（m-1）/2⌉。 （3）引起索引结点分裂的插入操作 如果插入主记录时，要在叶结点中插入其查找键值，并且叶结点中已放满查找键值，那么此时叶结点应分裂成两个。例如在图6.19的3阶B+树文件中，插入一个查找键值为“JIANG”的主记录，那么左边第一个叶结点就要分裂成两个结点，如图6.21所示。

48 6.3.5 B+树索引文件（10） 图6.21 插入JIANG后叶结点的分裂 图6.22 在图6.19的B+树中插入“JIANG” HE
LIU 图6.21 插入JIANG后叶结点的分裂 WEN LIU LOU ZHANG HE JIANG LIU LOU WEN ZHANG ZHOU 图6.22 在图6.19的B+树中插入“JIANG”

49 6.3.5 B+树索引文件（11） 图6.23 在图6.22的B+树中删除“LIU” （4）引起索引结点合并的删除操作
如果删除主记录时，要在叶结点中删除被删记录的查找键值，并且该值删除后叶结点中查找键值数目小于⌈（m-1）/2⌉，那么这个叶结点在作技术处理时有可能被删掉。 例如在图6.22中要删除“LIU”主记录，导致叶结点中删除“LIU”后成为空叶结点，因此该叶结点要删除。这将引起在父结点中删除相应指针及指针左边的查找键值“LIU”。此时索引的修改结束后如图6.23所示。 LOU ZHANG WEN HE JIANG ZHOU 图 在图6.22的B+树中删除“LIU”

50 6.3.5 B+树索引文件（12） 图6.24 在图6.23的B+树中删除“WEN”
如果要在图6.23中删除“WEN”的主记录，那么也会导致叶结点删除WEN后成为空叶结点而被删除。在其父结点中删除相应指针后，只剩下一个查找键值ZHANG和一个指针，这不符合B+树的要求。由于该结点中还有信息，因此不能像刚才那样进行简单的删除。此时由于其相邻的左孪结点中还有空闲空间，因此两个结点可合并成一个结点。这就引起根结点中也少了一个指针，不符合B+树要求，因此可把根结点直接删去即可（如图6.24所示）。此时B+树的高度减少了一层。 LOU ZHANG HE JIANG ZHOU 图 在图6.23的B+树中删除“WEN”

51 6.3.5 B+树索引文件（13） 图6.25 在图6.22的B+树中删除“WEN”
但有时结点的合并未必成功，只能重新安排指针。例如在图6.22中删除“WEN”的主记录（此时“LIU”未删除）。在叶结点中把“WEN”删除后成为空叶结点，在父结点中删除相应指针后，指针数目不够。此时父结点的左孪结点中已放满了查找键值，因而不能合并，只能重新安排指针，从左孪结点中移一个指针过来，同时在这两个结点的父结点（这里是根结点）中查找键值应修改为“LOU”，如图6.25所示。 LIU ZHANG LOU HE JIANG ZHOU 图 在图6.22的B+树中删除“WEN”

52 B+树索引文件（14） 虽然B+树索引的插入、删除比较复杂，但其速度与B+树高度成正比。前面已提到，100万个记录的B+树索引才4层，因此所花代价是不大的。由于这个原因，B+树结构在DBS中得到广泛应用。 5．B+树文件组织 前面提到的B+树索引文件组织，把B+树索引与主文件截然分开。在B+树结构中，所有叶子处在同一层次上，并且利用叶子中的指针指向主文件中的记录，或指向一个桶，再由桶内指针指向记录。在这样的结构中，B+树不仅是一个索引，而且还是一个文件中记录的组织者。

53 B+树索引文件（15） 对B+树索引文件组织作进一步的演变，使得B+树叶结点不存储指向主记录的指针，而是直接存储记录本身，那么这种结构称为“B+树文件组织”。图6.26表示了这种结构。这样，查询时到达叶结点后，直接可把主记录找到，不必再沿着指针去找主记录.显然文件的性能得到进一步的提高.虽然主记录长度要比指针大很多,也就是每个叶结点可存储的记录数目要小于非叶结点中的指针数目,但是我们仍然要求每个叶结点中至少有一半空间是装着记录的。 B+树文件组织的插入、删除操作与B+树索引记录的插入和删除操作是一样的，也有可能会引起结点的分裂或合并，层数的增加或减少。

54 6.3.5 B+树索引文件（16） 图6.26 B+树文件组织 C F 1 K M (A,4) (B,8) (C,2) (D,9)
(E,4) (F,7) (G,3) (H,3) (I,4) (J,8) (K,4) (L,6) (M,4) (N,8) (P,6) 图6.26 B+树文件组织

55 6.3.6 B树索引文件（1） 图6.27 与图6.22中B+树 等价的B树结构
B树索引类似于B+树索引。两者主要区别在于B树中所有查找键值只出现一次。例如，在图6.22的B+树中，查找键值“LIU”、“LOU”等都出现了两次。在B+树中，每个查找键值都必须在叶结点中出现，为了组织多级索引，某些查找键值还必须在上层结点中出现。 在B树中，查找键值可以出现在任何结点上，但只能出现一次。图6.22的B+树结构用B树形式表示如图6.27所示。显然，B树中的查找键值数目比B+树少。 图6.27 与图6.22中B+树 等价的B树结构 LIU ZHANG HE JIANG LOU WEN ZHOU bucket

56 B树索引文件（2） 在B树中查询的查找次数取决于查找键值的位置，有时未到达叶结点，就已找到了键值。查找键值靠近下面层次或叶结点层次，则查找次数较多。B树的查询时间复杂性仍然是对数级时间。 在B树中，如果查找键值出现在非叶结点，那么在它出现的地方应附加上一个指向主记录的指针；如果查找键值出现在叶结点，那么不必另加指针，可利用结点中的指针指向主记录。像B+树一样，这个指针也可指向一个桶，桶内存放指向主记录的指针。这个结构如图6.28所示。指针Pi的使用方法与B+树一样，非叶结点中的指针Bi指向一个桶或主记录。一棵m阶B树中，每个非叶结点中最多可包含m个指针，m-1个查找键值和m-1个指向桶的指针。而每个叶结点最多可包含n个指针和n-1个查找键值。由于叶结点中不包含Bi指针，因此叶结点中可以比非叶结点多存储一些查找键，也就是n＞m。

57 B树索引文件（3） B树中删除操作较复杂。B+树的删除操作总是在叶结点进行，而B树有时可在非叶结点进行。B树中，如果被删的查找键值在非叶结点中，那么必须从子树中选一个查找键值填补。譬如某个非叶结点中，要删除查找键值Ki，那么应从指针Pi+1指向的子树中选一个最小的查找键值移上来填补Ki的位置。如果叶结点中发现查找键值太少时，那么也要像B+树那样进行结点的合并工作。B树的插入基本上与B+树类似。 虽然B树的空间量比B+树小，但是由于B树的删除操作较复杂，因此大多数DBS都是使用B+树结构，而不使用B树结构。

58 6.3.6 B树索引文件（4） 图6.28 B树中非叶结点和叶结点的结构 非叶结点 P1 B1 K1 P2 B2 K2 Pm-1 Bm-1
…… Pm-1 Bm-1 Km-1 Pm 叶结点 P1 K1 P2 K2 …… Pn-1 Kn-1 Pn 图6.28 B树中非叶结点和叶结点的结构

59 6.4 散列技术 6.4.1 散列机制 6.4.2 散列索引 6.4.3 静态散列中的问题 6.4.4 可扩充散列结构
6.4 散列技术 6.4.1 散列机制 6.4.2 散列索引 6.4.3 静态散列中的问题 6.4.4 可扩充散列结构 前面提到的顺序文件组织的缺点是必须通过索引结构访问数据。而且索引组织的空间和I／O操作的时间代价都是很大的。而散列方法是一种不必通过索引就能访问数据的方法。在散列技术基础上结合索引方法可进一步提高访问效率。本节介绍DB技术中使用的散列技术。

60 散列机制（1） 1．散列概念 根据记录的查找键值，使用一个函数计算得到的函数值作为磁盘块的地址，对记录进行存储和访问，这种方法称为散列方法。在DB技术中，一般使用“桶”（bucket）作为基本的存储单位。一个桶可以存放多个记录。桶可以是磁盘中的块，也可以是比块大的空间。 定义6.2 设K是所有查找键值的集合，B是所有桶地址的集合。散列函数h是从K到B的一个函数，它把每个查找键值映像到地址集合中的地址。 要插入查找键值为Ki的记录，首先也是计算h（Ki），求出该记录的桶地址，然后在桶内查找。 删除操作是很方便的，先用查找方法把记录找到，然后直接从桶内删去即可。

61 散列机制（2） 2．散列函数 使用散列方法，首先要有一个好的散列函数。由于在设计散列函数时不可能精确知道要存储的记录的查找键值，因此要求散列函数在把查找键值转换成存储地址（桶号）时，因满足下面两个条件： ① 地址的分布是均匀的：把所有可能的查找键值转换成桶号以后，要求每个桶内的查找键值数目大抵相同。 ② 地址的分布是随机的：所有散列函数值不受查找键值各种顺序的影响，例如字母顺序、长度顺序等。 散列函数在数据结构教材中已有详细介绍，这里不再详述。下面介绍常用的“质数除余法”，把记录的查找键值除以一个质数，求得的余数作为桶号。为方便，下面例子中除数不是质数，而是10。

62 散列机制（3） 例6.3 对于图6.1的数据，我们可以用散列方法存储。假设查找键值是ENAME。散列函数用下列方法设计：把姓名字符串中每一个字符转换成一个整数（按字母表中的顺序），然后求出这些整数的和；假设存储空间分成10个桶，把求得的“和”除以10，得到余数作为桶号；然后把记录存入相应的桶。例如“LIU”转换成的整数和为42，除以桶数10，得到余数2，作为桶号，把LIU记录存入桶号为2的桶内。图6.1的数据用散列方法组织的示意图见图6.29。 散列函数应仔细设计。设计得不好，造成各个桶内的查找时间有长有短；设计得好，各个桶内的查找时间相差无几，并且查找的平均时间是最小的。

63 6.4.1 散列机制（4） 图6.29 查找键为ENAME的散列组织 桶0 ZHOU C-343 750 桶5 桶1 桶6 ZHANG
散列机制（4） 桶0 ZHOU C-343 750 桶5 桶1 桶6 ZHANG A-214 600 B-467 桶2 LIU A-102 桶7 B-215 800 C-333 400 WEN B-306 700 桶3 HE F-257 桶8 LOU B-428 850 桶4 桶9 图6.29 查找键为ENAME的散列组织

64 散列机制（5） 3．桶溢出的处理 在散列组织中，每个桶的空间是固定的，如果某个桶内已装满记录，还有新的记录要插入到该桶，那么称这种现象为“桶溢出”（也称为“散列碰撞”）。产生桶溢出的原因主要有以下两个： ●初始设计时桶数偏少。 ●由于散列函数的“均匀分布性”不好，造成某些桶存满了记录，而某些桶有较多空闲空间。 在设计散列函数时，桶数应放宽些，一般存储空间应有20%的余量，让它空闲着，以利减少桶溢出的机会。 但是不管散列函数如何好，再留有一定的存储空间余量，桶溢出现象难免还会发生。因而我们仍要有一系列处理溢出的方法，具体如下所述。

65 散列机制（6） （1） 溢出桶拉链法（溢出链法）：如果某个桶b（称为基本桶）已装满记录，还有新的记录等待插入桶b，那么可以由系统提供一个溢出桶，用指针链接在桶b的后面。如果溢出桶也装满了，那么用类似的方法在其后面再链接一个溢出桶。这种方法称为溢出链方法。图6.30是这个方法的示意图。 桶0 桶1 桶2 桶3 桶1的 溢出桶链 图6.30 散列结构 的溢出链

66 6.4.1 散列机制（7） （2） 开放式散列法（open hashing）
散列机制（7） （2） 开放式散列法（open hashing） 这个方法是把桶的集合固定下来，也就是只考虑基本桶，不考虑溢出桶。如果有一个桶b装满了记录，那么就在桶集中挑选一个有空闲空间的桶，装入新记录。就桶的选择方法的不同，可分为下面两种： ●线性探查法：在桶b的下面（以循环的次序）顺序选择一个有空闲空间的桶，把新记录装进去。 ●再散列探查法：采用二次散列方法，跳跃式地选择一个有空闲空间的桶，装入新记录。

67 散列机制（8） 上面开放式散列法一般使用在编译或汇编中构造符号表的情况。由于开放式散列法的删除操作比较复杂，因此数据库系统中使用封闭散列法。 散列方法的缺点是在系统实现时必须选择恰当的散列函数，并且不像索引结构那样随着数据量的变化容易变动。 标志散列组织装满程度的因子α称为“装填因子”或“负载因子”。α等于存储记录的空间量与给定的存储空间量的商。一般α取0.6 ~ 0.8。 如果α＞0.8，容易产生桶溢出； 如果α＜0.6，表示空间浪费太多。

68 散列索引（1） 散列方法不仅可以用在文件组织上，也可以用在索引结构的创建上。“散列索引”是把查找键值与指针一起组合成散列文件结构的一种索引。 散列索引的构造方法如下：首先为主文件中每个查找键值建立一个索引记录；然后把这些索引记录组织成散列结构（称为“散列索引”），而不是稠密或稀疏索引结构。 例6.4 对图6.10的数据建立一个散列索引。 查找键为ENO（工号），对每个查找键值建立一个索引记录。散列函数可以这样构造：对工号中的数字部分，求出其和，然后除以7（即桶数为7），得到余数作为索引的桶地址。这样，散列索引有7个桶。假设每个桶可放2个索引记录，如果超过2个，就要链接溢出桶。对图6.10的数据建立的散列索引如图6.31所示。

69 散列索引（2） 在这个例子中，ENO是一个候选键，每个ENO值只与一个主记录联系。一般，查找键值可以与多个主记录相联系，那么散列索引中的指针或者指向一个主记录，在主文件中再沿着指针链找到其它相应记录；或者指向一个桶，桶内存放指向主记录的指针。这些技术都是辅助索引中使用过的。 “散列索引”这个术语是指散列文件结构，也可以指辅助散列索引。 严格地讲，散列索引是一种辅助索引结构，不属于主索引结构。但是由于散列文件组织提供由索引直接找主记录的方法，因此我们可以认为散列文件组织提供了一个虚拟的主散列索引。

70 6.4.2 散列索引（3） 图6.31 在查找键ENO上的散列索引 HE F-257 800 LIU A-102 600 B-215
散列索引（3） HE F-257 800 LIU A-102 600 B-215 C-333 400 LOU B-428 850 WEN B-306 700 ZHANG A-214 B-467 ZHOU C-343 750 F-257 B-428 桶0 A-214 B-215 桶1 C-333 B-306 桶2 A-102 B-467 桶3 桶5 桶6 桶4 C-343 图6.31 在查找键ENO上的散列索引

71 散列索引中的问题 前面提到的散列技术属于静态散列，也就是在散列函数确定以后，所有的桶地址及桶空间都确定了。为了适应DB的快速增长，在使用静态散列技术时，有三种选择方案供用户使用。 ●（1）在当前文件规模的基础上选择一个散列函数。这种选择在文件急剧增长时，散列结构的维护、改组和查询的代价越来越大。 ●（2）在文件预计达到的规模基础上选择散列函数。这种方案虽然适应了未来的需要，但在初始一段时期内，空间的利用率非常低。 ●（3）随着数据量的增长，周期性地选择新的散列函数，重新组织散列文件。但重新组织的代价巨大。 为了克服静态索引的缺陷，在实际中往往使用动态散列技术，即桶空间可随时申请或释放，而维护的代价又不大。下面介绍动态散列中的一种技术——可扩充散列结构。

72 可扩充散列结构（1） 在静态散列文件中有一种扩充方法称为“成倍扩充法”。这种方法在需要时，把桶数扩大一倍，从原来m个桶扩大为2m个桶，而桶内的记录减少为原来的一半。但在数据量很大时，再扩大一倍，空间代价太大，利用率也低。 可扩充散列结构实际上是对成倍扩充法的改进，能从容地应付数据库经常性的增长或收缩，即桶的分裂或合并。空间利用率高，重新组织时，每次只是一个桶的增加或减少。 1．可扩充散列结构的组织方法 首先选择一个均匀性和随机性都比较好的散列函数h。并且这个散列函数产生的函数值（简称“散列值”）较大，是一个由b个二进制位组成的整数。如果b = 32，那么就有232（约4×109）个散列值，可以对应232个桶。但是每个散列值并不立即对应一个桶空间，而是根据实际需要申请或释放。

73 可扩充散列结构（2） 在初始时，不是根据全部b位值得出桶地址，而是根据这个b位的前i位(高位)(0≤i≤b)得出桶地址值。在数据增长过程中，取的位数i也随之增加。这i位组成的值是一个桶号。所有的桶地址放在一张“桶地址表”中，桶地址的位置就是桶号。 图6.32是可扩充散列结构的示意图。在桶地址表上方出现的i表示当前情况是取散列值的前i位作为桶地址的位置。在桶地址表中，有时可能某几个相邻的项中的指针指向同一个桶。每个桶的上方出现的整数i0、i1、i2……表示这些桶是沿着散列值的前i0、i1、i2……位作为桶地址表中的地址寻找来的。桶地址表和桶的上方出现的i、i0、i1、i2……这些值称为“散列前缀”。它们间的关系有ij≤i，这里ij是第j个桶的散列前缀。指向第j个桶的指针数目是2（i-ij）。

74 6.4.4 可扩充散列结构（3） 图6.32 可扩充散列结构 i i0 桶0，桶1 i1 i2 桶2 桶3 桶2 散列前缀 …00 …01
可扩充散列结构（3） i …00 …01 …10 …11 i0 散列前缀 桶0，桶1 i1 i2 桶2 桶3 桶地址表 桶2 图6.32 可扩充散列结构

75 6.4.4 可扩充散列结构（4） 2．可扩充散列结构的操作 主要有查找、插入、删除三类操作。 （1） 查找操作
可扩充散列结构（4） 2．可扩充散列结构的操作 主要有查找、插入、删除三类操作。 （1） 查找操作 设散列函数为h（K）。若查找键值为K1，桶地址表的散列前缀为i，那么首先求出h（K1）的前i位值m，然后沿着桶地址表位置m处的指针到达某一个桶中去找记录。 （2） 插入操作 要插入一个查找键值为K1的记录，首先要用查找操作找到应插入的桶，譬如第j个桶。如果桶内有空闲空间，直接插入即可。如果桶已装满记录，那么必须分裂桶，重新分布记录，并插入新记录。分裂桶的过程分成两种情况考虑：

76 可扩充散列结构（5） 第一种情况是：i = ij。也就是指向第j个桶的指针只有一个。这时应在桶地址表中增加项数，以保证第j个桶分裂后，在桶地址表中有位置存放指向新桶的指针。用增加散列前缀的方法，也就是i的值增1，譬如原来i为4，对应“桶地址表”中的16项，若i增为5，则对应“桶地址表”中的32项。也就是每一项分裂成相邻的两项，此时桶地址采用了成倍扩充法、但存储数据的桶空间还没有扩大。桶地址表的空间要比存储数据的桶空间小得多。 此时指向第j个桶的指针就有两个。再申请一个桶空间（第z个桶），置第二个指针值为指向桶z，在置第j和第z个桶的散列前缀均为新的i值。接着，把原来第j个桶中的记录根据散列值的前i位（已增1了）重新分配是仍留在第j个桶还是移到第z个桶。再把新记录插入到第j或第z个桶。

77 可扩充散列结构（6） 如果分裂以后，原来第j个桶的记录仍全部留下，而新记录还要插入到该桶，那么只能用上法把桶地址表再次扩大。但这种可能性极小。一般，单记录的插入不太可能造成桶地址表扩大两次。 第二种情况是：i＞ij。此时指向第j个桶的指针至少两个或两个以上，那么桶地址表不必扩大。只要分裂第j个桶即可。申请一个桶空间（桶z）。对ij的值增1，置第j个桶的指针和第z个桶的散列前缀都为新的ij值。然后在桶地址表中原来指向第j个桶的指针中分出后一半指针，填上桶z的地址，而前一半指针仍指向桶j。再把第j个桶中的记录按散列前缀确定的位数所表示的值重新分布的桶j或桶z中。再把新记录插入到桶j或桶z中。 在这两种情况下重新分布记录，只是对第j个桶的操作，而与其它桶无关。

78 可扩充散列结构（7） （3） 删除操作 要删除查找键值为K1的记录，首先也是先用查找方法，把记录找到，然后把记录从所在的桶内删除。如果删除后，桶为空，那么这个桶也要被删除，也就是桶的合并操作。有时很可能会引起桶地址表的收缩（成倍地收缩）。

79 可扩充散列结构（8） 例6.5 对图6.33的文件EMPLOYEE的数据，重建一个动态散列文件结构。设查找键为ENAME，有一个散列函数把查找键值转换成的32位散列值如图6.34所示。初始时，文件为空，如图6.35所示。下面把图6.33的记录一个个插入到可扩充散列文件中去。为示意，假设每个桶里只能放两个记录。 ENAME ENO SALARY h（ENAME） HE F-257 800 …… LIU A-102 600 …… B-215 LOU …… C-333 400 WEN …… B-428 850 ZHANG …… B-306 700 ZHOU …… A-214 B-467 C-343 750 图6.34 ENAME的散列值 （32位，图中只列出高位部分） 图6.33 EMPLOYEE文件的数据

80 6.4.4 可扩充散列结构（9） 图6.35 初始的可扩充散列结构 图6.36 插入3个记录后的散列结构 散列前缀 桶地址表 桶0 1 HE
可扩充散列结构（9） 散列前缀 桶地址表 桶0 图6.35 初始的可扩充散列结构 1 HE F-257 800 桶0 LIU A-102 600 B-215 桶1 图6.36 插入3个记录后的散列结构

81 6.4.4 可扩充散列结构（10） 图6.37 插入4个记录 后的散列结构 图6.38 插入8个记录后的散列结构 1 HE F-257
可扩充散列结构（10） 1 HE F-257 800 桶0 LIU C-333 400 溢出桶 A-102 600 B-215 桶1 图6.37 插入4个记录 后的散列结构 图6.38 插入8个记录后的散列结构 1 HE F-257 800 WEN B-306 700 桶0，桶1 2 LIU C-333 400 A-102 600 B-215 桶2 LOU B-428 850 ZHANG A-214 桶3 B-467 3

82 6.4.4 可扩充散列结构（11） 图6.39 EMPLOYEE文件的可扩充散列结构 1 HE F-257 800 WEN B-306
可扩充散列结构（11） 1 HE F-257 800 WEN B-306 700 桶0,桶1,桶2,桶3 2 LIU C-333 400 A-102 600 B-215 桶4，桶5 3 LOU B-428 850 ZHOU C-343 750 桶6 4 5 6 7 ZHANG A-214 B-467 桶7 图6.39 EMPLOYEE文件的可扩充散列结构

83 6.4.4 可扩充散列结构（12） 与其它索引或散列技术比较，可扩充散列技术有两个显著的优点：
可扩充散列结构（12） 与其它索引或散列技术比较，可扩充散列技术有两个显著的优点： ① 随着文件的数据量增长，仍然保持原有的操作和查询性能。 ② 空间开销达到最小，额外的开销是桶地址表，由于每个散列值只需一个指针，因此桶地址表只占少量空间。另外，存储记录的桶和溢出桶空间都能动态地申请或释放。 可扩充散列技术的缺点是比静态散列多了一个桶地址表。由于桶的编号在桶分裂或合并后不断变化，因此桶地址要存储在桶地址表中，以利查找。但这个间接访问对文件的性能影响较小，系统和用户都能接受。

84 6.5 多键访问 单键查询的问题 网格文件 分区散列技术

85 6.5.1 单键查询的问题（1） 前面几节提到的索引或散列技术只使用一个查找键来组织文件和处理查询。
单键查询的问题（1） 前面几节提到的索引或散列技术只使用一个查找键来组织文件和处理查询。 有时，可利用多个索引处理查询。例如EMPLOYEE文件有两个索引，一个索引的查找键是ENAME，另一个索引的查找键是SALARY。 用户有一个查询：“检索职工LIU工资为600的工作部门编号”，可用下列SQL语句实现： SELECT ENO FROM EMPLOYEE WHERE ENAME=“LIU” AND SALARY=600；

86 6.5.1 单键查询的问题（2） 处理这个查询有三种方法：
单键查询的问题（2） 处理这个查询有三种方法： （1）使用ENAME索引，把LIU的记录全部找到，再检查每个找到的记录的SALARY是否为600。 （2）使用SALARY索引，把SALARY为600的记录全部找到，再检查每个找到的记录的姓名是否为LIU。 （3）使用ENAME索引，求出指向LIU记录的指针集；使用SALARY索引，求出指向600的记录的指针集。然后求出这两个指针集的交集。最后沿着得到的指针把主记录找到。 这三种方法在多索引情况中都能使用，但都有这样一个缺陷。如果LIU的记录很多，工资为600的记录很多，而LIU工资为600的记录很少，那么上述三种方法都要扫描大量的指针，而最后只求出少量的记录。

87 单键查询的问题（3） 有一个改进的方法，把ENAME和SALARY一起作为一个查找键值，建立一个索引。这种索引与前面几节提到的索引技术本质上没有什么区别，只是查找键中属性个数不同而已。但是由多属性构成的有序索引，有一些弱点。例如查询语句 SELECT ENO FROM EMPLOYEE WHERE ENAME＜ˊLIUˊ AND SALARY = 600 对于姓名小于“LIU”的所有职工记录，都要检查其SALARY是否为600。由于这些记录很可能存储在不同的磁盘上，因此需要较多的I／O操作。原因是查询语句中的条件是比较操作，不是等值操作。显然，前面提到的索引技术不适宜于多键查找。下面介绍多键访问时采用的两种技术：网格文件和分区散列。

88 网格文件（1） 图6.40是一个网格文件（grid files）的示意图，查找键是EMPLOYEE文件中的ENAME和SALARY属性。图中二维矩阵称为“网格矩阵”，一维数组称为“线性标尺”（linear scales）。每个网格文件有惟一的网格矩阵，每个查找键有一个线性标尺。 我们设法把查找键值映射到网格矩阵的格子中去。每个格子中有一个指针，指向一个桶，桶内包含查找键值及指向主记录的指针。在图中，只画出某些格的指针。根据空间使用情况，有时多个格中的指针可指向同一个桶。指向同一个桶的那些格用虚框围起来。

89 图6.40 查找键为ENAME和SALARY的网格文件
网格文件（2） 4 TANG 3 NIAN 2 HAO 1 DING Bi Bj 5 6 600 800 1200 1400 1600 2000 ENAME 线性标尺 SALARY 桶 网格矩阵 图6.40 查找键为ENAME和SALARY的网格文件

90 网格文件（3） ENAME标尺中第i项值是网格矩阵中第i行涉及的查找键值中最小的一个。SALARY标尺中情况类似。如果要插入查找键值为（AN，1800）的记录，在ENAME标尺中，比“AN”大的最小项为第1项，那么网格矩阵应取第0行；在SALARY标尺中，比1800大的最小项为第6项，那么取第5列。从而在网格矩阵中选（0，5）格，然后沿着该格的指针到达桶Bj，把查找键值（AN，1800）和指向主记录的指针插入桶Bj。 如果要执行查找条件为： ENAME＜"LIU" AND SALARY = 600 的查找，那么首先使用ENAME标尺可知选取第0、第1、第2行，再使用SALARY标尺可知应选取第1列。可得到只有（0，1），（1，1），（2，1）格满足查找条件。然后沿着格中的指针到达所需的桶，在桶内再根据查找条件沿着指针到达主记录。

91 网格文件（4） 线性标尺的设计必须满足记录的查找键值能均匀地分布在格子中。如果有一个桶A装满了，那么要申请一个桶空间(桶B),然后把桶地址填到网格矩阵适当的位置上。如果原来指向桶A有多个指针，那么置其中一个指针指向桶B，然后再把原来桶A中的登记项重新分布在桶A、桶B中。如果原来指向桶A只有一个指针，那么可设计桶B是桶A的溢出桶，或者改组网格文件。采用网格矩阵扩大、标尺扩大的方法，类似于可扩充散列技术中桶地址表扩大的方法。 还可以把网格文件扩充到多个查找键情况。如果查询中有n个查找键，那么可构造网格矩阵是n维，线性标尺有n个。 网格文件在多键查询时比其它文件的组织减少了处理时间，但是空间开销较大，网格矩阵有时可以非常庞大。如果要经常进行插入、删除操作，那么网格文件的维护代价是很高的。

92 6.5.3 分区散列技术（1） 查找键值 散列值 （S4，C4） 0100 0100 （S3，C6） 0011 0110 （S2，C7）
分区散列技术（1） 分区散列技术是对散列技术的扩充，能允许在多个属性上进行索引。分区散列结构允许查找键是单属性或多属性，但是不支持范围查询。 例如对学生成绩关系(SNO, CNO,SCORE)的(SNO,CNO)建立散列结构。散列函数的值由两部分组成。譬如散列值的前四位由SNO产生，后四位由CNO产生。这种散列函数称为分区散列函数，如图6.41所示。 查找键值 散列值 （S4，C4） （S3，C6） （S2，C7） （S3，C15） （S9，C8） （S3，C8） （S4，C8） 图6.41 查找键值 为（SNO，CNO） 的分区散列函数

93 分区散列技术（2） 在图6.41中，查找键值(S3,C6)、(S3,C15)、(S3,C8)的散列值的前四位相同，而(S9,C8)、(S3,C8)、(S4,C8)散列值的后四位相同。若要检索“S3选修C8课程的成绩”，则计算(S3,C8)的散列值为 ，访问散列结构即可。若要检索“S3选修的课程”，则计算S3的散列值为0011，再访问散列结构，得知前四位为0011的完整散列值为 ， ， ，然后到与这三个散列值对应的桶中去查找。 分区散列技术类似于网格文件技术，但有两点不同： （1）分区散列是对查找键值进行分割，而不是范围分割。 （2）分区散列结构不是目录，散列值直接给出桶地址，而网格文件中网格矩阵是一个目录结构。

94 6.6 小结（1） 在磁盘中，数据库以文件形式组织。文件组织有两种方法：一种是把记录设计成定长格式，也就是每个文件只存储某一确定长度的记录；另一种是变长格式，使之能存放不同长度的记录。实现变长记录的技术有多种，包括分槽式页结构、指针方法和保留空间等方法。 文件结构有堆文件、顺序文件、散列文件和聚集文件等四种。 为了提高查找速度，可以为文件建立索引或散列机制。 索引有主索引和辅助索引两种。主索引有稠密索引、稀疏索引和多级索引等形式。主索引的顺序决定了文件的排列顺序。其余索引称为辅助索引。辅助索引可以提高对非主索引的查找键进行查询的效率，但是，他们通常会增加数据库修改的开销。

95 6.6 小结（2） 索引顺序文件组织的主要缺陷是随着文件的增大，性能会下降。为了克服这个缺陷，可以使用B+树索引。B+树索引是平衡树，即从树根到树叶所有路径长度相等。这种查找是简单有效的，但插入和删除比较复杂。B树索引和B+树索引类似。B树的主要优点在于它去除了查找键值存储中的冗余；主要缺陷在于整体的复杂性以及结点大小给定时减少了扇出。实际应用中，人们几乎总是更愿意使用B+树索引。 基于散列的文件允许通过散列函数直接得到记录所在的桶地址。静态散列所用的桶地址集合是固定的，不容易适应DB数据量的快速增长。可扩充散列结构是一种允许修改散列函数的动态散列技术，在DB增加或缩减时它可以通过分裂或合并桶来适应DB大小的变化。 也可以用散列法创建辅助索引，这样的索引称为散列索引。 网格文件和分区散列等索引技术可以处理一般的有多个属性的索引。