This repository provides an implementation of the Adaptive Radix Tree (ART) in a thread safe manner. Two different synchronization schemes are used, Optimistic Lock Coupling and Read-Optimized-Write-Exclusion (ROWEX).

The techniques used are described in the following papers:

• "The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases": https://db.in.tum.de/~leis/papers/ART.pdf
• "The ART of Practical Synchronization": DaMoN 2016 https://dl.acm.org/citation.cfm?id=2933352

• cmake
• C++ 14 compiler
• tbb
• jemalloc

for Debian/Ubuntu: sudo apt-get install cmake g++ libtbb-dev libjemalloc-dev

mkdir build
cd build/
cmake ..
make

Run the example test with:

./example n 0|1|2

n: number of keys
0: sorted keys
1: dense keys
2: sparse keys

Note that there may not be any keys that are prefixes of other keys. This can be achieved by all keys having the same length or by always passing the null terminator as part of the key.

Some g++ versions fail to link jemalloc. Ensure with ldd that jemalloc is linked. If it's not then either use clang or load jemalloc manually:

LD_PRELOAD=/path/to/jemalloc.so ./example ...

Copyright 2015-2016 Florian Scheibner

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.