一个用于存储持久化数据和对象的轻量级索引文件

• 下载源代码 - 15.8 KB

引言

有时需要一种方法将简单数据对象存储到文件中，然后可以通过键或索引检索它们。在许多有此需求的应用程序中，可以使用嵌入式数据库。但在某些情况下，使用嵌入式数据库可能过于复杂，而且数据库的引入会增加部署的复杂性。嵌入式数据库会成为需要管理的另一个组件。

在处理一个旧式销售点应用程序的源代码时，我偶然发现了一种轻量级文件存储机制的实现，该机制用于存储给定数据结构的多个实例，并使用一个简单的键来标识在文件中要访问的具体数据实例。在此销售点应用程序中，以这种方式存储的数据包括收银员列表（每个收银员的记录提供控制收银员操作的数据）、员工列表（每个员工的记录提供员工考勤的数据）以及其他数据。这些数据对象具有以下共同特征：

1. 实际存储的数据是一个简单的 C 语言二进制数据结构，
2. 特定类型的每个对象都有一个唯一的键，例如员工识别号，
3. 在对象创建和存储后，在操作过程中对数据对象元素进行的更改很少，
4. 大多数情况下，文件被创建并插入一组对象，对象的数量不经常改变，并且
5. 通常只有少数（少于 100 个）特定类型的数据对象。

背景

在原始应用程序编写时，开发人员并未考虑轻量级、可嵌入的数据库引擎。原始应用程序环境是一个内存有限的小型微处理器终端，使用一个简单、专有的操作系统。文件存储对象的这种模式在源代码的多个地方都有使用，尽管源代码被复制并修改，而不是开发人员创建一个通用的函数库供多个地方使用。对于一种类型的数据对象，其最大数量以数量级为单位进行了更改，引入了一个 B 树式数据库函数库，但其他文件并未更改。

销售点应用程序中数据存储的基本模式是为每种数据类型都有单独的文件。文件包含三个数据区域：

1. 文件描述头，包含文件内容管理数据，
2. 索引部分，具有固定大小，包含用于查找特定数据记录的索引数据，以及
3. 数据记录部分，包含正在存储的实际数据。

可用的索引数量在创建空文件时已固定，并且大小信息存储在文件描述头中。固定大小通常不会是应用程序的问题，因为设置销售点终端的安装人员通常会为实际预期的对象数量（收银员、员工等）设置比实际需求大得多的最大对象数量。例如，为一家拥有 10 名员工的小餐馆配置设置的人员会将员工文件的大小设置为可容纳 100 名员工。

索引信息存储在文件的索引区域，作为一个排序列表。检索特定索引时，使用对排序列表的二分搜索来定位正确的索引（如果存在），然后使用该索引定位数据记录本身。存储新记录时，会找到新索引的插入点，并将索引插入到该点。删除现有记录时，会找到现有索引并将其从列表中删除，然后合并列表。这使得记录的插入和删除成本很高，因为必须在不包含空索引槽的情况下维护列表的排序顺序。然而，如果大多数操作是读取操作或记录更新操作，那么对于较小的数据集，这种结构是可行且简单的。

销售点应用程序中这些文件访问原语的实现存在一些问题。首先，没有通用实现，每种数据类型都有其自身的通用概念实现，导致源代码重复，增加了源代码本身的大小以及生成二进制文件的大小。其次，使用文件访问原语需要多个步骤，程序员需要了解文件结构的相当多细节。

源代码提供了一个通用的函数库，该库提供了一个接口来创建文件并执行文件中的数据插入、删除、更新和检索操作。使用此库的步骤如下：

1. 确定数据对象记录和用于提供数据对象记录唯一键的数据对象索引，
2. 确定将存储的最大对象数量，以及
3. 确定一个比较函数，该函数将比较两个索引并指示索引的排序顺序。

比较函数将确定索引的排序顺序。

在此实现中，文件管理数据与用户数据分离，文件管理数据封装在函数库中，因此库的用户无需了解实际的物理文件实现。用户只关心存储的数据以及数据访问的语义。有两种层次的数据访问接口函数：一个层次指定文件名，另一个较低层次指定文件句柄。使用文件名的层次通过打开指定文件并调用适当的文件句柄函数来执行实际操作，从而使用较低层次的文件句柄层。对于大量多次访问，一次打开文件然后使用文件句柄层执行多次操作，比使用带文件打开开销的文件名层效率更高。

为了将文件内容管理职责与文件内容本身分离开来，文件创建涉及在文件首次使用之前创建文件索引部分的步骤。每个索引条目包含两部分数据：一个记录块号（从 1 到文件将包含的最大记录数的数字）和用户的索引数据。初始化过程包括写入每个索引，并附带其记录块号和一个用于用户索引数据的零填充区域。当添加新记录或删除现有记录时，带有指定记录块号的索引将被移动，并且索引的用户数据部分将被修改，但是分配给特定索引的记录块号永远不会改变。索引被管理为实际记录存储空间的句柄池。

由于文件和记录管理数据与用户数据分离，因此库的用户不会知道索引或索引引用的记录数据的物理位置。索引与相应数据记录的链接方式意味着实际数据记录可能包含也可能不包含索引数据。这也意味着用户可以使用该库创建一个仅由索引数据组成而没有相应记录的文件。

使用代码

函数库提供基本的文件记录操作：

1. 创建和初始化文件，
2. 将索引和记录插入文件，索引按排序函数排序，
3. 当排序函数指示文件中的索引与搜索索引匹配时，从文件中删除索引和记录，
4. 通过指定带有排序函数的索引从文件中检索记录，以及
5. 更新现有记录，其索引与指定索引匹配。

使用函数库，用户将提供至少一个数据结构（索引），以及可能的另外两个可选的：头部信息和用于使用索引作为键存储的数据的记录数据结构。

文件访问操作（插入、删除、检索和更新）需要两个信息，用于确定索引在索引列表中的位置：提供的索引数据结构和排序函数，该排序函数指示提供的索引数据结构是高于、低于还是等于从文件中检索到的索引数据结构。使用此方法，键的数据类型可以是用户希望的任何类型，只要存在键的排序序列，并且有一个函数可以比较两个索引并确定一个索引在排序序列中是高于还是低于另一个。

一些注意事项和权衡

该函数库确实包含几个数据结构和过程，这些过程会限制索引结构的大小。索引结构的大小应该是小的，意味着小于 256 字节，因为函数库中有临时缓冲区用于临时保存索引数据。为了提高吞吐量，文件的索引区域以存储的索引条目大小的倍数进行移动。存储的索引大小是用户索引数据结构的大小加上一个包含分配给该索引的记录块号的附加区域。

与索引关联的实际记录数据（存储在文件的记录数据部分）在索引移动时永远不会被移动。当记录被删除时，会将与该记录关联的索引复制到临时位置，然后将索引区域移动或“波动”下来，覆盖要删除的记录的索引，然后将临时区域中的索引放在已激活的排序索引列表之后。结果是索引永远不会被销毁，当需要时，它们会从存储在已使用索引排序列表之上的可用索引池中取出，当不需要时，它们会放回可用索引池。结果是记录区域中存储的记录不像索引那样是排序列表。因此，在进行多次插入和删除操作后，索引将是有序的，但记录数据将不是。

此函数库的当前实现不会在记录被删除并将其关联索引放入空闲池时覆盖记录数据。这对于敏感数据可能存在安全隐患。

此函数库中使用的底层文件访问原语是 Microsoft Visual Studio 2005 集成开发环境提供的标准 C 库（fopen()、fclose()、fread()、fwrite()、fseek() 和 fflush()）。更改文件访问原语需要修改函数库的内部。使用文件名进行外部接口函数需要文件名是 ANSI 单字节零终止的字符字符串。在需要使用 UNICODE 文件名和不同文件原语集的情况下，函数接口会发生变化。

创建和初始化文件

创建和初始化文件需要用户指定最大记录数，并提供索引和记录的大小。还可以指定一个文件内容头，允许用户存储文件内容管理信息，例如版本号或其他数据。在某些情况下，库的用户可能希望查询文件以确定文件可以放入的最大记录数以及当前文件中的记录数。在头文件中提供了一个次要文件信息结构，以允许进行此查询。

库使用者的意图是，他们将有一个 C 或 C++ 结构或类，用作实际存储对象的描述（记录数据），以及一个 C 或 C++ 结构或类，用作用于标识特定记录的索引对象的描述。因此，当调用函数创建和初始化文件时，最简单的方法是在函数调用中使用 sizeof() 运算符。

// Create and initialize the data file. The name of the file to be created is "testname1"
// We are sizing this to hold 5,000 records. The index struct is of type IndexThing and
// the record struct is of type RecordThing. We are using a user defined header as well.
FileLibCreate ("testname1", 5000, sizeof(IndexThing), sizeof(RecordThing), sizeof(HeaderThing));

访问和修改文件内容

该函数库提供了一套用于插入新记录、删除旧记录或更新现有记录的函数。

// Create variables for specifying the index and the record
IndexThing MyIndex;
RecordThing MyRecord;

// Create a record with it's index.
MakeIndexAndRecord (iLoop, MyIndex, MyRecord);

// Now do the insertion of the record into the file. We specify the
// address of the variable containing the index and the address of the
// variable containing the record. In addition we must provide the address
// of a collation function whose prototype is int CollateFunc (void *pIndex1, void *pIndex2)
FileLibInsert ("testname1", &MyIndex, &MyRecord, CollateFunc);

所有这些原语都使用排序函数来定位现有记录或新记录应插入排序列表中的位置。排序函数的原型是 int CollateFunc (void *pIndex1, void *pIndex2)，该函数将返回三个值之一。如果索引 pIndex1 在索引的排序序列中低于索引 pIndex2，则排序函数应返回负一 (-1)。如果索引 pIndex1 等于索引 pIndex2，则排序函数应返回零 (0)。如果索引 pIndex1 在排序序列中高于索引 pIndex2，则排序函数应返回正一 (+1)。排序函数返回的值应类似于标准 C 库中的比较函数返回值，例如字符串比较函数 strcmp(s1, s2) 或内存比较函数 memcmp (b1, b2, n)。实际上，如果键是文本字符串，排序函数可能仅仅是使用字符串比较函数 strcmp (s1, s2)，并让排序函数返回 strcmp() 的返回值。

// Collation function to determine the order of the two arguments.
//  - returns -1 if pIndex1 should go before pIndex2
//  - returns 0 if pIndex1 and pIndex2 have the same key
//  - returns +1 if Pindex1 should go after pIndex2
static int CollateFunc (void *pIndex1, void *pIndex2)
{
    IndexThing *pLookFor = (IndexThing *)pIndex1;
    IndexThing *pFileItem = (IndexThing *)pIndex2;

    // do a string compare on the two keys to determine if pLookFor is lower
    // in the collating order than pFileItem (strcmp returns -1), if the two
    // keys are equal (strcmp returns 0), or if pLookFor is higher in the
    // collating order than pFileItem.
    return (strcmp (pLookFor->aszKey, pFileItem->aszKey));
}

关注点

在测试时，我尝试使用一个包含五千个索引的文件，发现当向文件中插入五千条记录时，打开和关闭的开销非常大。通过将文件打开逻辑与实际文件操作函数分开，创建一个使用文件句柄指定文件的层而不是文件名文本，可以显著减少在笔记本电脑上生成包含五千条记录的文件所需的时间。

用于查找排序索引列表中指定索引的搜索过程使用二分搜索来探测磁盘上的索引列表，以确定一个小的索引窗口。当二分搜索探测将列表缩小到某个子集时，该子集将被读入内存并进行顺序搜索。原因是，在内存中搜索顺序列表比搜索存储在机电设备上的磁盘文件要快，机电设备在定位和检索磁盘上的特定区域时会涉及许多延迟。一个有趣的实验是更改搜索过程，以增加子集的大小，并也使用二分搜索来进行内存搜索。

在编写测试工具和演示源代码以展示该库如何使用时，我意识到各种文件类似于数据库中的表。这一见解促使向库中添加了一个额外的函数，用于迭代文件，允许使用过滤器或选择函数来选择符合除排序函数标准之外的其他标准的索引。通过添加这种迭代器功能，我们现在能够在使用此函数库时，使用外键来实现更面向数据库的方法。

另一个可能很有用的有趣数据是添加到文件管理数据中，这些数据存储在文件中，使用 FileLibHeader 结构，其中包含有关文件使用情况的信息，例如最后一次插入、最后一次删除和最后一次更新的日期和时间记录。其他可能有用信息是保留插入、删除、更新、检索等操作的计数，保存在头文件中。