基于C++在 Linux 下表的实现与应用【100012196】

# Linux 下表的实现与应用 ### **总体要求：** 在 Linux 环境下，采用 C 或 C++，存储一张表，然后能对该表进行查询、添加等操作。上述功能以 API 的形式提供给应用使用。 ### 存储要求： 利用文件操作 API，在文件系统中存储一张表。该表有 100 个属性，每个属性都是 8 字节大小。需要支持的最大行数为一百万行（可看作支持行数没有上限限制）。 ### 添加要求： 提供 API 函数，实现向表格添加一行的功能（添加到表格的末尾）。 ### 搜索要求： 提供 API 函数，实现对表格某一个属性进行范围查找或精确查找的功能。例如：查找在属性 A 上，大于等于 50，小于等于 100 的所有行，当上下限相等时，即为精确查找。 用户可以指定在哪一个属性上进行搜索。当搜索结果过多时，可以返回一小部分，如 10 行。 ### 索引要求： 提供 API 函数，为表格里的某一个属性建立索引结构，以实现快速搜索。 自行选择使用哪种数据结构，建立索引结构，比如 B+ 树等。 建立的索引结构，需要保存到一个文件中（索引文件），下次重启应用程序，并执行搜索任务时，应先检查是否已为相应属性建立了索引结构。即，搜索功能实现时，需要查找是否有索引文件存在，若有，则使用该文件加速搜索。 ### 并发要求： 应用程序可以以多线程的方式，使用上述 API。 要保证多线程环境下，表、索引结构、索引文件的一致性（考虑互斥的要求）。 ### 测试要求： 表中的数据随机生成。 测试用例要覆盖主要的需求。 # 一、总体设计 **程序总体架构** 图 2-1 程序总体架构 图 2-1 所示是程序的总体架构。可以看到，在本次实验中，首先是完善表的基本结构和功能。其中记录的存储与读取，索引结构的构造，索引文件的存储与读取，是最先完善的。接着实现表的查询和添加功能。除此之外，为了使用的方便性， 本实验封装了两个 API 供外部程序使用。第一个是将表的查询和添加进行封装，外部程序可直接调用；考虑到多线程的环境，又封装了创建线程的 API，调用该 API 可以创建用于查询和添加的线程，实现并发，提高了效率。 **关键流程分析** 在本次实验中，为了提高查询速度，查询功能是基于索引结构的，而添加记录会引起索引结构的更新，因此，索引结构的实现是关键。本次实验选择了 B+ 树作为表的索引结构，执行查询功能时，会先检查索引文件是否存在，若不存在则创建索引结构进行查询，并将索引结构保存到索引文件中，供下次查询使用；若存在索引文件，则从中读取出索引结构进行查询。 为了实现并发功能，本实验封装了创建线程的 API，用于创建查询线程和添加线程，通过调用操作表格的 API，执行相应的功能。由于在多线程环境下，表格属于共享资源，因此必须考虑到互斥的要求，保证索引文件和表格中记录的一致性。 # 二、详细设计与实现 基本的数据结构 在本实验中，每条记录有 100 个属性，为了区分开每条记录，将其在文件中的序号作为主键，如下所示：  构建某一属性的索引结构时，需要把所有记录的该属性值作为关键字构建 B+ 树，并将记录的序号一同保存，便于寻找该条记录。因此，B+ 树中的关键字定义如下：  为了提高查询效率，本实验选择构建四阶 B+ 树作为记录属性的索引，树节点定义如下：  B+ 树的实现  上面的代码为 B+ 树构建了一个类，里面是各种成员函数，包括构建一棵 B+ 树所需的一些基本函数，以及实现查询、插入、保存、读取的函数，下面依次展示它们的实现。 B+ 树的插入：  如上述代码所示，插入一条记录时，我们首先为其构建关键字结构。由于插入一个关键字有时会引起 B+ 树节点的分裂，所以我们在插入之前首先应检查当前节点关键字是否已满，如果已满，应先调BPlusTree_Split_Child 函数将其分裂成两个节点，然后再进行插入，以保证每次插入时当前节点都处于非满状态，此时调用 BPlusTree_Insert_NotFull 函数，插入该未满节点中。节点分裂的实现：  上述函数有三个参数，第一个是待分裂节点的父节点指针，第二个是分裂的位置，第三个是待分裂节点的指针。首先创建一个新的节点，将待分裂节点的后 M-1 个关键码和后 M 个孩子指针放入新建的节点，更新节点的成员值，并将待分裂节点最中间的关键码放入父节点，并调整父节点的孩子指针，使其指向正确的子节点。上述代码保证了每次分裂节点时，待分裂节点的父节点都处于非满状态，因此不会引起二次分裂。插入非满节点：  需要判断该节点是否为叶节点，若是则直接插入相应位置，若不是，则根据节点中的关键字判断应插入的子节点，同样的，为了避免二次分裂，我们在插入子节点时，都应先判断子节点是否已满，然后递归地调用此函数，最终将关键字插入叶节点中。 B+ 树的插入采取的是先检查再插入的策略，而不是先插入再判断的策略，这样做的好处是避免了二次分裂，无需考虑子节点分裂后引起父节点分裂的情形。 B+ 树的搜索： 根据设计需求，既要实现精确查找，也要实现范围查找，编写相应函数分别实现这两个功能。由上述代码可知，构建出来的 B+ 树的所有叶节点从左到右形成了一个链表，且叶节点中的关键字从小到大排列，因此查询时先找到对应的叶节点，然后再顺着叶节点的 next 指针寻找。精确查找：  精确查找的思路是：从根节点开始，从关键字数组的左端开始跟待查的关键字比较，遇到大于或者等于的关键字便停止，进入对应的子节点，重复该过程，直到到达叶节点，这样做是为了保证能够到达待查关键字可能出现的第一个叶节点，不会出现遗漏的情况。到达叶节点后，一直向右查找，保存与待查属性值相等的关键字的序号，遇到更大的属性值便停止，返回记录的序号数组。 范围查找：  与精确查找类似，查找某个范围时，从左端和右端分别查找到叶节点，然后再从左端叶节点向右边逼近，保存搜索到的所有符合条件的记录。 B+ 树的保存：  利用文件操作 API，将 B+ 树的每个节点按照深度优先的顺序写到文件中。 B+ 树的读取： ![](https://www.writebug.com/myres/static/uploads/20