概述
经过几天鏖战终于完成了lab2,本lab实现一个支持并发操作的b+树。简直b格满满。
b+树
为什么需要b+树
b+树本质上是一个索引数据结构。比如我们要用某个给定的id去检索某个student记录,如果没有索引的话,我们可能从第一条记录开始遍历每一个student记录,直到找到某个id和我们给定的id一致的记录。可想而知,这是非常耗时的。
如果我们已经维护了一个以id为key的索引结构,我们可以向索引查询这个id对应的记录所在的位置,然后直接从这个位置读取这个记录。从索引查询某个id对应的位置,这个操作需要高效,b+树能保证以o(log n)的时间复杂度完成。
b+树的性质
b+树由叶子节点和内部节点组成,和其它树结构差不多,但是对(key, value)的个数和排列顺序有要求。
叶子节点:
格式如下:
* --------------------------------------------------------------------------- * | header | key(1) + rid(1) | key(2) + rid(2) | ... | key(n) + rid(n) * ---------------------------------------------------------------------------
假设叶子结点最多能容纳个n个(key, rid)对,那么该叶子节点任何时候都不能少于n/2向上取整个(key, rid)对。假设(key, rid)对个数为x,那么x必须满足:
ceil(n/2) <= x <= n
ceil表示向上取整,博客园不支持latex o(╯□╰)o。
key是search key,rid是该key对应的记录的位置。(key, rid)对按照key的増序进行排列。
header的结构如下:
* ---------------------------------------------------------------------------------------- * | pagetype (4) | lsn (4) | currentsize (4) | maxsize (4) | parentpageid (4) | pageid(4) | * ---------------------------------------------------------------------------------------
parentpageid指向父节点。
内部节点
* ---------------------------------------------------------------------------------------- * | header | invalid_key+page_id(1) | key(2)+page_id(2) | ... | key(n)+page_id(n) | * ----------------------------------------------------------------------------------------
假设内部节点最多容纳n个(key, page_id)对,和叶子节点一样,x必须满足:
ceil(n/2) <= x <= n
key表示search key,page_id指的是子节点的id。
(key, page_id)对按照key的増序进行排列。
第一个key是无效的。
假设page_id(i)对应的子树中的key用sub_key表示,那么subkey都满足:key(i) <= sub_key < key(i+1)。
查找操作
课本p489给出了find的伪代码。总结来说就是先找到key应该出现的叶子节点,然后在该叶子节点中,查找key对应的rid。
如下图:
假如我们希望查找的key为38,第一步在根节点a查找38应该出现在哪个子节点中,根据之前的性质,38应该出现在以b为根的子树中,继续查找节点b,以此类推,最终38应该出现在h的叶子节点中。最后我们在h中查找38。
所以对于内部节点,我们需要一个lookup(const keytype &key,const keycomparator &comparator)方法,查找key应该出现在哪个子节点对应的子树中。
index_template_arguments valuetype b_plus_tree_internal_page_type::lookup(const keytype &key, const keycomparator &comparator) const { assert(getsize() >= 2); // 先找到第一个array[index].first大于等于key的index(从index 1开始) int left = 1; int right = getsize() - 1; int mid; int compareresult; int targetindex; while (left <= right) { mid = left + (right - left) / 2; compareresult = comparator(array[mid].first, key); if (compareresult == 0) { left = mid; break; } else if (compareresult < 0) { left = mid + 1; } else { right = mid - 1; } } targetindex = left; // key比array中所有key都要大 if (targetindex >= getsize()) { return array[getsize() - 1].second; } if (comparator(array[targetindex].first, key) == 0) { return array[targetindex].second; } else { return array[targetindex - 1].second; } }
因为key是已排序的,所以可以先二分查找第一个大于或等于key的下标targetindex,如果targetindex对应的key就是我们要找的key,那么targetindex对应的value就是下一步要搜索的节点,否则targetindex-1对应的value是下一步应该搜索的节点。
插入操作
课本p494给出了完整的insert(key, value)操作的伪代码。
思路就是:
- 先找到key应该出现的叶子节点,将(key, value)插入到该叶子节点中。
- 如果插入后该叶子节点中键值对超出了最大值,则进行分裂。如果插入后没有超出最大限制,那么就完成任务了。
如上图准备插入(7, ‘g’),但是插入前p1叶子结点已经满了,那么先插入,然后将插入后的节点,分裂出新的节点p3,将p1原来一半的元素挪到p3,然后将(6, p3)插入到父节点p2中,其中6是新创建的节点p3第一个key。
同样的,如果我们在父节点p2中插入了(6, p3)导致了p2超过最大限制,p2也需要分裂,以此类推,这个过程可能产生新的根节点。
删除操作
课本p498给出了完整的delete(key)操作的伪代码。
思路:
- 先找到key应该出现的叶子节点,删除该叶子节点中key对应的键值对。
- 删除后如果个数少于规定最少个数,那么有两个措施,如果当前节点个数和兄弟节点个数总和不超过允许的最大个数,那么进行并合。否则,从兄弟节点中借一个元素。
上图第一种情况:
删除(7, ‘g’)后,p3只有一个元素,少于最少允许的个数(2),于是将(6, ‘f’)已到兄弟节点p1, 删除p3节点,并且删除父节点p2中的(6, p3),如果p2也少于最少允许个数,递归进行。
第二种请求:
删除p3的(8, ‘h’)后,p3只有一个元素,于是从兄弟节点p1借一个元素(6, f),然后将父节点(7, ‘g’)修改为(6, ‘f’),这种情况不需要递归。
支持并发操作
最粗暴的方式就是在find, insert, delete开始就加锁,执行完毕后解锁,这样逻辑上没有问题,但是并发效率很低,相当于串行执行。
crabbing协议
该协议允许多个线程同时访问修改b+树。
基本算法
- 对于查询操作,从根节点开始,首先获取根节点的读锁,然后在根节点中查找key应该出现的孩子节点,获取孩子节点的读锁,然后释放根节点的读锁,以此类推,直到找到目标叶子节点,此时该叶子节点获取了读锁。
- 对于删除和插入操作,也是从根节点开始,先获取根节点的写锁,一旦孩子节点也获取了写锁,检查根节点是否安全,如果安全释放孩子节点所有祖先节点的写锁,以此类推,直到找到目标叶子节点。节点安全定义如下:如果对于插入操作,如果再插入一个元素,不会产生分裂,或者对于删除操作,如果再删除一个元素,不会产生并合。
举个查找过程的例子,查找key=38:
举个插入过程的例子,插入25:
crab有螃蟹的意思,了解完crabbing协议加锁的过程,应该不难理解为什么叫crabbing协议了吧。
需要注意的地方
我们需要保护根节点id。
考虑下面这种情况:
两个线程同时执行插入操作,插入前b+树只有一个节点,线程一插入当前key后将分裂,生成一个新的根节点。另一个线程在线程一分裂前读取了旧的根节点,从而将key插入到了错误的叶子节点中。
解决办法:
在访问,修改root_page_id_的地方加锁,访问或者修改完毕root_page_id_后释放锁。root_page_id_指向的是该b+树的根节点,会保存在内存中,以便快速查找。
实验遇到的坑和解决方案
- 前文提到我们需要保护root_page_id_这个变量,可以用一个mutex,访问或修改前加锁,访问或者修改后释放锁。一次加锁只能对应一次解锁,如果多调用了一次unlock(),同样起不到保护的作用。unlock()调用分别在各个函数中,很可能不小心就多调用了次,所以千万要小心。
- 必须先释放page上的锁,然后才能unpin该page。为什么?我们知道unpin后,如果pin_count为0,那么这个page将被送到lrureplacer,当没有足够的page时,将从lrureplacer中取page,将该page的内容保存到磁盘后用于保存其它其它页的内容。考虑下面这个场景:在插入25的过程中,查找到目标叶子节点,这时该叶子节点肯定被加上了写锁,如果我们执行完插入后,先unpin了该page,然后才释放该page的锁。可能出现这种情况,在unpin完后,释放锁前,这个page被送到了lrureplacer,另一个线程请求访问页面1,但是所有的page都被占用了,lrureplacer选择这个淘汰带锁的这个page来保存页面1,因为该page的锁还没释放,所以另一个线程可以直接访问或者修改,这是回到原来的线程,再释放已经晚了。
- lab本身提供的测试case是完全不够的,就算全部通过了,也不能保证代码是正确的。我自己加入了很多测试,涵盖多个线程的,根节点分裂等case。原代码只有对bplustree的测试,所以我添加了对bplustreeinternalpage和bplustreeleafpage单独的测试,这样在用bplustreeinternalpage和bplustreeleafpage构建bplustree前能保证自己是正确的。
- 在使用完一个page后应该立刻unpin掉,不能忘记unpin,如果忘记unpin的话,那么这个page将永远不能用于保存其它页,当所有page都被占用后,系统将无法继续运行。这个问题一度困扰我很久,一定要非常仔细。
- 本lab的一个难点是调试,多使用assert和log。
最后,贴个实现:
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/603637.html