- 协议介绍:
下降方法 {
获取根节点并锁住根节点(读锁)
while (true) {
if (此节点是叶子节点) {
if (插入方法调用) {
//这里为什么不用锁升级而要这么做,后面会解释.
解锁此节点(读锁)
此节点加锁(写锁)
更新此节点的内容.
}
返回此节点(此时此节点加锁,读调用加读锁,插入调用加写锁)
}
int rightPos;
while (需要右移) {
获取右节点位置
此节点解锁(读锁)
获取右节点并加锁(读锁)
此节点等于右节点
}
获取下降位置
此节点解锁
获取下一层节点并加锁
}
}
读方法 {
调用下降方法,获取叶子节点(已加读锁)
while (true) {
if (需要右移) {
获取右节点位置
此节点解锁(读锁)
获取右节点并加锁(读锁)
此节点等于右节点
continue;
}
检索叶子节点,查找是否有符合的key.
解锁此节点.
返回value;
}
}
插入方法 {
调用下降方法,获取叶子节点(已加写锁)
while (需要右移) {
获取右节点位置
此节点解锁(写锁)
获取右节点并加锁(写锁)
此节点等于右节点
}
if (节点满) {
调用分裂方法
} else {
插入key和value在此节点中.
此节点解锁(写锁).
}
}
分裂方法 {
while (此节点满) {
if (此节点为根节点) {
创建一个新的根节点(不用加锁)
分裂当前节点产生一个新节点(不用加锁)
key等于新节点的最小键值,value等于新节点的位置.
} else {
分裂当前节点产生一个新节点,且把key和value插入相应节点(不用加锁)
key等于新节点的最小键值,value等于新节点的位置.
获取父节点并加锁(写锁,且需要右移,右移与插入方法中的写法一致)
}
解锁当前节点(写锁)
当前节点等于父节点
}
把key和value插入当前节点
解锁当前节点(写锁)
}
- 协议证明:
-
不会死锁
-
死锁的必要条件
- 互斥：每个资源要么已经分配给了一个进程，要么就是可用的。
- 占有和等待：已经得到了某个资源的进程可以再请求新的资源。
- 不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显示地释放。
- 环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。
-
从下降方法可以看到,下降方法在获取下一个节点的锁的时候会先释放当前节点的锁,也就是说不满足死锁的必要条件的第二条,所以下降方法不会发生死锁.
这里解释一下下降方法里为什么不用锁升级,因为可能会有两个线程插入数据同时下降到同一个叶子节点,这时两个线程都锁升级就会发生死锁. -
在需要右移的时候也是先放弃当前节点的锁,再获取右节点的锁,所以右移也不会发生死锁.
-
在分裂方法里会同时持有两个锁,但是其加锁顺序是获得当前节点的锁,再请求父节点的锁,所以不会构成环路,不满足死锁的必要条件的第四条,所以分裂方法也不会死锁.
-
综上,该协议不会发生死锁,不需要进行死锁检验.
-
-
在并发读写时保证一致性.
-
首先考虑插入时叶子节点未满.
此时通过下降函数和右移找到那个叶子节点,此时那个叶子节点被加写锁,叶子节点插入完成后,才解除写锁.
此时有其他线程要读到这个叶子节点必须等待解除写锁,所以其他线程看到的叶子节点是完整的. -
再考虑插入时叶子节点满
-
不考虑中途断电
此时调用分裂函数,获得该节点的写锁,再生成另一个新节点,把该节点的一般数据分给新节点,写入磁盘.再把该节点写入磁盘,然后获得父节点的写锁,把新节点的位置写入父节点.这样递归上去,直至节点不满.可以发现,在获取节点的锁的时候,整个b+树会处在一致的状态. -
中途断电
如果在把新节点写入磁盘后断电,这时原节点还没有更新到磁盘,所以处于一致状态.
如果在把原节点写入磁盘后断电,这时因为父节点未写入新节点的位置.但是因为原节点的右指针指向新节点,所以新节点可以被访问到,所以处于一致的状态.
-
-
-
在这里提一下,我实现这个b+树的时候,b+树的节点储存在一个有日志的存储模块,节点写入前会记录在日志,重新启动时会重写日志的内容,所以每个节点要么完全写入了磁盘,要么完全没写入磁盘,
也就是说这个协议不用关注节点本身结构是否会被破坏,只关注节点之间的关系是否会影响b+树的一致性.