diff --git a/src/Makefile.am b/src/Makefile.am
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -158,6 +158,7 @@
   policy/policy.h \
   pow.h \
   protocol.h \
+  radix.h \
   random.h \
   rcu.h \
   reverse_iterator.h \
diff --git a/src/Makefile.test.include b/src/Makefile.test.include
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -78,6 +78,7 @@
   test/policyestimator_tests.cpp \
   test/pow_tests.cpp \
   test/prevector_tests.cpp \
+  test/radix_tests.cpp \
   test/raii_event_tests.cpp \
   test/random_tests.cpp \
   test/rcu_tests.cpp \
diff --git a/src/radix.h b/src/radix.h
new file mode 100644
--- /dev/null
+++ b/src/radix.h
@@ -0,0 +1,212 @@
+// Copyright (c) 2019 The Bitcoin developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_RADIX_H
+#define BITCOIN_RADIX_H
+
+#include <rcu.h>
+#include <util.h>
+
+#include <boost/noncopyable.hpp>
+
+#include <array>
+#include <atomic>
+#include <cstdint>
+#include <memory>
+
+/**
+ * This is a radix tree storing values identified by a unique key.
+ *
+ * The tree is composed of nodes (RadixNode) containing an array of
+ * RadixElement. The key is split into chunks of a few bits that serve as an
+ * index into that array. RadixElement is a discriminated union of either a
+ * RadixNode* representing the next level in the tree, or a T* representing a
+ * leaf. New RadixNode are added lazily when two leaves would go in the same
+ * slot.
+ *
+ * Reads walk the tree using sequential atomic loads, and insertions are done
+ * using CAS, which ensures both can be executed lock free. Removing any
+ * elements from the tree can also be done using CAS, but requires waiting for
+ * other readers before being destroyed. The tree uses RCU to track which thread
+ * is reading the tree, which allows deletion to wait for other readers to be up
+ * to speed before destroying anything. It is therefore crucial that the lock be
+ * taken before reading anything in the tree.
+ *
+ * It is not possible to delete anything from the tree at this time. The tree
+ * itself cannot be destroyed and will leak memory instead of cleaning up after
+ * itself. This obviously needs to be fixed in subsequent revisions.
+ */
+template <typename T> struct RadixTree : public boost::noncopyable {
+private:
+    static const int BITS = 4;
+    static const int MASK = (1 << BITS) - 1;
+    static const size_t CHILD_PER_LEVEL = 1 << BITS;
+
+    typedef decltype(std::declval<T &>().getId()) K;
+    static const size_t KEY_BITS = 8 * sizeof(K);
+    static const uint32_t TOP_LEVEL = (KEY_BITS - 1) / BITS;
+
+    struct RadixElement;
+    struct RadixNode;
+
+    std::atomic<RadixElement> root;
+
+public:
+    RadixTree() : root(RadixElement()) {}
+
+    /**
+     * Insert a value into the tree.
+     * Returns true if the value was inserted, false if it was already present.
+     */
+    bool insert(T *value) { return insert(value->getId(), value); }
+
+    /**
+     * Get the value corresponding to a key.
+     * Returns the value if found, null if not.
+     */
+    T *get(const K &key) {
+        uint32_t level = TOP_LEVEL;
+
+        RCULock lock;
+        RadixElement e = root.load();
+
+        // Find a leaf.
+        while (e.isNode()) {
+            e = e.getNode()->get(level--, key)->load();
+        }
+
+        T *leaf = e.getLeaf();
+        if (leaf == nullptr || leaf->getId() != key) {
+            // We failed to find the proper element.
+            return nullptr;
+        }
+
+        // The leaf is non-null and the keys match. We have our guy.
+        return leaf;
+    }
+
+    const T *get(const K &key) const {
+        return const_cast<RadixTree *>(this)->get(key);
+    }
+
+private:
+    bool insert(const K &key, T *value) {
+        uint32_t level = TOP_LEVEL;
+
+        RCULock lock;
+        std::atomic<RadixElement> *eptr = &root;
+
+        while (true) {
+            RadixElement e = eptr->load();
+
+            // Walk down the tree until we find a leaf for our node.
+            while (e.isNode()) {
+            Node:
+                eptr = e.getNode()->get(level--, key);
+                e = eptr->load();
+            }
+
+            // If the slot is empty, try to insert right there.
+            if (e.getLeaf() == nullptr) {
+                if (eptr->compare_exchange_strong(e, RadixElement(value))) {
+                    return true;
+                }
+
+                // CAS failed, we may have a node in there now.
+                if (e.isNode()) {
+                    goto Node;
+                }
+            }
+
+            // The element was already in the tree.
+            const K &leafKey = e.getLeaf()->getId();
+            if (key == leafKey) {
+                return false;
+            }
+
+            // There is an element there, but it isn't a subtree. We need to
+            // convert it into a subtree and resume insertion into that subtree.
+            std::unique_ptr<RadixNode> newChild =
+                MakeUnique<RadixNode>(level, leafKey, e);
+            if (eptr->compare_exchange_strong(e,
+                                              RadixElement(newChild.get()))) {
+                // We have a subtree, resume normal operations from there.
+                newChild.release();
+            }
+        }
+    }
+
+    struct RadixElement {
+    private:
+        union {
+            RadixNode *node;
+            T *leaf;
+            uintptr_t raw;
+        };
+
+        static const uintptr_t DISCRIMINANT = 0x01;
+        bool getDiscriminent() const { return (raw & DISCRIMINANT) != 0; }
+
+    public:
+        explicit RadixElement() : raw(DISCRIMINANT) {}
+        explicit RadixElement(RadixNode *nodeIn) : node(nodeIn) {}
+        explicit RadixElement(T *leafIn) : leaf(leafIn) { raw |= DISCRIMINANT; }
+
+        /**
+         * Node features.
+         */
+        bool isNode() const { return !getDiscriminent(); }
+
+        RadixNode *getNode() {
+            assert(isNode());
+            return node;
+        }
+
+        const RadixNode *getNode() const {
+            assert(isNode());
+            return node;
+        }
+
+        /**
+         * Leaf features.
+         */
+        bool isLeaf() const { return getDiscriminent(); }
+
+        T *getLeaf() {
+            assert(isLeaf());
+            return reinterpret_cast<T *>(raw & ~DISCRIMINANT);
+        }
+
+        const T *getLeaf() const {
+            assert(isLeaf());
+            return const_cast<RadixElement *>(this)->getLeaf();
+        }
+    };
+
+    struct RadixNode {
+    private:
+        union {
+            std::array<std::atomic<RadixElement>, CHILD_PER_LEVEL> childs;
+            std::array<RadixElement, CHILD_PER_LEVEL>
+                non_atomic_childs_DO_NOT_USE;
+        };
+
+    public:
+        RadixNode(uint32_t level, const K &key, RadixElement e)
+            : non_atomic_childs_DO_NOT_USE() {
+            get(level, key)->store(e);
+        }
+
+        std::atomic<RadixElement> *get(uint32_t level, const K &key) {
+            return &childs[(key >> (level * BITS)) & MASK];
+        }
+    };
+
+    // Make sure the alignment works for T and RadixElement.
+    static_assert(alignof(T) > 1, "T's alignment must be 2 or more.");
+    static_assert(alignof(RadixNode) > 1,
+                  "RadixNode alignment must be 2 or more.");
+};
+
+#endif // BITCOIN_RADIX_H
diff --git a/src/test/CMakeLists.txt b/src/test/CMakeLists.txt
--- a/src/test/CMakeLists.txt
+++ b/src/test/CMakeLists.txt
@@ -95,6 +95,7 @@
 	policyestimator_tests.cpp
 	pow_tests.cpp
 	prevector_tests.cpp
+	radix_tests.cpp
 	raii_event_tests.cpp
 	random_tests.cpp
 	rcu_tests.cpp
diff --git a/src/test/radix_tests.cpp b/src/test/radix_tests.cpp
new file mode 100644
--- /dev/null
+++ b/src/test/radix_tests.cpp
@@ -0,0 +1,220 @@
+// Copyright (c) 2019 The Bitcoin developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <radix.h>
+
+#include <test/test_bitcoin.h>
+
+#include <boost/test/unit_test.hpp>
+
+#include <limits>
+#include <type_traits>
+
+BOOST_FIXTURE_TEST_SUITE(radix_tests, BasicTestingSetup)
+
+/**
+ * Version of Boost::test prior to 1.64 have issues when dealing with nullptr_t.
+ * In order to work around this, we ensure that the null pointers are typed in a
+ * way that Boost will like better.
+ *
+ * TODO: Use nullptr directly once the minimum version of boost is 1.64 or more.
+ */
+#define NULLPTR(T) static_cast<T *>(nullptr)
+
+template <typename K> struct TestElement {
+    K key;
+
+    TestElement(K keyIn) : key(keyIn) {}
+    const K &getId() const { return key; }
+};
+
+template <typename K> void testInsert() {
+    typedef TestElement<K> E;
+    RadixTree<E> mytree;
+
+    E zero(0);
+    E one(1);
+    E two(2);
+    E three(3);
+
+    // Inserting a new element into the tree returns true.
+    BOOST_CHECK(mytree.insert(&one));
+
+    // Inserting an element already in the tree returns false.
+    BOOST_CHECK(!mytree.insert(&one));
+
+    // Let's insert more elements and check behavior stays consistent.
+    BOOST_CHECK(mytree.insert(&zero));
+    BOOST_CHECK(!mytree.insert(&one));
+    BOOST_CHECK(mytree.insert(&two));
+    BOOST_CHECK(mytree.insert(&three));
+    BOOST_CHECK(!mytree.insert(&zero));
+    BOOST_CHECK(!mytree.insert(&one));
+    BOOST_CHECK(!mytree.insert(&two));
+    BOOST_CHECK(!mytree.insert(&three));
+
+    // Check extreme values.
+    typedef typename std::make_signed<K>::type SK;
+    E maxsigned(std::numeric_limits<SK>::max());
+    E minsigned(std::numeric_limits<SK>::min());
+    typedef typename std::make_unsigned<K>::type UK;
+    E minusone(std::numeric_limits<UK>::max());
+    E minustwo(std::numeric_limits<UK>::max() - 1);
+
+    // Insert them into the tree.
+    BOOST_CHECK(mytree.insert(&maxsigned));
+    BOOST_CHECK(mytree.insert(&minsigned));
+    BOOST_CHECK(mytree.insert(&minusone));
+    BOOST_CHECK(mytree.insert(&minustwo));
+
+    // All elements are now in the tree.
+    BOOST_CHECK(!mytree.insert(&zero));
+    BOOST_CHECK(!mytree.insert(&one));
+    BOOST_CHECK(!mytree.insert(&two));
+    BOOST_CHECK(!mytree.insert(&three));
+    BOOST_CHECK(!mytree.insert(&maxsigned));
+    BOOST_CHECK(!mytree.insert(&minsigned));
+    BOOST_CHECK(!mytree.insert(&minusone));
+    BOOST_CHECK(!mytree.insert(&minustwo));
+}
+
+BOOST_AUTO_TEST_CASE(insert_test) {
+    testInsert<int32_t>();
+    testInsert<uint32_t>();
+    testInsert<int64_t>();
+    testInsert<uint64_t>();
+}
+
+template <typename K> void testGet() {
+    typedef TestElement<K> E;
+    RadixTree<E> mytree;
+
+    E zero(0);
+    E one(1);
+    E two(2);
+    E three(3);
+
+    // There are no elements in the tree so far.
+    BOOST_CHECK_EQUAL(mytree.get(1), NULLPTR(E));
+
+    // Insert an element into the tree and check it is there.
+    BOOST_CHECK(mytree.insert(&one));
+    BOOST_CHECK_EQUAL(mytree.get(1), &one);
+
+    // Let's insert more elements and check they are recovered properly.
+    BOOST_CHECK_EQUAL(mytree.get(0), NULLPTR(E));
+    BOOST_CHECK(mytree.insert(&zero));
+    BOOST_CHECK_EQUAL(mytree.get(0), &zero);
+    BOOST_CHECK_EQUAL(mytree.get(1), &one);
+
+    // More elements.
+    BOOST_CHECK_EQUAL(mytree.get(2), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(3), NULLPTR(E));
+    BOOST_CHECK(mytree.insert(&two));
+    BOOST_CHECK(mytree.insert(&three));
+
+    BOOST_CHECK_EQUAL(mytree.get(0), &zero);
+    BOOST_CHECK_EQUAL(mytree.get(1), &one);
+    BOOST_CHECK_EQUAL(mytree.get(2), &two);
+    BOOST_CHECK_EQUAL(mytree.get(3), &three);
+
+    // Check extreme values.
+    typedef typename std::make_signed<K>::type SK;
+    K maxsk = std::numeric_limits<SK>::max();
+    K minsk = std::numeric_limits<SK>::min();
+    typedef typename std::make_unsigned<K>::type UK;
+    K maxuk = std::numeric_limits<UK>::max();
+
+    E maxsigned(maxsk);
+    E minsigned(minsk);
+    E minusone(maxuk);
+    E minustwo(maxuk - 1);
+
+    // Check that they are not in the tree.
+    BOOST_CHECK_EQUAL(mytree.get(maxsk), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(minsk), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(maxuk), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(maxuk - 1), NULLPTR(E));
+
+    // Insert into the tree.
+    BOOST_CHECK(mytree.insert(&maxsigned));
+    BOOST_CHECK(mytree.insert(&minsigned));
+    BOOST_CHECK(mytree.insert(&minusone));
+    BOOST_CHECK(mytree.insert(&minustwo));
+
+    // And now they all are in the tree.
+    BOOST_CHECK_EQUAL(mytree.get(0), &zero);
+    BOOST_CHECK_EQUAL(mytree.get(1), &one);
+    BOOST_CHECK_EQUAL(mytree.get(2), &two);
+    BOOST_CHECK_EQUAL(mytree.get(3), &three);
+    BOOST_CHECK_EQUAL(mytree.get(maxsk), &maxsigned);
+    BOOST_CHECK_EQUAL(mytree.get(minsk), &minsigned);
+    BOOST_CHECK_EQUAL(mytree.get(maxuk), &minusone);
+    BOOST_CHECK_EQUAL(mytree.get(maxuk - 1), &minustwo);
+}
+
+BOOST_AUTO_TEST_CASE(get_test) {
+    testGet<int32_t>();
+    testGet<uint32_t>();
+    testGet<int64_t>();
+    testGet<uint64_t>();
+}
+
+#define THREADS 128
+#define ELEMENTS 65536
+
+static uint64_t next(uint64_t x) {
+    // Simple linear congruential generator by Donald Knuth.
+    return x * 6364136223846793005 + 1442695040888963407;
+}
+
+BOOST_AUTO_TEST_CASE(insert_stress_test) {
+    typedef TestElement<uint32_t> E;
+
+    RadixTree<E> mytree;
+    std::atomic<uint32_t> success{0};
+    std::vector<std::thread> threads;
+
+    for (int i = 0; i < THREADS; i++) {
+        threads.push_back(std::thread([&] {
+            uint64_t rand = 0;
+            for (int j = 0; j < ELEMENTS; j++) {
+                rand = next(rand);
+                uint32_t v(rand >> 32);
+                std::unique_ptr<E> ptr = MakeUnique<E>(v);
+                if (mytree.insert(ptr.get())) {
+                    success++;
+                    ptr.release();
+                    std::this_thread::yield();
+                }
+
+                // Regardless if we inserted or someone else did, the element
+                // should now be in the tree. For some reason, boost is spewing
+                // an inordinate amount of log when performing checks in other
+                // threads than the main one, so we'll use asserts.
+                assert(mytree.get(v)->getId() == v);
+            }
+        }));
+    }
+
+    // Wait for all the threads to finish.
+    for (std::thread &t : threads) {
+        t.join();
+    }
+
+    BOOST_CHECK_EQUAL(success.load(), ELEMENTS);
+
+    // All the elements have been inserted into the tree.
+    uint64_t rand = 0;
+    for (int i = 0; i < ELEMENTS; i++) {
+        rand = next(rand);
+        uint32_t v(rand >> 32);
+        BOOST_CHECK_EQUAL(mytree.get(v)->getId(), v);
+        E e(v);
+        BOOST_CHECK(!mytree.insert(&e));
+        BOOST_CHECK(mytree.get(v) != &e);
+    }
+}
+
+BOOST_AUTO_TEST_SUITE_END()