并发重平衡AVL树：一种细粒度方法
需积分: 1 26 浏览量
更新于2024-07-30
收藏 397KB PDF 举报
"这篇研究报告是关于并发重平衡AVL树的细粒度方法，由Luc Bougée, Joaquim Gabarró, Xavier Messeguer和Nicolas Sc habanel在Mai期间撰写，发表于Ecole Normale Supérieure de Lyon的Laboratoire d'Informatique du Parallélisme，该实验室与CNRS（法国国家科学研究中心）有合作关系。报告探讨了如何在并发环境下对几乎平衡的二叉搜索树（AVL树）进行重平衡，尤其是在连续插入和删除键之后的情况。报告采用了分布式系统自组织的视角，借鉴Dijkstra的方法来研究这个问题。
AVL树是一种自平衡的二叉搜索树，其每个节点的两个子树的高度最多相差1。这种平衡性保证了AVL树在插入、删除和查找操作上的高效性。然而，这些操作可能破坏树的平衡性，需要进行重平衡以恢复其特性。
并发重平衡是指在多线程或分布式环境下同时进行的重平衡操作，这增加了复杂性，因为需要确保在并发操作中数据结构的一致性和正确性。作者提出了一种细粒度的策略，这种方法将重平衡任务分解为更小、独立的单元，允许各个部分并行执行，同时保持对全局平衡状态的控制。
报告中，他们可能分析了不同并发策略的性能，比如锁的使用、无锁算法、读写冲突的解决以及如何通过局部规则来协调节点的移动，以实现整体的平衡。Dijkstra的自组织方法通常涉及每个节点基于局部信息做出决策，这在并发环境中可以减少全局协调的开销，提高系统的并发性和效率。
此外，报告可能还涵盖了实际应用中的性能评估、实验结果和与现有并发重平衡技术的比较。通过这种方式，作者们可能提供了新的见解和优化策略，以改进并发环境下的AVL树操作性能，这对于多线程编程和分布式系统设计具有重要的理论和实践意义。
这篇报告深入探讨了并发环境下的AVL树重平衡问题，提出了一种基于局部规则和细粒度控制的新方法，旨在解决并发操作中的平衡维护挑战，同时保持高效率和数据一致性。"
(and error-prone!) description. Moreover, the ro ot of the tree is a dramatic b ottleneck in this
approach, which can be qualied as \coarse-grained".
Later attempts have thus explored higher-level approaches. Kessels [Kes83] proposes to see the
reorganization of the data structure as a side eect of the access. The reorganization is split into
atomic steps involving a small number of nodes, so as to allow concurrency. Additional registers,
local on each node, are used to store the necessary information on intermediate states. At each
update, a reorganizing process is launched, which pro ceeds asynchronously. This approach is ex-
tended by Nurmi, Soisalon-Soininen and Woo d [NSS96, NSSW87, NSSW92]. Finally Larsen [Lar94]
shows that the reorganization process converges in
O
(
k:
log(
n
+ 2
:k
)) steps in a tree with
n
nodes
updated with
k
insertions. Each step consists in propagating a piece of information from a son
to its father, and applying the appropriate sequence of rotations to the father so as to restore its
balance. These transformations are described by 9 dierent rules, depending on the values of the
local registers. As an atomic step may include complex operation, this approach can b e qualied
as \medium-grained".
The contribution of this paper is to go one step further towards a \ne-grained" solution to
concurrent up dates of AVL search trees. As for Kessels, our source of inspiration is the seminal work
by Dijkstra, Lamport at al. [DLM
+
78] on concurrent \on the y" garbage-collection. Their key idea
is to completely uncouple the reorganization of the data structure (collecting the garbage cells and
linking them into the free list) from its up dates (creating garbage cells by p ointer manipulations).
Taking this viewp oint in our problem lets us consider the insertions or deletions of keys in the
data structure as external
perturbations
done by mutator pro cesses on which we have no control.
Reorganizing the data structure is the job of asynchronous daemons which have no knowledge
about the ongoing mutations. They just compete with the mutator pro cesses to access the data
structure. The only consistency restriction on their b ehavior is that it should resp ect the invariant
on which the insertion and deletion protocols are based: the keys appear in sorted order.
We even go one step further by splitting the macro-steps of Larsen into ner atomic steps, and
we dene two kinds of daemon actions:
Propagation:
Flowing the information about current up dates upwards in the tree, from the leaves
to the ro ot.
Rotation:
Rebalancing the no des according to their best knowledge ab out the shape of the tree.
It turns out that only one rule suces to sp ecify propagations, and three for the rotations, which
makes our approach signicantly simpler than the previous ones. Moreover, as the daemons have
no knowledge of the keys, the rules apply to any binary tree, without regards to the way it has b een
obtained by successive insertions and deletions. This is the reason why we have coined the term
AVL rebalancing
. As a byproduct, it answers in a very general setting an old question raised by
H.T. Kung and P.L. Lehman [KL80]: where should rotations take place for to rebalance arbitrary
trees? The answer is: anywhere.
The price to pay for this \ne-grained approach" is that (
n
2
) steps are needed to rebalance
an arbitrary binary tree in the worst case, instead of Larsen's
O
(
n:
log(
n
)) for an empty tree lled
by
n
successive insertions. Note however that a single atomic step of Larsen corresponds to several
steps here which makes the comparison slightly more balanced. Also, we provide the user with a
better degree of concurrency. Finally, there is go od experimental evidence that the convergence is
obtained in
O
(
n
) steps in the average.
The rest of the paper is organized as follows. Section 2.4 describes the mo del and the two
daemons. Correctness is easy: once no daemon can work any more, the tree is an balanced. On
2
剩余18页未读，继续阅读
2022-07-04 上传
2018-04-19 上传
2018-04-19 上传
2018-04-19 上传
2017-10-29 上传
2022-09-11 上传
2021-05-09 上传
AlexChenLei
- 粉丝: 4
- 资源: 15
我的内容管理
展开
最新资源
- 天池大数据比赛：伪造人脸图像检测技术
- ADS1118数据手册中英文版合集
- Laravel 4/5包增强Eloquent模型本地化功能
- UCOSII 2.91版成功移植至STM8L平台
- 蓝色细线风格的PPT鱼骨图设计
- 基于Python的抖音舆情数据可视化分析系统
- C语言双人版游戏设计：别踩白块儿
- 创新色彩搭配的PPT鱼骨图设计展示
- SPICE公共代码库：综合资源管理
- 大气蓝灰配色PPT鱼骨图设计技巧
- 绿色风格四原因分析PPT鱼骨图设计
- 恺撒密码：古老而经典的替换加密技术解析
- C语言超市管理系统课程设计详细解析
- 深入分析：黑色因素的PPT鱼骨图应用
- 创新彩色圆点PPT鱼骨图制作与分析
- C语言课程设计：吃逗游戏源码分享
