（计算机应用技术专业论文）b树并发控制的有效封锁的研究与实现.pdf

摘要 b 树及其变种近年来一直作为一种数据结构用来存储大文件信息，特别是在辅 存中。那如何保证b 树搜索，插入，册4 除的安全性就变得对数据库应用及其重要。 为解决b 树并发访问控制的有效封锁，已有一些论文设计了b 树的一些衍生结构 并在这些结构上派生出了相应的算法。但算法中人存有一些问题未解决，诸如删除 算法中破坏了b 树平衔性的问题及添加算法中一个进程由于另个进程分裂了根节 点而从栈中找不到需要回溯的节点因而导致添加算法的错误。b 树的平衡性是b 树极 其有用的一大特性。本论文中对b 树的结构做了很大的改进并提出了s m 算法解决了 以往所没有解决的问题。该算法的一大优点是任何时间，任何进程同时去操纵b 树 都只使用极小数目稳定的锁，并且极大发挥了b 树基础上构造的b “树的连接指针 ( 1 i n kp o i n t e r ) 的作用，完成两个或多个并发进程之间的沟通，确保b “树上的 任何操作不改变该树结构的正确性。 关键字：关键多b 树，b t ir a 树，并发性，有效封锁，锁。 a b s t r a c t t h eb - t r e ea n di t sv a r i a n t sh a v eb e e nw i d e l yu s e di nr e c e n ty e a r sa sa d a t as t r u c t u r ef o r s t o r i n gl a r g e f i l e so f i n f o r m a t i o n ，e s p e c i a l l y o n s e c o n d a r ys t o r a g ed e v i c e s t h eg u a r a n t e e ds m a l l 。a v e r a g es e a r c hi n s e r t i o n a n dd e l e t i o nt i m ef o rt h e s e 、s t r u c t u r e sm a k e st h e m q u i t ea p p e a l i n g f o r d a t a b a s ea p p l i c a t i o n s i no r d e rt os o l v et h ee f f i c i e n t l o c k i n gf o r c o n c u r r e n to p e r a t i o n so n bt r e e s s o m es c i e n t i s t sh a dd e s i g ns o m ed a t as t r u c t u r e sd e r i r e df r o mbt r e e a n db r o u g h tu ps o m ea l g o r i t h m sb a s e do nt h e s es t r u c t u r e s b u tt h e r ea r es o m e u n s o l r e d q u e s t i o n s i nt h e s et h e s i s e s f o re x a m p i e ，t h ep r o b l e mt h a tt h e b a l a n c ei sb r o k e nd o w ni nt h ed e l e t i o nw h i l et h eb a l a n c eo ft h ebt r e ei s t h em o s tu s e f u la t t r i b u t eo f b _ t r e e i nt h i sp a p e r ，p r o v e m e n tt h a ti sb e n e f i t t ot h ee f f i c i e n tl o c k i n go nt h ebt r e eh a sb e e nm a d eo nt h ed a t as t r u c t u r e o fb t r e e ih a v eb r o u g h tu pa n 、a l g o r i t h mn a m e d “s m t h es o l u t i o ng i v e ni n t h ec u r r e n tp a p e rh a st h ea d v a n t a g et h a ta n yp r o c e s sf o rm a n i p u l a t i n g t h e t r e eu s e s o n l y as m a ll ( c o n s t a n t ) n u m b e ro fl o c k sa t a n yt i m e t h e s e c h a r a c t e r sd on o t a p p l y t ot h ep r e y i o n ss 0 1 u t i o n t h ek e yp o i n to ft h e a l g o r i t h mi st h a ti te x e r t st h el i n kp o i n t e ro ft h eb l i “_ t r e en o d es t r u c t u r e d o nt h ebt r e en o d et of u l f i11t h ec o w a l u n i c a t i o nb e t w e e nt w oo rm o r ec o n c u r r e n t p r o c e s st o e n s u r et h et r e es t r u c t u r en o tb ec h a n g e db ya n yo p e r a t i o n k e y w o r d ：k e y w o r d ，b t r e e ，g i i “_ t r e e ，c o n c u r r e n c y ，l o c k i n ge f f i c i e n c y ，l o c k 南京航空航天大学硕士学位论文 引言 在完成的工程数据库研究中，数据库的并发访问控制仅考虑数据库文件本身。为提 高访问速度，般采用索引技术。索引本身也是一种共享资源，也应考虑并发访问的问 题。在数据库的数据量不大的情况下，索引一般很小，简单的将索引锁定即可。但是如 果对特大型的数据库，它的索引本身也是很大的。如果整个索引作为封锁的粒度，则粒 度过大，影响弗发度。因而索引的并发操作，也应相当重视。 数据库的索引结构多采用l t r e e 结构。b 树以其高效，易变，平衡和对硬件相对独 立四大特点，构成索引组织的一种标准形式。设计合适的b t r e e 并发操作算法一直是数 据库界的研究课题之一，并有不少前期成果。 本课题的目标是分析已有的b - t r e e 并发操作，提出新的方案，并加以实现，以求完 善现有系统的性能。 课题提出的新算法仅封锁bt r e e 戢 少数几个结点。因而提高并发度。 本论文共分为五章，其中第三章和第四章是本论文的重点。第一章介绍了b 树和它的 一些变体的概念和各自的特性，第二章简单介绍了文献 1 中提到的p b 算法，并作了评价， 指出了它的不足：第三章提出了b 树上并发操作的s m 算法，对原p & b 算法中的b “树数据结 构作了很大改进，分析了这种数据结构较前两章介绍的b 树和它的一些变体对于并发操作 上更大的便利，提出了自己的插入和删除算法。解决了p b 删除算法中破坏了b 树平衡性 的问题及添加算法中一个进程由于另一个进程分裂了根节点而从栈中找不到需要回溯的 节点因而导致添加算法的错误，接着又给出了s m 算法的正确性证明及封锁有效性的证 明。第四章对b “树内存和有效性方面又作了一些扩充，看了有关文献后，对选择阶数 组织b “树降低空间开销和提高封锁有效性方面又提出了一些想法，基于此，又提出了 对b “树上的一些理论上的扩展。第五章则对操作中的几点问题和索引技术的发展作了 简单描述。 b 树的并发操作算法研究与实现 第一章b 树及其变种b 木树 1 1b 树 为了提高文件的存取效率，人们往往借助索引文件。索引文件由数据文件和索引表 组成，索引表是一个记录关键字和该记录在外存起始地址偶对的集合。一旦对某数据文 件建立了索引，就可由索引方便地查到所需的记录。 目前，人们已研究出许多种不同的索引结构，b 树是其中一种较为高效的索引结构。 b 树以其高效，易变，平衡，和对硬件相对独立这四大特点，构成索引组织的一种标准 形式。 1 1 1b 树概述 b 树是一种平衡的多元树，它是由r b a y e r $ 口e m c c r e i g h t 在1 9 7 0 年提出的，到1 9 7 9 年，b 树几乎已经代替了除散列方法以外的所有大型文件访问方法。b 树，或者b 树的一些 变体是需要插入，删除和关键码范围检索的应用程序的标准文件组织方法b 树致力于解 决实现基于磁盘的检索树时遇到的所有问题： 1 b y 总是高度平衡的，所有叶结点都在同一层。 2 更新和检索操作只影响一些磁盘页，因此性能很好。 3 b 树把相关的记录放在同一个磁盘页中，从而利用了访问局部性原理。 4 b 树保证树中至少有一定比例的结点是满的。这样能够改进空间的利用率，同时 在检索和更新操作期间减少需要的磁盘读取数目。 一个阶为m 的b 树是树中每个内部结点都包含多达m 个分枝的树。内部结点有i i l 个 子女，存储m 一1 个关键码值。 一棵d 阶的b 树定义为： ( 1 ) 每个结点至多有d 个孩子； ( 2 ) 除了根和叶结点外，每个结点至少有ld 21 个孩子： ( 3 ) 除非根结点是叶结点，否则根结点至少有两个孩子； ( 4 ) 所有的叶结点都在同一层上，并且不带有任何信息( 也认为是外部结点或查 找失败的结点) ： ( 5 )带有k 个孩子的非叶结点含有k - 1 个关键字。 图1 1 是一个含有j 个关键字年t j j + 1 个指针的b 树结点的一般形式： 每个结点内的关键字是从左到右递增排序的。下图中，k l k 。 k i ，指针p 。指向包 含在k ，与k 。之间那些关键字的子树。 2 南京航空航天大学硕士学位论文 上p 。 囤1 1b 树结点的一般形式 1 1 2b 树的各种操作 p j 查找 b 树查找类似于二叉树查找，所不同的是，二又树结点中只需比较一次关键字，而b 树中需比较多次。设需查找的关键字为k ，则查找过程为：从根开始，每调入个结点， 进行如下的判断处理： ( 1 ) 若k k ，从指针p 。进入下一极子树； ( 3 ) 若k k k i + l ，( i = 1 ，2 ，j - 1 ) ，从指针p i 进入下一极子树： ( 4 ) 若k = k ；，查找成功。 如果一直到叶结点还未找到，则表示k 不在该b 树中。 用c 语言描述的算法如下： * r e t u r n0ifm a t c hf o u n d ，l ifn o tf o u n d n o d ei st h er o o tn o d ef o ri n i t i a lc a l l f i n d ( t r e e ，n o d e ，g iv e n k e y ) i = 1 ：* s t a r ts e a r c ho fn o d ew it hf i r s tk e yi nn o d e * w h i l e ( k e y ( n o d e ，i ) ) d ) s p l i t _ n o d e ( n o d e ) ：胁n o d ei ss p l i ti n t ot w on o d e i f ( n o d e is r o o t ) ( g e t n e w n o d e ( ) ：章g e t an e wn o d e * i n s e r t ( m i d d l e - k e y ，n e w n o d e ) ： i n s e r tm i d d l ek e yv a l u ei n t on e wr o o tn o d e * ) e l s e ( i n s e r t ( m i d d l e k e y ，f a a t h e r _ n o d e ) ： 攘i n s e r tm id d le _ k e yv a l u ei n t ot h ef a t h e rn o d e c h e c k f o r o v e r f l o w ( t r e e ，f a t h e r _ n o d e ) ： ) ) 删除 从b 树中册4 除关键字的操作比插入操作要复杂些，因为必须考虑删除一个关键字后 的树仍然满足b 树的定义。 设k 为要删除的关键字，不管该关键字是否在叶结点中，都要转换成在叶结点中的 关键字处理。删除操作有可能要破坏b 树的平衡性，所以删除操作分以下几种情况： ( 一) k 在非叶结点中 首先需要找出b 树中大于关键字k 的最小值。具体方法为：从p 。找到下一层 结点的p 0 1 ，若p 0 11 = n u l l ，则再由指针p 0 1 找到下一层结点的p 0 2 ，一直找到p 0 。= n u l l 为止，此时该结点中的第一个关键字k ，。即为指针p ；所指子树中的最小者。然后将k 与 k ，。交换，此时k 就在叶结点中了，再按k 在叶结点中的删除法处理。 ( 二) k 在叶结点中 ( 1 ) k 所在结点中的关键字数目 = d 2 i o 此时只要直接从结点中删去该关键字和相应的指针即可。 ( 2 ) k 所在结点中的关键字数目爿d 2 1 1 ，而其左兄弟或右兄弟结点中的关键字数 目 r d 2 1 。 由于删去k 后，其结点的关键字数目小于最低要求划d 2i 1 ，需要进行调整，方法 为：将关键字数目大于 d 2 1 的左或右兄弟中的最小( 或最大) 的关键字k 上移 至其父结点中，然后把父结点中的小于( 或大于) k 的关键字下移至k 所处的结点中， b 树的并发操作算法研究与实现 使之仍然满足b 树的定义。 ( 3 ) k 所在结点中的关键字数目和其左，右兄弟结点中的关键字数目均等于f d 2 一1 。 这种情况需要进行与分裂相反的操作j 合并”，即将k 所在的结点和左( 或右) 兄弟 的结点，以及这两个结点之间的父结点中的关键字和并。如果在合并的过程中导致某个 结点中的关键字数目小于f d 2 卜l ，则应继续进行合并操作。 1 1 3 关于b 树 1 结点个数与最大层号的关系 如果b t 是一棵d 阶b 树，其中所有的外部结点均在第l + i 层上，则可知该树 中的关键字个数的最大值为d l l 根据b 树定义，第一层结点( 即根) 数为1 ，第二层 至少有二个结点，第三层至少有2 f d 2 7 个结点，第四层至少有2 r d 2 1 2 个结点，依 次类推，则第l + i 层至少有2 v d 2 p 1 个结点。设有n 个关键字，则外部结点数为n + i 。 所以得到： n + i = b t 中外部结点的个数 = 第l + l 层上的结点个数 = f f d 2 - f j 。- 所以，b 树b t 中关键字的个数n 应满足： 2 id 2 卜- 1 = n = d “，推出： l k ：t h e n * ki sap a r a m e t e r * l o c k ( t a m p ) ： l o c k ( 1 e f t ) ： 南京航空航天大学硕士学位论文 胁取c 中的最大值m a x ，移至t e m p 中，t e m p 中紧靠着 大于其的记为 m a x ，移至c u r r e n t 中 m a x m a x k e y ( c ) ： m a x a b o v e ( t e m p ，m a x ) ： a n o d e d e l e t e ( a jv ) ： c n o d e d e l e t e ( c ，m a x ) ： b n o d e d e l e t e ( b ， m a x ) ： b n o d e i n s e r t ( b ，m a x ) ： a n o d e i n s e r t ( a ， m a x ) ： p u t ( a 。c u r r e n t ) ： p u t ( b ，t e m p ) ： p u t ( c ，l e f t ) u n l o c k ( c u r r e n t ) ： u n l o c k ( t e m p ) ： u n l o c k ( 1 e f t ) ： e ls e r i g h t f i n d r i g h t p t r ( t e m p ，c u r r e n t ) ： * f i n dt h ep o i n t e rf r o mt h ef a t h e rn o d ep o i n tt o t h er i g h tb r o t h e ro ft h ec u r r e n tn o d e * ifk e y n u m ( r i g h t ) k 。c h e n b g e t ( t e m p ) ： c g e t ( r i g h t ) ： 章右边结点中的关键字数目大于k 的情况下 l o c k ( t e m p ) ： l o c k ( r i g h t ) ： 取c 中的最小值m i n ，移至t e m p 中，t e m p 中紧靠着 小于其的记为 m i n ，移至c u r r e n t 中木 m i n m i n k e y ( c ) ： m i n b e l o w ( t e m p m i n ) ： a n o d e d e l e t e ( a 。v ) ： c n o d e d e l e t e ( c ，m i n ) ： b n o d e d e l e t e ( b ， kt h e n 左或右结点的关键字k e y l 与父结点的关键字k e y 2 移位 m o v e k e y ( k e y l ，l e f t ，t e m p ) ： * m o v ek e y i f r o mt h e l e f tn o d et ot h ef a t h e rn o d e * m o v e k e y ( k e y 2 ，t e m p ，c u r r e n t ) ： * m o v ek e y 2f r o mt h ef a t h e rn o d et ot h ec u r r e n tn o d e * c u r r e n t t e m p ： e is e 左或右与c u r r e n t 及父结的关键字合并： c u r r e n t t e m p ： e n d ； g o t od o c a t e n a t i o n ： 3 l b 树的并发操作算法研究与实现 e n d ： e n d ： e n d ： e n d ： e n d 以上为s m 算法中删除算法的中用到的一些函数说明： k e y n u m ( a ) 返回结点a 中的关键字数目。 f i n d c o m b i n n o d e ( a ) 顺着关键字数目为零的那个结点的连接指针找到合并后的那个 结点。 c a l l b a c k ( a ) 回收结点a 所占据的磁盘页面。 c l e a r s t a c k0 把用来存储记忆链表的栈清空。 n o d e d e l e t e ( a ，v ) 从结点a 中将关键字a 删除。 f i n d l e f t p t r ( a ，b ) 返回a 结点中指向结点b 的左兄弟结点的指针。 f i n d r i g h t p t r ( a ，b ) 返回a 结点中指向结点b 的右兄弟结点的指针。 m a x k e y ( a ) 返回结点a 中的最大关键字。 a b o v e ( a ，v a l u e ) 返回结点a 中大于值v a l u e 的最小关键字。 m i n k e y ( a ) 返回结点a 中的最小关键字。 b e l o w ( a ，v a l u e ) 返回结点a 中小于值v a l u e 的最大关键字。 f i n d k e y ( a ，r i g h t ，l e f t ) 返回结点a 中处于指针r i g h t 和l e f t 之间的那个关键字。 n e g a t i v e ( a ，k e y ) 将结点a 中的关键字k e y 值赋为负值。 m i n u s k e y n u m ( a ) 将结点a 中的关键字数目减1 。 m o v e k e y ( k e y ，a ，b ) 将关键字k e y 从结点a 移至结点b 。 3 4 正确性的粗略证明 3 4 1 正确性证明的几个先决条件 为了证明s m 算法的正确性，必须先证明每个进程都必须遵循的两个先决条件 ( 1 ) 定理一：永远不会死锁 ( 2 ) 这第二点在操作结束时，己被正确地执行了，特别是： ( a ) 定理二：所有的磁盘操作都保证树结构的正确性： ( b ) 交互操作定理三：所有的进程而不仅仅是更改进程看到的都是一棵一致的树 南京航空航天大学硕士学位论文 3 4 2 不死锁的证明( f r e e d o mf r o md e a d l o c k ) 首先，可以总结一下该算法中为保证死锁绝灭的一些证据。可以先规定一个结点的顺 序：从底沿着每一层至上，而在给定的一层，结点从左至右排序。下面提出的引理中就 按这种顺序排序。 引理l ：由添加者为结点所上的锁是有着良好排序性( w e l l - o r d e r i n g ) 的。 证明：看一下树中结点的排序。 ( 1 ) 在任何时刻，t ，若有两个结点a 和b ，它们到根结点的距离不同，也就是说，它 们在树中所处的层次不同，如果也只有当a 到根的距离大于b 到根的距离( 即a 在树中的层次低于b 时) 时，就认为a b 。 ( 2 ) 假如结点a 和b 到根结点的距离相同，( 即两者处于树中的同一层次) ，如果也 只有当b 可以由a 沿着一个或多个连接指针检索到( 即b 在a 右边) 时，认为a b 。 在添加进程中，若某一时刻t 。，a t 。，a b ，因为结点的生成 过程只是简单地将一个结点x 分裂成x 和x 。，并且x x7 ，那么，则有对任意结 点y ，若y x ，则y x7 和若x y ，则x7 y 。由此可见，分裂后的结点仍然保持着 良好的排序性。 在删除进程中，若某一时刻t 。，a t 。，a b ，结点的合并过程 将x 和其右边的结点x 右( 按s m 算法) 合并至右结点，生成新结点1 右占据与原右结 点相同的磁盘页面，则对任意结点y ，若y x 因为x 。右，所以y 1 右，所以y x 右， 若x y ，则x 右 y ( y c x 右) ，推出x 右 y 。由此可见，合并后的结点仍保持良好的排 序性。 添加和删除进程即循着这样的良好排序性，为结点上锁。一旦进程锁定了一个结点， 那么它不会再去锁定比该结点层次低的结点及同一层上在其左边的结点。由此可见，添 加进程也是按照给定的顺序设置锁的。 因为只有添加和删除进程可以为结点上锁，所以得出以下结论： 定理l ：移琵锁。s m 算法给定的系统不可能产生死锁。 3 4 3b 树更改操作正确性的证明 为了确保树结构的保存，必须检测所有可能改变树结构的操作。首先，注意到，只 有“p u t ”操作和“c a l l b a c k ”操作才会使树发生改变。s m 算法的添加算法中，有四处 “p u t ”操作，而删除算法中，五处“p u t ”操作。下面分别分析。 b 树的并发操作算法研究与实现 添加中； ( i ) “p u t ( a ，c u r r e n t ) ”去重新写回一个安全结点； ( 2 ) 关于危险结点的“p u t ( b ，u ) ”操作，形成由于分裂产生的两个结点中的第二个( 即 右边的) 结点。 ( 3 ) 关于危险结点的“p u t ( a c u r r e n t ) ”操作，形成分裂产生的第一个( 左边的) 结 点。其实这个页面已经存在树中，只需重新写回并且将该结点的连接指针指向由 “p u t ( b ，u ) ”操作产生的新结点即可。 ( 4 ) “p u t ( c ，h e a d ) ”形成一个新的根结点，老的根结点被分裂了。将新结点关键字的 两个指针分别指向分裂后的两个结点。 ( 5 ) “p u t ( b ，u ) ”因为新根结点的产生，将分裂后的第二个结点的连接指针指向新根 结点，以利其它进程回溯。 注意到，对于危险结点来说，“p u t ( b ，u ) ”操作在“p u t ( a ，c u r r e n t ) ”操作之前， 根据以下的引理，可以看出，这样的操作颇序使得这两个操作实际上象个操作。 引理2 ：“p u t ( a ，c u r r e n t ) ”和“p u t ( b ，u ) ”两个操作等同于树结构的一个变化。 证明： 假设两个操作分别写了结点a 和b 。执行操作“p u t ( b u ) ”时，没有包含指向结点b 的指针的结点被写回，所以，这个p u t 操作对树结构不产生影响。 执行操作“p u t ( a ，c u r r e n t ) ”时，这个操作更改了指针c u r r e n t 所指的结点a 。这 个更改包括将结点a 的连接指针指向结点b 。这时，结点b 已经存在b 的连接指针指 向分裂前的结点a 的连接指针指向的那个结点。以上这两个操作就好象在树结构中同时 更改结点a 并引入结点b 。证毕。 同理，操作“p u t ( c ，h e a d ) ”写了新的根结点c ，执行这个操作时，没有包含指向结 点c 的指针的结点被写回，结点c 指向子结点a ，b ，只是将树结构添加了一层所以这个 操作不破坏树结构。再次“p u t ( b ，u ) ”时，因为磁盘中该页面已存在，且新结点c 业已 存在，只需将结点b 的连接指针指向结点c 即可。 由以上分析，五个p u t 操作均不会破坏树结构。 引理2 ：所有的p u t 操作都正确地改变了树结构。 证明： 情况1 ：重新写回安全结点的“p u t ( a ，c u r r e n t ) ”。这个操作只改变了树中一个上 了锁的结点，树结构的正确性没有改变。 情况2 ：写回新结点“p u t ( b ，u ) ”。这个操作没有改变树结构。 情况3 ：“p u t ( a ，c u r r e n t ) ”，根据引理，这个操作改变了c u r r e n t 结点同时加入 南京航空航天大学硕士学位论文 了一个额外