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

全部博文(47)

文章存档

2016年(2)

2012年(10)

2011年(13)

2010年(1)

2009年(19)

2008年(2)

分类: 数据库开发技术

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"

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

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

  20.     memset(&key, 0, sizeof(DBT));
  21.     memset(&data, 0, sizeof(DBT));
  22.     rids = malloc(cnt * sizeof(DB_HEAP_RID));
  23.     buf = malloc(16384 * sizeof(char));

  24.     CHK_RET((ret = db_create(&db, NULL, 0)), "db_create");
  25.     CHK_RET((ret = db->set_heapsize(db, 1, 0, 0)), "db->set_heapsize");
  26.     CHK_RET((ret = db->open(db, NULL, "heap1.db", NULL, DB_HEAP,
  27.      DB_CREATE | DB_TRUNCATE, 0644)), "db->open");

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

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

  53.     memset(&key, 0, sizeof(DBT));
  54.     memset(&data, 0, sizeof(DBT));

  55.     printf("3 Overwrite the values:\n");
  56.     for (i = 0; i < cnt; i++) {
  57.         key.data = &rids[i];
  58.         key.size = sizeof(DB_HEAP_RID);
  59.         buf[0] = '\0';
  60.         for (j = 0; j < i; j++)
  61.             sprintf(buf + strlen(buf), "NewValue");
  62.         sprintf(buf + strlen(buf), "%d", i);
  63.         data.data = buf;
  64.         data.size = strlen(buf) + 1;
  65.         CHK_RET((ret = db->put(db, NULL, &key, &data, 0)), "db->put");
  66.     }

  67.     printf("4 Second traverse using the record ids:\n");
  68.     for (i = 0; i < cnt; i++) {
  69.         key.data = &rids[i];
  70.         key.size = sizeof(DB_HEAP_RID);
  71.         CHK_RET((ret = db->get(db, NULL, &key, &data, 0)),
  72.          "db->get");
  73.         printf("Data for {%u, %u}: %s\n", rids[i].pgno, rids[i].indx,
  74.          (char *)data.data);
  75.     }

  76.     printf("5 Delete some values:\n");
  77.     for (i = 0; i < cnt; i+= 2) {
  78.         key.data = &rids[i];
  79.         key.size = sizeof(DB_HEAP_RID);
  80.         CHK_RET((ret = db->del(db, NULL, &key, 0)), "db->del");
  81.         printf("delete record for {%u, %u}\n", rids[i].pgno, rids[i].indx);
  82.     }

  83.     printf("6 Third traverse using the record ids:\n");
  84.     for (i = 0; i < cnt; i++) {
  85.         key.data = &rids[i];
  86.         key.size = sizeof(DB_HEAP_RID);
  87.         ret = db->get(db, NULL, &key, &data, 0);
  88.         if (ret == DB_NOTFOUND)
  89.             printf("No data for {%u, %u}\n", rids[i].pgno, rids[i].indx);
  90.         else if(ret == 0) {
  91.             printf("Data for {%u, %u}: %s\n", rids[i].pgno, rids[i].indx,
  92.              (char *)data.data);
  93.         } else {
  94.             CHK_RET(ret, "db->get");
  95.         }
  96.     }

  97.     printf("7 Final traverse using cursor:");    
  98.     CHK_RET((ret = db->cursor(db, NULL, &dbc, 0)), "db->cursor");
  99.     memset(&key, 0, sizeof(DBT));
  100.     memset(&data, 0, sizeof(DBT));
  101.     i = 0;
  102.     while ((ret = dbc->get(dbc, &key, &data, DB_NEXT)) == 0) {
  103.         rid = key.data;
  104.         printf("Record %d --- {%u,%u}: %s\n", i++,
  105.          rid->pgno, rid->indx, (char *)data.data);
  106.     }

  107.     CHK_RET((db->close(db, 0)), "db->close");
  108.     free(rids);
  109. }

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

  111.     test_heap1(10);

  112. }


其对应的Java程序为:

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

  3. public class TestHeap {

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

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

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

  129. }


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

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


阅读(1924) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~