btree.c

基于btree索引算法的数据库代码

/**
 * @file btree.c 描述b树算法 2008-03-03 23:26
 *
 * @author lin shao chuan (email:[e-mail], msn:[e-mail])
 *
 * @brief if it works, it was written by lin shao chuan, if not, i don't know who wrote it.
 *        描述b树算法,基于页缓存机制pager基础上构建
 * 
 * btree page head define
 *   OFFSET   SIZE     DESCRIPTION
 *      0       1      Flags. 1: intkey, 2: hasdata, 4: leaf
 *      1       1      记录碎片的大小
 *      2       2      byte offset to the first freeblock
 *      4       2      number of cells on this page
 *      6       2      first byte of the cell content area
 *      8       4      Right child (the Ptr(N+1) value).  reserve on leaves.
 *
 * 一条记录的分布如下
 *    SIZE    DESCRIPTION
 *      4     Page number of the left child. Omitted if leaf flag is set.
 *      4     Number of bytes of data. Omitted if the zerodata flag is set.
 *      4     Number of bytes of key. Or the key itself if intkey flag is set.
 *      4     First page of the overflow chain.  Omitted if no overflow
 *      *     Payload
 *
 * 溢出页的格式定义
 *    SIZE    DESCRIPTION
 *      4     Page number of next overflow page
 *      *     Data
 *
 * 页内空闲块定义
 *    SIZE    DESCRIPTION
 *      2     Byte offset of the next freeblock
 *      2     Bytes in this freeblock
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  lin shao chuan makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 * see the GNU General Public License  for more detail.
 */

#include "btree.h"

#include <string.h>
#include <stdio.h>

#include "pager.h"
#include "mylist.h"
#include "mylog.h"
#include "mybuffer.h"
#include "MyAlgorithm.h"


/* 一页分成10份 */
#define BTREE_PERCENT 10

/* 溢出时,最大本页存储为1/10 */
#define BTREE_MAX_LOCAL 1

/* 每页的最小填充率4/10 */
#define BTREE_FILL_RATE 4

/* 每个cell"指针"的大小 */
#define BTREE_CELL_PTR_SIZE 2

/* master表的根节点 */
#define BTREE_MASTER_ROOT 2


/**
 * 一条记录的分布如下
 *    SIZE    DESCRIPTION
 *      4     Page number of the left child. Omitted if leaf flag is set.
 *      4     Number of bytes of data. Omitted if the zerodata flag is set.
 *      4     Number of bytes of key. Or the key itself if intkey flag is set.
 *      4     First page of the overflow chain.  Omitted if no overflow
 *      *     Payload
 */
typedef struct __btree_cell_info_t_
{
	/* cell内容的起始 */
	unsigned char * cell;
	/* 整个cell的总大小 */
	unsigned int cell_sz;

	/* payload之前的字节数 */
	unsigned int head_sz;

	/* key的大小,或者就是key本身(如果key是个整形数的话) */
	unsigned int key_sz;

	/* data的大小 */
	unsigned int data_sz;

	/* 本地存了多少payload,如果有溢出的话 */
	unsigned int local_sz;

	/* payload的总大小 */
	unsigned int payload_sz;

	/* 记录左孩子的页号(如果是非叶节点) */
	unsigned int lchild_pgno;
	/* 首个overflow的页号 */
	unsigned int overflow_pgno;
}btree_cellinfo;

/* 此结构体的存储空间附加的页缓存后面,所有权归页缓存管理所有 */
typedef struct __btree_node_
{
	/* 记录是否已经初始化过了 */
	int init_flag;

	/* 父节点 */
	struct __btree_node_ * parent;

	/* 索引数组是否有改变 */
	unsigned int idx_changed;

	/* 对应父节点中的cell的索引 */
	unsigned int idx_in_parent_cellarray;

	/* 页标识 */
	unsigned int node_flag;

	/* cell个数 */
	unsigned int ncell;

	/* 空闲存储空间大小 */
	unsigned int nfree;

	/* 页缓存指针 */
	HPAGE_HEAD pg;
	/* 记录用于读取的页缓存指针 */
	unsigned char * read_buf;
	/* 当前节点对应的页号 */
	unsigned int pg_no;

	/* 此节点归属于哪个btree管理器 */
	struct __btree_mgr_t_ * btree_mgr;

	/*
	* 溢出的cell,这里的溢出不是指记录超出本页最大存储量而产生的,
	* 而是指在添加记录时该页已经没有多余空间了,打包后的新记录暂时存放在这里
	* 之后在balance函数中再放入合适的位置(能过分裂节点而产生富余的存储空间)
	*/
	struct cell_overflow
	{
		HMYBUFFER cell_buf;
		unsigned int idx;
	}cell_ovfl;
	/* 标识,1:表示cell_ovfl里填充的内容是有效的 */
	int has_cell_ovfl;
}btree_node;

typedef struct __btree_cursor_
{
	/* 此游标对应btree的root page num */
	unsigned int root_pgno;

	/* 当前游标所处的页节点 */
	btree_node * cur_node;
	/* 当前游标在节点cell数组的位置 */
	unsigned int idx;

	/* 比较回调函数,用户的上下文信息 */
	XCOMPARE key_cmp;
	void * context;
	unsigned int context_sz;

	/* 此游标的归属于哪个btree管理 */
	struct __btree_mgr_t_ * btree_mgr;

	/* 游标链表 */
	struct __btree_cursor_ * cursor_prev, * cursor_next;

	/* cell信息的临时存储区 */
	btree_cellinfo cell_info;

	/* 错误码,在处理过程中是否发生错误 */
	int err;
}btree_cursor;

typedef struct __btree_mgr_t_
{
	/* 内存池句柄 */
	HMYMEMPOOL hm;

	/* 页管理器 */
	HPAGER hpgr;
	/* 页的大小 */
	unsigned int pg_sz;

	/* 记录溢出时,在本页存储的大小上限与下限 */
	unsigned int max_local;
	unsigned int min_local;

	/* 保存所有的游标 */
	btree_cursor * cursor_lst;

	/* 保存临界填充率对应的填充值,填充率,扣除了每个节点头空间的存储信息的大小 */
	unsigned int pg_min_fill_sz;
}btree_mgr_t;


/**
 * btree page head define
 *   OFFSET   SIZE     DESCRIPTION
 *      0       1      Flags. 1: intkey, 2: hasdata, 4: leaf
 *      1       1      记录碎片的大小
 *      2       2      byte offset to the first freeblock
 *      4       2      number of cells on this page
 *      6       2      first byte of the cell content area
 *      8       4      Right child (the Ptr(N+1) value).  reserve on leaves.
 */
typedef struct __unused_btree_head_
{
	char nodeflag[1];
	char nfrag[1];
	char first_free[2];
	char ncell[2];
	char first_content[2];
	char most_right_child[4];
}unused_btree_head;

/* 页标识的偏移 */
#define BTREE_HDR_PAGEFLAG_OFFSET (((unused_btree_head *)NULL)->pageflag - NULL)

/* 空闲碎片的总数 */
#define BTREE_HDR_NFRAG_OFFSET (((unused_btree_head *)NULL)->nfrag - NULL)

/* 节点标识的偏移 */
#define BTREE_HDR_NODEFLAG_OFFSET (((unused_btree_head *)NULL)->nodeflag - NULL)

/* 节点里cell值的偏移 */
#define BTREE_HDR_NCELL_OFFSET (((unused_btree_head *)NULL)->ncell - NULL)
/* 节点里存cell值空间的大小 */
#define BTREE_HDR_NCELL_SZ (sizeof(((unused_btree_head *)NULL)->ncell))

/* 节点里第一个空闲存储块偏移的值 */
#define BTREE_HDR_FIRST_FREE_OFFSET (((unused_btree_head *)NULL)->first_free - NULL)

/* 节点content的起始 */
#define BTREE_HDR_FIRST_CONTENT (((unused_btree_head *)NULL)->first_content - NULL)

/* 记录节点最右边子节点的偏移 */
#define BTREE_HDR_MOST_RIGHT_CHILD_OFFSET (((unused_btree_head *)NULL)->most_right_child - NULL)

/* 节点的头信息的最大值 */
#define BTREE_HDR_SZ (sizeof(unused_btree_head))

/* cell偏移数组的超始偏移 */
#define BTREE_CELL_PTR_OFFSET (sizeof(unused_btree_head))

/* 空闲碎片的上限 */
#define BTREE_MAX_FRAG 128

/* 一个节点的承载量 */
#define BTREE_NODE_PAYLOAD(_btree_mgr) (_btree_mgr->pg_sz - BTREE_HDR_SZ)


/**
 * 溢出页的格式定义
 *    SIZE    DESCRIPTION
 *      4     Page number of next overflow page
 *      *     Data
 */
typedef struct __unused_overflow_head_
{
	char next[4];
	char data[1];
}unused_overflow_head;

/* 溢出页头信息的大小 */
#define BTREE_OVERFLOW_HDR_SZ (((unused_overflow_head *)NULL)->data - NULL)

/* 溢出页的承载信息量 */
#define BTREE_OVERFLOW_PAYLOAD(__btree_mgr) ((__btree_mgr)->pg_sz - BTREE_OVERFLOW_HDR_SZ)


/*
 * 页内空闲块定义
 *    SIZE    DESCRIPTION
 *      2     Byte offset of the next freeblock
 *      2     Bytes in this freeblock
 */
typedef struct __unused_free_block_
{
	char next[2];
	char sz[2];
}unused_free_block;

/* 下一个空间块的偏移 */
#define BTREE_FREE_BLOCK_NEXT_OFFSET (((unused_free_block*)NULL)->next - NULL)

/* 本空闲块的大小 */
#define BTREE_FREE_BLOCK_SZ_OFFSET (((unused_free_block*)NULL)->sz - NULL)

/* 空闲块的最小值 */
#define BTREE_FREE_BLOCK_MIN_SZ (sizeof(unused_free_block))


/*
 * 一条记录的分布如下
 *    SIZE    DESCRIPTION
 *      4     Page number of the left child. Omitted if leaf flag is set.
 *      4     Number of bytes of data. Omitted if the zerodata flag is set.
 *      4     Number of bytes of key. Or the key itself if intkey flag is set.
 *      4     First page of the overflow chain.  Omitted if no overflow
 *      *     Payload
 */
typedef struct __unused_cell_
{
	unsigned char lchild[4];
	unsigned char data_sz[4];
	unsigned char key_sz[4];
	unsigned char overflow[4];
}unused_cell;

/* cell头信息最大长度 */
#define BTREE_CELL_HDR_SZ (sizeof(unused_cell))

/* cell的最小值 */
#define BTREE_CELL_MIN_SZ BTREE_CELL_HDR_SZ

/* lchild的偏移 */
#define BTREE_CELL_LCHILD_OFFSET (((unused_cell *)NULL)->lchild - NULL)
/* lchild的大小 */
#define BTREE_CELL_LCHILD_SZ (sizeof(((unused_cell *)NULL)->lchild))


/**
 * @brief 计算一个cell总会占去多少空间
 */
#define btree_mgr_cal_cell_real_fill_sz(__c_sz) (__c_sz + BTREE_CELL_PTR_SIZE)

/**
 * @brief 设置某个节点的属性
 */
static __INLINE__ int btree_mgr_set_nodeflag(btree_node * node, unsigned char nodeflag)
{
	unsigned char * wb = NULL;

	assert(node && node->pg);

	wb = PageHeadMakeWritable(node->pg);
	if(NULL == wb)
		return -1;

	node->node_flag = nodeflag;

	wb[BTREE_HDR_NODEFLAG_OFFSET] = nodeflag;

	return 0;
}

/**
 * @brief 增加某个节点承载页的引用计数
 */
#define btree_mgr_ref_node(_n) do{\
		assert(_n && _n->pg); \
		PageHeadRef(_n->pg);\
	}while(0)

/**
 * @brief 初始化一个节点
 * @param bnew:是否是一个新分配节点
 */
static __INLINE__ int btree_mgr_init_node(btree_node * node, int bnew)
{
	/*
	* btree page head define
	*   OFFSET   SIZE     DESCRIPTION
	*      0       1      Flags. 1: intkey, 2: hasdata, 4: leaf
	*      1       1      记录碎片的大小
	*      2       2      byte offset to the first freeblock
	*      4       2      number of cells on this page
	*      6       2      first byte of the cell content area
	*      8       4      Right child (the Ptr(N+1) value).  reserve on leaves.
	*/

	unsigned int cell_content = 0;
	unsigned int free_buf = 0;

	const unsigned char * data = node->read_buf;

	assert(node->read_buf == PageHeadMakeReadable(node->pg));
	assert(data);

	if(bnew)
	{
		unsigned char * wb = PageHeadMakeWritable(node->pg);
		if(NULL == wb)
			return -1;

		memset(wb, 0, BTREE_HDR_SZ);

		node->ncell = 0;
		node->nfree = node->btree_mgr->pg_sz - BTREE_CELL_PTR_OFFSET;
		node->node_flag = 0;
		node->has_cell_ovfl = 0;
		node->idx_changed = 0;
		node->cell_ovfl.cell_buf = NULL;
		node->cell_ovfl.idx = 0;

		return 0;
	}
	else
	{
		node->node_flag = data[BTREE_HDR_NODEFLAG_OFFSET];

		get_2byte(&(data[BTREE_HDR_NCELL_OFFSET]), BTREE_HDR_NCELL_SZ, node->ncell);
		get_2byte(&(data[BTREE_HDR_FIRST_CONTENT]), BTREE_CELL_PTR_SIZE, cell_content);

		if(0 == cell_content)
		{
			/* 说明这是个节点此时没有任何存储 */
			node->nfree = node->btree_mgr->pg_sz - BTREE_CELL_PTR_OFFSET;
		}
		else
		{
			/* 空闲存储空间大小 */
			node->nfree = cell_content - (2 * node->ncell + BTREE_CELL_PTR_OFFSET) +
				data[BTREE_HDR_NFRAG_OFFSET];

			get_2byte(&(data[BTREE_HDR_FIRST_FREE_OFFSET]), BTREE_CELL_PTR_SIZE, free_buf);

			/* 顺着空闲链表做统计 */
			while(free_buf)
			{
				unsigned int sz = 0;
				unsigned int next_free = 0;

				get_2byte(&(data[free_buf + BTREE_FREE_BLOCK_SZ_OFFSET]), sizeof(unsigned short), sz);
				node->nfree += sz;

				get_2byte(&(data[free_buf + BTREE_FREE_BLOCK_NEXT_OFFSET]), BTREE_CELL_PTR_SIZE, next_free);

				/* 空闲块按偏移的升序排列,并且不可能连续(释放时要处理合并连续空闲块的情况) */
				assert(next_free > free_buf + BTREE_FREE_BLOCK_MIN_SZ || 0 == next_free);

				free_buf = next_free;
			}
		}

		node->idx_changed = 0;

		return 0;
	}
}

/**
 * @brief 取消对某一页的引用,但不销毁这个节点.
 */
static __INLINE__ int btree_mgr_release_node(btree_node * node)
{
	assert(node);

	return  PagerReleasePage(node->pg);
}

/**
 * @brief 获取一个节点
 * @param b_in_cache:是否只从缓存里获取
 * @param b_new:是否是新的节点
 */
static __INLINE__ btree_node * btree_mgr_get_node_aux(btree_mgr_t * btree_mgr,
													  unsigned int pgno,
													  btree_node * parent,
													  int idx_in_parent,
													  int b_only_in_cache,
													  int b_new)
{
	HPAGE_HEAD pg = NULL;
	btree_node * node = NULL;

	assert(btree_mgr && pgno);

	if(b_only_in_cache)
		pg = PagerGetCachedPage(btree_mgr->hpgr, pgno);
	else
		pg = PagerGetPage(btree_mgr->hpgr, pgno);