SWFCDB的研究与探索摘 要：数据库技术已经成为现代信息技术的重要组成部分，是现代计算机信息系统的基础和核心。发展国产数据库系统，将对我国软件产业及相关产业发挥重大影响。本文对SWFCDB进行了研究和探索，通过对数据库系统结构，数据结构，多线程程序设计和网络方面的研究，实现了SWFCDB第一层和第二层的基本功能（包括可视化新建数据库，删除数据库，新建表，删除表，插入记录，返回记录等功能），完成了B+树算法的探索和实现，完成了SWFCDB网络模型的探索和实验（包括基于完成端口模型的服务器接口和基于Event Select 模型的客户端接口）
关键词：关系数据库 B+树 网络 完成端口 多线程
Study and exploration of SWFCDBLinFeng Deng(Dept. of Computer and Information Science, Southwest Forestry College, Kunming, Yunan, 650224, China)
Abstract: Database technology has become an important component of the modern information technology and is the basis and core of modern computer information systems. Development our owner database systems will play a significant impact in our software industry and related industries. Through research and exploration of the SWFCDB, studying the knowledge of database system structure, data structure, multi-thread programming and network, I has realized the first floor and the second floor functions of the SWFCDB, including visualization new database, delete the database, the new table, delete the table, insert records, return all records and so on), then completed the B+ tree algorithm exploration and achievement, also completed the SWFCDB network model exploration and experimentation, including model based on I/O Completion Port server interface and model based on I/O Event Select client interface.
Keywords: Relational database, B+ Tree, Network, I/O completion port, Multi-thread目 录1 引言 12 数据库系统发展现状 22.1 面向对象数据库系统 22.2 分布式数据库系统 22.3 多媒体数据库系统 32.4 知识数据库系统 32.5 并行数据库系统 32.6 模糊数据库系统 43 自主知识产权数据库--系统设计 53.1 系统结构 53.2 第一层设计思想 63.2.1 数据记录文件 63.2.2 索引文件 63.2.3 锁表文件 63.3 第二层设计思想 63.3.1 服务器层次树视图 73.3.2 数据库子项显示列表视图 73.3.3 表操作视图 73.4 网络模型设计思想 93.4.1 服务器接口设计思想 93.4.2 客户端接口设计思想 114 自主知识产权数据库--系统实现 124.1 开发环境 124.2 第一层实现 124.2.1 代码维护与更新 124.2.2 B+树索引 134.3 第二层实现 144.3.1 拆分窗口 144.3.2 服务器层次树视图 144.3.3 数据库子项列表视图 154.3.4 表操作视图 154.4 网络模型实现 164.4.1 完成端口内存管理接口 164.4.2 完成端口服务器线程 164.4.3 数据处理线程池 174.4.4 CIocp完成端口管理类 174.4.5 客户端接口实现 215 自主知识产权数据库—重点难点 225.1 B+树索引 225.1.1 插入平衡 225.1.2 删除平衡 235.1.3 B+树算法难点总结 255.2 完成端口(IOCP) 255.2.1 回调机制 265.2.2 线程池设计 266 总结 28参考文献 29指导教师简介 30致 谢 445
SWFCDB的研究与探索1 引言数据库技术是当代计算机科学的重要分支，也一直是目前计算机科学的一个重点热门研究领域，其历史追溯到六十年代C. W. Bachman提出的数据图。而自七十年代F. Codd的关系数据库理论与模型的问世之后，八十年代中至九十年代初，数据库(DB)技术蓬勃发展，日趋成熟[1]。迄今为止，已经经历了两代（第一代的网状、层次数据库系统；第二代的关系数据库系统）数据库系统的技术积累和正在进行开发的第三代数据库（以面向对象模型为主要特征的数据库系统）的推动，使DB技术取得了辉煌的成就与发展。关系数据库属于第二代数据库技术，在70～80年代得到长足的发展和广泛而有效地应用，80年代，关系数据库成为应用的主流，几乎所有新推出的数据库管理系统(Database Management System, DBMS) 产品都是关系型的，他在计算机数据管理的发展史上是一个重要的里程碑，这种数据库具有数据结构化、最低冗余度、较高的程序与数据独立性、易于扩充、易于编制应用程序等优点，目前较大的信息系统都是建立在关系数据库系统理论设计之上的。像Oracle公司的Oracle 10i、IBM公司的DB2、还是微软的SQL Server等都是关系型数据库。开发自主知识产权的系统软件一直是我国软件产业发展的目标。作为信息处理的核心软件之一，数据库系统是除操作系统外最重要的核心软件，是数据处理的核心，也是我国信息化建设中需求量最大、应用最广泛的基础性软件[3]。发展国产数据库系统，将对我国软件产业及相关产业发挥重大影响。本文对SWFCDB进行了研究和探索，已实现SWFCDB第一层和第二层的基本功能（包括可视化新建数据库，删除数据库，新建表，删除表，插入记录，返回记录等功能），完成了B+树算法的探索和实现，完成了SWFCDB网络模型的探索和实验（包括基于完成端口模型的服务器接口和基于Event Select 模型的客户端接口实现）。下面具体介绍SWFCDB第一层、第二层、B+树算法和网络模型的设计思想和实现。
2 数据库系统发展现状随着用户应用需求的提高、硬件技术的发展和Internet / Intranet 提供的丰富多彩的多媒体交流方式，促进了数据库技术与网络通信技术、人工智能技术、面向对象程序设计技术、并行计算技术等相互渗透，互相结合，成为当前数据库技术发展的主要特征，形成了数据库新技术。2.1 面向对象数据库系统面向对象的方法和技术对数据库发展的影响最为深远，他起源于程序设计语言，把面向对象的相关概念与程序设计技术相结合，是一种认识事物和世界的方法论，他以客观世界中一种稳定的客观存在实体对象为基本元素，并以“类”和“继承”来表达事物间具有的共性和他们之间存在的内在关系。面向对象数据库系统将数据作为能自动重新得到和共享的对象存储，包含在对象中的是完成每一项数据库事务处理指令，这些对象可能包含不同类型的数据，包括传统的数据和处理过程，也包括声音、图形和视频信号，对象可以共享和重用。面向对象的数据库系统的这些特性通过重用和建立新的多媒体应用能力使软件开发变得容易，这些应用可以将不同类型的数据结合起来。面向对象数据库系统的好处是他支持WWW应用能力。然而，面向对象的数据库是一项相对较新的技术尚缺乏理论支持，他可能在处理大量包含很多事务的数据方面比关系数据库系统慢得多，但人们已经开发了混合关系对象数据库，这种数据库将关系数据库管理系统处理事务的能力与面向对象数据库系统处理复杂关系与新型数据的能力结合起来[2]。2.2 分布式数据库系统分布式数据库系统（Distributed Database System，DDBS）是在集中式数据库基础上发展起来的，是数据库技术与计算机网络技术、分布处理技术相结合的产物。分布式数据库系统是地理上分布在计算机网络不同结点，逻辑上属于同一系统的数据库系统，能支持全局应用，同时存取两个或两个以上结点的数据。分布式数据库系统的主要特点是：（1）数据是分布的。数据库中的数据分布在计算机网络的不同结点上，而不是集中在一个结点，区别于数据存放在服务器上由各用户共享的网络数据库系统。（2）数据是逻辑相关的。分布在不同结点的数据，逻辑上属于同一个数据库统，数据间存在相互关联，区别于由计算机网络连接的多个独立数据库系统。（3）结点的自治性。每个结点都有自己的计算机软、硬件资源、数据库、数据库管理系统（即Local Database Management System，LDBMS 局部数据库管理系统），因而能够独立地管理局部数据库[1]。2.3 多媒体数据库系统多媒体数据库系统（Multi - media Database System ，MDBS）是数据库技术与多媒体技术相结合的产物。在许多数据库应用领域中，都涉及到大量的多媒体数据，这些与传统的数字、字符等格式化数据有很大的不同，都是一些结构复杂的对象。它们数据量大，结构复杂，大多是非结构化的数据，来源于不同的媒体且具有不同的形式和格式。时序性强，数据传输要求连续性、稳定，否则出现失真而影响效果[1]。2.4 知识数据库系统知识数据库系统的功能是如何把由大量的事实、规则、概念组成的知识存储起来，进行管理，并向用户提供方便快速的检索、查询手段。因此，知识数据库可定义为：知识、经验、规则和事实的集合。知识数据库系统应具备对知识的表示方法，对知识系统化的组织管理，知识库的操作，库的查询与检索，知识的获取与学习，知识的编辑，库的管理等功能。知识数据库是人工智能技术与数据库技术的结合[2]。2.5 并行数据库系统并行数据库系统是并行技术与数据库技术的结合，其发挥多处理机结构的优势，将数据库在多个磁盘上分布存储，利用多个处理机对磁盘数据进行并行处理，从而解决了磁盘“I/O”瓶颈问题，通过采用先进的并行查询技术，开发查询间并行、查询内并行以及操作内并行，大大提高查询效率。其目标是提供一个高性能、高可用性、高扩展性的数据库管理系统，而在性能价格比方面，较相应大型机上的DBMS高得多。并行数据库系统作为一个新兴的方向，需要深入研究的问题还很多，但可以预见，由于并行数据库系统可以充分地利用并行计算机强大的处理能力，必将成为并行计算机最重要的支撑软件之一[2]。2.6 模糊数据库系统模糊性是客观世界的一个重要属性，传统的数据库系统描述和处理的是精确的或确定的客观事物，但不能描述和处理模糊性和不完全性等概念，这是一个很大的不足，为此，开展模糊数据库理论和实现技术的研究，其目标是能够存储以各种形式表示的模糊数据，数据结构和数据联系、数据上的运算和操作、对数据的约束(包括完整性和安全性)、用户使用的数据库窗口用户视图、数据的一致性和无冗余性的定义等都是模糊的，精确数据可以看成是模糊数据的特例，模糊数据库系统是模糊技术与数据库技术的结合，由于理论和实现技术上的困难，模糊数据库技术近年来发展不是很理想，但他已在模式识别、过程控制、案情侦破、医疗诊断、工程设计、营养咨询、公共服务以及专家系统等领域得到较好的应用，显示了广阔的应用前景[1]。
SWFCDB的研究与探索3 自主知识产权数据库--系统设计3.1 系统结构图 3 1 数据库主框架图西南林学院自主知识产权数据库总体设计分为7层模块结构，（见：图 3 1 数据库主框架图）分别为：第一层：管理、存、取记录字节流。该层为上层提供多种接口来完成“管理、存、取记录字节流”功能；第二层：管理、存、取库信息和表信息。该层为上层提供多种接口来完成“管理、存、取记录字节流”功能，以及“管理、存、取库库信息和表信息”；第三层：（1）管理和控制各客户，解决并发问题。（2）事务处理；第四层：语义分析和查询处理（DDL、QL、ML、DML）。利用第二层和第一层接口，实现函数化和各种SQL语句，这里是DBMS的内部入口,为上层提供SQL语句的函数式接口；第五层：词法分析和语法分析，把一个SQL语句转换为内部形式；第六层：授权检查。对用户的权限进行检查，允许或禁止调用某些函数，这里应管理授权表；第七层：接口（包括：可视化操作接口、可视化查询接口、应用程序接口）。各层之间通过通用接口实现互访，共同构成一个有机结合体[3]。本文具体介绍SWFCDB第一层和第二层的基本功能（包括可视化新建数据库，删除数据库，新建表，删除表，插入记录，返回记录等功能），B+树算法，SWFCDB网络模型（包括基于完成端口模型的服务器接口和基于Event Select模型的客户端接口）的设计思想和实现。3.2 第一层设计思想第一层建立在操作系统之上，数据存储文件由三个文件组成，分别是：索引文件，数据记录文件，及锁表文件。由于第一层主要由2005届张蓉，曹亚玲同学设计，这里简单说下以上三个文件的结构。3.2.1 数据记录文件数据记录存储在数据记录文件中。对整个文件实行分页管理，每页8K，页内记录通过链表根据关键字由小到大链式存储。3.2.2 索引文件现阶段索引文件存储数据库的建库信息及索引信息。索引文件不分页。索引分为二级索引，第二级索引是记录文件中的页内链式索引；第一级索引是页的链式索引（主要包括页在数据记录文件中的该页起始地址，该页内最大关键字，页中第一条记录的地址，第一条空行的地址，及该页的下一页地址等信息）。以后第一级索引将采用B+树结构存储。3.2.3 锁表文件锁表存储页或记录的加锁情况并由上层管理（如，事务层）。分前缀锁和文件锁，本文暂不详述。3.3 第二层设计思想第二层在第一层提供的接口基础上，管理第一层接口，并向用户提供可视化操作界面，提供服务器层次树视图，数据库子项显示列表视图和对表的操作视图，实现可视化新建数据库，删除数据库，新建表，删除表，插入记录，返回记录等操作。3.3.1 服务器层次树视图如图 3 2 服务器视图界面 所示。本试图将数据库第一层中难理解并隐藏的信息通过图形用户界面，以友好的方式重现，并提供新建数据库，删除数据库等操作。 图 3 2 服务器视图界面3.3.2 数据库子项显示列表视图本视图显示数据库子项中包含的子项列表，并以大图标，小图标，列表，详细信息等方式显示。对表子项提供 新建表，设计表，插入记录，打开表，返回表记录，删除表等操作。如图 3 3 数据库表子项视图界面所示。 图 3 3 数据库表子项视图界面3.3.3 表操作视图本视图将数据库中存储的表信息，以友好的方式重现。分多种呈现方式，如以设计表显示字段信息如图 3 4 新建表或设计表视图所示，插入记录和打开表则显示表中已有记录信息如图 3 5 插入记录视图所示和图 3 6 返回记录视图 图 3 4 新建表或设计表视图 图 3 5 插入记录视图 图 3 6 返回记录视图3.4 网络模型设计思想西南林学院自主知识产权数据库网络模型采用C/S模式。服务器I/O模型采用目前应用最广且网络性能最佳的完成端口（I/O Completion Port）模型[8]，而客户端I/O模型采用事件选择（Event Select）通知模型[8]。3.4.1 服务器接口设计思想完成端口服务器模型模块框图如图 3 7所示。由(1) 完成端口内存管理接口 (2) 完成端口服务器线程 (3)数据处理线程池 (4) CIocp完成端口管理类四部分组成。A. 完成端口内存管理接口完成端口内存管理接口负责分配服务器运行期间服务器所有内存的分配和回收。服务器程序具有收发数据频繁，且长时间运行的特点，如果每次发送和接收操作都由操作系统负责分配并回收数据缓冲区，服务器运行一段时间后，系统内存碎片必然增多，而长时间运行后，导致系统分配不出用户请求的内存空间，而导致系统崩溃。完成端口内存管理接口正是为解决内存碎片而设计。其实现思想为：当程序启动时，该
SWFCDB的研究与探索接口从内存中先取得一块“足够大”的内存空间，并将其分成若干小块，服务器运行过程中，内存管理接口负责分配发送、接收数据缓冲区以及套接字“单句柄数据”缓冲区，并负责回收以上数据空间。由于每次分配数据都是以固定小块形式分配，在该内存块中不会产生内存碎片，因此能够提高系统的稳定性。 图 3 7B. 完成端口服务器线程完成端口服务器线程负责接受、关闭客户端连接，发送和接收数据，但不处理接收的数据，而是将接收的数据放入接收数据队列中，供数据处理线程处理；当发送数据时，对第一次没有发送成功的数据，将该数据放入未成功发送数据队列中，等待网络空闲时发送，如果再次未发送成功则丢失该数据。C. 数据处理线程池数据处理线程池主要负责对接收数据的处理，并提交待发送数据。数据处理线程池由线程池管理者线程和线程池工作者线程组成。空闲工作者线程入空闲工作者线程队列，管理者线程通过空闲工作者线程队列和未处理数据队列负责分派空闲工作者线程要处理的任务，如果未处理数据队列中有未处理数据，则将某个空闲工作者线程推出空闲工作者线程队列，而工作者线程完成任务后，通知管理者线程任务已完成，然后管理者线程检查任务队列中是否有未完成的任务，如果有则重新给工作者线程分配任务，如果没有，则将工作者线程阻塞，并推入空闲工作者线程队列中，待任务队列中有未完成的任务时再将工作者线程激活。D. CIocp完成端口管理类CIocp类管理并协调完成端口内存管理接口、完成端口服务器线程和数据处理线程池的正常工作，监视三者的工作状态，提供控制信息，并提供两种方案实现对接受的数据的处理，分别是回调机制和多态（即派生类重写CIocp类虚函数IOCPRecv()实现）。回调函数原型为：typedef void (*LPIOCP_RECV_CALLBACK)(const LPTASK_QUEUE_ITEM pTQI, CIocp* pIocp);3.4.2 客户端接口设计思想客户端采用异步的Event Select I/O 模型[8]，该模型允许应用程序在一个或多个套接字上，接收以事件为基础的网络事件通知。通过注册程序“感兴趣”的网络事件类型，来通知程序“感兴趣”的事件发生，以此为基础完成与服务器的通讯。对客户端来说，“感兴趣”的事情一般是接收（FD_READ）数据通知和服务器关闭（FD_CLOSE）通知。
4 自主知识产权数据库--系统实现4.1 开发环境目前比较流行的软件开发语言有Java，C#，VB，C，C++等语言。与C语言相比，二者都有较好的可移植性，同时C++是面向对象的程序设计语言，是C语言的一个向上兼容扩充，具有C语言的高效和面向对象语言的快速开发的特点。而与Java，C#或VB等基于虚拟机或解释性的语言相比，虽然它们能够给开发人员带来更快速的开发，但是这种开发的快速却带来了执行效率的大大降低，而数据库是基于系统底层的一项技术，对执行效率有严格的要求，综合考虑运行效率，开发效率和移植性等因素，这里选择C++语言来作为系统实现的首选语言。编译器选择 Microsoft Visual Studio C++ .Net 。4.2 第一层实现4.2.1 代码维护与更新2005届张蓉，曹亚玲同学完成了CreateTable()，InsertOneRecord()，DeleteOneRecord()，FindSomRecord()，UpdateOneRecord()，UpdateSomeRecord()，DeleteSomeRecord()，DeletetOneFiled()，InsertOneFiled()等函数的定义和基本实现。对CreateTable()进行了部分更新，为第一层添加了几种数据类型（如 short, long, float, double, char），并实现将各字段名及各字段数据类型存入建库信息。对InsertOneRecord()进行了大量修改，使其能够实现插入记录时，保证数据记录文件中每页的利用率至少为50%。实现思想是这样的：页内记录按照主关键字大小由小到大链式存储，第一级索引中的页头结点中记录了该页的最大关键字。当插入一条记录时，程序先获得待插记录的关键字，并在第一级索引（目前为链式存储页头结点，各页头结点按页关键字大小，由小到大顺序链式存储）中查找并比较待插入的记录的关键字是否小于页中的最大关键字，如果找到待插入关键字小于某页的最大关键字，则将待插入记录插入该页；否则，将待插入记录插入记录页的最后一页，并修改该页的最大关键字。新增页分裂函数SplitPage()。该函数主要实现页内记录已存储满时，将该页记录分裂成两页存储。实现思想为：先从索引文件中的空页链头中取出一空页（如果没有空页，则在文件尾部新建4空页），然后将满页中按关键字排序的后半段记录存入新页中（页内记录是按关键字由小到大链式存储），最后修改第一级索引链表。新增函数ReturnAllRows()。该函数实现遍历数据库中的所有记录，与FindSomeRecord()函数类似，提供快速遍历。第一层实现代码见：FirstLayer.h 和 FirstLayer.cpp 。4.2.2 B+树索引完成B+树算法[7][11][13]的实现。将B+树算法封装在类CBPTreeIndex 类中。B+树结点结构的定义为：typedef struct BPTNode{ int keyNum; //B+树中关键字个数 long lAddress; //自己节点在索引文件中的位置 long lParent; //父结点在文件中索引的位置 KeyType key[m+1][KSIZE]; //0 空间未用，关键字数组 long lPtr[m+1]; //子树在索引文件位置数组Record rec[m+1]; //0 空间未用，该数组存储对应关键字，在数据文件中的起始位置 BPTNode() //构造函数 { keyNum=0; lAddress=-1; lParent=-1; for(int i =0;i<(m+1); i++) lPtr[i]=-1; }}BPTNode,*PBPTNode;提供以下八个方法对B+索引树进行操作（其他方法为类内部实现，对外隐藏）：bool CreateBPTreeIndex(FILE *_file, long _lIndexStartPos, long _lIndexLength );//此函数为索引文件创建B+树索引。file：(in) 文件指针，
SWFCDB的研究与探索//_lIndexStartPos:(in) B+树索引在索引文件中的起始位置，//_lIndexLength:(in) 用于创建B+树索引结点的文件空间bool CreateBPTreeIndex(FILE *_file, long _lIndexStartPos, int iNodeCount );//重载版本，功能同上//iNodeCount：（in）B+树索引节点数bool OpenBPTreeIndex(FILE *_file , long _lIndexStartPos );//此函数打开B+树索引,然后可对索引文件进行操作//file:(in)文件指针, _lIndexStartPos:(in) file所指文件中,B+树索引结构所在文件中位置BPT_RET InsertBPTree(KeyType key[KSIZE], Record rec);//将关键字 及其关键字标识记录在数据文件中的位置 插入索引表BPT_RET DeleteKey(KeyType *key);//删除关键字索引BPT_RET TraverseBPTree(); //遍历B+树BPT_RET Find(KeyType *key);//搜索B+索引,查找与key匹配的节点,并将其rec返回char *GetBPTreeLastError();//返回最后一次错误信息全部实现代码在 BPTreeIndex.h 和 BPTreeIndex.cpp 两个文件中4.3 第二层实现第二层管理第一层接口，并向用户提供可视化操作界面的功能，是在MFC（Microsoft Foundation Class Library）环境下实现的，提供可视化新建数据库，删除数据库，新建表，删除表，插入记录，返回记录等操作。4.3.1 拆分窗口利用MFC中的CSplitterWnd类[12]将一个窗口框架拆分成若干窗格，实现在同一窗体中显示多个视图。本程序将主界面拆分成服务器层次结构树视图和数据库子项列表视图两个窗格。如图 4 1 程序主界面所示。4.3.2 服务器层次树视图该视图类继承 CTreeCtrl 类[12]，将数据库各层级已树状显示，如图 4 1 程序主界面左半部分所示。本视图提供新建数据库和删除数据库操作，实现代码分别在DBTreeView.h 和 DBTreeView.cpp 两个文件中。 图 4 1 程序主界面4.3.3 数据库子项列表视图该视图类继承 CListCtrl 类[12]，将数据库子项以列表的形式显示，如图 4 1 程序主界面右边为数据库表项的列表显示。本视图提供新建表，删除表，插入记录，返回记录等操作，实现代码分别在DBListView.h 和 DBListView.cpp两个文件中。4.3.4 表操作视图该视图类直接继承 CView 类[12]，显示表的结构信息和记录信息，并对新建表，插入记录，返回记录等操作的结果集实现图形化界面显示，如图 3 4 新建表或设计表视图，图 3 5 插入记录视图和图 3 6 返回记录视图所示。其功能实现代码分别在TableView.h 和 TableView.cpp 两个文件中。说明：由于VC++中并不存在DataGrid 类来显示网格空件。这里使用了由Chris Maunder 开发的开源控件 MFC Grid Control 来显示网格数据。在初略学习了该控件后，添加了几个函数来满足本程序的功能的需要。4.4 网络模型实现4.4.1 完成端口内存管理接口本接口主要提供以下六个函数实现缓冲区管理：DWORD AddReference();//添加对 完成端口内存管理接口 引用，引用次数自增1DWORD Release();//释放对 完成端口内存管理接口 引用，引用次数自减1；//如果引用次数减到0，则释放该内存接口。如果一个线程添加了对该接口的引用，//则必须调用Release（）释放掉。LPPER_IO_DATA GetPER_IO_DATA(DWORD dwThreadID); //从系统预先"单句柄数据"缓冲区中得到一 "单句柄数据" 区//如果成功,则返回缓冲区指针,否则返回NULLvoid FreePER_IO_DATA(LPPER_IO_DATA pIO);//将"单句柄数据"释放回系统预先"单句柄数据"缓冲区中LPIOCP_OVERLAPPED_DATA GetIOCP_OVERLAPPED_DATA(DWORD dwThreadID);//从系统预先分配的 IOCP重叠结构“单I/O操作数据”缓冲区取得一 IOCP重叠//结构“单I/O操作数据”；如果成功，返回指向一IOCP重叠结构“单I/O操作数//据”的指针；如果失败，返回NULLvoid FreeIOCP_OVERLAPPED_DATA(LPIOCP_OVERLAPPED_DATA pIOD);//将IOCP重叠结构“单I/O操作数据” 释放回IOCP重叠结构“单I/O操作数据”//缓冲区4.4.2 完成端口服务器线程服务器线程由以下两类服务器线程函数组成：DWORD WINAPI ServerWorkerThread(LPVOID lParam)//服务器工作者线程定义，负责接受和发送数据DWORD WINAPI IOCPStartAsThread(LPVOID lParam) //服务器控制线程，启动IOCP服务器4.4.3 数据处理线程池数据处理线程池由线程池管理者线程和线程池工作者线程组成，定义为：DWORD WINAPI ThreadPoolWorker(LPVOID lParam)//线程池工作者线程定义，负责处理服务器接收到的数据DWORD WINAPI ThreadPoolManager(LPVOID lParam)//线程池管理线程定义，负责分配工作者线程任务下面为工作者线程参数结构定义：typedef struct _THREAD_INFO //工作者 线程参数结构{ CIocp *pIocp; //IOCP管理类指针 HANDLE hThread; //指向本线程句柄 HANDLE hEvent; //指向本线程同步EVENT核心对象(如果本Event进入传信状态,则说明本线程有待处理的数据) HANDLE hEventWorkFinished; //指向线程当前任务是否完成(如果本Event进入传信状态,则说明本线程的数据处理完毕) TASK_QUEUE_ITEM tqi; //待处理的任务 DWORD dwThreadID; //本线程ID DWORD dwID; //本线程在线程数组中的编号 bool bExitThread; //true 则线程退出，false 继续执行}THREAD_INFO,*LPTHREAD_INFO;4.4.4 CIocp完成端口管理类CIocp类管理并协调完成端口内存管理接口、完成端口服务器线程和数据处理线程池的正常工作，提供两种方案实现对接受的数据的处理，分别是回调机制和多态（即派生类重写CIocp类虚函数IOCPRecv()实现）。下面给出其定义：class CIocp{public:
SWFCDB的研究与探索CIocp(void); ~CIocp(void); friend IOCP_RET WINAPI IOCPStartAsThread(LPVOID lParam);//声明服务器线程函数为该类友元函数，可以访问该类的私有成员 friend DWORD WINAPI ServerWorkerThread(LPVOID lParam);//声明服务器工作者线程函数为该类友元函数，可以访问该类的私有成员 friend DWORD WINAPI ThreadPoolManager(LPVOID lParam);//声明线程池管理者函数为该类友元函数 friend DWORD WINAPI ThreadPoolWorker(LPVOID lParam); //声明线程池工作者线程函数为该类友元函数//attributesprivate: typedef LPIOCP_OVERLAPPED_DATA (*_GetIOCP_OVERLAPPED_DATA) (DWORD dwThreadID);//定义完成端口内存管理接口GetIOCP_OVERLAPPED_DATA() 方法本类内回调//函数原型。功能：从系统预先分配的 IOCP重叠结构“单I/O操作数据”缓冲区//取得一 IOCP重叠结构“单I/O操作数据”；如果成功，返回指向一IOCP重//叠结构“单I/O操作数据”的指针；如果失败，返回NULL char cError[256]; //用于保存出错信息char cServerIPList[16*16];//保存服务器的IP列表,假设一个服务器的IP数目不超过16个 std::list
sendQueue;//定义初次发送失败的数据队列,初次发送失败的数据都存入该队列中 std::list recvQueue;//定义未处理的数据队列，IOCP服务器工作者线程只负责收发数据，不处理接收到//的收据，将接收到的数据放入未处理数据队列中，交由数据处理线程处理数据 CRITICAL_SECTION csSendQueue; //初次发送失败数据队列临界区 CRITICAL_SECTION csRecvQueue; //接收数据队列临界区 DWORD dwConnectCount;//当前服务器连接客户端数 HANDLE hCompletionPort;//服务器完成端口句柄 LPIOCP_RECV_CALLBACK pRecvCallBack;//指向服务器接收到数据后，客户端对数据处理的回调函数 HANDLE hRecvEvent;//同步Event核心对象,当向接收数据队列临界区添加数据时,将其设为传信,通知线//程池管理管理新加入了数据 int iPort;//保存服务器侦听端口号 THREAD_POOL_PARAM threadPoolParam;//传向线程池管理者线程参数 bool bExit;//true则服务器将关闭，false则服务器暂不关闭 HANDLE hThreadServer;//指向服务器线程句柄 HANDLE hThreadPoolManager;//指向线程池管理者线程句柄 DWORD dwThreadID;//服务器线程IDpublic:DWORD dwServerRecvedBytes;//服务器从启动开始接受客户端发送的字节总数DWORD dwServerSendedBytes;//服务器从启动开始发送给客户端的字节总数//operatespublic: IOCP_RET WINAPI IOCPStart(LPIOCP_RECV_CALLBACK callback, int port, DWORD dwThreadPoolWorkerCount=5);//启动IOCP服务器。callback 为指向对接收数据操作的回调函数，//dwThreadPoolWorkerCount 为处理接收数据创建的工作者线程数目,port 为服务 //器侦听端口号 IOCP_RET IOCPClose(int iMaxWaitTime=10);//关闭IOCP服务器,iMaxWaitTim为关闭服务器能承受的最大等待时间,以秒为单位private: IOCP_RET IOCPRecvTaskInsertQueue(const LPPER_IO_DATA pPerIoData, const LPIOCP_OVERLAPPED_DATA pIOD);// 处理接收操作，将接收到的任务插入任务队列void IOCPGetServerIPList();//获得服务器的IP地址列表public: IOCP_RET IOCPSend(LPPER_IO_DATA pData); //发送数据操作 char* IOCPGetLastError();//返回错误信息 DWORD IOCPGetClientCount();//返回连接客户端数 _GetIOCP_OVERLAPPED_DATA IOCPGetOverlappedData;//完成端口内存管理接口 函数指针，用于从完成端口内存管理接口获得一 IOCP//重叠结构“单I/O操作数据”DWORD IOCPGetServerThreadID();//返回服务器线程ID；const char* IOCPGetServerIP(); //返回服务器IP地址，若有多IP，则是IP listprotected: virtual void IOCPRecv(const LPTASK_QUEUE_ITEM pTQI, CIocp* pIocp); //派生类用于处理接收到的数据，及接收数据后的操作 virtual void IOCPAcceptClient(const SOCKET /*socket*/); //派生类用于处理接受客户端连接操作 virtual void IOCPClientClose(); //派生类用于处理客户端关闭事件};4.4.5 客户端接口实现客户端基于Event Select 异步I/O 模型设计，具体实现封装在CEventClient 类中。该类主要提供Connect()，Recv()，Send()，CloseClient()，ServerClosed()等函数完成与服务器通讯。完成端口服务器接口和Event Select 客户端接口的实现见：Iocp.h 和 Iocp.cpp 两文件。
SWFCDB的研究与探索5 自主知识产权数据库—重点难点5.1 B+树索引B+树是稠密层次索引的一种形式，具有动态重组的能力[5]，因此能够保证其中间结点介于M/2和M之间（M为B树的阶）。要实现B+树，实现动态重组，插入和删除B+树结点时，就必须维护其结点的平衡性，这就是实现B+树算法的难点。这里把B+树的中间结点叫做索引结点，而终端结点叫做叶子结点。对于5阶B+树，每个结点最多有4个关键字，5个指向子树的指针，而B+树的平衡因子为50%，因此每个结点中至少有2个关键字（根结点除外）。5.1.1 插入平衡插入平衡分为维护叶子结点平衡和维护索引结点平衡。 图 5 1如图图 5 1所示为一个只有2层的B+树，现在将G插入树中，显然将插入EFHI所在的结点中，但是该结点中的关键字数达到了最大值4，因此叶子结点将会分裂，分裂后的图如图 5 2 所示 图 5 2 现在在图 5 2 的基础上再插入M，显然M将插入KPQZ所在的结点中，但是其父结点中的关键字达到了最大关键字数目，这时必然导致索引结点的分裂，并产生新的根结点，如图 5 3 所示。 图 5 3 5.1.2 删除平衡相比插入平衡，删除平衡要复杂得多。如果删除某结点的一个关键字，如果删除该关键字后该结点关键字数目大于或等于5/2(向上取整)-1，则不影响其平衡性，删除完成。如果被删除关键字所在结点中的关键字数目等于5/2(向上取整)-1，而和该结点相邻的兄弟结点关键字数目大于5/2(向上取整)-1，则将该相邻兄弟结点中的一个关键字旋到该结点中（如果相邻结点是左兄弟，则将左兄弟中的最大关键字右旋入该结点；如果相邻节点是右兄弟，则将右兄弟中的最大关键字左旋入该结点）。如删除图 5 3 中的关键字K后，关键字I将右旋入关键字K所在结点，删除后如图 5 4所示。 图 5 4如果待删除关键字所在的结点中的关键字数目等于 5/2(向上取整)-1,而和它相邻的兄弟结点有关键字数目也等于 5/2(向上取整)-1，则将待删除关键字所在结点和兄弟结点合并。这种合并必然导致其父节点（索引结点）中的关键字数减1，如果父结点中的关键字数目（未删除结点前）等于 5/2(向上取整)-1，则导致父结点的平衡因子在50%以下，因此必须处理索引结点的平衡。现在先在图 5 4的基础上顺序插入X，Y，M，N，L，S，T，R。插入后的B+树结点图如图 5 5所示。删除关键字T,Z后，T,Z所在的结点均等于5/2(向上取整)-1，满足平衡因子50%，删除结束。现在删除关键字R，此时R所在的结点关键字数目 图 5 5等于5/2(向上取整)-1，删除R后该结点的关键字数目小于5/2(向上取整)-1，而其左兄弟的关键字数目等于5/2(向上取整)-1（如果大于5/2(向上取整)-1，则执行右旋操作），将执行叶子结点合并操作，叶子结点合并后（如果父结点的关键字数目大于或等于5/2(向上取整)-1，则删除结束），其父结点的关键字数目也小于5/2(向上取整)-1，因此父节点要执行索引结点合并操作。删除R关键字后的B+树结点图如图 5 6所示。 图 5 6维护叶子结点的平衡采用了左（右）兄弟右（左）旋一关键字和合并叶子结点的方法，同样维护索引结点也需采用以上两方法。在删除R关键字的过程中，涉及到了索引结点的合并，下面删除关键字D将涉及到索引结点的左旋。关键字D所在结点的关键字数目等于5/2(向上取整)-1，则删除D后关键字数目小于5/2(向上取整)-1，同样叶子结点合并后，此时索引结点的关键字数目小于5/2(向上取整)-1，这时应该执行索引结点的合并或旋转，但是D所在结点的父结点此时只有右兄弟，且其关键字数目达到了结点所能容纳的最大值，因此不能执行索引结点的合并，而执行索引结点的左旋操作。删除关键字D后B+树结点如图 5 7所示。 图 5 75.1.3 B+树算法难点总结B+树算法的难点是维护结点在插入和删除关键字后的结点平衡性。插入平衡通过叶子结点分裂和索引结点分裂来实现，而删除平衡则通过叶子结点的左（右）旋转，叶子结点合并和索引结点的左（右）旋转，索引结点合并来实现。与B树（B-树）相比，B+树在插入算法上要简单，而在删除算法上要复杂。以上两节的介绍只是说明算法的基本原理，而在具体的算法设计中，则更应该考虑更多的实现细节。如：合并索引结点时应该将合并的结点指向新的父结点；插入关键字时，如果结点分裂，产生新的结点，如果预先生成的B+树结点空间都用完了，则应该生成若干新的结点空间；删除关键字时，如果有结点的合并，则应该回收结点空间等。目前B+树算法采用的关键字类型为字符类型，可通过模版类思想[9]将其扩充为支持其他类型和自定义类型，如果为自定义类型，则需重载“ < ”运算符。5.2 完成端口(IOCP)完成端口采用了重叠I/O的机制，下面比较下完成端口与其他I/O模型产生性能差异的原因。默认情况下，每个socket 在系统底层都有一个发送和接收缓冲区。当发送数据时，实际上是把数据复制到发送数据缓冲区中，然后用WSASend()发送，并返回。但是如果发送缓冲区已满，则WSASend()中指定的缓冲区就会被锁定到系统的非分页内存池中，函数返回WSA_IO_PENDING，说明目前网络忙，一旦网络空闲时，数
SWFCDB的研究与探索据就从刚才提交的缓冲区中直接被发送出去，与其他I/O模型的“程序数据缓冲区 socket 底层缓冲区网络”相比节省了一次复制操作。对于WSARecv()操作，正常接收数据时，直接将socket 底层缓冲区数据复制到程序数据缓冲区，但是如果接收缓冲区中暂时没有数据，那WSARecv()中指定的缓冲区就会被锁定到系统非分页内存池以等待数据到来，当数据到来时直接将数据从网络复制到刚才指定的程序数据缓冲区，因而又节约了一次内存复制。5.2.1 回调机制为使完成端口I/O模型对数据的处理具有伸缩性及可扩张性，对接收数据的处理采用回调机制[6]或多态（即重写CIocp类虚函数IOCPRecv()）。对于回调机制，只需在启动服务器器函数（IOCPStart()）中，将数据处理函数名作为参数就可实现回调机制。回调函数原型声明为：typedef void (*LPIOCP_RECV_CALLBACK)(TASK_QUEUE_ITEM tqi, CIocp* pIocp);5.2.2 线程池设计线程池线程由管理者线程和工作者线程组成。管理者线程如何分配工作者线程任务以及协调多线程程序设计中的同步与异步问题，是设计线程池的一个难点。本线程池采用Event对象[9]，通过程序控制Event对象的激发和非激发状态，来实现管理者线程对工作者线程的控制。SetEvent()函数设置Event对象为激发状态，ResetEvent()函数设置Event 对象为非激发状态。在工作者线程创建时，管理者线程传给工作者的参数中包含hEvent和hEventWorkFinished两个Event对象，这两个Event对象就是实现线程池的关键。函数：DWORD WaitForSingleObject ( HANDLE hHandle, DWORD dwMilliseconds);的作用是当hHandle 指向的对象处于激活状态时，函数返回，否则函数一直阻塞。将该函数用在循环中，通过控制hHandle指向的对象的状态就可以控制线程的阻塞和非阻塞状态。函数：DWORD WaitForMultipleObjects( DWORD nCount, const HANDLE* lpHandles, BOOL bWaitAll, DWORD dwMilliseconds);是上面WaitForSingleObject()函数的扩展版本，同时可以检测多个HANDLE对象的状态，管理者线程将用该函数实现对多个Event 对象进行检测（hRecvEvent激活为接收数据队列中有未处理数据）。创建工作者线程时，hEvent和hEventWorkFinished处于非激活状态，工作者线程和管理者线程处于阻塞状态，当接收数据队列中存在未处理数据时，设置hRecvEvent为激活状态，则管理者线程激活（处于非阻塞状态），从接收数据队列中取出队头未处理任务（设置hRecvEvent为非激活状态），然后设置hEvent对象为激活状态（此时管理者线程可能又处于阻塞状态），工作者线程被激活，然后工作者线程设置hEvent为非激活状态，工作者线程处理任务，当处理完任务后，工作者线程设置hEventWorkFinished对象为激活状态（此时工作者线程处于阻塞状态，等待hEvent对象再次被激发），管理者线程知道该工作者线程已完成任务，检查任务队列中是否有未处理任务，如果有，则取出任务，设置hEvent为激活状态，工作者线程处理任务；如果没有，则管理者线程结束此次循环进入下次循环。如此循环，则实现了管理者线程对工作者线程的任务分配。
SWFCDB的研究与探索6 总结在这次毕业设计中，我主要完成了以下几件事：(1)学习了2005届同学的论文和第一层接口实现代码，对部分接口进行修改并完善相关功能，添加了几种数据类型（如 short, long, float, double, char），并实现了将各字段名及各字段数据类型存入建库信息；新增SplitPage()，ReturnAllRows()等函数，实现了记录页的分裂和快速返回数据表中所有记录的功能。具体实现见：FirstLayer.h 和FirstLayer.cpp 。(2)完成B+树算法的研究与探索，实现了B+树算法创建B+树文件索引，并将该算法封装在CBPTreeIndex类中。提供：CreateBPTreeIndex()，OpenBPTreeIndex()，InsertBPTree()，DeleteKey()，TraverseBPTree()，Find()等方法操作B+树索引。具体实现见：BPTreeIndex.h 和BPTreeIndex.cpp。(3)完成了数据库第二层的基本设计，基本实现了图形用户界面对第一层功能的管理。实现了可视化新建数据库，删除数据库，新建表，删除表，插入记录，返回记录等功能。具体实现见：DBTreeView.h，DBTreeView.cpp，DBListView.h，DBListView.cpp，TableView.h 和TableView.cpp。(4)完成了完成端口（I/O Completion Port）网络模型研究与探索，实现了基于完成端口模型的服务器接口和基于Event Select I/O 模型的客户端接口，并将完成端口服务器接口封装在CIocp类中，客户端接口封装在CEventClent类中。具体实现见：Iocp.h 和Iocp.cpp。
参考文献[1] 郭晔. 数据库新技术浅析.中图分类号: TP311.131, 文献标识码: B 文章编号: 1004-373X[2] 阎同喜. 数据库技术发展概述. 中图分类号: TP131.13 文献标识码: B 文章编号:1003-773X(2004)[3] 曹亚玲 自主知识产权数据库底层设计及接口实现[4] 张蓉 自主知识产权数据库初探[5] 张金明 自主知识产权数据库物理层索引技术的探索与实现[6] 谭浩强 C++程序设计.北京:清华大学出版社,2004.6[7] 严蔚敏，吴伟明,等.数据结构(C语言版).北京:清华大学出版社,1996[8] Anthony Jones, Jim Ohlund, 等 Windows 网络编程（第2版）.北京: 清华大学出版社2002.10[9] Jim Beveridge, Robert Wiener, 等 Win32多线程程序设计. 武汉: 华中科技大学出版社 2002.2[10] Stanley B.Lippman, Josee Lajoie, 等 C++ Primer（第三版）. 北京: 中国电力出版社 2005.2[11] Robert Sedgewick. 算法I-IV(C++实现).北京:中国电力出版社,2004[12] Tom Archer, Andrew Whitechapel, 等 Visual C++ .NET 宝典.北京:电子工业出版社,2003.2[13] Garcia-Molina, H, Ullman, J. D. , Widom, J. ,等. 数据库系统全书.北京: 机械工业出版社，2003.8
指导教师简介
赵X1960年出生，硕士、副教授。承担的主要课程：C++程序设计，组件技术，人工智能等主要研究方向为数据库设计、数据挖掘、模式识别，已发表《数据挖掘的关联规则研究》等多篇论文，主持和参加了多个科研项目。 论文致谢在此我要真诚地感谢我的指导老师赵X老师，感谢您在繁忙的工作之于，抽出时间指导我的毕业设计，并仔细审阅我的论文，给予了很多很好的建议；同时我也要感谢这四年中指导过我的所有老师，是你们让我打下良好的基础让我能够顺利完成本次毕业设计；最后感谢所有关心和帮助过我的朋友们，是你们让我的大学生活充实而精彩。
