1、第四章第四章 数据的存储方法数据的存储方法这一章将系统地回答以下一些问题：l怎样在域中表示SQL的数据类型？l怎样用记录来表示元组？l怎样在内存块中表示记录或元组的集合？l怎样存储对象关系型数据？例如对象标识符（或别的指向记录的指针）和大对象（例如2GB的MPEG格式的视频信息）。l当一些域被更新而引起记录长度改变时，应该做什么？同时怎样的结构才能适合变长记录的需要。4.1 4.1 数据元素的表示数据元素的表示用SQL语言的CREATE TABLE定义了一个关系:CREATE TABLE MovieStar（name CHAR（30）PRIMARY KEY，address VARCHAR（25
2、5），gender CHAR（1），birthdate DATE）；从本质上来说，所有的数据类型是一个字节序列。例如，INTEGER一般用两个或四个字节来表示，FLOAT一般用四个或八个字节来表示。整数和实数的具体表示由机器的硬件来确定。数据元素的表示数据元素的表示1.固定长度的字符串定义格式：CHAR（5）存储格式：cat。这里 是用来进行填补的字符。它补全了第四和第五个字符2。可变长度的字符串定义格式：VARCHAR（N）存储格式：1）。正文长度加一。我们为一个字符串分配N+1个字节。2）。使用空白终结符。同样我们为一个字符串分配N+1个字节。在字符串的最后一个字节上填放空白终结符。3。日
3、期和时间类型 一个日期实际上就是有一定格式的固定长度的字符串。所以日期可以用定长的字符串方法来表示。用8个字符表示。如，20:19:02表示下午8点19分2秒4。枚举类型 据需要给每个元素分配一个整型值，用它来表示枚举类型的值如：集合RED，GREEN，BLUE，YELLOW。可以将RED表示成0，GREEN表示成1，BLUE表示成2，YELLOW表示成3。这样它们可用两位来表示：00、01、10和11。而如果我们采用整个字节来表示它们会更方便。例如，YELLOW可被用3来表示，用整个字节为00000011。建立固定长度的记录建立固定长度的记录MovieStar关系的例子。它有四个域：lnam
4、e：具有30个字节的字符串。laddress：用VARCHAR（255）定义。这个域用256个字节来存储。lgender：单字节。它的值一般是F或M。lbirthdate：是日期类型。nameaddressgenderbirthday030286287297MovieStar关系的例子 当元组不是存储在主存，而是存储在外存中时，我们就必须留心它的组织问题。当我们从外存中读取数据块到主存中时，数据块的头地址应被放入4的倍数的主存地址处。最保险的做法是同样要求记录的每个域的头地址是4或8的倍数。应做到以下两点：l每个记录在数据块中的开始地址是4的倍数；l记录中的每个域对于数据块开始地址的偏移量是4
5、的倍数。MovieStar每个域的开始地址都是4的倍数nameaddressgenderbirthday032288292304记录的头信息记录的头信息 当我们设计记录格式时，需要考虑怎样存储那些不属于记录值而又必须被保存的信息。例如下面这些信息：l记录的视图，更具体的说，在记录中保存一个指向DBMS存储记录类型的指针；l记录的长度；l表示记录最后一次被读或写的标记。因此在记录的格式中，需考虑用一些字节来存储记录附加的信息。对例4.6中的结构进行修改，加进12个字节的头信息。开始4个字节用来表示记录类型。它实际上是指向存储关系的视图指针。第二部分用4个字节来表示记录的长度。第三部分用来表示元组
6、加入或最后一次更新的时间，它也是四个字节。这样记录的长度变为316个字节。例4.6中的结构进行修改加进头信息 nameaddressgenderbirthday1244300304316类型长度时间戳将定长记录组成数据块将定长记录组成数据块数据块的头信息，通常含有以下信息：l数据块之间的联系信息。l该数据块在整个数据块集合中所起的作用。l该数据块所表示的元组属于那一个关系。l每个记录在数据块中的偏移量。l数据块号。该数据块最后一次被修改或更新的时间标志。记录长为316个字节。假使我们使用的是长为4096个字节的数据块。对于这些空间，12个被用于数据块的头信息，余下4084个字节来存储数据。这样
7、我们在每个数据块中放了12个316字节的记录，即块因子为12。该数据块则浪费了292个字节的空间。考虑数据块的头信息考虑数据块的头信息块和记录地址的表示块和记录地址的表示 在我们考虑怎样表示那些具有更复杂数据结构的记录之前，我们必须先考虑怎样对记录和块编址，以及怎样去表示那些指向数据块的指针。在数据块装入内存的缓冲区时，数据块的地址可使用数据块的第一个字节的虚拟存储地址。同样记录在数据块内的地址为记录的第一个字节的虚拟内存地址。但是，当数据块在外存中时，该数据块并不作为应用程序虚拟地址空间的一部分。我们采用字节的序列来表示数据块在整个DBMS可管理的数据中的位置，它包括：磁盘的设备标识号，盘上
8、柱面号等等。我们给定记录所在的数据块和它在数据块中的偏移量就可找到该记录。c/s结构的DBMS的地址空间问题 一个数据库系统有一个服务器进程，用于从外存提取数据交给一个或多个客户进程。客户进程处理所送来的数据。服务器进程和客户进程可同在一台计算机上，或者服务器进程和多个客户进程分布于多个计算机中。客户应用进程使用传统的虚拟地址空间。一般用32位来表示一个地址，这样可表示40亿个不同的地址。操作系统和DBMS确定应将哪一部分地址空间装入内存，同时硬件建立虚拟地址空间到主存中物理地址的映射。我们将不再研究这种虚拟到物理地址的转换，而着重考虑调入内存中的数据块如何将用户地址空间转换到物理地址空间。数
9、据块和记录在外存中的真实地址。用物理地址中的一个或几个字节来指出如下信息：l这个存储器是在那一台主机上（如果数据库是存储在多台计算机中）。l数据块所在的磁盘号或别的设备号。l磁盘中的柱面号。l柱面中的磁道号。l在磁道中的数据块号。l数据块中的记录项对于数据块头的偏移量。物理地址 物理地址可能很长。例如，假使一个数据库系统的设计寿命是100年。在将来，这个系统也许要联入100万台机器，而每台机器以每十亿分之一秒产生一个对象。那么这个系统大概要存储277个对象，这就要求最少用10个字节来表示物理地址。由于我们还需预先保留一些字节来表示主机等，所以这个系统的物理地址就需要10个以上的字节来表示。逻辑
10、地址 计算机指令中地址部分所指示的地址称为逻辑地址。它是由二进制的定长比特流组成的。逻辑和物理地址的转换逻辑和物理地址的转换 映射表逻辑地址物理地址 查询物理地址所需的信息都保存在映射表中，然后，据指向某一记录的逻辑指针来查询映射表，以得到相应的物理地址。当然，为了找到记录，我们需要有足够的有关它位置的信息。最简单的例子是定长记录，如果它的关键字的偏移量已知。另外从数据块的头信息中就可知道该块包含有多少记录，据这些信息我们就能从数据块中方便的找到相应的记录。从数据块中找到相应的记录 一个简单而有效的办法是给每个数据块保存一个记录的偏移量表。偏移量表记录 3记录 2记录 1未用部分头信息 在c/
11、s结构的数据库系统中，每个数据块、每个记录、每个对象或别的可引用的数据项都有两种形式的地址：服务器的数据库地址空间中的编址。通常用8个字节来表示一个地址。我们称它为数据库地址。虚拟存储器中的地址（为内存工作缓冲区地址）。通常由4个字节组成。我们称之为内存地址。转换数据库地址到内存地址的表 地址转换表数据库地址内存地址前面所提到的物理地址和逻辑地址都是用来表示数据库地址的。在转换表中的内存地址反映了对象在内存中的位置。数据库中所有可编址的数据项，仅当其处在内存中时，才能在映射表中找到相应的行。为避免重复地进行数据库地址和内存地址的转换采用指针置换的方法 当数据块从外存中移动到内存时，对数据块中的
12、指针进行指针置换。也就是将数据库地址转换成内存地址.通常一个指针由下列信息组成：用一标志位来表示这个指针是数据库地址还是内存地址。数据库地址值或内存地址值。数据库存储空间 客户内存空间 将数据块读入内存 被置换过的指针 数据块 1 未置换过的指针 数据块 2两种类型的指针指针置换的方法 自动置换当数据块调入内存时，定位出其中所含有的指针和地址，如果置换表中还没有这些数据项，则将它们记入到地址转换表中。这些指针包括记录中指向其它数据块的指针，以及指向块内记录项的指针。定位数据块中的指针。例如：（1）如果数据块中存有记录的视图，那么它就告诉人们在记录中的什么地方是指针。（2）如果数据块中使用的是索
13、引结构，数据块中的指针位置也是可知的。（3）在数据块头信息中记录指针所在的位置。当一个数据块刚刚调入内存时，我们就将该块的一些地址加进地址转换表内，这时我们能确切地知道该块在内存中的地址。所以，我们可直接了当的为这些数据库地址生成对应的内存地址。如果我们将一个数据库地址A插入地址转换表时，发现A已在表中，这是因为A所在的数据块在先前已进入内存。在这种情况下，我们用对应的内存地址去代替数据块中A的地址，并且将标志位置成“1”。另一方面，如果A不在置换表中，则它所在的数据块还未调入内存。则不能置换该指针，而是将它继续以数据库指针的形式留在数据块中。如果我们要跟踪指针P，但它是没有被置换过的指针，那
14、么我们必须将包含指针P所指数据项的数据块B放入内存中（不然我们无法跟踪该指针）。查询地址转换表来确定在内存中是否有和指针P对应的单元。如果没有，将数据块B调入内存缓冲区中。一旦数据块B也在内存中，就可将指针P进行置换。另一个办法是在数据块首次调入内存时，对所有的指针都不进行置换。将数据块的数据库地址和它的指针的数据库地址跟它们所对应的内存地址一起放入地址转换表中。当需要跟踪指针P时，象自动置换方法中置换未知指针那样进行置换。但同时它可能造成无法跟踪一些已经置换的指针 按要求进行指针置换 一个有效的方法是将数据库的指针设计成与内存地址不同的形式。这样，我们可以象跟踪内存指针那样跟踪所有的指针。如
15、果碰到一个没有被置换的指针，就引起一个硬件中断。如果DBMS提供给操作系统一个被中断调用的函数，它将指针按照以上的方法进行置换；那么跟踪指针时，就不需要任何特别的操作，而只是在遇到没有置换的指针时多用一点时间。跟踪一些已经置换的指针将数据块写回磁盘将数据块写回磁盘 当数据块从内存被写回磁盘，那么它所包含的指针需要被反置换。也就是用数据库地址来代替内存地址。地址转换表可用来进行数据库地址到内存地址和内存地址到数据库地址的双向转换。给出一个内存地址，我们就可以找出对应的数据库地址。锁定记录锁定记录 如果一个数据块在某时不能被安全地写回磁盘中，我们称它被锁定了。可在数据块的头信息中用一位来表示数据块
16、是否被锁定 指针正在进行置换是记录被锁定的主要原因。当我们在数据块B1中使用了一个已置换的指向数据块B2的指针，那么当B2被调回磁盘或从磁盘又调入内存时，就必须对该指针进行处理。因为如果不进行处理，我们在跟踪B1中的指针时，它可能指向了内存缓冲区原被B2占用的部分，而这部分现在被数据块A使用，那么可能导致错误。这就是为什么要进行锁定的原因。当我们将一个数据块写回到磁盘中时，我们不仅要将该数据块中的指针进行反置换，而且还要检查要写回的数据块是否被锁定。如果它被锁定，则一方面要将该数据块继续留在内存中以保证它不被别的数据块覆盖，另一方面要将该数据块进行解锁操作。对数据块进行解锁是因为我们要将那些已
17、经置换的指针进行反置换。所以地址转换表必须为那些数据库中指向内存的数据项，记录下它们所指的内存位置。写回磁盘4.44.4可变长度的数据和记录可变长度的数据和记录 我们假设每种数据项都是定长的。这样记录就有一个固定的由定长域组成的结构视图，但是在现实中常常不这么简单。我们需要表示：长度可变数据项 重复的域 多种记录格式 大对象带有可变长域的记录带有可变长域的记录 如果一个记录中的一个或多个域是可变长的域，那么记录就需要额外加进一些信息来定位记录中的域。一个简单而有效的方法是将所有固定长度的域放在前面，最后放可变长度的域。我们应在记录的头信息中放如下信息：记录的长度。所有可变长域的偏移量。其它头信
18、息 记录长度 指向 name 指向 address gender birthdate name address固定长度的域放在前面，最后放可变长度的域带重复域的记录带重复域的记录如果记录中有不定个数的定长的域F。我们可将这些相同的域合并起来，并在记录的头信息中保存这个集合的第一个的偏移量。这样就可方便的找到所有的域F。如果域F所占的字节数是L，那么其它域F的偏移量是第一个域F的偏移量加L的整数倍。其它头信息 记录长度 指向 address 指向电影指针域 name address 指向电影记录pointer用来指向该电影中的所有演员 记录头信息 指向 name name 的长度 指向 addr
19、ess address 的长度 指向电影指针记录 电影指针个数 记录 address name 附加存储空间可变长度的部分放在特殊的数据块中格式可变的记录一个最简单的表示格式可变的记录的方法是使用标记域，它们包括：1 1 该域所起作用的信息，包括：（a）、属性或域的名字；（b）、域的类型 （c）、如果不能从域的类型知道域的长度，那么记录域的长度。2 域的值。（1）有的应用从多个信息源来的信息格式不尽相同。有时一个关系接收从多个数据源来的信息，并且这些数据的格式是不同的。例如，有的记录不带有birthdate域；有的记录不带有address域；等等。如果一个记录中没有多少域，那么我们可将不存在的
20、域用NULL填补。但是，如果一个记录中为NULL的域很多，最好使用标记域。（2）灵活的记录结构：即使关系的视图是确定的，但如果记录中的一些域是可出现可不出现的，我们也可使用标记域。例如，假设有些演员的记录有所导演的电影、前任配偶、所拥有的产业和别的被定义了而无信息的域。那么我们就可使用标记域。使用标记域有两方面的原因 姓名的编码姓名的编码 饭店老板的编码饭店老板的编码 字符串的编码字符串的编码 字符串的编码字符串的编码 长度长度 长度长度 N S 14 Clint Weatwood R S 16 Ju N S 14 Clint Weatwood R S 16 Jus Breath Inns B
21、reath Inn使用单个的代码来表示不同的域的名字和类型使用单个的代码来表示不同的域的名字和类型长度大于数据块长的记录 块头块头 记录头记录头 记录记录 1 1 记录记录 2-a 2-a 记录记录 2-b 2-b 记录记录 3 3 块 1 块 2对象的存储对象的存储对象标识符:可用若干不同的方法构造，它们各有利弊。ORION中所用方法为，一个对象标识符是个二元组（类标识符，实例标识符）.类的存储类的存储格式 类标识符 名字 标识号 引用次数 索引1,2 实例索引 超类表 类作为一组对象的说明而存在。它是被作为一种特殊的对象来类作为一组对象的说明而存在。它是被作为一种特殊的对象来处理的。我们将
22、类和对象实例分开存储，同时类指出属于它的对象处理的。我们将类和对象实例分开存储，同时类指出属于它的对象实例的位置。实例的位置。当一个类作为其它类的属性或超类时，我们称类被引用。将类当一个类作为其它类的属性或超类时，我们称类被引用。将类的属性和方法用单独的记录块存储，这些记录按照属性和方法的名的属性和方法用单独的记录块存储，这些记录按照属性和方法的名字分别建立两个索引，字分别建立两个索引，索引的根存储在类的定义中。属于该类的实索引的根存储在类的定义中。属于该类的实例被聚集在某个索引之下，超类表是一个含有超类信息的表，其中例被聚集在某个索引之下，超类表是一个含有超类信息的表，其中存放的是超类的个数
23、以及各超类的标识。存放的是超类的个数以及各超类的标识。对象实例的存储结构 实例标识符 对象长度 属性个数 属性向量 关联域 实例标识符是一个对象的全程唯一标识符；对象长度和属性个数记录了以磁盘格式存储的对象总长度及属性的个数；属性向量:属性序号,数据类型,长度 关联域:关联类型 关联类标识符 关联实例标识符 对象关系型数据记录的存储对象关系型数据记录的存储 指向对象域的起址头信息 记录长度 指向相应的对象存储地址 实例标识符 对象长度 属性个数 属性向量 关联域 属性序号 数据类型 长度 数据 关联类型 关联类标识符 关联实例标识符定义关系emp,Create table emp(Name varchar(30),Salary int,Startdate date,Location point,Picture image);例例存储格式 头信息 记录长度 12 32 33 34 wang 2000 1982/8 指向 point 对象 指向 image 对象
