深入理解mysql之BDB系列（3）---数据页结构(摘自老杨)

新风花雪月

四：数据页结构
4.1 B/H主要页结构
4.1.1结构图
http://p.blog.csdn.net/images/p_blog_csdn_net/whyangwanfu/bdb3_1210_1.bmp
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_SEC64
功能：
如果没有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_ttype;  /* 00: Page type. */
u_int8_tdata[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))
功能：
增加一个元组所需分配的空间。