Chinaunix首页 | 论坛 | 博客

winter.zhangwinterzhang.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

winter.zhang

  • 博客访问： 302060
  • 博文数量： 47
  • 博客积分： 2455
  • 博客等级： 大尉
  • 技术积分： 558
  • 用 户 组： 普通用户
  • 注册时间： 2008-12-25 15:43
文章分类

全部博文（47）

文章存档

2016年（2）

2012年（10）

2011年（13）

2010年（1）

2009年（19）

2008年（2）

我的朋友
最近访客
推荐博文
相关博文
使用BerkeleyDB新提供的Heap存储方法

分类： 数据库开发技术

2011-08-04 00:57:49

从5.2开始, BerkeleyDB新提供了一种称为Heap的存储方法, 为用户存储数据提供了一种新的选择.

一般而言, BerkeleyDB存在空间使用效率不高的问题

在Btree中, 节点只有添加时的分裂而没有删除后的合并, 所以当删除很多记录后再插入很多记录, 删除记录所产生的空闲区域经常不能被新纪录有效利用, 导致数据库在使用中越来越大, 即使数据容量本身没有发生什么变化. Recno是基于Btree, 所以也存在同样的问题, 而Hash也存在类似的问题.

Queue则要求记录长度固定, 且关键字为记录号, 当插入一个大的记录号时, 前面的记录号极其记录会自动产生(虽然无法访问), 导致有许多无用记录占用宝贵磁盘空间.

Heap则不同, 其可以有效利用先前删除记录所产生的空闲空间, 而且不会自动产生无用记录. 所以, 对于数据容量变化不大的程序而言, Heap可以有效的使数据库文件的大小保持在一个合理的范围内. 对于严格空间受限的嵌入式程序而言, Heap将会是一个不错的存储数据的选择.

当然, Heap在使用方式上不如Btree/Hash/Recno/Queue方便. 不同于其他访问方式可以自己定义关键字, Heap中记录的关键字是系统产生的, 并且返回给用户. 用户只有使用返回的关键字才能对指定的记录进行更新, 查询,删除等操作.

所以一般使用Heap的标准方式为:

* 以追加的方式向Heap数据库总插入记录, 并且保存范围的记录关键字.
* 使用该关键字进行各种操作(更新,删除,查询).

Heap可以控制数据库文件大小的上限, 通过以下方法:
int DB->set_heapsize(DB *db, u_int32_t gbytes, u_int32_t bytes, u_int32_t flags); flags目前必须为0. 当一个操作会导致数据库文件超过限制时, 该操作将会失败, 且返回DB_HEAP_FULL. 当该方法未被调用时, 不会对数据库文件施加限制.

在Heap中, 记录关键字使用结构体DB_HEAP_RID表示的, 其定义如下:
struct __db_heap_rid {
db_pgno_t pgno; /* Page number. */
db_indx_t indx; /* Index in the offset table. */
}; 当以append方式添加记录时, 返回的key.data就是一个指向该结构体的指针.


下面是一个使用Heap的C的示例程序:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "db.h"

  6. #define CHK_RET(ret, str) do { \
  7.     int _ret = (ret); \
  8.     if (_ret) { \
  9.         fprintf(stderr, "Error(%d, %s): %s\n", \
  10.          _ret, (str), db_strerror(_ret)); \
  11.         exit(1); \
  12.     } \
  13. } while(0)

  15. void test_heap1(int cnt) {
  16.     DB *db;
  17.     DBC *dbc;
  18.     int ret, i, j;
  19.     DB_HEAP_RID *rids, *rid;
  20.     char *buf;
  21.     DBT key, data;

  23.     memset(&key, 0, sizeof(DBT));
  24.     memset(&data, 0, sizeof(DBT));
  25.     rids = malloc(cnt * sizeof(DB_HEAP_RID));
  26.     buf = malloc(16384 * sizeof(char));

  28.     CHK_RET((ret = db_create(&db, NULL, 0)), "db_create");
  29.     CHK_RET((ret = db->set_heapsize(db, 1, 0, 0)), "db->set_heapsize");
  30.     CHK_RET((ret = db->open(db, NULL, "heap1.db", NULL, DB_HEAP,
  31.      DB_CREATE | DB_TRUNCATE, 0644)), "db->open");

  33.     printf("1 Initial put:\n");
  34.     for (i = 0; i < cnt; i++) {
  35.         buf[0] = '\0';
  36.         for (j = 0; j < i; j++)
  37.             sprintf(buf + strlen(buf), "Value");
  38.         sprintf(buf + strlen(buf), "%d", i);
  39.         data.data = buf;
  40.         data.size = strlen(buf) + 1;
  41.         CHK_RET((ret = db->put(db, NULL, &key, &data, DB_APPEND)),
  42.          "db->put(DB_APPEND)");
  43.         memcpy(rids+i, key.data, sizeof(DB_HEAP_RID));
  44.         printf("Return id for %s : {%u, %u}\n", buf, rids[i].pgno,
  45.          rids[i].indx);
  46.     }

  48.     memset(&key, 0, sizeof(DBT));
  49.     memset(&data, 0, sizeof(DBT));
  50.     printf("2 First traverse using the record ids:\n");
  51.     for (i = 0; i < cnt; i++) {
  52.         key.data = &rids[i];
  53.         key.size = sizeof(DB_HEAP_RID);
  54.         CHK_RET((ret = db->get(db, NULL, &key, &data, 0)),
  55.          "db->get");
  56.         printf("Data for {%u, %u}: %s\n", rids[i].pgno, rids[i].indx,
  57.          (char *)data.data);
  58.     }

  60.     memset(&key, 0, sizeof(DBT));
  61.     memset(&data, 0, sizeof(DBT));

  63.     printf("3 Overwrite the values:\n");
  64.     for (i = 0; i < cnt; i++) {
  65.         key.data = &rids[i];
  66.         key.size = sizeof(DB_HEAP_RID);
  67.         buf[0] = '\0';
  68.         for (j = 0; j < i; j++)
  69.             sprintf(buf + strlen(buf), "NewValue");
  70.         sprintf(buf + strlen(buf), "%d", i);
  71.         data.data = buf;
  72.         data.size = strlen(buf) + 1;
  73.         CHK_RET((ret = db->put(db, NULL, &key, &data, 0)), "db->put");
  74.     }

  76.     printf("4 Second traverse using the record ids:\n");
  77.     for (i = 0; i < cnt; i++) {
  78.         key.data = &rids[i];
  79.         key.size = sizeof(DB_HEAP_RID);
  80.         CHK_RET((ret = db->get(db, NULL, &key, &data, 0)),
  81.          "db->get");
  82.         printf("Data for {%u, %u}: %s\n", rids[i].pgno, rids[i].indx,
  83.          (char *)data.data);
  84.     }

  86.     printf("5 Delete some values:\n");
  87.     for (i = 0; i < cnt; i+= 2) {
  88.         key.data = &rids[i];
  89.         key.size = sizeof(DB_HEAP_RID);
  90.         CHK_RET((ret = db->del(db, NULL, &key, 0)), "db->del");
  91.         printf("delete record for {%u, %u}\n", rids[i].pgno, rids[i].indx);
  92.     }

  94.     printf("6 Third traverse using the record ids:\n");
  95.     for (i = 0; i < cnt; i++) {
  96.         key.data = &rids[i];
  97.         key.size = sizeof(DB_HEAP_RID);
  98.         ret = db->get(db, NULL, &key, &data, 0);
  99.         if (ret == DB_NOTFOUND)
  100.             printf("No data for {%u, %u}\n", rids[i].pgno, rids[i].indx);
  101.         else if(ret == 0) {
  102.             printf("Data for {%u, %u}: %s\n", rids[i].pgno, rids[i].indx,
  103.              (char *)data.data);
  104.         } else {
  105.             CHK_RET(ret, "db->get");
  106.         }
  107.     }

  109.     printf("7 Final traverse using cursor:");    
  110.     CHK_RET((ret = db->cursor(db, NULL, &dbc, 0)), "db->cursor");
  111.     memset(&key, 0, sizeof(DBT));
  112.     memset(&data, 0, sizeof(DBT));
  113.     i = 0;
  114.     while ((ret = dbc->get(dbc, &key, &data, DB_NEXT)) == 0) {
  115.         rid = key.data;
  116.         printf("Record %d --- {%u,%u}: %s\n", i++,
  117.          rid->pgno, rid->indx, (char *)data.data);
  118.     }

  120.     CHK_RET((db->close(db, 0)), "db->close");
  121.     free(rids);
  122. }

  124. int main(int argc, char *argv[]) {

  126.     test_heap1(10);

  128. }


其对应的Java程序为:

  1. import com.sleepycat.db.*;
  2. import java.util.*;

  4. public class TestHeap {

  6.     public static int test_heap1(int cnt) throws Exception{
  7.         DatabaseConfig config1 = new DatabaseConfig();
  8.         config1.setType(DatabaseType.HEAP);
  9.         config1.setAllowCreate(true);
  10.         config1.setHeapsize(100000000L);

  12.         Database db1 = new Database("heap1.db", null, config1);
  13.         ArrayList<HeapRecordId> list1 = new ArrayList<HeapRecordId>();
  14.     
  15.         System.out.println("1 Initial put:");
  16.         for (int i = 0; i < cnt; i++) {
  17.             String str1 = ""+i;
  18.             for(int j = 0; j < i; j++)
  19.                 str1 = "Value"+str1;
  20.             DatabaseEntry k1 = new DatabaseEntry();
  21.             DatabaseEntry d1 = new DatabaseEntry(str1.getBytes());
  22.             OperationStatus st1 = db1.append(null, k1, d1);
  23.             if (st1 != OperationStatus.SUCCESS){
  24.                 System.out.println("Error to put " + str1);
  25.             } else {
  26.                 HeapRecordId hid1 = HeapRecordId.fromArray(k1.getData());
  27.                 System.out.println("Return id for " + str1 +" :{" +
  28.                  hid1.getPageNumber()+","+hid1.getIndex()+"}");
  29.                 list1.add(hid1);
  30.             }
  31.         }
  32.         
  33.         int len = list1.size();
  34.         
  35.         System.out.println("2 First traverse using the record ids:");
  36.         for(int i = 0; i < len; i++) {
  37.             HeapRecordId hid1 = list1.get(i);
  38.             DatabaseEntry k1 = new DatabaseEntry(hid1.toArray());
  39.             DatabaseEntry d1 = new DatabaseEntry();
  40.             OperationStatus st1 = db1.get(null, k1, d1, null);
  41.             if (st1 != OperationStatus.SUCCESS){
  42.                 System.out.println("Error to get " + "{" +
  43.                  hid1.getPageNumber()+","+hid1.getIndex()+"}");
  44.                 continue;
  45.             }    
  46.             String str1 = new String(d1.getData());
  47.             System.out.println("Data for " + " {" +
  48.              hid1.getPageNumber()+","+hid1.getIndex()+"}: " + str1);
  49.         }
  50.         
  51.         System.out.println("3 Overwrite the values:");
  52.         for(int i = 0; i < list1.size();i++) {
  53.             HeapRecordId hid1 = list1.get(i);
  54.             DatabaseEntry k1 = new DatabaseEntry(hid1.toArray());
  55.             String str1 = ""+i;
  56.             for(int j = 0; j < i; j++)
  57.                 str1 = "NewValue"+str1;
  58.             DatabaseEntry d1 = new DatabaseEntry(str1.getBytes());
  59.             OperationStatus st1 = db1.put(null, k1, d1);    
  60.             if (st1 != OperationStatus.SUCCESS){
  61.                 System.out.println("Error to put " + str1);
  62.             }        
  63.         }

  65.         System.out.println("4 Second traverse using the record ids:");
  66.         for(int i = 0; i < len; i++) {
  67.             HeapRecordId hid1 = list1.get(i);
  68.             DatabaseEntry k1 = new DatabaseEntry(hid1.toArray());
  69.             DatabaseEntry d1 = new DatabaseEntry();
  70.             OperationStatus st1 = db1.get(null, k1, d1, null);
  71.             if (st1 != OperationStatus.SUCCESS){
  72.                 System.out.println("Error to get " + "{" +
  73.                  hid1.getPageNumber()+","+hid1.getIndex()+"}");
  74.                 continue;
  75.             }    
  76.             String str1 = new String(d1.getData());
  77.             System.out.println("Data for " + " {" +
  78.              hid1.getPageNumber()+","+hid1.getIndex()+"}: " + str1);
  79.         }
  80.         
  81.         System.out.println("5 Delete some values:");
  82.         for(int i = 0; i < len; i+=2) {
  83.             HeapRecordId hid1 = list1.get(i);
  84.             DatabaseEntry k1 = new DatabaseEntry(hid1.toArray());
  85.             OperationStatus st1 = db1.delete(null, k1);
  86.             if (st1 != OperationStatus.SUCCESS){
  87.                 System.out.println("Error to delete " + "{" +
  88.                  hid1.getPageNumber()+","+hid1.getIndex()+"}");
  89.             } else {
  90.                 System.out.println("Delete " + "{" +
  91.                  hid1.getPageNumber()+","+hid1.getIndex()+"}");
  92.             }
  93.         }
  94.         
  95.         System.out.println("6 Third traverse using the record ids:");
  96.         for(int i = 0; i < len; i++) {
  97.             HeapRecordId hid1 = list1.get(i);
  98.             DatabaseEntry k1 = new DatabaseEntry(hid1.toArray());
  99.             DatabaseEntry d1 = new DatabaseEntry();
  100.             OperationStatus st1 = db1.get(null, k1, d1, null);
  101.             if (st1 != OperationStatus.SUCCESS){
  102.                 System.out.println("Error to get " + "{" +
  103.                     hid1.getPageNumber()+","+hid1.getIndex()+"}");
  104.                 continue;
  105.             }    
  106.             String str1 = new String(d1.getData());
  107.             System.out.println("Data for " + " {" +hid1.getPageNumber()+
  108.                     ","+hid1.getIndex()+"}: " + str1);    
  109.         }
  110.         
  111.         System.out.println("7 Final traverse using cursor:");        
  112.         Cursor cursor1 = db1.openCursor(null, new CursorConfig());
  113.         DatabaseEntry ck1 = new DatabaseEntry();
  114.         DatabaseEntry cd1 = new DatabaseEntry();
  115.         int no1 = 0;
  116.         while(cursor1.getNext(ck1, cd1, null) == OperationStatus.SUCCESS) {
  117.             HeapRecordId hid1 = HeapRecordId.fromArray(ck1.getData());
  118.             String str1 = new String(cd1.getData());
  119.             System.out.println("Record " + no1 + " -- {" +
  120.              hid1.getPageNumber()+","+hid1.getIndex()+"}: " + str1);
  121.             no1++;
  122.         }
  123.         cursor1.close();
  124.         
  125.         db1.close();
  126.         
  127.         return 0;
  128.     }
  129.     
  130.     public static void main(String[] args) throws Exception{
  131.         int ret1 = test_heap1(5);
  132.     }

  134. }


这两个程序都输出一下内容:

1 Initial put:
Return id for 0 : {2, 0}
Return id for Value1 : {2, 1}
Return id for ValueValue2 : {2, 2}
Return id for ValueValueValue3 : {2, 3}
Return id for ValueValueValueValue4 : {2, 4}
Return id for ValueValueValueValueValue5 : {2, 5}
Return id for ValueValueValueValueValueValue6 : {2, 6}
Return id for ValueValueValueValueValueValueValue7 : {2, 7}
Return id for ValueValueValueValueValueValueValueValue8 : {2, 8}
Return id for ValueValueValueValueValueValueValueValueValue9 : {2, 9}
2 First traverse using the record ids:
Data for {2, 0}: 0
Data for {2, 1}: Value1
Data for {2, 2}: ValueValue2
Data for {2, 3}: ValueValueValue3
Data for {2, 4}: ValueValueValueValue4
Data for {2, 5}: ValueValueValueValueValue5
Data for {2, 6}: ValueValueValueValueValueValue6
Data for {2, 7}: ValueValueValueValueValueValueValue7
Data for {2, 8}: ValueValueValueValueValueValueValueValue8
Data for {2, 9}: ValueValueValueValueValueValueValueValueValue9
3 Overwrite the values:
4 Second traverse using the record ids:
Data for {2, 0}: 0
Data for {2, 1}: NewValue1
Data for {2, 2}: NewValueNewValue2
Data for {2, 3}: NewValueNewValueNewValue3
Data for {2, 4}: NewValueNewValueNewValueNewValue4
Data for {2, 5}: NewValueNewValueNewValueNewValueNewValue5
Data for {2, 6}: NewValueNewValueNewValueNewValueNewValueNewValue6
Data for {2, 7}: NewValueNewValueNewValueNewValueNewValueNewValueNewValue7
Data for {2, 8}: NewValueNewValueNewValueNewValueNewValueNewValueNewValueNewValue8
Data for {2, 9}: NewValueNewValueNewValueNewValueNewValueNewValueNewValueNewValueNewValue9
5 Delete some values:
delete record for {2, 0}
delete record for {2, 2}
delete record for {2, 4}
delete record for {2, 6}
delete record for {2, 8}
6 Third traverse using the record ids:
No data for {2, 0}
Data for {2, 1}: NewValue1
No data for {2, 2}
Data for {2, 3}: NewValueNewValueNewValue3
No data for {2, 4}
Data for {2, 5}: NewValueNewValueNewValueNewValueNewValue5
No data for {2, 6}
Data for {2, 7}: NewValueNewValueNewValueNewValueNewValueNewValueNewValue7
No data for {2, 8}
Data for {2, 9}: NewValueNewValueNewValueNewValueNewValueNewValueNewValueNewValueNewValue9
7 Final traverse using cursor:Record 0 --- {2,1}: NewValue1
Record 1 --- {2,3}: NewValueNewValueNewValue3
Record 2 --- {2,5}: NewValueNewValueNewValueNewValueNewValue5
Record 3 --- {2,7}: NewValueNewValueNewValueNewValueNewValueNewValueNewValue7
Record 4 --- {2,9}: NewValueNewValueNewValueNewValueNewValueNewValueNewValueNewValueNewValue9


阅读(1872) | 评论(0) | 转发(0) |
0

上一篇：Linux系统信息查看命令全集 -- 纯属装载

下一篇：实现Linux和QNX双系统启动

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6