BERKELEY DB 课程设计答辩

1、Berkeley DB 课程设计答辩课程设计答辩张天意 周冰楠9班第1小组介绍n基本数据结构和函数nB-Tree设计与逻辑实现nUB-Tree设计与逻辑实现n性能分析n感悟和结语实验环境和性能测试指标n实验环境q计算机：Intel Core i5 CPU / 4GB RAMq操作系统：Ubuntu 12.03q编译器：gccq程序语言：Cq已有源代码：BerkeleyDB 1.86n 性能测试指标q建立的索引大小q建立索引的时间q查询时I/O读写情况Intel，Intel Core 是英特尔公司在美国和/或其他国家和地区的商标。基本基本数据结构和函数数据结构和函数Berkeley DB 课程课

2、程设计答辩设计答辩数据结构名数据结构名描述与用途描述与用途定义位置定义位置DB数据库定义DB.hDBTB-Tree节点结构，包括key，data均是此结构DB.hEPG记录寻址结构，包含pgno和indexbtree.hEPGNO记录寻址结构，包含pgno指针和indexbtree.hBTREEINFOB树建立时候系列参数，包括缓冲大小、页数、支持重复与否等btree.hBTREE保存在内存中的树结构，可调用internal中系列函数btree.hPAGEB-Tree中页属性结构，包含页号、指针等btree.hBerkeley DB 1.86 数据结构函数函数名名功能功能dbopen打开数据库

3、dbclose关闭数据库_bt_seq顺序访问B树_bt_ret获取指定记录的信息_bt_put往btree插入数据_bt_defcmp比较key大小函数函数名名功能功能_bt_first找到指定键值的第一条记录_bt_seqset从指定键值顺序访问_bt_seqadv提前进行顺序访问mpool_put获取页面基本信息在实验过程中，还调用了string系列函数，以及atoi，atof，sscanf 等库函数。Berkeley DB 1.86 函数B-TREE设计设计与逻辑与逻辑实现实现Berkeley DB 课程设计答辩课程设计答辩B-Tree设计与实现n根据属性shipdate对lineit

4、em表建立 B-Tree索引；n在（1）基础上，根据属性discount对lineitem表建立索引；n完成范围查询。查询条件设计思路index2index1lineitem.tbl共同的问题n如何利用Berkeley代码？n哪些代码可以用？n还需要添加哪些部分？nBerkeley代码有几大部分？n我需要实现/解决哪些问题？nBerkeley中哪些部分是和这个问题相关的？从需求出发，按需调配相关模块从需求出发，按需调配相关模块建立B-Tree索引Index1n如何从lineitem里逐行读取条目，并分离出需要的key和data部分？sscanf(char *buffer,char *forma

5、t,argument .)n分离后的key和data应该如何插入？ 来源：dbtest dbp-put(dbp, &key, &data, 0); dbp指向需要插入的索引 key，data作为DBT结构传入函数需求分析建立index1 123456789101112131415161718DB *dbp = (DB*)malloc(sizeof(DB*), DBT data, key;char *fname = “index1_new.db”;char buf8*1024;FILE *ifp = fopen(file_name, r);while(fgets(buf, siz

6、eof(buf), ifp) != NULL) sscanf(buf,%*|%*|%*|%*|%*|%*|%*|%*|%*|%*|%10|, mydata.key); key.data = mydata.key; key.size = strlen(mydata.key)+1; data.data = buf; data.size = strlen(buf)+1; dbp-put(dbp, &key, &data, 0);逻辑实现规格化key data获得index1index1lineitem.tbl94/1/1 | 0.06 | XXXXX94/1/1 94/1/1 | 0

7、.06 | XXXXX建立B-Tree索引index2n如何遍历index1？_bt_seq(dbp, key, data, flags)来源：bt_get()n如何获取对应的页号和槽号？利用EPG结构，来源：bt_seq()_bt_seqset(t, , &key, flags); 页号和槽号即构成rid。n如何进一步获取index2所需的key呢？ _bt_ret(t, &e, &key, &t-bt_rkey, &data, &t-bt_rdata, 0);需求分析123456789101112131415/The details abov

8、e have been omitted.status = _bt_seqset(t, &e, &key, R_FIRST);while (status = RET_SUCCESS) pagenum = (e.page)-pgno;slotnum = e.index;_bt_setcur(t, pagenum, slotnum);status = _bt_ret(t, &e, &key, &t-bt_rkey, &data, &t-bt_rdata, 0); /use sscanf() to get the discount attr. /

9、Put the data and key(rid) into new index2 /Continue;建立Index2 将页号槽号作为Index2 的Data，即rid通过e在index1中找相应条目为下一步获取discount作准备逻辑实现Index1 Index2nlineitem.tbl nIndex1 Key = shipdatenIndex2 Key = discount, rid = slot+no.index2index1lineitem.tbl94/1/1 | 0.06 | XXXXX94/1/1 94/1/1 | 0.06 | XXXXX0.06 1 | 1范围查询n方案一

10、：仅根据index1范围查询n如何比较Key的大小 _bt_defcmp(DBT a, DBT b) 来源：bt_search(); 根据返回值确定大小index194/1/1 94/1/1 | 0.06 | 50 | XXXXXXXDiscountQuantity符合条件？计算结果YESNO需求分析范围查询12345678status = dbp-seq(dbp, &key, &data, R_FIRST); while (status = RET_SUCCESS) if (_bt_defcmp()= 0 is satisfied for each attr.)sum +=

11、atof(extendedprice) * atof(discount);status = dbp-seq(dbp, &key, &data, R_NEXT); 逻辑实现范围查询实验测试与结果测试数据(query.in)测试结果(query.out) query.out中数据和给定的理论数据相符范围查询n方案二：通过index2、index1需求分析I/O更少更少下推，优化查询方案更省处理字符串更少更快范围查询n方案二：通过Index2、Index1I/O更少更少下推，优化查询方案更省处理字符串更少更快范围查询n方案二：通过Index2、Index1Key次序不对应于记录的储存

12、次序对任何数据页读取都可能重复最坏情况开销等于数据记录的数目I/O更少更少下推，优化查询方案更省处理字符串更少更快范围查询n方案二：通过Index2，再到Index1并没有得到较大改进的表现UB-TREE设计与逻辑实现设计与逻辑实现Berkeley DB 课程设计答辩24n将shipdate、discount、quantity 三维的数据通过interleave（按位交叉）方式，映射为一个一维的ubkey；n根据得到的ubkey，建立 的 UB-Tree索引；n根据建立的UB-Tree索引进行点查询；n根据建立的UB-Tree索引完成范围查询。UB-Tree设计与实现设计思路如何按位交叉得到Z

13、_Value？按位交叉得到Z_Value1. 将每一维度属性值转化为二进制字符串；2. 将各个字符串统一位数，按位交叉生成新的二进制字符串；3. 新的二进制字符串作为UB-Key按位交叉得到Z_Value1234567891011char* getZvalue(char* attr1, char* attr2, char* attr3) char* z_value; char* temp1 = tobinary(attr1); char* temp2 = tobinary (attr2); char* temp3 = tobinary (attr3); int z_value_length =

14、 max(temp1,temp2,temp3); z_value = Interleave(tmep1,temp2, temp3,z_value_length); return (z_value); 逻辑实现这里将UB-Key直接保存为char型是一种方法。为了减小索引大小，加快查询速度，对UB-Key更好的处理包括不等长Key、压缩以及保存为int型。上述方法可交叉重叠使用。详细参见“性能分析”。建立 的 UB-Tree索引12345678910111213141516DB *dbp = (DB*)malloc(sizeof(DB*);DBT data, key; char *fname =

15、 index3_new.db; char buf8*1024; FILE *ifp = fopen(file_name, r); while(fgets(buf, sizeof(buf), ifp) != NULL) sscanf(buf,%*|%*|%*|%*|%4|%*| %5|%*|%*|%*|%10|,quantity,discount,shipdate); char *z_value; z_value = getZvalue(quantity, discount, shipdate); . dbp3-put(dbp3, &key, &data, 0) ; 逻辑实现点查

16、询 PK 范围查询fgets(buf, sizeof(buf), fp) Sizeof(buf) seq(dbp3, &key, &data, R_FIRST); while (status = RET_SUCCESS) if ( _bt_defcmp(&key_t, &key) = 0 ) sscanf(buf,%*|%*|%*|%*|%*| |%10|%5|,_extendedprice,_discount); sum += atof(_extendedprice) * atof(_discount); status = dbp3-seq(dbp3, &am

17、p;key, &data, R_NEXT); 点查询实验测试与结果测试数据(query.in)测试结果(query.out) query.out中数据和通过SQL查询结果相符SQL结果UB-Tree结果点查询 PK 范围查询fgets(buf, sizeof(buf), fp) Sizeof(buf) 30点查询范围查询范围查询 范围查询流程图查找开始Flags =R_CURSOR, cur/start = ql, end=qhKey各维在查找范围内计算SumYN下一条目Key在查找范围内Y继续遍历Flags=R_NEXTN跳转到nisp(实现优化)Flags = R_CURSORKe

18、y seq(dbp3, &key_z, &data_z, flags); while (status = RET_SUCCESS) if (strcmp(key_z.data, qh) = 0) break; if( ifKeyInQurey(key_z, start, end) = 0) /details are omitted. sum+= atof(_extendedprice) * atof(_discount); flags=R_NEXT; 范围查询151617181920212223242526272829else status = dbp3-seq(dbp3, &

19、amp;key_z, &data_z, R_NEXT); if ( strcmp(key_z.data, qh) 0) break; if ( ifKeyInQurey ( key_z, start, end) = 0) sum+= atof(_extendedprice) * atof(_discount); flags =R_NEXT; else new_z = changeZvalue(key_z, start, end); flags = R_CURSOR; status = dbp3-seq(dbp3, &key_z, &data_z, flags); 逻辑实

20、现范围查询实验测试与结果测试数据(query.in)测试结果(query.out) query.out中数据和给定的理论数据相符。其中范围查询部分结果应该和B-Tree一致。UB-Tree查询结果B-Tree查询结果性能分析性能分析Berkeley DB 课程设计答辩性能分析n性能测试指标q建立的索引大小q建立索引时间q查询时I/O读写情况n测试数据q建立索引以lineitem.tbl为源数据q查询条件B树UB树性能分析n索引大小nB-Tree Index1 大小nB-Tree Index2 大小nUB-Tree Index 大小可以通过删去不必要的属性以减小大小可以通过优化UB-Key保存方

21、式减小大小性能分析n建立索引时间nB-Tree index1 128 缓冲页 8 缓冲页建立相同索引所用的时间有少许减少，这可能大的缓冲页使程序不必频繁在内存和辅存中交换数据页，减少I/O开销。性能分析n建立索引时间nB-Tree index2 128 缓冲页 8 缓冲页128页时间有少许减少。这可能index2所储存的数据仅是Key和槽号页号，数据不必频繁在内存和辅存中交换数据页，因而没有很大程度上减少建立索引的时间。对于UB-Key的处理优化n各维属性不等长* 1994 01 01 0. 0 1 77 4 x 4 + 4 + 5 + 4 x 2 + 4 x 2 = 41 Bytes 通过提取各维属性中有效部分的信息，减少UB-K