[word doc]基于B＋树索引的实时数据库缓冲区管理算法

[word doc]基于B＋树索引的实时数据库缓冲区管理算法[word doc]基于B＋树索引的实时数据库缓冲区管理算法基于B，树索引的实时数据库缓冲区管理算法工程技术计算机光盘软件与应用 ComputerCDSoftwareandApplications2010年第12期基于B+树索引的实时数据库缓冲区管理算法社冀秦 (华北计算机系统工程研究所,北京100083) 摘要:考虑到工控位号历史数据时间戳递增的特点,针对已有实时数据库产品历史数据存储索引查询效率不高,磁盘空间利用率低的不足,提出了一种以B+树为索引方式,以状态链表和页式存储为管理...

[word doc]基于B＋树索引的实时数据库缓冲区管理算法基于B，树索引的实时数据库缓冲区管理算法工程技术计算机光盘软件与应用 ComputerCDSoftwareandApplications2010年第12期基于B+树索引的实时数据库缓冲区管理算法社冀秦 (华北计算机系统工程研究所,北京100083) 摘要:考虑到工控位号历史数据时间戳递增的特点,针对已有实时数据库产品历史数据存储索引查询效率不高,磁盘空间利用率低的不足,提出了一种以B+树为索引方式,以状态链表和页式存储为管理方式的历史数据缓冲区管理方式. 经过实际测试表明,基于该缓冲区管理算法的历史数据存储模块存取效率高,并发性能好,磁盘空间的利用率高,完全可以替代关系数据库作为实时数据库的历史数据存储模块. 关键词:实时数据库;历史数据;B+树中图分类号:TP309文献标识码:A文章编号:1007-9599(2010)12-0116 一叭 B+TreeIndexbasedBuffermanagementAlgorithmofReal-timeDatabase DuJiqin (NationalComputerSystemsEngineeringResearchInstituteofChina,Beijing100083,China) Abstract:Consideringtheincrementofhistorydatatimestampinreal-timedatabase,withrespecttothedefectthatexisting real-timedatabaseproductarenoteffectiveatindexofdataandarelowinstorageutilization,thearticleproposesaB+treebased buffermanagementalgorithmwithstatelinkedlistandsegmentationwithpaging.theresultshowsthatthehistorystoragemodule usingthisalgorithmisgoodathandlinghistorydataaCCeSSandconcurrentrequests,withgoodstorageutilization. Keywords:Real-timedatabase;Historydata;B+tree 一 ,引言实时数据库系统是开发实时控制系统,数据采集系统,CIMS 系统等的支撑软件.在流程行业中,大量使用实时数据库系统进行控制系统监控,系统先进控制和优化控制”,本文针对工控历史数据的特点,提出了一种改善的B+树索引,并将其应用到实时数据库历史数据缓冲管理当中,测试结果证明,该设计有效避免了因I/0操作而引起的系统阻塞,从而达到了高效管理历史数据缓存的目的. 二,数据结构及算法 (一)改进的B+树 B一和B+树是关系数据库普遍常采用的数据结构,由于其每个节点具有固定的大小,并且非叶子节点具有的大量的分支,使其具有了更小的查找深度和更少的磁盘空间开销.但是由于为了保持B+树的平衡性,当一个节点(无论是叶子节点还是非叶子节点)由于数据写满而产生分裂的时候,节点会从中部裂开,并将处于中间位置的键值写入其父节点,当写入键值的大小是随机的情况下,这种策略是可以保证树的整体平衡性的,但是,对于工业现场采集的历史数据而言,数据往往以其时间标签作为键值 ,正常情况下,该键值只会增加而不会减小.在这种情况下, 如果依然按照原来的策略进行节点分裂的话,势必造成时间标签较小的那一页面的空间浪费,因为在无历史数据追加的情况下, 这一页面永远都不会再次插入数据了.因此,为了尽量提高页面的利用率,我们将节点分裂的部位向后推移,对于叶节点,我们将最后一条记录值复制到新申请的兄弟节点上,并将该记录的键值插入到父节点中,对于非叶子节点,我们将最后一条键值写入其兄弟节点中,将倒数第二条键值插入其父节点中,采用这种策略,相比于原来的B+树,磁盘空间的利用率提升了近一倍,虽然在一定程度上,B树的平衡性降低了,但查找效率并没有损失太多,因此,总体来讲,改进的结果是利远大于弊. (二)插入及查找算法大致流程最初系统为每一个测点分配一个叶子节点,当该结点写满之后,会按照所讲到的策略进行分裂生成新的父节点和兄弟节点. 以后每生成一个新的兄弟节点,都会将该节点的第一条记录插入父节点当中,如果父节点也被写满了,就按照策略进行内部节点的分裂,当爷爷节点也被写满的时候,便按照父节点被写满时的分裂方式,再次分裂,依次类推,直到父节点不需要再分裂,或者没有父节点为止.当根节点因写满而分裂时,B+树的层次便提升了一层,随着树的层次不断升高,B+树所索引的数据量也在以指数方式增长. 三,数据写入速度测试结果为了方便对比,本文选择在组态单点,10点,i00点和1000 点的情况下,写入7800万条数据所用的时间,经测试,平均写入速度在150万次/秒左右. 四,总结基于新的缓冲区管理算法的历史数据存储系统,具有层次清晰,磁盘空间利用率大,数据存取效率高,并发性能良好的特点, 很适合作为要求快速响应的实时数据库的历史存储核心.今后应当在此基础上,引入数据库点组态功能,支持更多的点类型,并且逐步探索数据恢复功能,保证存储系统在遭到意外而终止之后, 能够在重启动之后将系统恢复到一致性状态. 参考文献: …刘卫昌,马增良.企业综合自动化系统中实时数据库系统设计卟计算机应用研究,2005,22,8:146—149 【2】ThomasKyte.ExpertOracleDatabaseArchitecture9iandlOg ProgrammingTechniquesandSolutions[M].Apress,UnitedStatesof America,2005 【3】魏小亮,蔡弘B一树/B+树的批量插入算法叽北京:中央民族大学 (自然科学版),2001,10,1:57—61

                    本文档为【[word doc]基于B＋树索引的实时数据库缓冲区管理算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

[word doc]基于B＋树索引的实时数据库缓冲区管理算法

你可能还喜欢