[科普中国]-不定长记录

简介

记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。一个记录应包含哪些数据项，取决于需要描述对象的哪个方面。而一个对象，由于他所处的环境不同可把他作为不同的对象。不定长记录是指每个记录含有信息长度不等，也可以称之为变长记录。变长记录是由以下因素引起的，第一，多种记录类型在一个文件中存储；第二，记录类型允许一个或多个字段是变长的；第三，记录类型允许有可重复的字段。举例如下：

type account-list = record branch-name: char(22); account-info: array[1..∞] of record account-number: char(10); balance: real; end end记录在计算机科学中，记录也称为结构体或复合资料（Struct/record）是基本的数据结构，记录是一些相关字段的聚集，它们可由不同的资料类型组成，通常是固定的数量和序列。记录中的每个字段或称为元素，但可能与集合的元素概念混淆不清。在面向对象编程中，记录的字段也另外被称为成员；依照惯例和具体的编程语言，多元组有可能会被认为是一个记录，反之亦然。

譬如将日期储存为一个记录，则其中包含了数字的年份，以字串表示的月份和数字的日期等字段。而人事记录可包含姓名，薪水和职级等字段。一个圆形的记录可包含圆中心点和它的半径－在这种情况下，圆中心点本身可能表示为x和y座标的点记录。

记录与阵列的区别在于，它们的字段数通常是固定的，每个字段都有一个名称，而且每个字段可能有不同的类型。

一个记录型别是描述其中字段所具有值和变量的资料类型。大多数现代计算机语言允许开发人员自由定义新的记录型别。记录型别的定义将会指定每个字段的资料类型和存取它的标识符（名称或标签）。

记录可以存在于任何存储介质中，包括主内存和大容量存储装置，如磁带或硬盘。记录是大多数数据结构的基本组成部分，特别是链接的数据结构。

许多计算机档案是以逻辑记录的阵列组成的，通常被分组成更大的实体记录或区块以提高存取效率。

函数或程序的参数通常当作是一个记录变量其中的字段；而在呼叫该函数时，传递给它的参数可被视为将字段的值指派给该记录变量。此外，通常用于实现程序调用的呼叫堆叠中，每个登录即是一条启动记录或呼叫框页，包含了程序参数和局部变量，返回位址和其它内部字段。

面向对象语言中的物件本质上是一个记录，有如何处理该记录的专用程序；而物件型别是对记录类型的详细描述。实际上在大多数面向对象语言中，记录只是物件的特殊情况，并且被称为普通旧数据结构（plain old data structures, PODS），与使用OO特征的物件形成对比。

不定长记录的数据组织方法背景记录是指同类信息中独立的一部分数据，例如，电子邮箱中的一封信件，手机中的一条短信息等，都属于一条记录。应用程序在接收输入信息时通常会将这些信息组织成为一条条的记录的形式存放在存储设备中。应用程序对这些生成的记录需要采用一定的存储方式存放在非易失类存储设备中，以便于长期保存记录。应用程序产生的记录长度通常是不确定的，如一封信件，少则几十个字节，多则几百万字节，如果采用统一大小的格式存储，不仅存储小记录时浪费存储空间，而且对大记录也有长度限制，如果采用连续存储的方式，则删除的记录所占用的存储空间无法被有效的再次利用，例如无法再存储比删除的记录长度长的大记录，因此执行删除、修改等操作效率极低，不易管理而且浪费空间。

步骤1、应用程序将记录的存储空间划分为固定大小的数据块，每个数据块包括数据区和结构信息两部分，数据块的结构信息中包含有记录ID、记录长度、节点号、下一块地址、数据块状态标记等信息；

2、应用程序按步骤a所划分的数据块的大小将记录数据切分成若干个数据块，并将每块数据块附加上结构信息；

3、长度不大于一个数据块的记录占用一个数据块，大于一个数据块的记录占用多个数据块，应用程序将同一记录的数据块采用链表形式组织前后关系，将同一记录的数据块的记录ID号定为相同，在其结构信息中存放前后节点关系；

4、当删除一条记录时，应用程序将该记录所属的全部数据块的状态标记改写为删除；当写记录数据时，则从存储空间最前面的删除状态的数据块开始写起，依次寻找下一个删除状态的数据块，如无删除状态的数据块，则写入第一个空闲数据块，写数据块时先写入数据，最后将数据块标记改写为有效标记。2

存储方法不定长记录（变长记录）在文件中的存储方法有以下几种：字节流表示法、分槽的页结构、定长表示法。

字节流表示法变长记录在文件中的存储方法之一就是采用字节流表示法：即在每个记录的末尾都附加一个特殊的记录终止符号(┴)，或者是在每个记录的开头存储该记录的长度，这样就可以把每个记录作为一个连续的字节流来存储，如图所示。值得注意的有以下两点：⑴ 要想重新使用被删除记录曾经占用的空间十分困难，很容易导致磁盘碎片；⑵ 如果一个记录变长了，该记录就必须移动；如果一个记录变短了，就造成磁盘碎片。而移动记录的代价很高。

分槽的页结构分槽的页结构是基本字节流表示方法的一种改进形式，普遍用于物理块内部的记录组织，如图所示，分槽的页结构由三部分组成：

⑴ 块头部分：块头部分记录了有关这一块的详细信息，包括块中记录个数、块中空闲空间的末尾地址以及描述块中每个记录的大小和位置的数组；
⑵ 块尾部分：实际记录从块的尾部开始连续分配存储空间；
⑶ 块中部分：块中空闲空间是连续的，处在块头数组的最后一个条目和块尾记录的第一个条目之间，用于为新插入的记录分配空间。
对于分槽的页结构，如何实现记录的插入和删除呢？通常可以采用以下维护策略：
⑴ 删除一条记录：该记录所占用的空间被释放，同时块中在被删记录之前的记录都要移动。因此块头的相关部分都要进行修改，而空闲空间还是集中在块中间；
⑵ 插入一条记录：在块中空闲空间的尾部给这条记录分配空间，同时修改块头的相关部分；
⑶ 记录的增长和缩短：该条记录的末尾地址不变，而在此记录之前的记录都要移动，同时修改块头的相关部分。由于块的大小是有限制的，因此块内能存储的记录个数有限，这样移动记录的代价就不会太高。

定长表示法变长记录的定长表示法是用一个或多个定长记录来表示一个变长记录的方法。由于所采用的策略不同，变长记录的定长表示法又分为以下几种情况。
⑴ 保留空间法：假设所有的变长记录都不会超过某个长度，就为每个记录都分配这样长度的空间，具体情况如图所示：

对于保留空间法来说，值得注意的是：首先假设是不合理的，既然是变长记录，记录的长度就捉摸不定，我们又如何估计出所有记录的最大长度呢？其次这样的做法浪费了大量的存储空间，在实际应用中不可取；
⑵ 指针法：用一系列通过指针链接起来的定长记录来表示一个变长记录，如图所示：

变长记录的指针链接法与表示定长记录类似，在这里变长记录变成了一个链表，和保留空间法相比浪费的空间量较少，但引入了额外的结构，即指针列；

⑶ 锚块-溢出块表示法：这是指针法的变形。在文件中使用两种不同类型的物理块：锚块和溢出块。其中锚块是包含链表中第一个记录的块；而溢出块是包含链表中除第一个记录以外的其他记录的块。具体情形如图所示：

在锚块-溢出块表示法中文件里包含不同的块，而每个块中的记录都是定长的，所谓的变长记录被表示成将不同块中的记录用指针链接起来的一个链表。3