第6章DB的存储结构(2008)

1、1第第6章章 DB的存储结构的存储结构2第第6章章 数据库的存储结构数据库的存储结构v6.1 文件组织文件组织v6.2 文件结构文件结构v6.3 索引技术索引技术v6.4 散列技术散列技术v6.5 多键访问多键访问v6.6 小结小结3前前 言言v前面几章，主要强调数据库的逻辑结构。在关系模前面几章，主要强调数据库的逻辑结构。在关系模型中，我们把数据库看成关系的汇集。数据库系统型中，我们把数据库看成关系的汇集。数据库系统的一个目标是使用户能简单、方便、容易地存取数的一个目标是使用户能简单、方便、容易地存取数据库中的数据。用户访问数据库，不必关心数据库据库中的数据。用户访问数据库，不必关心数据库的

2、存储结构和具体的实现方式。但是，用户如能了的存储结构和具体的实现方式。但是，用户如能了解数据库的存储结构，那么对于数据库就会有一个解数据库的存储结构，那么对于数据库就会有一个比较完整的了解，拓宽知识面。比较完整的了解，拓宽知识面。v本章先介绍文件组织形式，然后介绍以及常用的索本章先介绍文件组织形式，然后介绍以及常用的索引组织和散列组织。引组织和散列组织。46.1 文件组织文件组织v6.1.1 定长记录定长记录v6.1.2 变长记录变长记录v在外存中，数据库以文件形式组织，而文件由记在外存中，数据库以文件形式组织，而文件由记录组成。文件结构由操作系统的文件系统提供和管录组成。文件结构由操作系统的

3、文件系统提供和管理。那么逻辑文件中的记录在物理文件中将如何实理。那么逻辑文件中的记录在物理文件中将如何实现。这是本节所讨论的问题。现。这是本节所讨论的问题。v一般，文件组织有两种方式，一种是把记录设计一般，文件组织有两种方式，一种是把记录设计成定长格式，另一种是变长格式，下面分别讨论。成定长格式，另一种是变长格式，下面分别讨论。5v为关系模式为关系模式EMP（ENAME，ENO，SALARY）可）可以设计一个文件，记录格式如下：以设计一个文件，记录格式如下：TYPE EMP_TYPE = RECORDENAME：CHAR(10)；ENO：CHAR(10)；SALARY：REAL； ENDv假设

4、一个实数占假设一个实数占8个字节，那么每个记录占个字节，那么每个记录占28个字个字节。可以像图节。可以像图6.1那样把记录依次组织起来。一个职那样把记录依次组织起来。一个职工可以为几个部门工作，因此可以有几个工号。工可以为几个部门工作，因此可以有几个工号。6.1.1 定长记录（定长记录（1）66.1.1 定长记录（定长记录（2）v在系统运行时，有两个问在系统运行时，有两个问题需考虑：题需考虑：如果要删除一个记录，如果要删除一个记录，那么必须在被删位置上填那么必须在被删位置上填补一个记录，或者设法使补一个记录，或者设法使文件忽略该位置。文件忽略该位置。除非每块的大小恰好是除非每块的大小恰好是28

5、的倍数，否则可能有的的倍数，否则可能有的记录横跨两个块。读记录横跨两个块。读 / 写写这样的记录就要访问两个这样的记录就要访问两个块。块。记录记录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 定长记录的文件定长记录的文件76.1.1 定长记录（定长记录（3）v1删除操作时的考虑删除操作时的考虑v删除一个记录，可采用下

6、面删除一个记录，可采用下面三种方法之一实现：三种方法之一实现：v（1） 把被删记录后的记录把被删记录后的记录一次移上来一次移上来v例如在图例如在图6.1中，要删除记录中，要删除记录2，那么要把记录，那么要把记录38依次移依次移上来，如图上来，如图6.2所示。这时删所示。这时删除一个记录平均要移动文件除一个记录平均要移动文件中的一半记录。中的一半记录。记录记录0LIUA-102 600记录记录1WENB-306 700记录记录3 ZHANGA-214 600记录记录4 ZHOU C-343 750记录记录5LIUB-215 800记录记录6LOUB-428 850记录记录7 ZHANG B-46

7、7 600记录记录8LIUC-333 400图图6.2 把被删记录后的把被删记录后的记录依次移上来记录依次移上来 86.1.1 定长记录（定长记录（4）v（2） 把文件中最后一把文件中最后一个记录填补到被删记录个记录填补到被删记录位置，如图位置，如图6.3所示。所示。v这两种方法都要移动结这两种方法都要移动结点，操作不灵活。由于点，操作不灵活。由于数据库中删除操作总是数据库中删除操作总是少于插入操作，因此我少于插入操作，因此我们可以采用下面方式实们可以采用下面方式实现。现。记录记录0LIUA-102 600记录记录1WENB-306 700记录记录8LIUC-333 400记录记录3 ZHAN

8、GA-214 600记录记录4 ZHOU C-343 750记录记录5LIUB-215 800记录记录6LOUB-428 850记录记录7 ZHANG B-467 600图图6.3 把最后一个记录把最后一个记录填补到被删记录位置填补到被删记录位置9v（3） 把被删结点用指针把被删结点用指针链接起来链接起来v在每个记录中增加一个指在每个记录中增加一个指针，在文件中增设一个文针，在文件中增设一个文件首部。文件如图件首部。文件如图6.4所示。所示。v这种方式较好。但要注意，这种方式较好。但要注意，是否还有指针指向被删记是否还有指针指向被删记录。在录。在DB中，被指针指向中，被指针指向的记录称为的记录

9、称为“被拴记录被拴记录”。如果不小心把被拴记录删如果不小心把被拴记录删掉，那么指向该记录的指掉，那么指向该记录的指针成了针成了“悬挂指针悬挂指针”。悬。悬挂指针指向的空间称为挂指针指向的空间称为“垃圾垃圾”，即该空间别人，即该空间别人无法使用而又被空闲着。无法使用而又被空闲着。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 删除记录删

10、除记录1、4、6后的文件结构后的文件结构10v2插入操作时的考虑插入操作时的考虑v如果采用把被删记录链接起来的方法，那么插入操如果采用把被删记录链接起来的方法，那么插入操作可采用下列方法：作可采用下列方法：v在空闲记录链表的第一个空闲记录中，填上插入记在空闲记录链表的第一个空闲记录中，填上插入记录的值，同时使首部指针指向下一个空闲记录；如录的值，同时使首部指针指向下一个空闲记录；如果空闲记录链表为空，那么只能把新记录插到文件果空闲记录链表为空，那么只能把新记录插到文件尾。尾。v定长记录文件的插入操作比较简单，因为插入记录定长记录文件的插入操作比较简单，因为插入记录的长度与被删记录的长度是相等的

11、。在变长记录文的长度与被删记录的长度是相等的。在变长记录文件中操作就复杂了。件中操作就复杂了。6.1.1 定长记录（定长记录（6）11v在在DBS中，有时需要文件中的记录是变长格式。中，有时需要文件中的记录是变长格式。v例如，一个文件存储了多种不同的记录类型记录；文件中允例如，一个文件存储了多种不同的记录类型记录；文件中允许记录类型的记录是变长的；允许记录中某个字段可以出现许记录类型的记录是变长的；允许记录中某个字段可以出现重复组等等。重复组等等。v例如图例如图6.1的文件也可以设计成变长记录格式：的文件也可以设计成变长记录格式：TYPE EMP_LIST=RECORD ENAME：CHAR（

12、10）；）； ENO_INFO：ARRAY1. OFRECORD ENO：CHAR（10）；）； SALARY：REAL；END ENDv此处定义（此处定义（ENO，SALARY）作为成分元素组成一个数组，）作为成分元素组成一个数组，成分具体个数视实际情况而定。成分具体个数视实际情况而定。6.1.2 变长记录（变长记录（1）126.1.2 变长记录（变长记录（2）v变长记录的表示有字节串形式和定长形式两种。变长记录的表示有字节串形式和定长形式两种。v1变长记录的字节串表示形式变长记录的字节串表示形式这种形式是把每个记录看成连续的字节串，然后在每这种形式是把每个记录看成连续的字节串，然后在每个记

13、录的尾部附加个记录的尾部附加“记录尾标识符记录尾标识符”（）。图）。图6.1的定长的定长记录文件可以用图记录文件可以用图6.5的格式表示。的格式表示。0LIUA-102 600 B-215 800 C-333 4001WEN B-306 7002HEF-257 8003 ZHANGA-214 600 B-467 6004ZHOU C-343 7505LOUB-428 850图图6.5 变长记录的字节串表示形式变长记录的字节串表示形式13v字节串表现形式的另一种方式是在记录的开始加一个记录长字节串表现形式的另一种方式是在记录的开始加一个记录长度的字段来实现，而不是使用在记录尾加标志符的方法。度的

14、字段来实现，而不是使用在记录尾加标志符的方法。v字节串表示形式有两个缺点：字节串表示形式有两个缺点：v（1） 由于各记录的长度不一，因此被删记录的位置难以重由于各记录的长度不一，因此被删记录的位置难以重新使用。既使制订许多技术规则，仍然会导致磁盘中出现大新使用。既使制订许多技术规则，仍然会导致磁盘中出现大量小的空间（即量小的空间（即“碎片碎片”）浪费了。）浪费了。v（2） 如果文件中的记录要伸长，很难实现。必须要把记录如果文件中的记录要伸长，很难实现。必须要把记录移到他处才能伸长。如果要伸长的记录是移到他处才能伸长。如果要伸长的记录是“被拴记录被拴记录”，那，那么移动的代价是很大的。么移动的代

15、价是很大的。v由于上述两个缺点，现在一般不使用字节串表现形式。在实由于上述两个缺点，现在一般不使用字节串表现形式。在实际中，往往使用的是一种改进的字节串表现形式，称为际中，往往使用的是一种改进的字节串表现形式，称为“分分槽式页结构槽式页结构”（slotted page structure），如图），如图6.6所示。所示。6.1.2 变长记录（变长记录（3）14v在每块的开始处设置一个在每块的开始处设置一个“块首部块首部”，其中包括下列信息：，其中包括下列信息： 块中记录数目块中记录数目 指向块中自由空间尾部的指针指向块中自由空间尾部的指针 登记每个记录的开始位置和大小的信息登记每个记录的开始位

16、置和大小的信息6.1.2 变长记录（变长记录（4）块首部块首部记录大小记录大小 记录数目记录数目自由空间自由空间记录位置记录位置自由空间尾部自由空间尾部图图6.6 分槽式页结构分槽式页结构15v在块中实际记录紧连着，并靠近块尾部存放。块中在块中实际记录紧连着，并靠近块尾部存放。块中自由空间也紧连着，在块的中间。插入总是从自由自由空间也紧连着，在块的中间。插入总是从自由空间尾部开始，并在块首部登录其插入记录的开始空间尾部开始，并在块首部登录其插入记录的开始位置和大小。位置和大小。v记录删除时只要在块首部该记录的大小登记处改为记录删除时只要在块首部该记录的大小登记处改为-1即可。更进一步，可以把被

17、删记录左边的记录移即可。更进一步，可以把被删记录左边的记录移过来填补，使实际记录仍然紧连着。当然此时块首过来填补，使实际记录仍然紧连着。当然此时块首部记录的信息也要修改。记录的伸缩也可使用这样部记录的信息也要修改。记录的伸缩也可使用这样的方法。在块中移动记录的代价也不太高，这是因的方法。在块中移动记录的代价也不太高，这是因为一块的大小最多只有为一块的大小最多只有4KB。v在分槽式页结构中，要求其它指针不能直接指向记在分槽式页结构中，要求其它指针不能直接指向记录本身，而是指向块首部中的记录信息登记项，这录本身，而是指向块首部中的记录信息登记项，这样块中记录的移动就独立与外界因素了。样块中记录的移

18、动就独立与外界因素了。6.1.2 变长记录（变长记录（5）16v2变长记录的定长表示形式变长记录的定长表示形式在文件系统中往往是使用一个或多个定长记录在文件系统中往往是使用一个或多个定长记录来表示变长记录的方法。具体实现时有两种技术：来表示变长记录的方法。具体实现时有两种技术：预留空间和指针技术。预留空间和指针技术。v（1） 预留空间的方法预留空间的方法取所有变长记录中最长的一个记录的长度作为取所有变长记录中最长的一个记录的长度作为存储空间的记录长度，来存储变长记录。如果变长存储空间的记录长度，来存储变长记录。如果变长记录短于存储记录长度，那么在多余空间处填上某记录短于存储记录长度，那么在多余

19、空间处填上某个特定的空值或记录尾标志符。例如图个特定的空值或记录尾标志符。例如图6.5的字节串的字节串表现形式可以用图表现形式可以用图6.7的预留空间方法实现。这方法的预留空间方法实现。这方法一般使用在大多数记录的长度接近最大长度时才使一般使用在大多数记录的长度接近最大长度时才使用，否则使用时空间浪费很大。用，否则使用时空间浪费很大。6.1.2 变长记录（变长记录（6）176.1.2 变长记录（变长记录（7）图图6.7 变长记录变长记录的预留空间的预留空间表示形式表示形式0 0LIULIU A-102A-102 600600 B-215B-215 800800 C-333C-333 40040

20、01 1WENWEN B-306B-306 7007002 2HEHEF-257F-257 8008003 3 ZHANGZHANGA-214A-214 600600 B-467B-467 6006004 4 ZHOUZHOU C-343C-343 7507505 5LOULOU B-428B-428 850850v（2） 指针形式指针形式v如果记录的长度相差很大，那么可用指针形式实现变长记录如果记录的长度相差很大，那么可用指针形式实现变长记录的定长表示形式。在每个记录后加一个指针字段，图的定长表示形式。在每个记录后加一个指针字段，图6.5的文的文件可以用图件可以用图6.8来表示。来表示。v使

21、用改进的指针形式，在一个文件中使用两种块，固定块和使用改进的指针形式，在一个文件中使用两种块，固定块和溢出块。图溢出块。图6.9表示文件的固定块和溢出块结构。表示文件的固定块和溢出块结构。18图图6.8 变长记录的变长记录的指针表示方式指针表示方式6.1.2 变长记录（变长记录（8）图图6.9 固定块和固定块和溢出块的结构溢出块的结构固固定定块块0LIUA-102 6001WENB-306 7002HEF-257 8003 ZHANGA-214 6004 ZHOU C-343 7505B-215 8006LOUB-428 8507B-467 6008C-333 400溢溢出出块块LIULIU

22、A-102A-102 600600WENWEN B-306B-306 700700HEHEF-257F-257 800800ZHANGZHANGA-214A-214 600600ZHOUZHOU C-343C-343 750750LOULOU B-428B-428 850850B-215B-215 800800C-333C-333 400400B-467B-467 600600196.2 文件结构文件结构 v6.2.1 四种文件结构四种文件结构v6.2.2 顺序文件顺序文件v6.2.3 聚集文件聚集文件20v文件结构主要有下列四种形式：文件结构主要有下列四种形式：v（1）堆文件（）堆文件（he

23、ap file）记录可以放在文件的任何位置上。一般，以输入顺序为记录可以放在文件的任何位置上。一般，以输入顺序为序。记录的存储顺序与关键码没有直接的联系。删除操作只序。记录的存储顺序与关键码没有直接的联系。删除操作只是加个删除标志，新插入记录总是在文件尾。是加个删除标志，新插入记录总是在文件尾。v（2）顺序文件（）顺序文件（sequential file）记录是按查找键值升序或降序的顺序存储的。记录是按查找键值升序或降序的顺序存储的。v（3）散列文件（）散列文件（hashing file）据记录的某个属性值通过散列函数求得的值作为记录的据记录的某个属性值通过散列函数求得的值作为记录的存储地址（

24、即存储地址（即“块号块号”）。这个技术通常与索引技术连用。）。这个技术通常与索引技术连用。v（4）聚集文件（）聚集文件（clustering file）一个文件可以存储多个关系的记录。不同关系中有联系一个文件可以存储多个关系的记录。不同关系中有联系的记录存储在同一块内，可以提高查找速度和的记录存储在同一块内，可以提高查找速度和I / O速度。速度。v本节介绍顺序文件和聚集文件，散列文件在本节介绍顺序文件和聚集文件，散列文件在6.4节中介绍。节中介绍。6.2.1 四种文件结构四种文件结构21v根据查找键的值的顺序存储记根据查找键的值的顺序存储记录的文件称为顺序文件。在文录的文件称为顺序文件。在文

25、件中，每个记录增加一个指针件中，每个记录增加一个指针字段，根据查找键值的大小用字段，根据查找键值的大小用指针把记录链接起来。指针把记录链接起来。v文件初始建立时，存储记录尽文件初始建立时，存储记录尽可能使物理顺序和查找键值的可能使物理顺序和查找键值的顺序一致。顺序一致。v图图6.10是顺序文件的例子，记是顺序文件的例子，记录按录按ENAME值升序排列。顺值升序排列。顺序文件可以很方便地按查找键序文件可以很方便地按查找键的值的大小顺序读出所有的记的值的大小顺序读出所有的记录。录。6.2.2 顺序文件（顺序文件（1）HEHE F-257F-257 800800LIULIU A-102A-102 6

26、00600LIULIU B-215B-215 800800LIULIU C-333C-333 400400LOULOU B-428B-428 850850WENWEN B-306B-306 700700ZHANGZHANGA-214A-214 600600ZHANGZHANGB-467B-467 600600ZHOUZHOU C-343C-343 750750图图6.10 顺序文件顺序文件22v删除操作可以通过修改指针实删除操作可以通过修改指针实现，被删记录链接成一个自由现，被删记录链接成一个自由空间，以便插入时使用。空间，以便插入时使用。v插入操作包括定位和插入两步：插入操作包括定位和插入两

27、步：v（1）定位：在指针链中，找）定位：在指针链中，找到插入的位置，即插入记录应到插入的位置，即插入记录应插在哪个记录的前面。插在哪个记录的前面。v（2）插入：在找到记录的块）插入：在找到记录的块内，如果有空闲记录，那么在内，如果有空闲记录，那么在该位置插入新记录，并加入到该位置插入新记录，并加入到指针链中；如果无空闲记录，指针链中；如果无空闲记录，那么就只能插入到溢出块中。那么就只能插入到溢出块中。v在图在图6.10中，插入一个新记录中，插入一个新记录（MA，B-547，500），就得），就得到图到图6.11。6.2.2 顺序文件（顺序文件（2）HEF-257 800LIUA-102 600

28、LIUB-215 800LIUC-333 400LOUB-428 850WEN B-306 700ZHANGA-214 600ZHANGB-467 600ZHOU C-343 750MAB-547 500图图6.11 插入一个记录插入一个记录后的顺序文件后的顺序文件23v在小型在小型DBS中，数据量小，每个关系处理成一个文件。这种中，数据量小，每个关系处理成一个文件。这种文件称为单记录类型文件，文件中每个记录都是定长的。文文件称为单记录类型文件，文件中每个记录都是定长的。文件之间是分离的，没有联系。件之间是分离的，没有联系。v随着数据量的增大，系统的性能和查询速度日益下降。此时随着数据量的增大

29、，系统的性能和查询速度日益下降。此时应采用新的文件结构，称为应采用新的文件结构，称为“聚集文件聚集文件”。这种变化允许一。这种变化允许一个文件由多个关系的记录组成，即多记录类型文件。聚集文个文件由多个关系的记录组成，即多记录类型文件。聚集文件的管理由件的管理由DBS实现。实现。v例如教学数据库中关系例如教学数据库中关系S（SNO，SNAME，AGE，SEX）和）和SC（SNO，CNO，SCORE），如果将每个关系组织成一个），如果将每个关系组织成一个文件，那么查找学生的成绩，就要做连接操作：文件，那么查找学生的成绩，就要做连接操作：SELECT S.SNO，SNAME，CNO，GRADEFRO

30、M S，SCWHERE S.SNO = SC.SNO；6.2.3 聚集文件（聚集文件（1）24v在图在图6.12中，关系中，关系S和和SC如图（如图（a）、（）、（b）所示，）所示，S和和SC的的元组混合放在一起，如图（元组混合放在一起，如图（c）所示。即使一个学生的成绩）所示。即使一个学生的成绩信息很多，一块访不下，那么也是放在相邻的块内。为了进信息很多，一块访不下，那么也是放在相邻的块内。为了进一步提高查询速度，我们可以在文件中建立以查询学生信息一步提高查询速度，我们可以在文件中建立以查询学生信息为主的链表，在图为主的链表，在图6.12的（的（c）中已表示。）中已表示。6.2.3 聚集文件

31、（聚集文件（2）S1 WANG 20 MS1 C1 80S1 WANG 20 MS2LIU21 FS1 C2 70S1C180S3 CHEN 22 MS3 C1 90S1C270S3 C2 85S2LIU21 FS3 C3 95S3 CHEN 22 MS3C190S3C285S3C395（a）关系）关系S （b）关系）关系SC 图图6.12 聚集文件例子聚集文件例子（c）聚集文件）聚集文件 256.3 索引技术索引技术v6.3.1 索引机制索引机制v6.3.2 有序索引的分类有序索引的分类v6.3.3 主索引主索引v6.3.4 辅助索引辅助索引v6.3.5 B+树索引文件树索引文件v6.3.6

32、 B树索引文件树索引文件26v根据记录中某种排序顺序建立的索引，称为有序索引。根据记录中某种排序顺序建立的索引，称为有序索引。v在索引技术中，用户可根据下面五个方面选择各种实现方法：在索引技术中，用户可根据下面五个方面选择各种实现方法： 存取类型：用户是根据属性值找记录，还是根据属性值的范存取类型：用户是根据属性值找记录，还是根据属性值的范围找记录。围找记录。 存取时间；查找记录所花费的时间。存取时间；查找记录所花费的时间。 插入时间；插入新记录所花费的时间，应包括两部份，找到插入时间；插入新记录所花费的时间，应包括两部份，找到正确的位置插入新记录所花时间和修改索引结构所花时间。正确的位置插入

33、新记录所花时间和修改索引结构所花时间。 删除时间；也应包括两部分，找到被删记录删除所花时间和删除时间；也应包括两部分，找到被删记录删除所花时间和修改索引结构所花时间。修改索引结构所花时间。 索引空间开销。索引空间开销。v在索引中，用于找记录的属性集称为查找键。应注意，查找在索引中，用于找记录的属性集称为查找键。应注意，查找键不一定是主键（候选键、超键），前者的值允许重复，而键不一定是主键（候选键、超键），前者的值允许重复，而后者的值不允许重复。后者的值不允许重复。6.3.1 索引机制索引机制27v索引文件由两个部分组成：索引和主文件。由于主文件记录索引文件由两个部分组成：索引和主文件。由于主文

34、件记录多、数据量大并且占据大量物理块，因此在主文件中查找，多、数据量大并且占据大量物理块，因此在主文件中查找，速度是很慢的。如果对记录建立索引，那么相对主文件而言，速度是很慢的。如果对记录建立索引，那么相对主文件而言，索引空间小，因而查找速度就快。索引空间小，因而查找速度就快。v这里考虑的主文件是指顺序文件，文件按某个属性值大小的这里考虑的主文件是指顺序文件，文件按某个属性值大小的顺序排列。对主文件可以建立几套不同的索引。顺序排列。对主文件可以建立几套不同的索引。v如果索引的查找键值的顺序与主文件的顺序一致，那么这种如果索引的查找键值的顺序与主文件的顺序一致，那么这种索引称为主索引，也称为聚集

35、索引。一般，主索引的查找键索引称为主索引，也称为聚集索引。一般，主索引的查找键往往是文件的主键。往往是文件的主键。v如果查找键的值的顺序与主文件的顺序不一致，那么这种索如果查找键的值的顺序与主文件的顺序不一致，那么这种索引称为辅助索引，或非聚集索引。引称为辅助索引，或非聚集索引。6.3.2 有序索引的分类有序索引的分类28v当索引查找键值的顺序与主文件顺序一致时，这种索引文件当索引查找键值的顺序与主文件顺序一致时，这种索引文件称为称为“索引顺序文件索引顺序文件”。这种文件既适用随机处理，也适用。这种文件既适用随机处理，也适用顺序处理。下面以图顺序处理。下面以图6.10的顺序文件为例介绍主索引以

36、及稠的顺序文件为例介绍主索引以及稠密索引、稀疏索引和多级索引三种实现方法。密索引、稀疏索引和多级索引三种实现方法。v1稠密索引和稀疏索引稠密索引和稀疏索引v对于主索引，可以采用下面两种实现方法：对于主索引，可以采用下面两种实现方法：v（1） 稠密索引（稠密索引（dense index）：对于主文件中每一个查找）：对于主文件中每一个查找键值建立一个索引记录（索引项），索引记录包括查找键值键值建立一个索引记录（索引项），索引记录包括查找键值和指向具有该值的记录链表中第一个记录的指针。这种索引和指向具有该值的记录链表中第一个记录的指针。这种索引称为称为“稠密索引稠密索引”。读者应注意，在有些教材中稠

37、密索引定。读者应注意，在有些教材中稠密索引定义为对主文件中每个记录建立一个索引记录，与我们的提法义为对主文件中每个记录建立一个索引记录，与我们的提法有区别。有区别。v图图6.13是为图是为图6.10的顺序文件建立的稠密索引。的顺序文件建立的稠密索引。6.3.3 主索引（主索引（1）296.3.3 主索引（主索引（2）图图6.13 稠密索引稠密索引HELIULOUWENZHANGZHOUHEF-257 800LIUA-102 600LIUB-215 800LIUC-333 400LOUB-428 850WENB-306 700ZHANG A-214 600ZHANG B-467 600ZHOU

38、C-343 750306.3.3 主索引（主索引（3）v（2） 稀疏索引（稀疏索引（sparse index）：在主文件中，对若干个）：在主文件中，对若干个查找键值才建立一个索引记录，此时索引记录的内容仍和查找键值才建立一个索引记录，此时索引记录的内容仍和稠密索引一样。这种索引称为稠密索引一样。这种索引称为“稀疏索引稀疏索引”。v图图6.14为图为图6.10的顺序文件建立的稀疏索引。的顺序文件建立的稀疏索引。HELOUZHANGHEF-257 800LIUA-102 600LIUB-215 800LIUC-333 400LOUB-428 850WENB-306 700ZHANGA-214 60

39、0ZHANG B-467 600ZHOU C-343 750图图6.14 稀疏索引稀疏索引31v相比之下，在带稠密索引的主文件中，查找速度较快；而带相比之下，在带稠密索引的主文件中，查找速度较快；而带稀疏索引的文件中查找较慢，但稀疏索引的空间较小，因此稀疏索引的文件中查找较慢，但稀疏索引的空间较小，因此插入、删除操作时指针的维护量相对要少些。插入、删除操作时指针的维护量相对要少些。v系统设计者应在存取时间和空间开销方面权衡，选择何种索系统设计者应在存取时间和空间开销方面权衡，选择何种索引。有一个折衷的办法，可把两种索引结合起来。引。有一个折衷的办法，可把两种索引结合起来。v首先为顺序文件的每一

40、块建立一个索引记录，得到一个以块首先为顺序文件的每一块建立一个索引记录，得到一个以块为基本单位的稠密索引，然后再在稠密索引基础上建立一个为基本单位的稠密索引，然后再在稠密索引基础上建立一个稀疏索引。查找时，先在稀疏索引中找到记录所在的范围，稀疏索引。查找时，先在稀疏索引中找到记录所在的范围，然后在稠密索引中确定记录在哪一块，最后在主文件的块中然后在稠密索引中确定记录在哪一块，最后在主文件的块中顺序查找，找到所在的主记录。这种方法实际已是二级索引顺序查找，找到所在的主记录。这种方法实际已是二级索引了。了。6.3.3 主索引（主索引（4）32v2多级索引多级索引v即使采用稀疏索引，可能建成的索引还

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

42、对最外层索引再往外建一层索引。这就形成了多级索引技术。索引技术。6.3.3 主索引（主索引（5）336.3.3 主索引（主索引（6）图图6.15 二级稀疏索引二级稀疏索引外层索引外层索引内层索引内层索引索引块索引块0数据块数据块0索引块索引块1数据块数据块134v3索引的更新：在索引文件中，主记录的插入或删除可能会索引的更新：在索引文件中，主记录的插入或删除可能会引起索引的修改。在只有一级的索引中索引的修改算法如下引起索引的修改。在只有一级的索引中索引的修改算法如下所述。所述。v（1） 删除操作删除操作为了在主文件中删除一个记录，首先要找到被删记录，才为了在主文件中删除一个记录，首先要找到被删

43、记录，才能执行删除操作。能执行删除操作。如果符合查找键值的记录在文件中只有一个，那么被删记如果符合查找键值的记录在文件中只有一个，那么被删记录删除后，肯定要修改索引。录删除后，肯定要修改索引。如果要修改索引，对于稠密索引，要从索引中删除被删记如果要修改索引，对于稠密索引，要从索引中删除被删记录相应的索引记录；对于稀疏索引，如果被删记录的查找键录相应的索引记录；对于稀疏索引，如果被删记录的查找键值在索引块中出现，那么用主文件中被删记录的下一个主记值在索引块中出现，那么用主文件中被删记录的下一个主记录的查找键值录的查找键值A替换，如果替换，如果A已在索引块中出现，那么被删记已在索引块中出现，那么被

44、删记录的相应索引记录应从索引块中删除。录的相应索引记录应从索引块中删除。6.3.3 主索引（主索引（7）35v（2） 插入操作插入操作首先，用插入记录的查找键值找到插入位置。首先，用插入记录的查找键值找到插入位置。 如果是稠密索引并且查找键值在索引块中未出现过，那么如果是稠密索引并且查找键值在索引块中未出现过，那么要把插入记录的查找键值插入到索引块中。要把插入记录的查找键值插入到索引块中。 如果是稀疏索引，每一个数据块对应一个索引记录，那么如果是稀疏索引，每一个数据块对应一个索引记录，那么在数据块能放得下新记录时，不必修改索引。如果要加入新在数据块能放得下新记录时，不必修改索引。如果要加入新的

45、数据块，那么插入记录的查找键值将成为新数据块的第一的数据块，那么插入记录的查找键值将成为新数据块的第一个查找键值，并将在索引块中插入一个新的索引记录。个查找键值，并将在索引块中插入一个新的索引记录。v在多级索引时在多级索引时,可以采取类似的办法。在插入、删除主记录时，可以采取类似的办法。在插入、删除主记录时，最低一级索引的修改方法如上所述。如果第二级索引（外层）最低一级索引的修改方法如上所述。如果第二级索引（外层）要修改，那么把第一级索引（内层）看成顺序文件。在第一要修改，那么把第一级索引（内层）看成顺序文件。在第一级索引中插入或删除一个索引记录时，第二级索引的修改也级索引中插入或删除一个索引

46、记录时，第二级索引的修改也像上面叙述的方法一样。以此类推。像上面叙述的方法一样。以此类推。6.3.3 主索引（主索引（8）36v在主索引中，我们可以方便、快速地根据某个查找键值找记在主索引中，我们可以方便、快速地根据某个查找键值找记录。如果我们要根据另一个查找键值寻找主文件的记录，那录。如果我们要根据另一个查找键值寻找主文件的记录，那么可以用辅助索引方法实现。么可以用辅助索引方法实现。v在主索引中，具有相同查找键值的记录在同一块中或相邻的在主索引中，具有相同查找键值的记录在同一块中或相邻的块中，因而查找速度较快。而在辅助索引中，具有相同查找块中，因而查找速度较快。而在辅助索引中，具有相同查找键

47、值的记录将分散在文件的各处，因而查找速度较慢，并且键值的记录将分散在文件的各处，因而查找速度较慢，并且查找时无法利用主文件中按主索引键值建立的指针链。查找时无法利用主文件中按主索引键值建立的指针链。v辅助索引可采用下面的方法实现：仍然为每个查找键值建立辅助索引可采用下面的方法实现：仍然为每个查找键值建立一个索引记录，内容包括查找键值和一个指针。但这个指针一个索引记录，内容包括查找键值和一个指针。但这个指针不指向主文件中的记录，而是指向一个桶（不指向主文件中的记录，而是指向一个桶（bucket），桶内），桶内存放指向具有同一查找键值的主记录的指针。例如在图存放指向具有同一查找键值的主记录的指针。

48、例如在图6.10的顺序文件中，可以对属性的顺序文件中，可以对属性SALARY建立一个辅助索引，其建立一个辅助索引，其结构如图结构如图6.16所示。所示。6.3.4 辅助索引（辅助索引（1）376.3.4 辅助索引（辅助索引（2）图图6.16 辅助索引例子辅助索引例子400600700750800850HEF-257 800LIUA-102 600LIUB-215 800LIUC-333 400LOUB-428 850WENB-306 700ZHANG A-214 600ZHANG B-467 600ZHOU C-343 75038v在主索引中可以采取顺序查找方法。在辅助索引中，由于同在主索引中

49、可以采取顺序查找方法。在辅助索引中，由于同一个查找键值的记录分散在文件的各处，因此以辅助索引查一个查找键值的记录分散在文件的各处，因此以辅助索引查找键顺序扫描文件是行不通的，每读一个记录几乎都要执行找键顺序扫描文件是行不通的，每读一个记录几乎都要执行读一块到内存的操作。读一块到内存的操作。v辅助索引都是稠密索引，不可能是稀疏索引结构。在主记录辅助索引都是稠密索引，不可能是稀疏索引结构。在主记录插入或删除时，都要修改辅助索引，修改的方法与主索引的插入或删除时，都要修改辅助索引，修改的方法与主索引的方法类似。方法类似。v辅助索引机制曾在辅助索引机制曾在20世纪世纪60年代中期广泛流行，倒排文件系年

50、代中期广泛流行，倒排文件系统就是建立了许多辅助索引的文件系统。辅助索引改善了系统就是建立了许多辅助索引的文件系统。辅助索引改善了系统的查询效率和查询方式，但是也给系统带来很大的负担。统的查询效率和查询方式，但是也给系统带来很大的负担。数据库应用设计者应在查询效率和修改的代价方面作出权衡，数据库应用设计者应在查询效率和修改的代价方面作出权衡，以选择合适的索引结构。以选择合适的索引结构。6.3.4 辅助索引（辅助索引（3）39v1平衡树的概念平衡树的概念v为了改善索引结构的性能，可以采用多级索引，目前广泛流为了改善索引结构的性能，可以采用多级索引，目前广泛流行的一种技术，称为平衡树（行的一种技术，

51、称为平衡树（Balanced tree）技术。数据库）技术。数据库技术中平衡树的形式定义如下所述。技术中平衡树的形式定义如下所述。v定义定义6.1 一棵一棵m阶平衡树或者为空，或者满足以下条件：阶平衡树或者为空，或者满足以下条件： 每个结点至多有每个结点至多有m棵子树；棵子树； 根结点或为叶结点，或至少有两棵子树；根结点或为叶结点，或至少有两棵子树； 每个非叶结点至少有每个非叶结点至少有 m/2 棵子树；棵子树； 从根结点到叶结点的每一条路径都有同样的长度，即从根结点到叶结点的每一条路径都有同样的长度，即 叶结点在同一层次上。叶结点在同一层次上。v平衡树又分为两类：平衡树又分为两类：B+树和树

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

53、织方式v叶结点中的指针（叶结点中的指针（1im-1）指向主文件中的记录。譬如指针）指向主文件中的记录。譬如指针Pi指向查找键值为指向查找键值为Ki的主记录。的主记录。v如果查找键恰好是主文件的主键，那么叶结点中的指针直接如果查找键恰好是主文件的主键，那么叶结点中的指针直接指向主文件中的记录。如果查找键不是主文件的主键，并且指向主文件中的记录。如果查找键不是主文件的主键，并且查找键值的顺序也不是主文件的顺序，那么叶结点中的指针查找键值的顺序也不是主文件的顺序，那么叶结点中的指针指向一个桶，桶中存放指向具有该查找键值的主记录的指针。指向一个桶，桶中存放指向具有该查找键值的主记录的指针。v每个叶结点

54、中至少应有每个叶结点中至少应有 （m-1）/2 个查找键，至多有个查找键，至多有m-1个查找键，并且查找键值不允许重复。如果个查找键，并且查找键值不允许重复。如果B+树索引是稠密树索引是稠密索引，那么每个查找键值必须在某个叶结点中出现。索引，那么每个查找键值必须在某个叶结点中出现。v叶结点中最后一个指针叶结点中最后一个指针Pm，指向下一个叶结点（按查找键值，指向下一个叶结点（按查找键值顺序）。这样可以很方便地在主文件进行顺序访问。顺序）。这样可以很方便地在主文件进行顺序访问。v图图6.18表示表示3阶阶B+树的叶结点结构。树的叶结点结构。6.3.5 B+树索引文件（树索引文件（3）426.3.

55、5 B+树索引文件（树索引文件（4）图图6.18 3阶阶B+树的树的叶结点结构叶结点结构叶结点叶结点HELIUHEF-257800LIUA-102600LIUB-215800LIUC-333400下一个叶结点下一个叶结点主文件主文件v（3） 非叶结点的组织方式非叶结点的组织方式B+树中的非叶结点形成了叶结点上的一个多级稀树中的非叶结点形成了叶结点上的一个多级稀疏索引。每个非叶结点（不包括根结点）中至少有疏索引。每个非叶结点（不包括根结点）中至少有 m/2 个个指针，至多有指针，至多有m个指针。指针的数目称为结点的个指针。指针的数目称为结点的“扇出端数扇出端数”（fanout）。图）。图6.19

56、是一个完整的是一个完整的3阶阶B+树索引。图树索引。图6.20是一个是一个5阶阶B+树索引的例子。树索引的例子。43图图6.19 3阶阶B+树索引树索引6.3.5 B+树索引文件（树索引文件（5）图图6.20 5阶阶B+树索引树索引WENHELIULOUWEN ZHANG ZHOUZHANGLOUWENHELIULOUWENZHANGZHOU44v3B+树的查询树的查询v如果用户要检索查找键值为如果用户要检索查找键值为K的所有记录，那么首先在根结的所有记录，那么首先在根结点中找大于点中找大于K的最小查找键值（设为的最小查找键值（设为Ki），然后沿着），然后沿着Ki左边的左边的指针指针Pi到达第

57、二层的结点。如果根结点中有到达第二层的结点。如果根结点中有n个指针，并且个指针，并且KKn-1，那么就沿着指针，那么就沿着指针Pn到达第二层的结点。在第二层的结到达第二层的结点。在第二层的结点，用类似的方法找到一个指针，进入第三层的结点点，用类似的方法找到一个指针，进入第三层的结点一一直到进入直到进入B+树的叶结点，找到一个指针直接指向主文件的记树的叶结点，找到一个指针直接指向主文件的记录，或指向一个桶（存放指向主文件记录的指针）。最后把录，或指向一个桶（存放指向主文件记录的指针）。最后把所需记录找到。所需记录找到。v如果文件中查找键值有如果文件中查找键值有W个值，那么对于个值，那么对于m阶阶

58、B+树而言，从树而言，从根结点到叶结点的路径长度不超过根结点到叶结点的路径长度不超过 log m/2 （W） 。6.3.5 B+树索引文件（树索引文件（6）45v例例6.2 讨论讨论B+树索引查询中查询次数与文件的存储块数的关系。树索引查询中查询次数与文件的存储块数的关系。如果在如果在B+树索引中，每块存储一个结点，占树索引中，每块存储一个结点，占4096字节。字节。如果查找键的长度为如果查找键的长度为32字节，指针仍为字节，指针仍为8字节，那么每块大约字节，那么每块大约可存储可存储100个查找键值和指针，即个查找键值和指针，即m约为约为100。在在m为为100时，如果文件中查找键有时，如果文

59、件中查找键有100万个值，那么一次万个值，那么一次查找需读索引块的数目为查找需读索引块的数目为 log50（1000000） =4。如果。如果B+树索引的根结点常驻内存，那么查找时只需再读三个索引块即树索引的根结点常驻内存，那么查找时只需再读三个索引块即可。可。 vB+树的结构与内存中普遍使用的二叉排序树的主要区别是结点树的结构与内存中普遍使用的二叉排序树的主要区别是结点的大小以及树的高度。在二叉排序树中，每个结点很小，只有的大小以及树的高度。在二叉排序树中，每个结点很小，只有一个键值和两个指针。而一个键值和两个指针。而B+树中，每个结点很大，可以是磁盘树中，每个结点很大，可以是磁盘上的一个块

60、，包含更多查找键值和指针。二叉排序树显得瘦而上的一个块，包含更多查找键值和指针。二叉排序树显得瘦而高，而高，而B+树显得胖而矮。树显得胖而矮。6.3.5 B+树索引文件（树索引文件（7）46v4B+树的更新树的更新在在B+树索引文件中插入主记录时，有可能叶结点要分裂，树索引文件中插入主记录时，有可能叶结点要分裂，并引起上层结点的分裂和并引起上层结点的分裂和B+树层数的增加。在删除主记录时，树层数的增加。在删除主记录时，这有可能出现相反的现象。下面就是否出现分裂与合并情况这有可能出现相反的现象。下面就是否出现分裂与合并情况分别讨论。分别讨论。v（1）不引起索引结点分裂的插入操作）不引起索引结点分