这篇是实现concurrent KDTree snapshot的第3个方法,也是打算写的最后一个方法。使用的方法来自的Range Queries in Non-blocking k-ary Search Trees。
这篇是k-ary的第二篇,为k-ary加入了range query,列举了range query的各种实现方法:STM,lock,Persistent data structures和snapshots,并说明各种方法的优劣,提出了range query的新方法。
Brown在Toronto大学读PhD期间写过2篇关于k-ary的文章,他读PhD期间的导师是Ellen,而Ellen正是写了Non-blocking Binary Search Trees的那位。这篇文章里看到了好几个methods或者ideas是extended from Non-blocking Binary Search Trees。
这篇记录了另一种简单的方法来实现concurrent KDTree snapshot,当然简单是有代价的,那就是在snapshot的时候不允许并发的update(inset,delete)。