MyBase?文件存储结构的设计
zhaokai@hit.edu.cn
MyBase是一个正在设计的轻量级数据库管理系统（DBMS）。MyBase以现有商业DBMS为蓝本，试图设计一个“Simple”DBMS，在其上体现数据库管理系统的基本原理。当前的目标是：
①支持SQL语句的子集；
②支持内存算法，即查询的空间复杂度小于当前内存可用空间的大小。
MyBase的系统结构如下图：
Figure 1 MyBase系统结构
查询优化器是DBMS的重要组成部分，我们将其划分到执行引擎中。本文主要介绍MyBase的文件系统及文件缓存的设计。
一：设计环境：Windows操作系统，利用Windows API实现。
二：数据存储方式：我们主要利用OS的文件系统来存储表和索引。
三：数据库数据字典的组织形式：数据库的字典将存储在.dic结尾的文件中，其包括每一个表建立的时间、表中元组的个数、每一个元组的属性、该属性的类型、长度、是否为主键、是否为空等。
四：数据库中表的存储组织方式：每一个表存储在以.mdb结尾的文件中。元组在文件中的以定长组织方式如下：
Figure 2 元组在文件中的存储格式
举例如下：
?e.g create table student
( id int primary key,
name char(20) not null,
age int )
Figure 3 举例
可将是否为空的标志以位图形式存储（这也是SqlServer 2k的存储方法），所以对该存储结构的改进如下：
Figure 4 将是否为空标志以位图形式存储
五：对读到缓存中元组的存取控制
文件中得元组将读到表空间的cache中，下面说明如何存取cache中的元组。
对于一个元组中的每一个属性都有一个内存结构来控制该属性的存取，包括该属性值是否为空、属性的名称、属性的长度、属性的类型、是否为主键以及指向该属性值在cache中的地址的指针。其对应于struct tagAttribute。
Figure 5 对Cache元组的控制的元数据结构
举例如下：
Figure 6 举例
六：文件系统的定义
文件系统设计如下（不完全?）：
//MyBase_FileSystem.h
#ifndef __MYBASE_FILESYSTEM
#define __MYBASE_FILESYSTEM
#include
#include
#define MAX_NAME_LENGTH10 //属性名称的长度
#define MAX_ATTRIBUTE_NUMBER20 //关系中属性的个数
#define TABLE_CACHE_SIZE8192 //8K
#define TABLE_FILE_NAME_LENGTH11 //8+3
#define TABLE_SPACE_NUMBER 10 //表空间的个数
#define TYPE_FLOAT 0
#define TYPE_INT 1
#define TYPE_STRING 2
#define TYPE_DATE 3
#define TYPE_CHAR 4
#define PRIMARY_KEY 0
#define NOT_PRIMARY_KEY 1
#define NULLABLE 0
#define DIS_NULLABLE 1
//关系中的属性
struct tagAttribute
{
INT type; //该属性的的类型 4
CHAR name[MAX_NAME_LENGTH]; //属性名称 10
CHAR* ptr;//该属性在内存中的地址 4
UINT length; //该属性的长度 4
BOOL is_primary_key;//是否为主键 4
BOOL is_null; //是否可以为空 4
CHAR reserved[2];//保留，填满32字节
};
typedef struct tagAttribute Attribute;
typedef struct tagAttribute* pAttribute;
struct tagTableSpace
{
SYSTEMTIME create_table_date;//该关系的创建时间
INTtuple_number;//该关系的元组的总个数
INT tuple_length;//每个元组的长度
INT attribute_number;//该关系的属性个数
Attributeattribute_list[MAX_ATTRIBUTE_NUMBER]; //该关系的属性
INT current_index; //当前在缓冲中所指的记录的索引
CHAR*ptr_current_index;//当前在缓冲中所指的记录的指针
CHAR cache[TABLE_CACHE_SIZE];//关系的缓冲
INT tuple_number_in_cache;//当前调入缓存的元组个数
INT begin_index;//当前在缓冲中所指的记录的索引的最小值
INT end_index;//当前在缓冲中所指的记录的索引的最大值
HANDLE table_file_handle;//表文件句柄
CHAR table_file_name[TABLE_FILE_NAME_LENGTH];//表文件名称
BOOL is_table_file_open; //该文件是否打开
BOOLis_table_space_open;//判断该关系是否打开
};
typedef struct tagTableSpace TableSpace;
typedef struct tagTableSpace* pTableSpace;
pTableSpace table_space[TABLE_SPACE_NUMBER];
INT iTableSpaceMap[TABLE_SPACE_NUMBER];//记录可使用空表空间的位图
//底层文件和缓冲区的操作
BOOL Seek_Nth_Tuple_In_File();//将文件指针移到第N个元组
BOOL Seek_First_Tuple_In_File();//将文件指针移到第一个元组
BOOL Seek_Next_Tuple_In_File();//将文件指针移到当前元组的下一个元组
BOOL Seek_Previous_Tuple_In_File();//将文件执针移到当前元组的前一个元组
BOOL Update_Table_Space_In_File();//更新表空间所在的文件，即将表空间中的数据重新写入文件
BOOL Load_Current_Tuple_From_File_To_Cache();//将当前文件指定的元组从文件调入缓存，同时
BOOL Load_Nth_Tuple_From_File_To_Cache();//将当前文件指定的第N个元组从文件调入缓存
BOOL Save_Current_Tuple_In_Cache_To_File();//将当前在缓存中修改的元组重新写入文件
BOOL Save_Nth_Tuple_In_Cache_To_File();//将缓存中修改的第N个元组重新写入文件
BOOL Get_Nth_Attribute_Value_From_Current_Tuple_In_Cache();//获得当前元组的第N个属性值
BOOL Update_Nth_Attribute_Value_From_Current_Tuple_In_Cache();//更新当前元组的第N个属性值
BOOL Is_Table_File_Open();//判断该表文件是否打开
//表空间的操作
BOOL Load_Table_Space();//打开表空间
BOOL Create_Empty_Table_Space();//建立一个空的表空间
BOOL Save_Table_Space();//保存表空间到文件
BOOL Close_Table_Space();//关闭表空间
BOOL Is_Table_Space_Open();//判断表空间是否打开
INT Get_Available_Table_Space_Index()//获得现在可以使用的表空间的下标，利用iTableSpaceMap
#endif
七：MyBase还处于设计阶段，结构还不是非常清楚，摆在前面的问题还很多，
希望感兴趣的xdjm们多多指教，互相交流，共同进步。
