Repository files navigation

This library provides a C99 implementation of the Adaptive RadixTree or ART. The ART operates similar to a traditional radix tree butavoids the wasted space of internal nodes by changing the node size.It makes use of 4 node sizes (4, 16, 48, 256), and can guarantee thatthe overhead is no more than 52 bytes per key, though in practice it ismuch lower.

As a radix tree, it provides the following:

• O(k) operations. In many cases, this can be faster than a hash table sincethe hash function is an O(k) operation, and hash tables have very poor cache locality.
• Minimum / Maximum value lookups
• Prefix compression
• Ordered iteration
• Prefix based iteration

Building the test code will generate errors if libcheck is not available.To build the test code successfully, do the following::

$ cd deps/check-0.9.8/$ ./configure$ make# make install# ldconfig (necessary on some Linux distros)$ cd ../../$ scons$ ./test_runner

Or, if you prefer, you can skip the installation of libcheck and the testwill adapt to it being in the tree (leave outmake install):

 $ LD_LIBRARY_PATH=deps/check-0.9.8/src/.libs:. ./test_runner

This build will produce a test_runner executable for testing and a shared_object(libart.so on *NIX systems) for linking with.

Related works:

• The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases