基于 SB 树的嵌入式数据库查询优化技术.doc

《基于 SB 树的嵌入式数据库查询优化技术.doc》由会员分享，可在线阅读，更多相关《基于 SB 树的嵌入式数据库查询优化技术.doc（6页珍藏版）》请在三一办公上搜索。

1、精品论文大集合基于 S-B 树的嵌入式数据库查询优化技术黄楷胤 1，何艳珊 2，陈鹏飞 2，李龙杰 21.华南师范大学 经济与管理学院,广州 石牌 5106312. 兰州大学 信息科学与工程学院,甘肃 兰州 730000摘要： 本文针对嵌入式设备存储空间有限的情况，提出一种静态平衡树S-B 树来代替 B+ 树作为嵌入式数据库的索引结构。S-B 树基于一些嵌入式数据库在具体的应用中无插入和删 除操作的情况，同时利用了 B+树效率高和静态树空间利用率高的优点，大大提高了 B+树的 空间利用率。并在固定资产管理系统的嵌入式数据库 SQLite 中应用了这一技术，实验表明 在相同情况下，S-B 树查询

2、效率略高于 B+树，空间利用率平均高出 B+树约 30%。 关键字：嵌入式数据库 B+树 静态平衡树 S-B 树中图分类号：TP311.132.31.引言嵌入式数据库管理系统是最近几年才兴起的一项新的数据管理技术。它以目前成熟的数 据库技术为基础，针对具体的嵌入式设备与系统特点，结合实际应用需求，主要实现对嵌入 式设备上数据的存储、组织和管理，以及同后台主数据源的数据交换。在国外，Sybase 为 移动和嵌入式计算提供了完整解决方案 Sybase SQL AnyWhere Studio 7.0；Oracle 公司的 Oracle Lite 以及 Berkeley DB；IBM 公司的 IBM

3、DB2 等都是嵌入式数据库的典型代表。近年 来，国内的嵌入式研究也已发展到应用阶段。人大金仓研发的“小精灵”系统，东北大学提 出了 OpenBase Mini 以及北京大学的 ECOBASE 等 1都是具有代表性的嵌入式数据库系统。数据库在当今社会各个领域都有着举足轻重的作用，数据库中的常用操作包括插入，选 择，更新和删除等。然而，在实际的操作中，特别是在嵌入式数据库的应用中，有时仅仅需要数据库的部分功能。例如，各企事业单位的门禁系统，固定资产盘点等，这些嵌入式数据 库系统中只是用到了选择和更新的功能，而不进行插入和删除操作。目前，绝大多数嵌入式 数据库都提供 B+树检索机制，B+树是一种效率

4、很高的外查找索引机制，是基本 B-树的变型树2。B+树的最大的缺点是空间利用率低下，这对于存储空间有限的嵌入式数据库来说是致 命的，特别是对于无需插入删除操作的嵌入式数据库，如果仍沿用 B+数作为索引显然不是 最优选择，这就要求一种更适合这类数据库的索引机制。在广东省教育部产学研结合项目“基于 RFID 技术的嵌入式数据库系统及相关产品的开 发”中，我们应用 RFID 技术和 Web Service 技术设计并实现了固定资产管理系统。本系统应用了两种数据库来管理固定资产，分别是服务器端的 Oracle 9i 和手持机 PDA 上的嵌入式 数据库 SQLite3.3.4。服务器端数据库存储了全部

5、的固定资产信息，支持插入，选择，更新， 删除等操作。手持机端由于硬件和内存限制，仅存储了部分常用数据，需要时与服务器端交互，同步双方数据库。根据系统需求，手机端数据库担负着大量的实时查询工作和部分修改 工作，而无需插入或删除操作。SQLite 是一个轻量级别的文件数据库，使用方便，不需要 安装，无须任何配置，也不需要管理员。SQLite 支持大部分 SQL 语句，而且它是开源的嵌入式数据库产品，因此可以根据具体需要对其进行改进。我们按照实际使用情况，设计出一 种静态平衡树（S-B 树）来组织文件和担任查询工作。1 本课题得到广东省教育部产学研结合基金项目（2007A090302117）的资助-

6、 6 -2.SQLite的查询优化2.1 SQLite 的索引机制SQLite 是一个功能强大的嵌入式数据库，为了满足所有的操作需求，SQLite 采用 B+树 作为文件组织形式。B+树是一种用于数据库索引的数据结构，其综合效率比较高。SQLite 的文件组织中，数据库中的每个表和索引都使用一个单独的 B+树。图 1 B+树的结点结构B+树的非叶子结点构成了叶子结点上的一个多级索引，其所有指针都指向树中的结点。 叶子结点跟非叶子结点具有相同的结构（如图 1），不同的是，叶子结点指针指向磁盘上的 文件。由于各叶结点按照所含的关键字值有一个线性顺序，所以就可以利用各个叶结点的指 针 Pn 将叶结点

7、按关键字顺序链接在一起。这种排序能够高效地对文件进行顺序处理，而 B+ 树索引的其他结构能够高效地对文件进行随机处理67。B+树的最大优点是效率高，同时能进行随机查找和顺序查找，并且保持动态平衡。 然而，B+树同样存在弊端，空间利用率低下是 B+树最大的缺点。据统计，B+树索引机制平均空间利用率仅为 50%45。大量的指针，以及为方便插入而预留的空间会占用许多的 存储空间而使的空间利用率大大下降，这对于嵌入式设备是致命的缺陷。而且，B+树中的 n 值对特定的树是固定的，在最坏的情况下，也就是每个非叶子结点的关键字数目都是最小(即n /2 1 )时，B+树的空间和时间效率将很差。（a）（b）图

8、2 B+树的空间利用对比图一颗 4 阶的 B+树，当所有的结点都仅满足 B+树的最低要求（如图 2（a）所示），其空 间利用率仅有约 50%；而当所有节点都是满的，其空间利用率就会大大提高（如图 2（b） 所示）。同时，从图 2 可以明显看出，（a）图中 B+树的层数是 4 层，而（b）图中层数是 两层。也就是说对这两个 B+树检索，（a）中的 B+树耗费时间将是（b）中的 B+树的 3 倍。 当数据量较大时，时间效率也会相应的有所影响。2.2 静态平衡树（S-B 树）本文在原有 B+树索引的机制上，对于无插入和删除操作的数据库，提出了一种新的索 引结构静态平衡树（S-B 树）。1.S-B 树

9、的结构S-B 树是一个高度为 l 的 m 叉树，所有结点的子树间两两深度差 d 1 。S-B 树中的结点包括两类：叶子结点和非叶子结点。叶子结点实际上是一个数组。为了平衡时间和空间效率，两类结点分别采用了两种数据结构。（1）非叶子结点S-B 树中的非叶子结点形成了叶子结点上的一个索引。除最后一层的最后一个非叶子节 点外，每个非叶子结点均有 m 颗子树。具体结构如图 3 所示：图 3 S-B 树非叶子结点结构非叶子结点包含 m 个关键字值 K1,K2,Km，以及 m 个指针 P1,P2,Pm，Pi 实际上存储了叶子结点的数组中 Ki 的下标( 1 i m )。每个结点中的关键字值按次序存放，即如

10、果ij，那么 KiKj.为了使得 S-B 树的查询效率达到最优，就要求 S-B 数即不能太高也不能太宽。一个具有 n 条记录的 m 叉的 S-B 树，其查询效率是跟其高度 l 成正比的，因此要使得 查询效率越高，高度 l 就要越小，也就是说 S-B 树越矮。因此，要使得 S-B 树的空间利用率和查询效率达到最高，m 与 l 的关系满足式（1），且使得式（2）中的查询时间 达到最小：（2）叶子结点l = log mn = l + m /2 （1）（2）B+树中叶子结点和非叶子结点采用了相同的结构，不同的是其 Pn 指针指向的是相邻结 点，这样可以方便顺序查询。用这种带有指针的结点的结构的优点是可

11、以方便添加和删除操 作。S-B 树中的叶子结点采用了数组的形式来节省空间，不再沿用 B+树中有大量的指针的 结点存储信息，提高了空间利用率。数组中每个单元由两个域组成：关键字域和指针域。其 中，关键字域中存储记录关键字，指针域指向具体记录。叶子结点数组中的关键字自小而大 顺序存储。具有 s 条记录的数据库表，其 S-B 树的叶子结点的结构如图 4 所示：2.S-B 树构造算法图 4 S-B 树叶子结点结构S-B 树是一棵自底向上构造的多叉静态平衡树。S-B 树的构造算法如图 5 所示：Algorithm: S-Btree(keyn)Input: the array of keys keyn i

12、n the table Output: S-B tree of keys in the table num=ceil(n/m);sign = num;a1,sign = key1,keym+1,key(sign-1)m+1;b1,sign = m,m+1,(sign-1)m+1;/contribute the index while(sign!=1)create ceil(sign/m) nodes;for(i=1,l=1;i=ceil(sign/m);i+)for(j=1;j=m;j+) nodei.kj=al; nodei.pj=bl;l+;sign=ceil(sign/m);图 5 S-

13、B 树构造算法构造一棵 m 叉的 S-B 树，首先根据式（1）、式（2）得出高度 l 和 m 的最佳值，根据此值可以保证构造出的 S-B 树达到空间利用率和时间效率上的折中，然后自底向上构造 S-B树作为所有记录的索引树。S-B 树保持了 B+树的既可以随即查找又可以顺序查找的优点， 并且利用其静态树的优势改善了 B+树空间利用率低下的问题。3.实验与性能分析3.1 实验环境本文中固定资产管理系统的具体实现环境如下：服务器端 2.8GHz Pentium PC, 1GB RAM，Oracle 9i 数据库。手持机端使用远望谷公司提供的带有 PDA 的手持式读写器， Windows Mobile

14、TM 5.0, ARM920T dxA27x, 64MB RAM。在 PDA 中嵌入数据库 SQLite3.3.4， 所有程序用 VC6.0 集成开发环境编写调试。3.2 空间利用率在测试空间利用率的实验中，所有关键字都是定长的 8 个字节，记录条数分别为 10，100，1000，10000，100000。结点大小由具体的 m 值来确定。实验所用公式如下3： 关键字所占空间=关键字长度 记录条数 （3） 实际占用空间 = 结点总数 结点大小 （4）关键字所占空间S-BtreeB+tree空间利用率 = 100%实际占用空间（5）测试结果如图 6 所示：9080空间利用率（%）706050403

15、02010010 100 100010000 100000记录条数图 6 空间利用率比较由图 6 可以看出，S-B 树在空间利用率上比相同情况下的 B+树平均高出约 30%，并且 随着记录条数增加，空间利用率呈现上升势态。3.3 时间效率SQlite3.3.4 时间效率的测试代码段如图 7 所示：Algorithm: test(num)Input: the number of records numOutput: the running time sqlite3 *db;int rc;char *sql;clock_t start,end; File *records; Sqlite3_ope

16、n(“test.db”,&db); records = fopen(“datafile”,”r”); while(records)char *p = fread(fopen);sql=”insert into testtb values (p)”;sqlite3_exec(db,sql,NULL,NULL,&zErr); fclose(records); start = clock();for(i=0;inum;i+)key=rand();sql = “select * from testtb where key=key”;sqlite3_exec(db,sql,NULL,&zErr); Sq

17、lite3_close(db);测试结果如图 8 所示：图 7 SQlite3.3.4 测试代码段9080B+treeS-Btree70时间（秒）60504030201000.021 0.625 7.53574.094 记录条数图 8 时间效率比较理论上，S-B 树与 B+树的时间复杂度均为 O(logmn)。然而实际的实验结果显示，随着记 录条数的增加，S-B 树的时间效率略高于 B+树，这是由于 S-B 树充分的利用了结点的空间， 使得树的高度有所减小，从而提高了查询效率。4.总结利用 S-B 树来解决无插入删除的嵌入式数据库系统中索引的空间利用率问题，对此类数 据库具有普遍的意义。将其应

18、用于固定资产管理系统，方便了自动化的管理。参考文献1蒋琳.嵌入式数据库关键技术的研究与实现D.东华大学,2006.122Comer D.The Ubiquitous B-TreeJ.ACM Computing Surveys, 1979,11( 2):121-137. 3刘彩苹.面向嵌入式数据库索引机制研究D.湖南大学,2004.124Yasushi Saito. Optimistic Replication Algorithm Tech report. University of Washington, Augest 2000.5Shirish Phatak,B R Badrinath. M

19、ultiversion Reeoneiliation for Mobile Databases. Proeeedings of the 1sthInternational Conferenceon Data Engineering, 1999:582-592.6Abraham Silberschatz, Henry F. Korth, S.Sudarshan. Database System Concepts(third edition), China MachinePress. 1999.3(1):346-358 7严蔚敏，吴伟民.数据结构(第二版)，清华大学出版社. 1993.9(4):

20、241-248An Improved Query Technique for Embedded DatabaseBased on S-B TreeHUANG Kai-yin1, HE Yan-shan2, CHEN Peng-fei2, LI Long-jie21. School of Economics & Management, South China Normal University, Shipai Guangzhou, PRC (510631)2. School of Information Science & Engineering, LanzhouUniversity, Lanz

21、hou Gansu, PRC (730000)AbstractFor the issue that embedded devices have limited space, this paper proposes a static balanced tree-S-B tree to substitute B+-tree as index of embedded database. Based on some embedded databases do not have to insert and delete on the actual application, S-B tree combin

22、es the brilliant time efficiency of B+-tree and the space utilization of static tree to reduce space waste by B+-tree index. We use this technique in the Embedded database SQLite of Fixed Assets Management System. The results of experiment show, compared to B+-tree in the same conditions, S-B tree h

23、as a better performance on time efficiency and space utilization which is above B+-tree about 30% on the average.Keywords: Embedded Database, B+-tree, Static Balanced Tree, S-B Tree作者简介: 黄楷胤(1964 ), 男, 教授，硕士, 主要研究方向为信息管理、新经济模式 (dr_huang)；何艳珊(1983),女,硕士研究生,主要研究方向为数据仓库、数据挖掘； 陈鹏飞(1986),男,硕士研究生,主要研究方向为数据仓库、数据挖掘；李龙杰(1980),男,助 理工程师,硕士,主要研究方向为数据仓库、数据挖掘。