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