Basic Idea

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

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

Approaches to Range Queries

• STM
• Lock
• Persistent data structures
• Snapshot
  • Ctrie
  • Snap

Range Query in k-ary Search Trees

dirty field

The dirty field is set to dirty when the leaf is affected by some update operations (helpInsert and helpMark).

Validate

The Validate check all leaves stored in snap. If any dirty field is true, than Validate returns false.

Range Query

The abridged RangeQuery follows few steps,

1. Use DFS to populate snap with all leaves that may contain a key in range.
2. Invoke Validate to check all the leaves stored in snap. If Validate returns false, than retry.
3. Extract all keys in range from snap and return.

Differences between snaphots in BST and range query in k-ary search trees

Just personal opinion, may contain errors.

About k-ary Search Trees

• No duplicate key
• Leaf-oriented k-ST
• Each leaf has zero children and at most k - 1 keys
• Each internal node has exactly k children and k − 1 keys (in increasing order)

Non-blocking k-ary Search Trees需要平衡，tree的深度和每个internal node进行search和update时的work总量。

Basic Idea

这里使用的方法是Trevor Brown的non-blocking binary search tree的实现里面提到的，并没有在论文里说明。

基本思想非常简单，

Concurrent KDTree with Snapshots, implemented in Java. This article is about some details in implementation.

Basic Idea

The methods used in this structure is heavily based on ideas in CTrie (snapshot) and Non-blocking Binary Search Trees (search, insert and delete).

• RDCSS
• GCAS
• Mark and Flag
• Leaf-oriented tree

Problems and Solutions in Implementation

下面是实现的时候遇到的问题和自己对一些细节的思考，有的已经在两篇论文里面有所记录，但是自己没注意，又踩坑了，还有的是这个结构的设计隐含的问题。

RDCSS是Harris提出的一种实现double compare single swap方法，它的语义（也就是DCAS）如下，

The CAS1 Approach

下面使用CAS1（single word compare and swap）来实现RDCSS。