DIY DB---编写你自己的DB（1）

打算利用自己的业余时间，将APUE上的DB动手进行实际操作演练一遍，以加深自己的对DB的理解。

将采用分而治之的思想，首先讲解源文件，makefile，然后从最重要的函数开始讲起，最后给出gdb调试步骤。

数据库的函数库使用两个文件来存储信息：

索引文件

数据文件

索引文件包含键值（通过hash）以及指向该键值所对应数据的指针，本文中采用取模的方法，

此处的指针同C中的指针不是一个概念，但是功能是类似的，不要混淆）

数据文件 主要包含数据记录（同我们常见DB中的record相对应）

索引文件使用固定大小的hash表来存储键值（大小为137），这也就意味着即使存储的数据时均匀分布，在插入137条记录（最理想的情况下），当继续插入138条记录，将会产生哈希冲突，解决方法是使用链表法解决解决散列冲突。

需要说明的索引文件与数据都是采用ascii形式进行存储，这样才不同的平台就可以实现共享。

由于本文采用C实现，而C中没有字符串变量，因此对字符的处理仍然是采用C的惯例，以'\n'表示。

索引文件的构成如下：

FREE POINTER|HASH POINTER HP1| HASH POINTER HP2|......|HASH POINTER HP137\n

紧跟着hash指针的INDEX RECORD

INDEX RECORD的构成如下：

OFFSET_OF_NEXT_INDEX_RECORD|

INDEX_RECORD_LENGTH|KEY|SEPERATOR|

OFFSET_OF_DATA_RECORD|SEPERATOR

|LENGTH_OF_DATA_RECORD\n

INDEX RECORD 的构成相对来说比较简单，第一个字段表示指向下一个 INDEX RECORD OFFSET，

INDEX_RECORD_LENGTH 该条 INDEX_RECORD的长度，这两个字段为定长字段

剩下三个字段KEY 键值,OFFSET_DATA_RECORD(IN DATA FIEL) 数据记录在数据文件中的偏移量,LENGTH_OF_DATA_RECORD，该键值所对应的数据记录的长度，使用separator分隔符来分隔，具体实现的时候，使用STRCHR来定位字符，从而计算出每一个字段的长度。

如下图所示：

数据文件相对来说比较简单，都是使用\n来分隔的字符串，每一个数据记录对应不同的偏移量。

下面是具体的实现部分。

文件source的整体布局如下：

ubuntu@ubuntu-virtual-machine:~/Desktop/mydb/diydb$ ls
apue.c  apue.o  db.h  error.c  main    makefile
apue.h  db.c    db.o  error.o  main.c  

使用过的makefile如下
ubuntu@ubuntu-virtual-machine:~/Desktop/mydb/diydb$ cat makefile
main:apue.o error.o db.o
    gcc -Wall -g -o main apue.o error.o db.o main.c
    rm db4.*
apue.o:apue.c
    gcc -c apue.c
error.o:error.c
    gcc -c error.c
db.o:db.c
    gcc -c db.c
为了便于理解，我将从DB.C函数开始讲解。该函数包含了我们DB的最主要的实现。

首先说点题外话，由于C的函数必须是先定义后使用，因此函数定义的顺序一定早于

函数调用的顺序，以防止不必要的错误。

每一个DB在创建的时候，都包含两个文件，一个是数据文件，一个是索引文件。索引文件使用hash值

来进行数据的访问。因此首先讲解hash函数的实现。

static  DBHASH
_db_hash(DB *db,const char *key ) {
    DBHASH hval = 0;
    char c;
    int i;
    for ( i = 1;(c = *key++) !=  0;i++)
        hval +=c*i; /*  ascii char times its 1-based index */
    return(hval % db->nhash);
}

该函数首先取每一个字符的ascii值乘以自己在字符中位置，然后将所有的值进行加和，最后采用最常用的hash计算方法获得哈希值。

其中db->nhash为DBhash表的大小，为137。在本例中为常量，采用宏定义来实现，便于扩展。

写到这里，为了后面叙述方便，我们首先给出头文件。

#ifndef    _APUE_DB_H
#define    _APUE_DB_H

typedef void * DBHANDLE;
DBHANDLE db_open(const  char * ,int,...);
void db_close(DBHANDLE);
char * db_fetch(DBHANDLE,const char *);
int db_store(DBHANDLE,const char *,const char *,int );
int  db_delete(DBHANDLE,const char *);
void db_rewind(DBHANDLE);
char * db_nextrec(DBHANDLE,char *);

/*
 * Flags for db_store()
 */
#define DB_INSERT  1   /* insert new record only */
#define DB_REPLACE 2   /* replace existing record*/
#define DB_STORE   3   /* replace or  insert */

/*
 * implementation limits
 */

#define IDXLEN_MIN 6  /* KEY SEP START,SEP,length \n*/
#define IDXLEN_MAX 1024 /* ARBITRARY  */
#define DATLEN_MIN 2 /* data byte ,newline */
#define DATLEN_MAX 1024/* ARBITRARY */
#endif /* _APUE_DB_H */

发现现在描述到这里，讲解有点纠结，感觉思路不是太好，或许我应该从DB的架构上把思路理清楚，那样再讲函数的实现会好一点。为此，首先给出DB的结构。

typedef unsigned long count;  /* unsigned counter */
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 inde file of index record */
                            /*  key is at (idxoff+PTR_SZ+IDXLEN_SZ) */
    off_t idxlen;           /*  length of the index file record */
    size_t datlen ;         /* length of data record */
                            /* includes newline at end */
    off_t  datoff ;         /* offset in the data file  of data record*/
    off_t ptrval  ;         /* contents of the chain ptr in index record */
    off_t ptroff  ;         /* chain ptr offset  pointing to this index record */
    off_t chainoff;        /* offset of hash chain of this index record */
    off_t hashoff ;         /*offset in the index file of hash table */
    DBHASH nhash ;          /* current hash table size ;*/
    COUNT  cnt_delok;       /* delete ok */
    COUNT  cnt_delerr;      /* delter error */
    COUNT  cnt_fetchok;     /* fetch ok */
    COUNT  cnt_fetcherr;    /* fetch error */
    COUNT  cnt_nextrec ;    /* nextrec */
    COUNT  cnt_stor1;       /* store: DB_INSERT,no empty,append */
    COUNT  cnt_stor2;       /* store: DB_INSERT,found empty,reused */
    COUNT  cnt_stor3;       /* store: DB_REPLACE,difflen,append */
    COUNT  cnt_stor4;       /* store: DB_REPLACE,samelen,override */
    COUNT  cnt_storerr;       /* store: DB_REPLACE,samelen,override */
}DB;

从该结构的定义，不难看出，该结构体定义了两个文件描述符，一个用来指向DB 索引文件，一个指向DB的数据文件。然后定义了两个buffer，用来临时存储DATA RECORD，INDEX RECORD。

name 定义了该数据的名字，这个应该是最好理解的。

当一个新的DB创建以后，该DB所对应的图示（现在的理解，不一定全对）

待续---------------------