首页 > 代码库 > 一个简易数据库的实现 ---- APUE chapter 20 A Database library
一个简易数据库的实现 ---- APUE chapter 20 A Database library
A Database library
我会说明天上午十点考数据库,我现在还在写博客... 什么心态 QAQ
我还是忍不住吐槽, 那个数据库的课上的.... (此处省略一万五千字的感想)
----------------------------------------------------------------------------------------------------------------
正题... 之前一直搁置了 APUE的后面几章, 明天考数据库, 今天心血来潮, 反正APUE提供了实现一个数据的思路,
不妨我们自己写一个数据库. 哼╭(╯^╰)╮ 就是这么傲娇~
名字我的都想好了, 数据库的名字就叫 ..... jasper.
声明: 这个数据库不是我原创的(K神作品, 我完全... 不是一个数量级的),我会对其进行稍稍的改动...
先摆结果吧，有兴趣就看下去，也可以和我一起讨论，jasonleaster@gmail.com，没兴趣，浏览器点击X.
本来是想像很正规的成熟数据库那样，搭个shell出来的，感觉交互界面的字符串语法命令的分析有点＊＊
于是，就这样凑合着先表示概念吧～ 想测试或者使用这个＂玩具＂数据库，需要一定的Ｃ语言基础，然后调用提供好的API即可．
为了能够操作数据库，我们必须写个简单的调用程序～
#include "apue_db.h"
#include <stdio.h>
#include <fcntl.h>
#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里面的数据
就这样把数据储存在了database.dat中，并且利用database.idx 进行索引
当然，我想看我啰啰嗦嗦写到这里的人是想看怎么实现的．．．
有任何对这个数据有兴趣的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 ? : ) 不得不佩服这些设计者的思想.
图1
最最值得强调的就是, 我们在储存地址指针的时候, 即图中你所看到所有有关ptr的标识符.
他们的储存形式都是ASCII码! 再三强调, 不然看代码会看哭的.
这是数据库设计的一大亮点,由于数据库的数据可能会被用在不同的系统,不同的硬件平台上面, 会由于系统表示数据的方式不同(大小端, 指针长度,等), 而导致数据可能不一致. 这时候有个办法,直接用ASCII码表示,以字符串的形式存在.
比方说地址 0x0010 就直接用 "16"来表示和储存.简直酷帅....
设计者假设了指针的最大长度为十进制的6位数.
图2
那个999999 == 10^(PTR_SZ) - 1
对于数据库可以进行的哪些操作,定义了以下API. (之后我会写一个类似于shell的东东, 使得控制这个数据库的语法像MySQL的语法,肯定不会是完全实现MySQL的语法,但是会很naive 很有意思, 这样以来, 最起码简单数据库的实现原理就明白了, 专杀纸老虎).
图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实现以来下面这些函数. 提一次深刻的体会到什么叫做接口与实现的分离...以后我也要这么干
图4
代码接近10^3 所以不一一拿出来扯了. 记录我觉得关键的部分吧
db_open(const char *pathname, int oflag, ...)
图5
根据pathname提供的文件名, 计算文件名的字符串长度(不包括NUL)
然后传递给_db_alloc(len), 这个_db_alloc会真正的返回一个DB结构体和我们的文件名pathname所指字符相关联.
图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的严谨性!
图7
db_close 和_db_free() 感觉都很简单,只是APUE作者实现的时候有点略微..稍微.. 不安全.
API参数的指针没有进行NULL检测.
图8
万一db 是NULL 就跪的稳稳的了
db_fetch()
该函数用来根据key查找数据库中是否已经有了该项数据.
没什么值得强调的,这就是个接口, 成功找到了对应数据, OK.那返回一个指针ptr,
这个指针指向要查找的数据(指向data file)
接口的核心在于_find_and_lock()
_find_and_lock()
根据key指向的字符串,计算hash值, 然后确定hash表的入口,尝试找到对应项.
第三个参数,writelock, 旨在提供防止并发是带来的抢占问题.
read_lock 保证仅可读不可写, write_lock 既不可读也不可写.
图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失败.
图10
值得注意的是图10会有调用_db_readidx()
这个函数会更新data file的文件偏置,即db->datoff.
后记:
本来以为一天可以搞定的，磨磨蹭蹭搞了两天这东西......
摄于某教室 极力的试图通过空旷的场景和黑白的沉闷，表现当代高校学生的迷茫，无从与困惑
一个简易数据库的实现 ---- APUE chapter 20 A Database library