第6章 DB的存储结构1第6章 数据库的存储结构v6.1 文件组织v6.2 文件结构v6.3 索引技术v6.4 散列技术v6.5 多键访问v6.6 小结2前 言v前面几章，主要强调数据库的逻辑结构在关系模 型中，我们把数据库看成关系的汇集数据库系统 的一个目标是使用户能简单、方便、容易地存取数 据库中的数据用户访问数据库，不必关心数据库 的存储结构和具体的实现方式但是，用户如能了 解数据库的存储结构，那么对于数据库就会有一个 比较完整的了解，拓宽知识面v本章先介绍文件组织形式，然后介绍以及常用的索 引组织和散列组织36.1 文件组织v6.1.1 定长记录v6.1.2 变长记录v在外存中，数据库以文件形式组织，而文件由记 录组成文件结构由操作系统的文件系统提供和管 理那么逻辑文件中的记录在物理文件中将如何实 现这是本节所讨论的问题v一般，文件组织有两种方式，一种是把记录设计 成定长格式，另一种是变长格式，下面分别讨论4v为关系模式EMP（ENAME，ENO，SALARY）可 以设计一个文件，记录格式如下： TYPE EMP_TYPE = RECORD ENAME：CHAR(10)； ENO：CHAR(10)； SALARY：REAL；ENDv假设一个实数占8个字节，那么每个记录占28个字节 。
可以像图6.1那样把记录依次组织起来一个职工 可以为几个部门工作，因此可以有几个工号6.1.1 定长记录（1）56.1.1 定长记录（2）v在系统运行时，有两个 问题需考虑：●如果要删除一个记录，那 么必须在被删位置上填补 一个记录，或者设法使文 件忽略该位置●除非每块的大小恰好是28 的倍数，否则可能有的记 录横跨两个块读 / 写这 样的记录就要访问两个块 记录记录 0LIUA-102 600 记录记录 1WENB-306 700 记录记录 2HEF-257 800 记录记录 3 ZHANG A-214 600 记录记录 4 ZHOUC-343 750 记录记录 5LIUB-215 800 记录记录 6LOUB-428 850 记录记录 7 ZHANG B-467 600 记录记录 8LIUC-333 400图6.1 定长记录的文件66.1.1 定长记录（3）v1．删除操作时的考虑v删除一个记录，可采用下面 三种方法之一实现：v（1） 把被删记录后的记录 一次移上来v例如在图6.1中，要删除记 录2，那么要把记录3～8依次 移上来，如图6.2所示这时 删除一个记录平均要移动文件 中的一半记录。
记录记录 0LIUA-102 600记录记录 1 WENB-306 700记录记录 3ZHANGA-214 600记录记录 4 ZHOU C-343 750记录记录 5LIUB-215 800记录记录 6LOUB-428 850记录记录 7ZHANG B-467 600记录记录 8LIUC-333 400图6.2 把被删记录后的 记录依次移上来 76.1.1 定长记录（4）v（2） 把文件中最后一 个记录填补到被删记录位 置，如图6.3所示v这两种方法都要移动结 点，操作不灵活由于数 据库中删除操作总是少于 插入操作，因此我们可以 采用下面方式实现记录记录 0LIUA-102 600 记录记录 1WENB-306 700 记录记录 8LIUC-333 400 记录记录 3 ZHANG A-214 600 记录记录 4 ZHOU C-343 750 记录记录 5LIUB-215 800 记录记录 6LOUB-428 850 记录记录 7 ZHANG B-467 600图6.3 把最后一个记录 填补到被删记录位置8v（3） 把被删结点用指针 链接起来v在每个记录中增加一个指 针，在文件中增设一个文 件首部。
文件如图6.4所示 v这种方式较好但要注意 ，是否还有指针指向被删 记录在DB中，被指针指 向的记录称为“被拴记录” 如果不小心把被拴记录 删掉，那么指向该记录的 指针成了“悬挂指针”悬 挂指针指向的空间称为“垃 圾”，即该空间别人无法使 用而又被空闲着6.1.1 定长记录（5）文件 首部 记录记录 0LIUA-102 600 记录记录 1 记录记录 2HEF-257 800 记录记录 3 ZHANG A-214 600 记录记录 4 记录记录 5LIUB-215 800 记录记录 6 记录记录 7 ZHANG B-467 600 记录记录 8LIUC-333 400图6.4 删除记录1、4、6 后的文件结构9v2．插入操作时的考虑v如果采用把被删记录链接起来的方法，那么插入操 作可采用下列方法：v在空闲记录链表的第一个空闲记录中，填上插入记 录的值，同时使首部指针指向下一个空闲记录；如 果空闲记录链表为空，那么只能把新记录插到文件 尾v定长记录文件的插入操作比较简单，因为插入记录 的长度与被删记录的长度是相等的在变长记录文 件中操作就复杂了6.1.1 定长记录（6）10v在DBS中，有时需要文件中的记录是变长格式。
v例如，一个文件存储了多种不同的记录类型记录；文件中允 许记录类型的记录是变长的；允许记录中某个字段可以出现 重复组等等v例如图6.1的文件也可以设计成变长记录格式： TYPE EMP_LIST=RECORDENAME：CHAR（10）；ENO_INFO：ARRAY[1∞] OF RECORDENO：CHAR（10）；SALARY：REAL； ENDENDv此处定义（ENO，SALARY）作为成分元素组成一个数组， 成分具体个数视实际情况而定6.1.2 变长记录（1）116.1.2 变长记录（2）v变长记录的表示有字节串形式和定长形式两种v1．变长记录的字节串表示形式 这种形式是把每个记录看成连续的字节串，然 后在每个记录的尾部附加“记录尾标识符”（⊥）图6.1的定 长记录文件可以用图6.5的格式表示0LIUA-102 600 B-215 800 C-333 400⊥ 1WEN B-306 700⊥ 2HEF-257 800⊥ 3 ZHANGA-214 600 B-467 600⊥ 4ZHOU C-343 750⊥ 5LOUB-428 850⊥ 图6.5 变长记录的字节串表示形式12v字节串表现形式的另一种方式是在记录的开始加一个记录长 度的字段来实现，而不是使用在记录尾加标志符的方法。
v字节串表示形式有两个缺点：v（1） 由于各记录的长度不一，因此被删记录的位置难以重 新使用既使制订许多技术规则，仍然会导致磁盘中出现大 量小的空间（即“碎片”）浪费了v（2） 如果文件中的记录要伸长，很难实现必须要把记录 移到他处才能伸长如果要伸长的记录是“被拴记录”，那么 移动的代价是很大的v由于上述两个缺点，现在一般不使用字节串表现形式在实 际中，往往使用的是一种改进的字节串表现形式，称为“分槽 式页结构”（slotted – page structure），如图6.6所示6.1.2 变长记录（3）13v在每块的开始处设置一个“块首部”，其中包括下列信息： ① 块中记录数目 ② 指向块中自由空间尾部的指针 ③ 登记每个记录的开始位置和大小的信息6.1.2 变长记录（4）块块首部 记录记录 大小 记录记录 数目自由空间间…… 记录记录 位置自由空间尾部图6.6 分槽式页结构14v在块中实际记录紧连着，并靠近块尾部存放块中 自由空间也紧连着，在块的中间插入总是从自由 空间尾部开始，并在块首部登录其插入记录的开始 位置和大小v记录删除时只要在块首部该记录的大小登记处改为- 1即可。
更进一步，可以把被删记录左边的记录移过 来填补，使实际记录仍然紧连着当然此时块首部 记录的信息也要修改记录的伸缩也可使用这样的 方法在块中移动记录的代价也不太高，这是因为 一块的大小最多只有4KBv在分槽式页结构中，要求其它指针不能直接指向记 录本身，而是指向块首部中的记录信息登记项，这 样块中记录的移动就独立与外界因素了6.1.2 变长记录（5）15v2．变长记录的定长表示形式 在文件系统中往往是使用一个或多个定长记录 来表示变长记录的方法具体实现时有两种技术： 预留空间和指针技术v（1） 预留空间的方法 取所有变长记录中最长的一个记录的长度作为 存储空间的记录长度，来存储变长记录如果变长 记录短于存储记录长度，那么在多余空间处填上某 个特定的空值或记录尾标志符例如图6.5的字节串 表现形式可以用图6.7的预留空间方法实现这方法 一般使用在大多数记录的长度接近最大长度时才使 用，否则使用时空间浪费很大6.1.2 变长记录（6）166.1.2 变长记录（7）图6.7 变长记录的预留空间 表示形式0LIU A-102 600 B-215 800 C-333 400 1WEN B-306 700⊥⊥⊥⊥ 2HEF-257 800⊥⊥⊥⊥ 3 ZHANGA-214 600 B-467 600⊥⊥ 4 ZHOU C-343 750⊥⊥⊥⊥ 5LOU B-428 850⊥⊥⊥⊥•（2） 指针形式•如果记录的长度相差很大，那么可用指针形式实现变长记录 的定长表示形式。
在每个记录后加一个指针字段，图6.5的文 件可以用图6.8来表示•使用改进的指针形式，在一个文件中使用两种块，固定块和 溢出块图6.9表示文件的固定块和溢出块结构17图6.8 变长记录的指针表示方式6.1.2 变长记录（8）图6.9 固定块和溢出块的结构固 定 块块0LIUA-102 600 1WENB-306 700 2HEF-257 800 3 ZHANG A-214 600 4 ZHOU C-343 750 5B-215 800 6LOUB-428 850 7B-467 600 8C-333 400溢 出 块块LIU A-102 600 WEN B-306 700 HEF-257 800 ZHANG A-214 600 ZHOU C-343 750 LOU B-428 850B-215 800 C-333 400 B-467 600186.2 文件结构 v6.2.1 四种文件结构v6.2.2 顺序文件v6.2.3 聚集文件19v文件结构主要有下列四种形式：v（1）堆文件（heap file） 记录可以放在文件的任何位置上一般，以输入顺序为 序记录的存储顺序与关键码没有直接的联系。
删除操作只 是加个删除标志，新插入记录总是在文件尾v（2）顺序文件（sequential file） 记录是按查找键值升序或降序的顺序存储的v（3）散列文件（hashing file） 据记录的某个属性值通过散列函数求得的值作为记录的 存储地址（即“块号”）这个技术通常与索引技术连用v（4）聚集文件（clustering file） 一个文件可以存储多个关系的记录不同关系中有联系 的记录存储在同一块内，可以提高查找速度和I / O速度v本节介绍顺序文件和聚集文件，散列文件在6.4节中介绍6.2.1 四种文件结构20v根据查找键的值的顺序存储 记录的文件称为顺序文件在 文件中，每个记录增加一个指 针字段，根据查找键值的大小 用指针把记录链接起来v文件初始建立时，存储记录 尽可能使物理顺序和查找键值 的顺序一致v图6.10是顺序文件的例子， 记录按ENAME值升序排列 顺序文件可以很方便地按查找 键的值的大小顺序读出所有的 记录6.2.2 顺序文件（1）HEF-257 800 LIU A-102 600 LIU B-215 800 LIU C-333 400 LOU B-428 850 WEN B-306 700 ZHANGA-214 600 ZHANGB-467 600 ZHOU C-343 750 图6.10 顺序文件21v删除操作可以通过修改指针 实现，被删记录链接成一个自 由空间，以便插入时使用。