欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

一个简易数据库的实现 ---- APUE chapter 20 A Database library

程序员文章站 2024-02-03 08:39:22
...

A Database library 我会说明天上午十点考数据库,我现在还在写博客... 什么心态 QAQ 我还是忍不住吐槽, 那个数据库的课上的.... (此处省略一万五千字的感想) --------------------------------------------------------------------------------------------

A Database library

我会说明天上午十点考数据库,我现在还在写博客... 什么心态 QAQ


我还是忍不住吐槽, 那个数据库的课上的.... (此处省略一万五千字的感想)

----------------------------------------------------------------------------------------------------------------


正题... 之前一直搁置了 APUE的后面几章, 明天考数据库, 今天心血来潮, 反正APUE提供了实现一个数据的思路,

不妨我们自己写一个数据库. 哼╭(╯^╰)╮ 就是这么傲娇~

名字我的都想好了, 数据库的名字就叫 ..... jasper.


声明: 这个数据库不是我原创的(K神作品, 我完全... 不是一个数量级的),我会对其进行稍稍的改动...

先摆结果吧,有兴趣就看下去,也可以和我一起讨论,jasonleaster@gmail.com,没兴趣,浏览器点击X.


本来是想像很正规的成熟数据库那样,搭个shell出来的,感觉交互界面的字符串语法命令的分析有点**

于是,就这样凑合着先表示概念吧~ 想测试或者使用这个"玩具"数据库,需要一定的C语言基础,然后调用提供好的API即可. 


为了能够操作数据库,我们必须写个简单的调用程序~

#include "apue_db.h"
#include 
#include 

#define STRING_SZ 100
#define DATA_SET  3

int main()
{

	char str_key[DATA_SET][STRING_SZ] = {
					      {"Alpha"},
					      {"Belta"},
					      {"Gama"}
					     };

	char str_dat[DATA_SET][STRING_SZ] = {
					      {"data1"},
					      {"data2"},
				     	      {"data3"}
				    	    };

	DBHANDLE handler = db_open("./database",
				   O_CREAT | O_TRUNC | O_RDWR,
				   FILE_MODE);


	if(db_store(handler,str_key[0],str_dat[0],DB_INSERT) != 0)
	{
		printf("Error! db_store failed in function %s\n",
			                            __FUNCTION__);

		printf("Trying to store key:%s\t data:%s\n",
				      str_key[0],str_dat[0]);

		goto failed;
	}

	if(db_store(handler,str_key[1],str_dat[1],DB_INSERT) != 0)
	{
		printf("Error! db_store failed in function %s\n",
			                            __FUNCTION__);

		printf("Trying to store key:%s\t data:%s\n",
				      str_key[1],str_dat[1]);

		goto failed;
	}

	if(db_store(handler,str_key[2],str_dat[2],DB_INSERT) != 0)
	{
		printf("Error! db_store failed in function %s\n",
			                            __FUNCTION__);

		printf("Trying to store key:%s\t data:%s\n",
				      str_key[2],str_dat[2]);

		goto failed;
	}

failed:
	db_close(handler);

	return 0;
}


显然,我们想利用db_store来根据str_key来储存str_dat里面的数据


一个简易数据库的实现 ---- APUE chapter 20 A Database library

就这样把数据储存在了database.dat中,并且利用database.idx 进行索引


当然,我想看我啰啰嗦嗦写到这里的人是想看怎么实现的...

特地用分割线划开了.下面主要是个人的想法,或者遇到的个人觉得可能是难点的地方.

并不是"介绍如何搞定这个数据库". RTFSC :)


有任何对这个数据有兴趣的viewer, 希望能通过邮箱交流jasonleaster@gmail.com

Don't panic

-------------------------------------------------------------------------------------------------------------------

如果觉得书上的代码风格不和口味,可以试试,去github拿我自己重新写的源代码

不懂的地方再对照书上的注释看就是了

https://github.com/jasonleaster/APUE_study_source_code/tree/liu/chapter_20



数据库的设计:

这个简易的数据库由两个文件构成---- index file & data file.

一个索引文件,一个数据文件. 实现索引和储存的数据进行分离. 在我个人看来, 这样做无非是让构架看得清晰.

试想,用一个文件来表述数据库的话,会很"乱", 冗长, 杂. Do you think so ? : ) 不得不佩服这些设计者的思想.

一个简易数据库的实现 ---- APUE chapter 20 A Database library

图1


最最值得强调的就是, 我们在储存地址指针的时候, 即图中你所看到所有有关ptr的标识符.

他们的储存形式都是ASCII码! 再三强调, 不然看代码会看哭的.

这是数据库设计的一大亮点,由于数据库的数据可能会被用在不同的系统,不同的硬件平台上面, 会由于系统表示数据的方式不同(大小端, 指针长度,等), 而导致数据可能不一致. 这时候有个办法,直接用ASCII码表示,以字符串的形式存在.

比方说地址 0x0010 就直接用 "16"来表示和储存.简直酷帅....


设计者假设了指针的最大长度为十进制的6位数.

一个简易数据库的实现 ---- APUE chapter 20 A Database library

图2

那个999999 == 10^(PTR_SZ) - 1


对于数据库可以进行的哪些操作,定义了以下API. (之后我会写一个类似于shell的东东, 使得控制这个数据库的语法像MySQL的语法,肯定不会是完全实现MySQL的语法,但是会很naive 很有意思, 这样以来, 最起码简单数据库的实现原理就明白了, 专杀纸老虎).

一个简易数据库的实现 ---- APUE chapter 20 A Database library

图3


用结构体DB , 对整个数据库进行抽象. 我们所有的API,不过是围绕这个对象打转转而已, 变着花样操作这个database.

我们把所有能用来描述一个数据库的东东,都写到这个结构体里面了, 这种思想的本质就是OO.

/*
 * Library's private representation of the database.
 */
typedef struct {
  int    idxfd;  /* fd for index file */
  int    datfd;  /* fd for data file */
  char  *idxbuf; /* malloc'ed buffer for index record */
  char  *datbuf; /* malloc'ed buffer for data record*/
  char  *name;   /* name db was opened under */
  off_t  idxoff; /* offset in index file of index record */
			      /* key is at (idxoff + PTR_SZ + IDXLEN_SZ) */
  size_t idxlen; /* length of index record */
			      /* excludes IDXLEN_SZ bytes at front of record */
			      /* includes newline at end of index record */
  off_t  datoff; /* offset in data file of data record */
  size_t datlen; /* length of data record */
			      /* includes newline at end */
  off_t  ptrval; /* contents of chain ptr in index record */
  off_t  ptroff; /* chain ptr offset pointing to this idx record */
  off_t  chainoff; /* offset of hash chain for this index record */
  off_t  hashoff;  /* offset in index file of hash table */
  DBHASH nhash;    /* current hash table size */
  COUNT  cnt_delok;    /* delete OK */
  COUNT  cnt_delerr;   /* delete error */
  COUNT  cnt_fetchok;  /* fetch OK */
  COUNT  cnt_fetcherr; /* fetch error */
  COUNT  cnt_nextrec;  /* nextrec */
  COUNT  cnt_stor1;    /* store: DB_INSERT, no empty, appended */
  COUNT  cnt_stor2;    /* store: DB_INSERT, found empty, reused */
  COUNT  cnt_stor3;    /* store: DB_REPLACE, diff len, appended */
  COUNT  cnt_stor4;    /* store: DB_REPLACE, same len, overwrote */
  COUNT  cnt_storerr;  /* store error */
} DB;


之前图3定义了很多操作DB的API,那么我们来一个个看这些API的实现.

上面的图3的API实现以来下面这些函数. 提一次深刻的体会到什么叫做接口与实现的分离...以后我也要这么干

一个简易数据库的实现 ---- APUE chapter 20 A Database library

图4


代码接近10^3 所以不一一拿出来扯了. 记录我觉得关键的部分吧

db_open(const char *pathname, int oflag, ...)

一个简易数据库的实现 ---- APUE chapter 20 A Database library

图5

根据pathname提供的文件名, 计算文件名的字符串长度(不包括NUL)

然后传递给_db_alloc(len), 这个_db_alloc会真正的返回一个DB结构体和我们的文件名pathname所指字符相关联.


一个简易数据库的实现 ---- APUE chapter 20 A Database library

图6

这里我们得到了初始的数据库之后,就开始初始化它, 确定好hash table在index file中的起始位置(HASH_OFF 6)以及hash table总的大小(NHASH_DEF 137), 这里的6 就是前面的PTR_SZ, 也就是说 index file的前6 byte是空出来的.

,每个hash 单元是PTR_SZ大小,一共有 NHASH_DEF个. 前面空出来的6bybe是故意的, 用来记录一个指针(用字符串表示的). 这个指针用法很特别, 后面会讲明白的, 叫free list pointer(这家伙折腾我好久).


_db_alloc

会注意到这里 malloc有分别的+ 5 , 2, 2. 这是因为db->name的时候要考虑 我们的数据库文件命名方式,要添加.dat

于是这里".dat" 就是5个char. 然后后面两个+2 是考虑到字符串输入的时候我们会带有 \n 和 NUL.

这确保了我们定义IDXLEN_MAX 和 DATLEN_MAX的严谨性!

一个简易数据库的实现 ---- APUE chapter 20 A Database library

图7

db_close 和_db_free() 感觉都很简单,只是APUE作者实现的时候有点略微..稍微.. 不安全.

API参数的指针没有进行NULL检测.

一个简易数据库的实现 ---- APUE chapter 20 A Database library

图8

万一db 是NULL 就跪的稳稳的了



db_fetch()

该函数用来根据key查找数据库中是否已经有了该项数据.

没什么值得强调的,这就是个接口, 成功找到了对应数据, OK.那返回一个指针ptr,

这个指针指向要查找的数据(指向data file)


接口的核心在于_find_and_lock()



_find_and_lock()

根据key指向的字符串,计算hash值, 然后确定hash表的入口,尝试找到对应项.

第三个参数,writelock, 旨在提供防止并发是带来的抢占问题.

read_lock 保证仅可读不可写, write_lock 既不可读也不可写.


一个简易数据库的实现 ---- APUE chapter 20 A Database library

图9

上面也看到了, db->chainoff 通过hash加上初始的hash table的起始偏置得到.

根据chianoff通过_db_readptr去找hash table 对应位置的数据,这个数据就是index的地址标记.

如果这个地址为0, while循环进不去, 最后返回-1, 提示_find_and_lock失败,就是说, 根据参数key,没有对应的数据.

如果offset非零,说明我们有可能找到了对应的数据.

只有真正一个个比对key ,而不是简单的hash值相同. 才可以判定找到了对应数据.

如果找到了,那么break 跳出while循环, 返回0. 提示我们找到这家伙了.

如果沿着hash chian的单向链表一直没找到,我们就会遇到_db_readidx返回0, 提示_find_and_lock失败.

一个简易数据库的实现 ---- APUE chapter 20 A Database library

图10

值得注意的是图10会有调用_db_readidx()

这个函数会更新data file的文件偏置,即db->datoff.

一个简易数据库的实现 ---- APUE chapter 20 A Database library


后记:

本来以为一天可以搞定的,磨磨蹭蹭搞了两天这东西......





摄于某教室 极力的试图通过空旷的场景和黑白的沉闷,表现当代高校学生的迷茫,无从与困惑


一个简易数据库的实现 ---- APUE chapter 20 A Database library