b树并发控制的有效封锁的研究与实现

《b树并发控制的有效封锁的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、南京航空航天大学硕士学位论文B树并发控制的有效封锁的研究与实现姓名：孙鸣申请学位级别：硕士专业：计算机应用技术指导教师：林钧海20000201摘要B树及其变种近年来一直作为一种数据结构用来存储大文件信息，特别是在辅存中。那如何保证B树搜索，插入，册4除的安全性就变得对数据库应用及其重要。为解决B树并发访问控制的有效封锁，已有一些论文设计了B树的一些衍生结构并在这些结构上派生出了相应的算法。但算法中人存有一些问题未解决，诸如删除算法中破坏了B树平衔性的问题及添加算法中一个进程由于另～个进程分裂了根节点而从栈中找不到需要回溯的节点因而导致添加算法的错误。B树的平衡

2、性是B树极其有用的一大特性。本论文中对B树的结构做了很大的改进并提出了SM算法解决了以往所没有解决的问题。该算法的一大优点是任何时间，任何进程同时去操纵B树都只使用极小数目稳定的锁，并且极大发挥了B树基础上构造的B““树的连接指针(1inkpointer)的作用，完成两个或多个并发进程之间的沟通，确保B““树上的任何操作不改变该树结构的正确性。关键字：关键多B树，Btira树，并发性，有效封锁，锁。AbstractTheB-treeanditsvariantshavebeenwidelyusedinrecentyearsasadatastructurefors

3、toringlargefilesofinformation，especiallYonsecondarystoragedevices．Theguaranteedsmall。averagesearchinsertionanddeletiontimeforthese、structuresmakesthemquiteappealingfordatabaseapplications．InordertosolvetheefficientlockingforconcurrentoperationsonBtrees．SomeSCientistShaddesignsomedat

4、astructuresderiredfromBtreeandbroughtupsomealgorithmsbasedonthesestructures．Buttherearesomeunsolredquestionsinthesethesises．ForexampIe，theproblemthatthebalanceiSbrokendowninthedeletionwhilethebalanceoftheBtreeiSthemostusefulattributeofB_tree．Inthispaper，provementthatiSbenefittotheef

5、ficientlockingontheBtreehasbeenmadeonthedatastructureofB—tree．Ihavebroughtupan、algorithmnamed“SM'’．Thesolutiongiveninthecurrentpaperhastheadvantagethatanyprocessformanipulatingthetreeusesonlyasmall(constant)numberoflocksatanytime．ThesecharactersdonotapplYtothepreyionsS01ution．Thekey

6、pointofthealgorithmisthatitexertsthelinkpointeroftheBli“_treenodestructuredontheBtreenodetofulfi1theCOWalunicationbetweentwoormoreconcurrentprocesstoensurethetreestructurenotbechangedbyanyoperation．Keyword：keyword，B—tree，gIi“_tree，concurrency，lockingefficiency，lock．南京航空航天大学硕士学位论文引言在

7、完成的工程数据库研究中，数据库的并发访问控制仅考虑数据库文件本身。为提高访问速度，～般采用索引技术。索引本身也是一种共享资源，也应考虑并发访问的问题。在数据库的数据量不大的情况下，索引一般很小，简单的将索引锁定即可。但是如果对特大型的数据库，它的索引本身也是很大的。如果整个索引作为封锁的粒度，则粒度过大，影响弗发度。因而索引的并发操作，也应相当重视。数据库的索引结构多采用Ltree结构。B树以其高效，易变，平衡和对硬件相对独立四大特点，构成索引组织的一种标准形式。设计合适的B—tree并发操作算法一直是数据库界的研究课题之一，并有不少前期成果。本课题的目标是分

8、析已有的B-tree并发操作，提出新的