CKDTree(3)

Basic Idea

使用的方法同样来自Trevor Brown。在他的论文,Range Queries in Non-blocking k-ary Search Trees中,阐述了如何实现range query。

由于进行range query时,需要tree局部的一个constant view,因此snapshot是一个合适的工具。

在update操作中,这里方法比先前的方法多了一个操作:每个leaf都带有一个dirty field。每次进行update时,就把old leaf的dirty设为dirty(实现的时候,是把update info放到dirty)。

进行snapshot的时候,

  1. 把所有leaf都放到一个list,snap里面,
  2. 检测snap中每个leaf的dirty。如果发现dirty已被设置为update info,那么就help update info,并重新开始snapshot。

References

  1. Range Queries in Non-blocking k-ary Search Trees, Trevor Brown, Hillel Avni