四：数据页结构
4.1 B/H主要页结构
4.1.1结构图
4.1.2数据结构
typedef struct _db_page {
DB_LSN lsn; //LSN
db_pgno_t pgno; //页号
db_pgno_t prev_pgno; //前一页页号
db_pgno_t next_pgno; //下一页页号
db_indx_t entries; //items数量
db_indx_t hf_offset; //空闲区的高地址
#define
LEAFLEVEL 1
#define
MAXBTREELEVEL 255
u_int8_t level; //页层次，叶结点为1。
u_int8_t type; //页类型
} PAGE;
//结构大小为26字节
typedef struct __pg_chksum {
u_int8_t unused[2]; //对齐
u_int8_t chksum[4]; //chksum
} PG_CHKSUM;
typedef struct __pg_crypto {
u_int8_t unused[2]; //对齐
u_int8_t chksum[DB_MAC_KEY]; //chksum
u_int8_t iv[DB_IV_BYTES]; //iv
} PG_CRYPTO;
4.1.3相关宏功能分析
#define
P_INP(dbp, pg) /
((db_indx_t *)((u_int8_t *)(pg) + SIZEOF_PAGE + /
(F_ISSET((dbp), DB_AM_ENCRYPT) ? sizeof(PG_CRYPTO) : /
(F_ISSET((dbp), DB_AM_CHKSUM) ? sizeof(PG_CHKSUM) : 0))))
功能：
取得页中index对应的首地址。
执行流程：
1.首先加上公共的页头大小，这里为SIZEOF_PAGE（26字节）
2.判断数据库是否有DB_AM_ENCRYPT标志，如果有，则加上PG_CRYPTO结构的大小。并返回。否则执行下一步。
3.判断数据库是否有DB_AM_CHKSUM标志，如果有，则加上PG_CHKSUM结构的大小。并返回。
备注：
DB_AM_ENCRYPT总是伴随DB_AM_CHKSUM标志，所以先测试DB_AM_ENCRYPT标志。
#define
P_IV(dbp, pg) /
(F_ISSET((dbp), DB_AM_ENCRYPT) ? ((u_int8_t *)(pg) + /
SIZEOF_PAGE + SSZA(PG_CRYPTO, iv)) /
: NULL)
功能：
取得页中iv对应的首地址。
#define
P_CHKSUM(dbp, pg) /
(F_ISSET((dbp), DB_AM_ENCRYPT) ? ((u_int8_t *)(pg) + /
SIZEOF_PAGE + SSZA(PG_CRYPTO, chksum)) : /
(F_ISSET((dbp), DB_AM_CHKSUM) ? ((u_int8_t *)(pg) + /
SIZEOF_PAGE + SSZA(PG_CHKSUM, chksum)) /
: NULL))
功能：
取得chksum对应的首地址。
4.1.4.公共宏功能分析
#define
RE_NREC(p) /
((TYPE(p) == P_IBTREE || TYPE(p) == P_IRECNO) ? PREV_PGNO(p) : /
(db_pgno_t)(TYPE(p) == P_LBTREE ? NUM_ENT(p) / 2 : NUM_ENT(p)))
#define
RE_NREC_ADJ(p, adj) /
PREV_PGNO(p) += adj;
#define
RE_NREC_SET(p, num) /
PREV_PGNO(p) = (num);
功能：
记录数相关操作。
#define
P_INIT(pg, pg_size, n, pg_prev, pg_next, btl, pg_type) do { /
PGNO(pg) = (n); /
PREV_PGNO(pg) = (pg_prev); /
NEXT_PGNO(pg) = (pg_next); /
NUM_ENT(pg) = (0); /
HOFFSET(pg) = (db_indx_t)(pg_size); /
LEVEL(pg) = (btl); /
TYPE(pg) = (pg_type); /
} while (0)
功能：
初始化页。
#define
P_OVERHEAD(dbp) P_TO_UINT16(P_INP(dbp, 0))
功能：
页头长度。
#define
LOFFSET(dbp, pg) /
(P_OVERHEAD(dbp) + NUM_ENT(pg) * sizeof(db_indx_t))
功能：
空闲空间的首地址。
#define
P_FREESPACE(dbp, pg) (HOFFSET(pg) - LOFFSET(dbp, pg))
功能：
空闲空间的大小。
#define
P_ENTRY(dbp, pg, indx) ((u_int8_t *)pg + P_INP(dbp, pg)[indx])
功能：
取得特定索引的指针。
4.2 Q主要页结构
4.2.1数据结构
typedef struct _qpage {
DB_LSN lsn; //LSN
db_pgno_t pgno; //页号
u_int32_t unused0[3]; //保留
u_int8_t unused1[1]; //保留
u_int8_t type; //页类型
u_int8_t unused2[2]; //保留
u_int8_t chksum[DB_MAC_KEY]; //28-47: Checksum
u_int8_t iv[DB_IV_BYTES]; //48-63: IV
} QPAGE;
//该结构大小为64字节
4.2.2相关宏功能分析
#define
QPAGE_NORMAL 28
#define
QPAGE_CHKSUM 48
#define
QPAGE_SEC 64
功能：
如果没有crypto或者checksumming，这些宏用来回收空间。
#define
QPAGE_SZ(dbp) /
(F_ISSET((dbp), DB_AM_ENCRYPT) ? QPAGE_SEC : /
F_ISSET((dbp), DB_AM_CHKSUM) ? QPAGE_CHKSUM : QPAGE_NORMAL)
功能：
返回实际所需的页头大小。
执行流程：
1.如果数据库设置了DB_AM_ENCRYPT，则页头大小为64。返回。
2.如果数据库设置了DB_AM_CHKSUM，则页头大小为48。返回。
3.返回28。
4.3.overflow页结构
4.3.1相关宏功能分析
#define
OV_LEN(p) (((PAGE *)p)->hf_offset)
功能：
返回页中已经存储的overflow数据。
#define
OV_REF(p) (((PAGE *)p)->entries)
功能：
Overflow页被引用次数。
#define P_MAXSPACE(dbp, psize) ((psize) - P_OVERHEAD(dbp))
功能：
可以在页中存储的overflow数据的最大长度（页大小减去页头大小）。
#define
P_OVFLSPACE(dbp, psize, pg) (P_MAXSPACE(dbp, psize) - HOFFSET(pg))
功能：
Overflow页中的空闲空间。
4.4.HASH页结构
4.4.1相关数据结构以及宏功能分析
#define
H_KEYDATA 1 /* Key/data item. */
#define
H_DUPLICATE 2 /* Duplicate key/data item. */
#define
H_OFFPAGE 3 /* Overflow key/data item. */
#define
H_OFFDUP 4 /* Overflow page of duplicates. */
功能：
HASH页item元组所支持的元组类型。
#define
HPAGE_PTYPE(p) (*(u_int8_t *)p)
#define
HPAGE_TYPE(dbp, pg, indx) (*P_ENTRY(dbp, pg, indx))
功能：
返回元组item的类型。
typedef struct _hkeydata {
u_int8_t type; /* 00: Page type. */
u_int8_t data[1]; /* Variable length key/data item. */
} HKEYDATA;
#define
HKEYDATA_DATA(p) (((u_int8_t *)p) + SSZA(HKEYDATA, data))
功能：
取得item中，data字段所对应的指针。
#define
LEN_HITEM(dbp, pg, pgsize, indx) /
(((indx) == 0 ? (pgsize) : /
(P_INP(dbp, pg)[(indx) - 1])) - (P_INP(dbp, pg)[indx]))
功能：
取得HKEYDATA item的长度。
#define
LEN_HKEYDATA(dbp, pg, psize, indx) /
(db_indx_t)(LEN_HITEM(dbp, pg, psize, indx) - HKEYDATA_SIZE(0))
功能：
取得item中data字段的长度。
#define
HKEYDATA_SIZE(len) /
((len) + SSZA(HKEYDATA, data))
#define
HKEYDATA_PSIZE(len) /
(HKEYDATA_SIZE(len) + sizeof(db_indx_t))
功能：
增加一个item所需要的空间。
#define
PUT_HKEYDATA(pe, kd, len, type) { /
((HKEYDATA *)pe)->type = type; /
memcpy((u_int8_t *)pe + sizeof(u_int8_t), kd, len); /
}
功能：
在给定位置插入一条item元组。
#define
H_NUMPAIRS(pg) (NUM_ENT(pg) / 2)
#define
H_KEYINDEX(indx) (indx)
#define
H_DATAINDEX(indx) ((indx) + 1)
#define
H_PAIRKEY(dbp, pg, indx) P_ENTRY(dbp, pg, H_KEYINDEX(indx))
#define
H_PAIRDATA(dbp, pg, indx) P_ENTRY(dbp, pg, H_DATAINDEX(indx))
#define
H_PAIRSIZE(dbp, pg, psize, indx) /
(LEN_HITEM(dbp, pg, psize, H_KEYINDEX(indx)) + /
LEN_HITEM(dbp, pg, psize, H_DATAINDEX(indx)))
#define
LEN_HDATA(dbp, p, psize, indx) /
LEN_HKEYDATA(dbp, p, psize, H_DATAINDEX(indx))
#define
LEN_HKEY(dbp, p, psize, indx) /
LEN_HKEYDATA(dbp, p, psize, H_KEYINDEX(indx))
功能：
其他相关宏。
typedef struct _hoffpage {
u_int8_t type; //类型以及删除标志
u_int8_t unused[3]; //保留
db_pgno_t pgno; //overflow页的页号
u_int32_t tlen; //overflow页的数量
} HOFFPAGE;
#define
HOFFPAGE_PGNO(p) (((u_int8_t *)p) + SSZ(HOFFPAGE, pgno))
#define
HOFFPAGE_TLEN(p) (((u_int8_t *)p) + SSZ(HOFFPAGE, tlen))
功能：
取得页号，取得长度。
#define
HOFFPAGE_SIZE (sizeof(HOFFPAGE))
#define
HOFFPAGE_PSIZE (HOFFPAGE_SIZE + sizeof(db_indx_t))
功能：
增加一个新元组所需要的长度。
typedef struct _hoffdup {
u_int8_t type; //类型以及删除标志
u_int8_t unused[3]; //保留
db_pgno_t pgno; //overflow页的页号
} HOFFDUP;
#define
HOFFDUP_PGNO(p) (((u_int8_t *)p) + SSZ(HOFFDUP, pgno))
功能：
取得页号。
#define
HOFFDUP_SIZE (sizeof(HOFFDUP))
功能：
增加一个元组所需要的空间大小。
4.5.BTREE页结构
#define
B_KEYDATA 1 /* Key/data item. */
#define
B_DUPLICATE 2 /* Duplicate key/data item. */
#define
B_OVERFLOW 3 /* Overflow key/data item. */
功能：
BTREE支持的元组类型。
typedef struct _bkeydata {
db_indx_t len; //元组长度
u_int8_t type; //类型以及删除标志
u_int8_t data[1]; //元组存放数据的地方
} BKEYDATA;
功能：
该结构对应的元组类型为B_KEYDATA。
#define
GET_BKEYDATA(dbp, pg, indx) /
((BKEYDATA *)P_ENTRY(dbp, pg, indx))
功能：
取得特定的元组。
#define
BKEYDATA_SIZE(len) /
(u_int16_t)DB_ALIGN((len) + SSZA(BKEYDATA, data), sizeof(u_int32_t))
#define
BKEYDATA_PSIZE(len) /
(BKEYDATA_SIZE(len) + sizeof(db_indx_t))
功能：
添加一个元组，所需分配的空间大小。
typedef struct _boverflow {
db_indx_t unused1; //保留
u_int8_t type; //类型以及删除标志
u_int8_t unused2; //保留
db_pgno_t pgno; //页号
u_int32_t tlen; //页的数量。
} BOVERFLOW;
功能：
该结构对应的元组类型为B_DUPLICATE或B_OVERFLOW。
#define
BOVERFLOW_SIZE /
((u_int16_t)DB_ALIGN(sizeof(BOVERFLOW), sizeof(u_int32_t)))
#define
BOVERFLOW_PSIZE /
(BOVERFLOW_SIZE + sizeof(db_indx_t))
#define
BITEM_SIZE(bk) /
(B_TYPE((bk)->type) != B_KEYDATA ? BOVERFLOW_SIZE : /
BKEYDATA_SIZE((bk)->len))
#define
BITEM_PSIZE(bk) /
(B_TYPE((bk)->type) != B_KEYDATA ? BOVERFLOW_PSIZE : /
BKEYDATA_PSIZE((bk)->len))
功能：
增加一个元组所需要的分配空间。
4.6.BTREE中间层页结构
typedef struct _binternal {
db_indx_t len; //元组长度
u_int8_t type; //类型以及删除标志
u_int8_t unused; //保留
db_pgno_t pgno; //引用的页的页号
db_recno_t nrecs; //子树的记录数量
u_int8_t data[1]; ///存放key */
} BINTERNAL;
功能：
内部元组结构。
#define
GET_BINTERNAL(dbp, pg, indx) /
((BINTERNAL *)P_ENTRY(dbp, pg, indx))
功能：
取得特定的元组。
#define
BINTERNAL_SIZE(len) /
(u_int16_t)DB_ALIGN((len) + SSZA(BINTERNAL, data), sizeof(u_int32_t))
#define
BINTERNAL_PSIZE(len) /
(BINTERNAL_SIZE(len) + sizeof(db_indx_t))
功能：
增加一个元组所需分配的空间。
4.7. RECNO中间层页结构
typedef struct _rinternal {
db_pgno_t pgno; //引用页的页号
db_recno_t nrecs; //子树的记录数量
} RINTERNAL;
功能：
内部元组结构。
#define
GET_RINTERNAL(dbp, pg, indx) /
((RINTERNAL *)P_ENTRY(dbp, pg, indx))
功能：
取得特定的元组。
#define
RINTERNAL_SIZE /
(u_int16_t)DB_ALIGN(sizeof(RINTERNAL), sizeof(u_int32_t))
#define
RINTERNAL_PSIZE /
(RINTERNAL_SIZE + sizeof(db_indx_t))
功能：
增加一个元组所需分配的空间。