b

sourceforge历史版本完整下载: http://sourceforge.net/project/showfiles.php?group_id=202044 提供了基于b树索引算法的文件数据数据

固定第一页记录b树相关的属性
固定第二页为第一棵b树的根节点,这棵b树称之为主树


主树记录其他b树的根节点,如下:

其他b树标识 - 根节点页号
树标识 -> 实际上为数据库的表名,索引名

用户对某棵树的引用体现为游标

比较回调函数,主树的比较回调函数可以使用memcmp
其他树的比较回调函数则

b树的填充率写死为40%,溢出则分裂,
低于40%(删除记录之后),则从左右sibling借,
如果借用会导致sibling节点不足40%,则合并两个节点

maxlocal:溢出时的最大本页存储应不超过页大小的10%
minlocal:溢出时的最小本页存储



关于页内存储空间分配算法

 空闲存储空间,以链表形式存在,以下简称fb_list(free block list);
 分配存储空间时,顺着fb_list寻找第一个足够大小的空闲块(以下简称fb);
 如果找不到足够大的,则应进行碎片整理,分配存储空间的前提(assert(nfree > 要分配的空间大小))

 从该块的末尾取出要分配的空间大小,如果该块恰好等所需要的大小,则应从fb_list里脱链,
 释放存储空间时,顺着链表查找,fb是按起始位置的顺序进链表的,这样做便于合并相邻的fb,

 空闲存储碎片整理,将所有的cell content拷贝到一个临时的内存,再依次的拷回
 
 注:sqlite采用的是空间碎总量达到一定的值就进行整理,这样做的好处是可以减少链表的大小,
 但是也相应的增加了拷贝的工作量.



createtable: 根据表名,在主树里查找,如果表已经存在,则失败返回
往主树里添加一条记录,关键字为表名,数据域前4个字节为表的根节点,其余为用户的表信息
并返回一个游标,在游标里记录根节点的页号索引

opentable:根据表名在主树里查找,如果不存在,失败返回
如果存在,返回用户信息,并返回游标,填充根节点页索引

droptable:根据表名,从主树里删除相应的记录,释放所有该表相关的页(工程浩大啊,遍历b树,干掉每个节点)

用户对表的引用,在游标中体现




建表时可以指定主键,也可以不指定,
不指定,将以rowid作为主键,
rowid生成算法:从1开始递增至0xffffffff,因为数据表是以rowid为主键作排序的,
找到最大的rowid很容易,
当rowid达到上限时,采用随机算法生成rowid,如果有冲突,重试指定次数,超过重试次数
添加失败
所以主键是唯一的
用户指定了主键,则用户添加了重复的主键,会导致添加失败.

索引不是唯一的,但它与主键联合,作为key存入索引记录表里,即索引其实是联合索引,此时一定是唯一的
因为主键是唯一的    

综上所述,b算法添加,删除不用考虑重复关键字的情况,此时应注意比较回调函数的设计
因为要支持上层的索引重复,以及结果集的返回


删除时: 要删除相应的索引,索引+主键可以定位至索引表里一条唯一记录
添加时:索引+主键(注意索引在前)往索引表里添加
查询时:用户指定索引值查询,如果用户没有指定主键,会导致由于索引记录重复,而得出多条结果
实现了结果集的返回,
比较回调时,如果关键字A关键字域有2,而B有3,只比较前两个构成域,忽略第三个构成域
这样就实现了索引可以重复,而关键字又是唯一的设计,(因为主键是唯一的,关键无论如何都不可能重复)

如果用户在没有指定索引与主键的字段上做查询与删除,遍历整个表。。。。。。查询很漫长，后果很严重。。。。呵呵