情感社区,陈建州的老婆,上海迪斯尼票价
经过几天鏖战终于完成了lab2，本lab实现一个支持并发操作的b+树。简直b格满满。
b+树本质上是一个索引数据结构。比如我们要用某个给定的id去检索某个student记录，如果没有索引的话，我们可能从第一条记录开始遍历每一个student记录，直到找到某个id和我们给定的id一致的记录。可想而知，这是非常耗时的。
如果我们已经维护了一个以id为key的索引结构，我们可以向索引查询这个id对应的记录所在的位置，然后直接从这个位置读取这个记录。从索引查询某个id对应的位置，这个操作需要高效，b+树能保证以o(log n)的时间复杂度完成。
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)操作的伪代码。
思路就是：
课本p498给出了完整的delete(key)操作的伪代码。
思路：
最粗暴的方式就是在find, insert, delete开始就加锁，执行完毕后解锁，这样逻辑上没有问题，但是并发效率很低，相当于串行执行。
该协议允许多个线程同时访问修改b+树。
举个查找过程的例子，查找key=38：
举个插入过程的例子，插入25：
crab有螃蟹的意思，了解完crabbing协议加锁的过程，应该不难理解为什么叫crabbing协议了吧。
我们需要保护根节点id。
考虑下面这种情况：
两个线程同时执行插入操作，插入前b+树只有一个节点，线程一插入当前key后将分裂，生成一个新的根节点。另一个线程在线程一分裂前读取了旧的根节点，从而将key插入到了错误的叶子节点中。
解决办法：
在访问，修改root_page_id_的地方加锁，访问或者修改完毕root_page_id_后释放锁。root_page_id_指向的是该b+树的根节点，会保存在内存中，以便快速查找。
最后，贴个实现：
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论