SERVER-35820 Implements radix trie for biggie storage engine allowing more efficient copying on modification

6 files changed, 1745 insertions, 298 deletions

diff --git a/src/mongo/db/storage/biggie/biggie_record_store.cpp b/src/mongo/db/storage/biggie/biggie_record_store.cpp
index 6168c706d6e..d7afd580edc 100644
--- a/src/mongo/db/storage/biggie/biggie_record_store.cpp
+++ b/src/mongo/db/storage/biggie/biggie_record_store.cpp
@@ -196,14 +196,18 @@ Status RecordStore::updateRecord(OperationContext* opCtx,
                                  UpdateNotifier* notifier) {
     StringStore* workingCopy = getRecoveryUnitBranch_forking(opCtx);
     std::string key = createKey(_ident, oldLocation.repr());
-    StringStore::iterator it = workingCopy->find(key);
+    StringStore::const_iterator it = workingCopy->find(key);
     invariant(it != workingCopy->end());
-    it->second = std::string(data, len);
+
+    StringStore::value_type vt{key, std::string(data, len)};
+    workingCopy->update(std::move(vt));
+    // it->second = std::string(data, len);
     return Status::OK();
 }
 
 bool RecordStore::updateWithDamagesSupported() const {
-    return true;
+    // TODO: enable updateWithDamages.
+    return false;
 }
 
 StatusWith<RecordData> RecordStore::updateWithDamages(OperationContext* opCtx,
@@ -211,17 +215,7 @@ StatusWith<RecordData> RecordStore::updateWithDamages(OperationContext* opCtx,
                                                       const RecordData& oldRec,
                                                       const char* damageSource,
                                                       const mutablebson::DamageVector& damages) {
-    StringStore* workingCopy = getRecoveryUnitBranch_forking(opCtx);
-    std::string key = createKey(_ident, loc.repr());
-    StringStore::iterator doc = workingCopy->find(key);
-    invariant(doc != workingCopy->end());  // Only update existing records.
-    for (const auto& d : damages) {
-        const char* source = damageSource + d.sourceOffset;
-        char* target = (&doc->second[0]) + d.targetOffset;
-        std::memcpy(target, source, d.size);
-    }
-    RecordData updatedRecord(doc->second.c_str(), doc->second.length());
-    return updatedRecord;  // Data is un-owned.
+    return Status::OK();
 }
 
 std::unique_ptr<SeekableRecordCursor> RecordStore::getCursor(OperationContext* opCtx,
@@ -233,8 +227,8 @@ std::unique_ptr<SeekableRecordCursor> RecordStore::getCursor(OperationContext* o
 
 Status RecordStore::truncate(OperationContext* opCtx) {
     StringStore* str = getRecoveryUnitBranch_forking(opCtx);
-    StringStore::iterator it = str->lower_bound(_prefix);
-    StringStore::iterator end = str->upper_bound(_postfix);
+    StringStore::const_iterator it = str->lower_bound(_prefix);
+    StringStore::const_iterator end = str->upper_bound(_postfix);
     std::vector<std::string> keysToErase;
     while (it != end) {
         keysToErase.push_back(it->first);
@@ -382,7 +376,7 @@ boost::optional<Record> RecordStore::ReverseCursor::next() {
     StringStore* workingCopy = getRecoveryUnitBranch_forking(opCtx);
     if (_needFirstSeek) {
         _needFirstSeek = false;
-        it = StringStore::reverse_iterator(workingCopy->upper_bound(_postfix));
+        it = StringStore::const_reverse_iterator(workingCopy->upper_bound(_postfix));
     } else if (it != workingCopy->rend()) {
         ++it;
     } else {
@@ -404,12 +398,12 @@ boost::optional<Record> RecordStore::ReverseCursor::seekExact(const RecordId& id
     _savedPosition = boost::none;
     StringStore* workingCopy = getRecoveryUnitBranch_forking(opCtx);
     std::string key = createKey(_ident, id.repr());
-    StringStore::iterator canFind = workingCopy->find(key);
+    StringStore::const_iterator canFind = workingCopy->find(key);
     if (canFind == workingCopy->end() || !inPrefix(canFind->first)) {
         it = workingCopy->rend();
         return boost::none;
     }
-    it = StringStore::reverse_iterator(++canFind);  // reverse iterator returns item 1 before
+    it = StringStore::const_reverse_iterator(++canFind);  // reverse iterator returns item 1 before
     _savedPosition = it->first;
     return Record{id, RecordData(it->second.c_str(), it->second.length())};
 }
@@ -421,7 +415,7 @@ void RecordStore::ReverseCursor::saveUnpositioned() {}
 bool RecordStore::ReverseCursor::restore() {
     StringStore* workingCopy = getRecoveryUnitBranch_forking(opCtx);
     it = _savedPosition
-        ? StringStore::reverse_iterator(workingCopy->upper_bound(_savedPosition.value()))
+        ? StringStore::const_reverse_iterator(workingCopy->upper_bound(_savedPosition.value()))
         : workingCopy->rend();
     return true;
 }
diff --git a/src/mongo/db/storage/biggie/biggie_record_store.h b/src/mongo/db/storage/biggie/biggie_record_store.h
index b7207fe721c..9310a875c24 100644
--- a/src/mongo/db/storage/biggie/biggie_record_store.h
+++ b/src/mongo/db/storage/biggie/biggie_record_store.h
@@ -144,7 +144,7 @@ private:
         StringData _ident;
         std::string _prefix;
         std::string _postfix;
-        StringStore::iterator it;
+        StringStore::const_iterator it;
         boost::optional<std::string> _savedPosition;
         bool _needFirstSeek{true};
 
@@ -166,7 +166,7 @@ private:
         StringData _ident;
         std::string _prefix;
         std::string _postfix;
-        StringStore::reverse_iterator it;
+        StringStore::const_reverse_iterator it;
         boost::optional<std::string> _savedPosition;
         bool _needFirstSeek{true};
 
diff --git a/src/mongo/db/storage/biggie/biggie_sorted_impl.cpp b/src/mongo/db/storage/biggie/biggie_sorted_impl.cpp
index eb0492d4e00..66beebd5aba 100644
--- a/src/mongo/db/storage/biggie/biggie_sorted_impl.cpp
+++ b/src/mongo/db/storage/biggie/biggie_sorted_impl.cpp
@@ -336,7 +336,8 @@ Status SortedDataInterface::insert(OperationContext* opCtx,
     if (!dupsAllowed) {
         std::string workingCopyLowerBound = combineKeyAndRID(key, RecordId::min(), _prefix, _order);
         std::string workingCopyUpperBound = combineKeyAndRID(key, RecordId::max(), _prefix, _order);
-        StringStore::iterator lowerBoundIterator = workingCopy->lower_bound(workingCopyLowerBound);
+        StringStore::const_iterator lowerBoundIterator =
+            workingCopy->lower_bound(workingCopyLowerBound);
 
         if (lowerBoundIterator != workingCopy->end() &&
             lowerBoundIterator->first.compare(_KSForIdentEnd) < 0) {
@@ -377,7 +378,11 @@ Status SortedDataInterface::truncate(OperationContext* opCtx) {
     StringStore* workingCopy = getRecoveryUnitBranch_forking(opCtx);
     auto workingCopyLowerBound = workingCopy->lower_bound(_KSForIdentStart);
     auto workingCopyUpperBound = workingCopy->upper_bound(_KSForIdentEnd);
-    workingCopy->erase(workingCopyLowerBound, workingCopyUpperBound);
+    // workingCopy->erase(workingCopyLowerBound, workingCopyUpperBound);
+    while (workingCopyLowerBound != workingCopyUpperBound) {
+        workingCopy->erase(workingCopyLowerBound->first);
+        ++workingCopyLowerBound;
+    }
     return Status::OK();
 }
 
@@ -428,8 +433,8 @@ bool SortedDataInterface::appendCustomStats(OperationContext* opCtx,
 long long SortedDataInterface::getSpaceUsedBytes(OperationContext* opCtx) const {
     StringStore* str = getRecoveryUnitBranch_forking(opCtx);
     size_t totalSize = 0;
-    StringStore::iterator it = str->lower_bound(_KSForIdentStart);
-    StringStore::iterator end = str->upper_bound(_KSForIdentEnd);
+    StringStore::const_iterator it = str->lower_bound(_KSForIdentStart);
+    StringStore::const_iterator end = str->upper_bound(_KSForIdentEnd);
     int64_t numElements = str->distance(it, end);
     for (int i = 0; i < numElements; i++) {
         totalSize += it->first.length();
@@ -547,7 +552,8 @@ void SortedDataInterface::Cursor::setEndPosition(const BSONObj& key, bool inclus
         // Reverse iterators work with upper bound since upper bound will return the first element
         // past the argument, so when it becomes a reverse iterator, it goes backwards one,
         // (according to the C++ standard) and we end up in the right place.
-        _endPosReverse = StringStore::reverse_iterator(workingCopy->upper_bound(_endPosBound));
+        _endPosReverse =
+            StringStore::const_reverse_iterator(workingCopy->upper_bound(_endPosBound));
     }
 }
 
@@ -614,8 +620,8 @@ boost::optional<IndexKeyEntry> SortedDataInterface::Cursor::seekAfterProcessing(
                 // Reverse iterators work with upper bound since upper bound will return the first
                 // element past the argument, so when it becomes a reverse iterator, it goes
                 // backwards one, (according to the C++ standard) and we end up in the right place.
-                _reverseIt =
-                    StringStore::reverse_iterator(_workingCopy->upper_bound(workingCopyBound));
+                _reverseIt = StringStore::const_reverse_iterator(
+                    _workingCopy->upper_bound(workingCopyBound));
             }
             // Here, we check to make sure the iterator doesn't fall off the data structure and is
             // in the ident. We also check to make sure it is on the correct side of the end
@@ -633,7 +639,8 @@ boost::optional<IndexKeyEntry> SortedDataInterface::Cursor::seekAfterProcessing(
             // Reverse iterators work with upper bound since upper bound will return the first
             // element past the argument, so when it becomes a reverse iterator, it goes
             // backwards one, (according to the C++ standard) and we end up in the right place.
-            _reverseIt = StringStore::reverse_iterator(_workingCopy->upper_bound(workingCopyBound));
+            _reverseIt =
+                StringStore::const_reverse_iterator(_workingCopy->upper_bound(workingCopyBound));
         }
         // Once again, we check to make sure the iterator didn't fall off the data structure and
         // still is in the ident.
@@ -725,7 +732,7 @@ void SortedDataInterface::Cursor::restore() {
         if (_saveKey.length() == 0) {
             _reverseIt = workingCopy->rend();
         } else {
-            _reverseIt = StringStore::reverse_iterator(workingCopy->upper_bound(_saveKey));
+            _reverseIt = StringStore::const_reverse_iterator(workingCopy->upper_bound(_saveKey));
         }
         if (!checkCursorValid()) {
             _atEOF = true;
diff --git a/src/mongo/db/storage/biggie/biggie_sorted_impl.h b/src/mongo/db/storage/biggie/biggie_sorted_impl.h
index 35a719207f1..468cb27ab9e 100644
--- a/src/mongo/db/storage/biggie/biggie_sorted_impl.h
+++ b/src/mongo/db/storage/biggie/biggie_sorted_impl.h
@@ -133,8 +133,8 @@ public:
         // This is the "working copy" of the master "branch" in the git analogy.
         StringStore* _workingCopy;
         // These store the end positions.
-        boost::optional<StringStore::iterator> _endPos;
-        boost::optional<StringStore::reverse_iterator> _endPosReverse;
+        boost::optional<StringStore::const_iterator> _endPos;
+        boost::optional<StringStore::const_reverse_iterator> _endPosReverse;
         // This means if the cursor is a forward or reverse cursor.
         bool _forward;
         // This means whether the cursor has reached the last EOF (with regard to this index).
@@ -146,10 +146,10 @@ public:
         // These are the same as before.
         std::string _prefix;
         std::string _identEnd;
-        // These two store the iterator, which is the data structure for cursors. The one we use
-        // depends on _forward.
-        StringStore::iterator _forwardIt;
-        StringStore::reverse_iterator _reverseIt;
+        // These two store the const_iterator, which is the data structure for cursors. The one we
+        // use depends on _forward.
+        StringStore::const_iterator _forwardIt;
+        StringStore::const_reverse_iterator _reverseIt;
         // This is the ordering for the key's values for multi-field keys.
         Ordering _order;
         // This stores whether or not the end position is inclusive for restore.
diff --git a/src/mongo/db/storage/biggie/store.h b/src/mongo/db/storage/biggie/store.h
index 7b2fd7038af..8fad8fd5248 100644
--- a/src/mongo/db/storage/biggie/store.h
+++ b/src/mongo/db/storage/biggie/store.h
@@ -28,8 +28,13 @@
 
 #pragma once
 
+#include <array>
+#include <boost/optional.hpp>
 #include <exception>
-#include <map>
+#include <iostream>
+#include <memory>
+#include <string.h>
+#include <vector>
 
 namespace mongo {
 namespace biggie {
@@ -40,10 +45,15 @@ class merge_conflict_exception : std::exception {
     }
 };
 
+/**
+ * RadixStore is a Trie data structure with the ability to share nodes among copies of trees to
+ * minimize data duplication. Each node has a notion of ownership and if modifications are made to
+ * non-uniquely owned nodes, they are copied to prevent dirtying the data for the other owners of
+ * the node.
+ */
 template <class Key, class T>
-class Store {
-private:
-    std::map<Key, T> map;
+class RadixStore {
+    class Node;
 
 public:
     using mapped_type = T;
@@ -52,135 +62,492 @@ public:
     using pointer = typename std::allocator_traits<allocator_type>::pointer;
     using const_pointer = typename std::allocator_traits<allocator_type>::const_pointer;
     using size_type = std::size_t;
+    using uint8_t = std::uint8_t;
 
-    template <class pointer_type, class reference_type, class iter_type>
-    class store_iterator {
-    private:
-        friend class Store;
-        iter_type iter;
-        store_iterator(iter_type iter) : iter(iter) {}
+    template <class pointer_type, class reference_type>
+    class radix_iterator {
+        friend class RadixStore;
 
     public:
-        using iterator_category = std::bidirectional_iterator_tag;
-        using value_type = typename Store::value_type;
+        using iterator_category = std::forward_iterator_tag;
+        using value_type = RadixStore::value_type;
         using difference_type = std::ptrdiff_t;
         using pointer = pointer_type;
         using reference = reference_type;
 
-        store_iterator() = default;
+        radix_iterator() : _root(nullptr), _current(nullptr) {}
+
+        radix_iterator(const radix_iterator& other)
+            : _root(other._root), _current(other._current) {}
+
+        ~radix_iterator() = default;
 
-        store_iterator& operator++() {
-            ++this->iter;
+        radix_iterator& operator++() {
+            _findNext();
             return *this;
         }
 
-        store_iterator operator++(int) {
-            store_iterator old = *this;
-            ++this->iter;
+        radix_iterator operator++(int) {
+            radix_iterator old = *this;
+            ++*this;
             return old;
         }
 
-        store_iterator& operator--() {
-            --this->iter;
+        radix_iterator& operator=(const radix_iterator& other) = default;
+
+        bool operator==(const radix_iterator& other) const {
+            return this->_current == other._current;
+        }
+
+        bool operator!=(const radix_iterator& other) const {
+            return this->_current != other._current;
+        }
+
+        reference operator*() const {
+            return *(_current->data);
+        }
+
+        const_pointer operator->() {
+            return &*(_current->data);
+        }
+
+    private:
+        radix_iterator(const std::shared_ptr<Node>& root) : _root(root), _current(nullptr) {}
+
+        radix_iterator(const std::shared_ptr<Node>& root, Node* current)
+            : _root(root), _current(current){};
+
+        /**
+        * This function traverses the tree to find the next left-most node with data. Modifies
+        * '_current' to point to this node. It uses a pre-order traversal ('visit' the current
+        * node itself then 'visit' the child subtrees from left to right ).
+        */
+        void _findNext() {
+            // If 'current' is a nullptr there is no next node to go to.
+            if (_current == nullptr)
+                return;
+
+            // If 'current' is not a leaf, continue moving down and left in the tree until the next
+            // node.
+            if (!_current->isLeaf()) {
+                _traverseLeftSubtree();
+                return;
+            }
+
+            // Get path from root to '_current' since it is required to traverse up the tree.
+            Key key = _current->data->first;
+            std::vector<Node*> context = RadixStore::_buildContext(key, _root.get());
+
+            // 'node' should equal '_current' because that should be the last element in the stack.
+            // Pop back once more to get access to it's parent node. The parent node will enable
+            // traversal through the neighboring nodes, and if there are none, the iterator will
+            // move up the tree to continue searching for the next node with data.
+            Node* node = context.back();
+            context.pop_back();
+
+            // In case there is no next node, set _current to be 'nullptr' which will mark the end
+            // of the traversal.
+            _current = nullptr;
+            while (!context.empty()) {
+                uint8_t oldKey = node->trieKey;
+                node = context.back();
+                context.pop_back();
+
+                // Check the children right of the node that the iterator was at already. This way,
+                // there will be no backtracking in the traversal.
+                for (auto iter = oldKey + 1 + node->children.begin(); iter != node->children.end();
+                     ++iter) {
+
+                    // If the node has a child, then the sub-tree must have a node with data that
+                    // has not yet been visited.
+                    if (*iter != nullptr) {
+
+                        // If the current node has data, return it and exit. If not, continue
+                        // following the nodes to find the next one with data. It is necessary to go
+                        // to the left-most node in this sub-tree.
+                        if ((*iter)->data != boost::none) {
+                            _current = iter->get();
+                            return;
+                        }
+                        _current = iter->get();
+                        _traverseLeftSubtree();
+                        return;
+                    }
+                }
+            }
+            return;
+        }
+
+        void _traverseLeftSubtree() {
+            // This function finds the next left-most node with data under the sub-tree where
+            // '_current' is root. However, it cannot return the root, and hence at least 1
+            // iteration of the while loop is required.
+            do {
+                for (auto child : _current->children) {
+                    if (child != nullptr) {
+                        _current = child.get();
+                        break;
+                    }
+                }
+            } while (_current->data == boost::none);
+        }
+
+        // "_root" is a copy of the root of the tree over which this is iterating.
+        std::shared_ptr<Node> _root;
+
+        // "_current" is the node that the iterator is currently on. _current->data will never be
+        // boost::none (unless it is within the process of tree traversal), and _current will be
+        // become a nullptr once there are no more nodes left to iterate.
+        Node* _current;
+    };
+
+    using iterator = radix_iterator<pointer, value_type&>;
+    using const_iterator = radix_iterator<const_pointer, const value_type&>;
+
+    template <class pointer_type, class reference_type>
+    class reverse_radix_iterator {
+        friend class RadixStore;
+        friend class radix_iterator<pointer_type, reference_type&>;
+
+    public:
+        using value_type = RadixStore::value_type;
+        using difference_type = std::ptrdiff_t;
+        using pointer = pointer_type;
+        using reference = reference_type;
+
+        reverse_radix_iterator() : _root(nullptr), _current(nullptr) {}
+
+        reverse_radix_iterator(const const_iterator& it) : _root(it._root), _current(it._current) {
+            // If the iterator passed in is at the end(), then set _current to root which is
+            // equivalent to rbegin(). Otherwise, move the iterator back one node, due to the fact
+            // that the relationship &*r == &*(i-1) must be maintained for any reverse iterator 'r'
+            // and forward iterator 'i'.
+            if (_current == nullptr) {
+                // If the tree is empty, then leave '_current' as nullptr.
+                if (_root->isLeaf())
+                    return;
+
+                _current = _root.get();
+                _traverseRightSubtree();
+            } else {
+                _findNextReverse();
+            }
+        }
+
+        reverse_radix_iterator(const iterator& it) : _root(it._root), _current(it._current) {
+            if (_current == nullptr) {
+                _current = _root.get();
+                _traverseRightSubtree();
+            } else {
+                _findNextReverse();
+            }
+        }
+
+        reverse_radix_iterator(const reverse_radix_iterator& other)
+            : _root(other._root), _current(other._current) {}
+
+        reverse_radix_iterator& operator=(const reverse_radix_iterator& other) = default;
+
+        ~reverse_radix_iterator() = default;
+
+        reverse_radix_iterator& operator++() {
+            _findNextReverse();
             return *this;
         }
 
-        store_iterator operator--(int) {
-            store_iterator old = *this;
-            --this->iter;
+        reverse_radix_iterator operator++(int) {
+            reverse_radix_iterator old = *this;
+            ++*this;
             return old;
         }
 
-        // Non member equality
-
-        friend bool operator==(const store_iterator& lhs, const store_iterator& rhs) {
-            return lhs.iter == rhs.iter;
+        bool operator==(const reverse_radix_iterator& other) const {
+            return this->_current == other._current;
         }
 
-        friend bool operator!=(const store_iterator& lhs, const store_iterator& rhs) {
-            return !(lhs.iter == rhs.iter);
+        bool operator!=(const reverse_radix_iterator& other) const {
+            return this->_current != other._current;
         }
 
         reference operator*() const {
-            return *this->iter;
+            return *(_current->data);
+        }
+
+        const_pointer operator->() {
+            return &*(_current->data);
+        }
+
+
+    private:
+        reverse_radix_iterator(const std::shared_ptr<Node>& root)
+            : _root(root), _current(nullptr) {}
+        reverse_radix_iterator(const std::shared_ptr<Node>& root, Node* current)
+            : _root(root), _current(current) {}
+
+        void _findNextReverse() {
+            // Reverse find iterates through the tree to find the "next" node containing data,
+            // searching from right to left. Normally a pre-order traversal is used, but for
+            // reverse, the ordering is to visit child nodes from right to left, then 'visit'
+            // current node.
+            if (_current == nullptr)
+                return;
+
+            Key key = _current->data->first;
+
+            std::vector<Node*> context = RadixStore::_buildContext(key, _root.get());
+            Node* node = context.back();
+            context.pop_back();
+
+            // Due to the nature of the traversal, it will always be necessary to move up the tree
+            // first because when the 'current' node was visited, it meant all its children had been
+            // visited as well.
+            uint8_t oldKey;
+            _current = nullptr;
+            while (!context.empty()) {
+                oldKey = node->trieKey;
+                node = context.back();
+                context.pop_back();
+
+                // After moving up in the tree, continue searching for neighboring nodes to see if
+                // they have data, moving from right to left.
+                for (int i = oldKey - 1; i >= 0; i--) {
+                    if (node->children[i] != nullptr) {
+                        // If there is a sub-tree found, it must have data, therefore it's necessary
+                        // to traverse to the right most node.
+                        _current = node->children[i].get();
+                        _traverseRightSubtree();
+                        return;
+                    }
+                }
+
+                // If there were no sub-trees that contained data, and the 'current' node has data,
+                // it can now finally be 'visited'.
+                if (node->data != boost::none) {
+                    _current = node;
+                    return;
+                }
+            }
         }
 
-        pointer operator->() const {
-            return &(*this->iter);
+        void _traverseRightSubtree() {
+            // This function traverses the given tree to the right most leaf of the subtree where
+            // 'current' is the root.
+            do {
+                for (auto iter = _current->children.rbegin(); iter != _current->children.rend();
+                     ++iter) {
+                    if (*iter != nullptr) {
+                        _current = iter->get();
+                        break;
+                    }
+                }
+            } while (!_current->isLeaf());
         }
+
+        // "_root" is a copy of the root of the tree over which this is iterating.
+        std::shared_ptr<Node> _root;
+
+        // "_current" is a the node that the iterator is currently on. _current->data will never be
+        // boost::none, and _current will be become a nullptr once there are no more nodes left to
+        // iterate.
+        Node* _current;
     };
 
-    using iterator = store_iterator<pointer, value_type&, typename std::map<Key, T>::iterator>;
-    using const_iterator =
-        store_iterator<const_pointer, const value_type&, typename std::map<Key, T>::const_iterator>;
-    using reverse_iterator = std::reverse_iterator<iterator>;
-    using reverse_const_iterator = std::reverse_iterator<const_iterator>;
+    using reverse_iterator = reverse_radix_iterator<pointer, value_type&>;
+    using const_reverse_iterator = reverse_radix_iterator<const_pointer, const value_type&>;
+
+    // Constructor
+    RadixStore(const RadixStore& other) {
+        _root = other._root;
+        _numElems = other._numElems;
+        _sizeElems = other._sizeElems;
+    }
+
+    RadixStore() {
+        _root = std::make_shared<RadixStore::Node>('\0');
+        _numElems = 0;
+        _sizeElems = 0;
+    }
 
-    // Constructors
+    ~RadixStore() = default;
 
-    Store(const Store& other) = default;
-    Store() = default;
+    // Equality
+    bool operator==(const RadixStore& other) const {
+        RadixStore::const_iterator iter = this->begin();
+        RadixStore::const_iterator other_iter = other.begin();
 
-    ~Store() = default;
+        while (iter != this->end()) {
+            if (*iter != *other_iter) {
+                return false;
+            }
 
-    // Non member equality
+            iter++;
+            other_iter++;
+        }
 
-    friend bool operator==(const Store& lhs, const Store& rhs) {
-        return lhs.map == rhs.map;
+        return other_iter == other.end();
     }
 
     // Capacity
-
     bool empty() const {
-        return map.empty();
+        return _numElems == 0;
     }
 
-    // Number of nodes
     size_type size() const {
-        return map.size();
+        return _numElems;
     }
 
-    // Size of mapped data in store
     size_type dataSize() const {
-        size_type s = size_type(0);
-        for (const value_type val : *this) {
-            s += val.second.size();
-        }
-
-        return s;
+        return _sizeElems;
     }
 
     // Modifiers
-
     void clear() noexcept {
-        map.clear();
+        _root = std::make_shared<Node>('\0');
+        _numElems = 0;
+        _sizeElems = 0;
+    }
+
+    std::pair<const_iterator, bool> insert(value_type&& value) {
+        Key key = value.first;
+        mapped_type m = value.second;
+
+        Node* item = _findNode(key);
+        if (item != nullptr || key.size() == 0)
+            return std::make_pair(end(), false);
+
+        auto result = _upsertWithCopyOnSharedNodes(key, std::move(value));
+        if (result.second) {
+            _numElems++;
+            _sizeElems += m.size();
+        }
+
+        return result;
     }
 
-    std::pair<iterator, bool> insert(value_type&& value) {
-        auto res = this->map.insert(value);
-        iterator iter = iterator(res.first);
-        return std::pair<iterator, bool>(iter, res.second);
+    std::pair<const_iterator, bool> update(value_type&& value) {
+        Key key = value.first;
+        mapped_type m = value.second;
+
+        // Ensure that the item to be updated exists.
+        auto item = RadixStore::find(key);
+        if (item == RadixStore::end())
+            return std::make_pair(item, false);
+
+        size_t sizeOfRemovedNode = item->second.size();
+        auto result = _upsertWithCopyOnSharedNodes(key, std::move(value));
+        if (result.second) {
+            _sizeElems -= sizeOfRemovedNode;
+            _sizeElems += m.size();
+        }
+
+        return result;
     }
 
     size_type erase(const Key& key) {
-        return map.erase(key);
-    }
+        std::vector<std::pair<Node*, bool>> context;
+
+        std::shared_ptr<Node> node = _root;
+        bool isUniquelyOwned = _root.use_count() - 1 == 1;
+        context.push_back(std::make_pair(node.get(), isUniquelyOwned));
 
-    void erase(iterator first, iterator last) {
-        map.erase(first.iter, last.iter);
+        for (const char* charKey = key.data(); charKey != key.data() + key.size(); ++charKey) {
+            const uint8_t c = static_cast<const uint8_t>(*charKey);
+            node = node->children[c];
+            if (node == nullptr)
+                return false;
+
+            isUniquelyOwned = isUniquelyOwned && node.use_count() - 1 == 1;
+            context.push_back(std::make_pair(node.get(), isUniquelyOwned));
+        }
+
+        size_t sizeOfRemovedNode = node->data->second.size();
+        Node* last = context.back().first;
+        isUniquelyOwned = context.back().second;
+        context.pop_back();
+        if (last->isLeaf()) {
+            // If the node to be deleted is a leaf node, might need to prune the branch.
+            uint8_t trieKey;
+            while (!context.empty()) {
+                trieKey = last->trieKey;
+                last = context.back().first;
+                isUniquelyOwned = context.back().second;
+                context.pop_back();
+
+                // If a node on the branch has data, stop pruning.
+                if (last->data != boost::none)
+                    break;
+
+                // If a node has children other than the one leading to the to-be deleted node, stop
+                // pruning.
+                bool hasOtherChildren = false;
+                for (auto iter = last->children.begin(); iter != last->children.end(); ++iter) {
+                    if (*iter != nullptr && (*iter)->trieKey != trieKey) {
+                        hasOtherChildren = true;
+                        break;
+                    }
+                }
+
+                if (hasOtherChildren)
+                    break;
+            }
+
+            if (isUniquelyOwned) {
+                // If this node is uniquely owned, simply set that child node to null and
+                // "cut" off that branch of our tree
+                last->children[trieKey] = nullptr;
+            } else {
+                // If its not uniquely owned, copy the branch so we can preserve it for the other
+                // owner(s).
+                std::shared_ptr<Node> child = std::make_shared<Node>(last->trieKey);
+                auto lastIter = last->children.begin();
+                for (auto iter = child->children.begin(); iter != child->children.end();
+                     ++iter, ++lastIter) {
+                    if (*lastIter != nullptr && (*lastIter)->trieKey == trieKey)
+                        continue;
+
+                    *iter = *lastIter;
+                }
+
+                std::shared_ptr<Node> node = child;
+                while (!context.empty()) {
+                    trieKey = last->trieKey;
+                    last = context.back().first;
+                    context.pop_back();
+                    node = std::make_shared<Node>(last->trieKey);
+
+                    auto lastIter = last->children.begin();
+                    for (auto iter = node->children.begin(); iter != node->children.end();
+                         ++iter, ++lastIter) {
+                        *iter = *lastIter;
+                    }
+
+                    node->children[trieKey] = child;
+                    child = node;
+                }
+                _root = node;
+            }
+        } else {
+            // The to-be deleted node is an internal node, and therefore updating its data to be
+            // boost::none will "delete" it
+            _upsertWithCopyOnSharedNodes(key, boost::none);
+        }
+
+        _numElems--;
+        _sizeElems -= sizeOfRemovedNode;
+        return true;
     }
 
-    /**
-     * Returns a Store that has all changes from both 'this' and 'other' compared to base.
-     * Throws merge_conflict_exception if there are merge conflicts.
-     */
-    Store merge3(const Store& base, const Store& other) const {
-        Store store;
+    // Returns a Store that has all changes from both 'this' and 'other' compared to base.
+    // Throws merge_conflict_exception if there are merge conflicts.
+    RadixStore merge3(const RadixStore& base, const RadixStore& other) const {
+        RadixStore store;
 
         // Merges all differences between this and base, along with modifications from other.
-        for (const Store::value_type val : *this) {
-            Store::const_iterator baseIter = base.find(val.first);
-            Store::const_iterator otherIter = other.find(val.first);
+        RadixStore::const_iterator iter = this->begin();
+        while (iter != this->end()) {
+            const value_type val = *iter;
+            RadixStore::const_iterator baseIter = base.find(val.first);
+            RadixStore::const_iterator otherIter = other.find(val.first);
 
             if (baseIter != base.end() && otherIter != other.end()) {
                 if (val.second != baseIter->second && otherIter->second != baseIter->second) {
@@ -190,10 +557,10 @@ public:
 
                 if (val.second != baseIter->second) {
                     // Merges non-conflicting insertions from this.
-                    store.insert(Store::value_type(val));
+                    store.insert(RadixStore::value_type(val));
                 } else {
                     // Merges non-conflicting modifications from other or no modifications.
-                    store.insert(Store::value_type(*otherIter));
+                    store.insert(RadixStore::value_type(*otherIter));
                 }
             } else if (baseIter != base.end() && otherIter == other.end()) {
                 if (val.second != baseIter->second) {
@@ -208,18 +575,21 @@ public:
                 }
 
                 // Merges insertions from this.
-                store.insert(Store::value_type(val));
+                store.insert(RadixStore::value_type(val));
             }
+            iter++;
         }
 
         // Merges insertions and deletions from other.
-        for (const Store::value_type otherVal : other) {
-            Store::const_iterator baseIter = base.find(otherVal.first);
-            Store::const_iterator thisIter = this->find(otherVal.first);
+        RadixStore::const_iterator other_iter = other.begin();
+        for (; other_iter != other.end(); other_iter++) {
+            const value_type otherVal = *other_iter;
+            RadixStore::const_iterator baseIter = base.find(otherVal.first);
+            RadixStore::const_iterator thisIter = this->find(otherVal.first);
 
             if (baseIter == base.end()) {
                 // Merges insertions from other.
-                store.insert(Store::value_type(otherVal));
+                store.insert(RadixStore::value_type(otherVal));
             } else if (thisIter == this->end() && otherVal.second != baseIter->second) {
                 // Throws exception if modifications from this conflict with deletions from other.
                 throw merge_conflict_exception();
@@ -229,77 +599,305 @@ public:
         return store;
     }
 
-    // Iterators
+    // iterators
+    const_iterator begin() const noexcept {
+        if (_numElems == 0) {
+            return RadixStore::end();
+        }
 
-    iterator begin() noexcept {
-        return iterator(this->map.begin());
+        auto node = _root;
+        while (node->data == boost::none) {
+            for (auto child : node->children) {
+                if (child != nullptr) {
+                    node = child;
+                    break;
+                }
+            }
+        }
+        return RadixStore::const_iterator(_root, node.get());
     }
 
-    iterator end() noexcept {
-        return iterator(this->map.end());
-    }
+    const_reverse_iterator rbegin() const noexcept {
+        if (_numElems == 0)
+            return RadixStore::rend();
 
-    reverse_iterator rbegin() noexcept {
-        return reverse_iterator(end());
+        auto node = _root;
+        while (!node->isLeaf()) {
+            for (auto iter = node->children.rbegin(); iter != node->children.rend(); ++iter) {
+                if (*iter != nullptr) {
+                    node = *iter;
+                    break;
+                }
+            }
+        }
+        return RadixStore::const_reverse_iterator(_root, node.get());
     }
 
-    reverse_iterator rend() noexcept {
-        return reverse_iterator(begin());
+    const_iterator end() const noexcept {
+        return RadixStore::const_iterator(_root);
     }
 
-    const_iterator begin() const noexcept {
-        return const_iterator(this->map.begin());
+    const_reverse_iterator rend() const noexcept {
+        return RadixStore::const_reverse_iterator(_root);
     }
 
-    const_iterator end() const noexcept {
-        return const_iterator(this->map.end());
-    }
+    const_iterator find(const Key& key) const {
+        RadixStore::const_iterator it = RadixStore::end();
 
-    reverse_const_iterator rbegin() const noexcept {
-        return reverse_const_iterator(end());
+        Node* node = _findNode(key);
+        if (node == nullptr)
+            return it;
+        else
+            return RadixStore::const_iterator(_root, node);
     }
 
-    reverse_const_iterator rend() const noexcept {
-        return reverse_const_iterator(begin());
-    }
+    const_iterator lower_bound(const Key& key) const {
+        Node* node = _root.get();
+        std::vector<Node*> context;
+        context.push_back(node);
+
+        const char* charKey = key.data();
+        uint8_t idx = '\0';
+
+        // Traverse the path given the key to see if the node exists.
+        for (; charKey != key.data() + key.size(); ++charKey) {
+            idx = static_cast<uint8_t>(*charKey);
+            if (node->children[idx] != nullptr) {
+                node = node->children[idx].get();
+                context.push_back(node);
+            } else {
+                break;
+            }
+        }
 
-    // Look up
+        // If the node existed, then can just return an iterator to that node.
+        if (charKey == key.data() + key.size())
+            return const_iterator(_root, node);
+
+        // The node did not exist, so must find an node with the next largest key (if it exists).
+        // Use the context stack to move up the tree and keep searching for the next node with data
+        // if need be.
+        while (!context.empty()) {
+            node = context.back();
+            context.pop_back();
+
+            for (auto iter = idx + 1 + node->children.begin(); iter != node->children.end();
+                 ++iter) {
+
+                if (*iter != nullptr) {
+                    // There exists a node with a key larger than the one given, traverse to this
+                    // node which will be the left-most node in this sub-tree.
+                    node = iter->get();
+                    while (node->data == boost::none) {
+                        for (auto iter = node->children.begin(); iter != node->children.end();
+                             ++iter) {
+                            if (*iter != nullptr) {
+                                node = iter->get();
+                                break;
+                            }
+                        }
+                    }
+                    return const_iterator(_root, node);
+                }
+            }
+            idx = node->trieKey;
+        }
 
-    iterator find(const Key& key) {
-        return iterator(this->map.find(key));
+        // If there was no node with a larger key than the one given, return end().
+        return end();
     }
 
-    const_iterator find(const Key& key) const {
-        return const_iterator(this->map.find(key));
-    }
+    const_iterator upper_bound(const Key& key) const {
+        const_iterator it = lower_bound(key);
+        if (it == end())
+            return it;
 
-    iterator lower_bound(const Key& key) {
-        return iterator(this->map.lower_bound(key));
-    }
+        if (it->first == key)
+            return ++it;
 
-    const_iterator lower_bound(const Key& key) const {
-        return const_iterator(this->map.lower_bound(key));
+        return it;
     }
 
-    iterator upper_bound(const Key& key) {
-        return iterator(this->map.upper_bound(key));
+    typename RadixStore::iterator::difference_type distance(iterator iter1, iterator iter2) {
+        return std::distance(iter1, iter2);
     }
 
-    const_iterator upper_bound(const Key& key) const {
-        return const_iterator(this->map.upper_bound(key));
+    typename RadixStore::iterator::difference_type distance(const_iterator iter1,
+                                                            const_iterator iter2) {
+        return std::distance(iter1, iter2);
     }
 
-    // std::distance
+private:
+    class Node {
+        friend class RadixStore;
 
-    typename iterator::difference_type distance(iterator iter1, iterator iter2) {
-        return typename iterator::difference_type(std::distance(iter1.iter, iter2.iter));
-    };
+    public:
+        Node(uint8_t key) : trieKey(key) {
+            children.fill(nullptr);
+        }
 
-    typename iterator::difference_type distance(const_iterator iter1, const_iterator iter2) const {
-        return typename iterator::difference_type(std::distance(iter1.iter, iter2.iter));
+        bool isLeaf() {
+            for (auto child : children) {
+                if (child != nullptr)
+                    return false;
+            }
+            return true;
+        }
+
+        uint8_t trieKey;
+        boost::optional<value_type> data;
+        std::array<std::shared_ptr<Node>, 256> children;
     };
+
+
+    Node* _findNode(const Key& key) const {
+        auto node = _root;
+        for (const char* it = key.data(); it != key.data() + key.size(); ++it) {
+            const uint8_t k = static_cast<const uint8_t>(*it);
+            if (node->children[k] != nullptr)
+                node = node->children[k];
+            else
+                return nullptr;
+        }
+
+        if (node->data == boost::none)
+            return nullptr;
+
+        return node.get();
+    }
+
+    /**
+     * _upsertWithCopyOnSharedNodes is a helper function to help manage copy on modification for the
+     * tree. This function follows the path for the to-be modified node using the keystring. If at
+     * any point, the path is no longer uniquely owned, the following nodes are copied to prevent
+     * modification to other owner's data.
+     *
+     * 'key' is the key which can be followed to find the data.
+     * 'value' is the data to be inserted or updated. It can be an empty value in which case it is
+     * equivalent to removing that data from the tree.
+     */
+    std::pair<const_iterator, bool> _upsertWithCopyOnSharedNodes(
+        Key key, boost::optional<value_type> value) {
+
+        auto node = _root;
+        std::shared_ptr<Node> parent = nullptr;
+        const char* keyString = key.data();
+        size_t i = 0;
+
+        // Follow the path in the tree as defined by the key string until a non-uniquely owned node.
+        // This loop would exit at the root if the root itself was shared, or exit at the end in the
+        // event the entire path was uniquely owned.
+        for (; i < key.size(); i++) {
+
+            // The current node in the traversal, if unique, will always have two pointers to it,
+            // not one. This is because the parent node holds it as a child node, but now also we
+            // have 'node' pointing to it. The loop will exit if the tree node is no longer uniquely
+            // owned.
+            if (node.use_count() > 2)
+                break;
+
+            uint8_t c = static_cast<uint8_t>(keyString[i]);
+
+            if (node->children[c] != nullptr) {
+                parent = node;
+                node = node->children[c];
+            } else {
+                node->children[c] = std::make_shared<Node>(c);
+                parent = node;
+                node = node->children[c];
+            }
+        }
+
+        std::shared_ptr<Node> old;
+
+        if (i == 0) {
+            // If the _root node is shared to begin with, copy the _root. This is necessary since
+            // '_root' is a member variable and must be updated if changed, unlike other inner nodes
+            // of the tree.
+            old = _root;
+            _root = std::make_shared<Node>('\0');
+            node = _root;
+
+        } else if (i < key.size()) {
+            // If there is a shared node in the middle of the tree, backtrack and create a new node
+            // that is singly owned by this tree. It is necessary to copy all following nodes as
+            // well.
+            old = node;
+            uint8_t c = static_cast<uint8_t>(keyString[i - 1]);
+            parent->children[c] = std::make_shared<Node>(c);
+            node = parent->children[c];
+
+        } else if (i >= key.size()) {
+            // If all nodes prior to the last node in the traversal are uniquely owned, then set
+            // 'old' to nullptr to prevent reassigning the node's children.
+            old = nullptr;
+
+            if (node.use_count() > 2) {
+                // In the special case in which the to-be modified node (the last node in our
+                // traversal) is itself the first non-uniquely owned node - copy it and reassign its
+                // parents and children.
+                old = node;
+                uint8_t c = static_cast<uint8_t>(keyString[i - 1]);
+                parent->children[c] = std::make_shared<Node>(c);
+                node = parent->children[c];
+            }
+        }
+
+        for (; i < key.size(); i++) {
+            uint8_t c = static_cast<uint8_t>(keyString[i]);
+
+            if (old != nullptr) {
+                node->children = old->children;
+
+                if (old->data != boost::none)
+                    node->data.emplace(old->data->first, old->data->second);
+
+                old = old->children[c];
+            }
+
+            node->children[c] = std::make_shared<Node>(c);
+            node = node->children[c];
+        }
+
+        if (value != boost::none) {
+            node->data.emplace(value->first, value->second);
+        } else {
+            node->data = boost::none;
+        }
+
+        // If 'old' isn't a nullptr, add the children since the modified node need not be a leaf in
+        // the tree. Will only have to do this if the modified node was not uniquely owned, and a
+        // copy was created.
+        if (old != nullptr) {
+            node->children = old->children;
+        }
+
+        const_iterator it(_root, node.get());
+        return std::pair<const_iterator, bool>(it, true);
+    }
+
+    /**
+    * This function traverses the tree starting at the provided node using the provided the
+    * key. It returns the stack which is used in tree traversals for both the forward and
+    * reverse iterators. Since both iterator classes use this function, it is declared
+    * statically under RadixStore.
+    */
+    static std::vector<Node*> _buildContext(Key key, Node* node) {
+        std::vector<Node*> context;
+        context.push_back(node);
+        for (const char* it = key.data(); it != key.data() + key.size(); ++it) {
+            uint8_t c = static_cast<uint8_t>(*it);
+            node = node->children[c].get();
+            context.push_back(node);
+        }
+        return context;
+    }
+
+    std::shared_ptr<Node> _root;
+    size_type _numElems;
+    size_type _sizeElems;
 };
 
-using StringStore = Store<std::string, std::string>;
-}
-}
+using StringStore = RadixStore<std::string, std::string>;
+}  // namespace biggie
+}  // namespace mongo
diff --git a/src/mongo/db/storage/biggie/store_test.cpp b/src/mongo/db/storage/biggie/store_test.cpp
index 00833e6d517..d194e196a2f 100644
--- a/src/mongo/db/storage/biggie/store_test.cpp
+++ b/src/mongo/db/storage/biggie/store_test.cpp
@@ -1,5 +1,5 @@
 /**
- *    Copyright 2018 MongoDB Inc.
+ *    Copyright 2017 MongoDB Inc.
  *
  *    This program is free software: you can redistribute it and/or  modify
  *    it under the terms of the GNU Affero General Public License, version 3,
@@ -26,20 +26,22 @@
  *    it in the license file.
  */
 
-#include "mongo/platform/basic.h"
+#define MONGO_LOG_DEFAULT_COMPONENT ::mongo::logger::LogComponent::kDefault
 
 #include "mongo/db/storage/biggie/store.h"
-
+#include "mongo/platform/basic.h"
 #include "mongo/unittest/unittest.h"
+#include "mongo/util/log.h"
+#include <iostream>
 
 namespace mongo {
 namespace biggie {
 namespace {
 
-using StringStore = Store<std::string, std::string>;
+using StringStore = RadixStore<std::string, std::string>;
 using value_type = StringStore::value_type;
 
-class StoreTest : public unittest::Test {
+class RadixStoreTest : public unittest::Test {
 protected:
     StringStore thisStore;
     StringStore otherStore;
@@ -47,75 +49,758 @@ protected:
     StringStore expected;
 };
 
-TEST_F(StoreTest, InsertTest) {
-    value_type value1 = std::make_pair("1", "foo");
-    std::pair<StringStore::iterator, bool> res = thisStore.insert(value_type(value1));
+TEST_F(RadixStoreTest, SimpleInsertTest) {
+    value_type value1 = std::make_pair("food", "1");
+    value_type value2 = std::make_pair("foo", "2");
+    value_type value3 = std::make_pair("bar", "3");
+
+    std::pair<StringStore::const_iterator, bool> res = thisStore.insert(value_type(value1));
+    ASSERT_EQ(thisStore.size(), StringStore::size_type(1));
     ASSERT_TRUE(res.second);
     ASSERT_TRUE(*res.first == value1);
+
+    res = thisStore.insert(value_type(value2));
+    ASSERT_EQ(thisStore.size(), StringStore::size_type(2));
+    ASSERT_TRUE(res.second);
+    ASSERT_TRUE(*res.first == value2);
+
+    res = thisStore.insert(value_type(value3));
+    ASSERT_EQ(thisStore.size(), StringStore::size_type(3));
+    ASSERT_TRUE(res.second);
+    ASSERT_TRUE(*res.first == value3);
 }
 
-TEST_F(StoreTest, EmptyTest) {
-    value_type value1 = std::make_pair("1", "foo");
-    ASSERT_TRUE(thisStore.empty());
+TEST_F(RadixStoreTest, SimpleIteratorAssignmentTest) {
+    value_type value1 = std::make_pair("food", "1");
+    value_type value2 = std::make_pair("foo", "2");
+    value_type value3 = std::make_pair("bar", "3");
 
     thisStore.insert(value_type(value1));
-    ASSERT_FALSE(thisStore.empty());
+    thisStore.insert(value_type(value2));
+    thisStore.insert(value_type(value3));
+
+    otherStore = thisStore;
+
+    StringStore::const_iterator thisIter = thisStore.begin();
+    StringStore::const_iterator otherIter = otherStore.begin();
+
+    ASSERT_TRUE(thisIter == otherIter);
+
+    thisIter = otherStore.begin();
+    ASSERT_TRUE(thisIter == otherIter);
 }
 
-TEST_F(StoreTest, SizeTest) {
-    value_type value1 = std::make_pair("1", "foo");
-    auto expected1 = StringStore::size_type(0);
-    ASSERT_EQ(thisStore.size(), expected1);
+TEST_F(RadixStoreTest, InsertInCopyFromRootTest) {
+    value_type value1 = std::make_pair("foo", "1");
+    value_type value2 = std::make_pair("fod", "2");
+    value_type value3 = std::make_pair("fee", "3");
+    value_type value4 = std::make_pair("fed", "4");
 
     thisStore.insert(value_type(value1));
-    auto expected2 = StringStore::size_type(1);
-    ASSERT_EQ(thisStore.size(), expected2);
+    thisStore.insert(value_type(value2));
+    thisStore.insert(value_type(value3));
+
+    otherStore = thisStore;
+
+    std::pair<StringStore::const_iterator, bool> res = otherStore.insert(value_type(value4));
+    ASSERT_TRUE(res.second);
+
+    StringStore::const_iterator it1 = thisStore.find(value4.first);
+    StringStore::const_iterator it2 = otherStore.find(value4.first);
+
+    ASSERT_TRUE(it1 == thisStore.end());
+    ASSERT_TRUE(it2 != otherStore.end());
+
+    StringStore::const_iterator check_this = thisStore.begin();
+    StringStore::const_iterator check_other = otherStore.begin();
+
+    // Only 'otherStore' should have the 'fed' object, whereas thisStore should point to the 'fee'
+    // node
+    ASSERT_TRUE(check_other->first == value4.first);
+    ASSERT_TRUE(check_this->first == value3.first);
+    check_other++;
+
+    // Both should point to the same "fee" node.
+    ASSERT_EQUALS(&*check_this, &*check_other);
+    check_this++;
+    check_other++;
+
+    // Now both should point to the same "fod" node.
+    ASSERT_EQUALS(&*check_this, &*check_other);
+    check_this++;
+    check_other++;
+
+    // Both should point to the same "foo" node.
+    ASSERT_EQUALS(&*check_this, &*check_other);
+    check_this++;
+    check_other++;
+
+    ASSERT_TRUE(check_this == thisStore.end());
+    ASSERT_TRUE(check_other == otherStore.end());
 }
 
-TEST_F(StoreTest, ClearTest) {
-    value_type value1 = std::make_pair("1", "foo");
+TEST_F(RadixStoreTest, InsertInBothCopiesTest) {
+    value_type value1 = std::make_pair("foo", "1");
+    value_type value2 = std::make_pair("fod", "2");
+    value_type value3 = std::make_pair("fee", "3");
+    value_type value4 = std::make_pair("fed", "4");
 
     thisStore.insert(value_type(value1));
-    ASSERT_FALSE(thisStore.empty());
+    thisStore.insert(value_type(value2));
 
-    thisStore.clear();
-    ASSERT_TRUE(thisStore.empty());
+    otherStore = thisStore;
+
+    thisStore.insert(value_type(value3));
+    otherStore.insert(value_type(value4));
+
+    StringStore::const_iterator check_this = thisStore.find(value4.first);
+    StringStore::const_iterator check_other = otherStore.find(value3.first);
+
+    // 'thisStore' should not have value4 and 'otherStore' should not have value3.
+    ASSERT_TRUE(check_this == thisStore.end());
+    ASSERT_TRUE(check_other == otherStore.end());
+
+    check_this = thisStore.begin();
+    check_other = otherStore.begin();
+
+    // Only 'otherStore' should have the 'fed' object, whereas thisStore should point to the 'fee'
+    // node
+    ASSERT_TRUE(check_this->first == value3.first);
+    ASSERT_TRUE(check_other->first == value4.first);
+    check_other++;
+    check_this++;
+
+    // Now both should point to the same "fod" node.
+    ASSERT_EQUALS(&*check_this, &*check_other);
+    check_this++;
+    check_other++;
+
+    // Both should point to the same "foo" node.
+    ASSERT_EQUALS(&*check_this, &*check_other);
+    check_this++;
+    check_other++;
+
+    ASSERT_TRUE(check_this == thisStore.end());
+    ASSERT_TRUE(check_other == otherStore.end());
 }
 
-TEST_F(StoreTest, EraseTest) {
-    value_type value1 = std::make_pair("1", "foo");
-    value_type value2 = std::make_pair("2", "bar");
+TEST_F(RadixStoreTest, InsertTwiceInCopyTest) {
+    value_type value1 = std::make_pair("foo", "1");
+    value_type value2 = std::make_pair("fod", "2");
+    value_type value3 = std::make_pair("fee", "3");
+    value_type value4 = std::make_pair("fed", "4");
+    value_type value5 = std::make_pair("food", "5");
 
     thisStore.insert(value_type(value1));
     thisStore.insert(value_type(value2));
-    auto expected1 = StringStore::size_type(2);
-    ASSERT_EQ(thisStore.size(), expected1);
+    thisStore.insert(value_type(value3));
 
-    thisStore.erase(value1.first);
-    auto expected2 = StringStore::size_type(1);
-    ASSERT_EQ(thisStore.size(), expected2);
+    otherStore = thisStore;
 
-    thisStore.erase("3");
-    ASSERT_EQ(thisStore.size(), expected2);
+    otherStore.insert(value_type(value4));
+    otherStore.insert(value_type(value5));
+
+    StringStore::const_iterator check_this = thisStore.begin();
+    StringStore::const_iterator check_other = otherStore.begin();
+
+    // Only 'otherStore' should have the 'fed' object, whereas thisStore should point to the 'fee'
+    // node
+    ASSERT_TRUE(check_other->first == value4.first);
+    ASSERT_TRUE(check_this->first == value3.first);
+    check_other++;
+
+    // Both should point to the same "fee" node.
+    ASSERT_EQUALS(&*check_this, &*check_other);
+    check_this++;
+    check_other++;
+
+    // Now both should point to the same "fod" node.
+    ASSERT_EQUALS(&*check_this, &*check_other);
+    check_this++;
+    check_other++;
+
+    // Both should point to "foo", but they should be different objects
+    ASSERT_TRUE(check_this->first == value1.first);
+    ASSERT_TRUE(check_other->first == value1.first);
+    ASSERT_TRUE(&*check_this != &*check_other);
+    check_this++;
+    check_other++;
+
+    ASSERT_TRUE(check_this == thisStore.end());
+    ASSERT_TRUE(check_other->first == value5.first);
+    check_other++;
+
+    ASSERT_TRUE(check_other == otherStore.end());
 }
 
-TEST_F(StoreTest, FindTest) {
-    value_type value1 = std::make_pair("1", "foo");
-    value_type value2 = std::make_pair("2", "bar");
+TEST_F(RadixStoreTest, InsertInBranchWithSharedChildrenTest) {
+    value_type value1 = std::make_pair("foo", "1");
+    value_type value2 = std::make_pair("fod", "2");
+    value_type value3 = std::make_pair("fee", "3");
+    value_type value4 = std::make_pair("fed", "4");
+    value_type value5 = std::make_pair("feed", "5");
+
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value2));
+    thisStore.insert(value_type(value3));
+
+    otherStore = thisStore;
+
+    otherStore.insert(value_type(value4));
+    otherStore.insert(value_type(value5));
+
+    StringStore::const_iterator check_this = thisStore.begin();
+    StringStore::const_iterator check_other = otherStore.begin();
+
+    // Only 'otherStore' should have the 'fed' object, whereas thisStore should point to the 'fee'
+    // node
+    ASSERT_TRUE(check_other->first == value4.first);
+    ASSERT_TRUE(check_this->first == value3.first);
+    check_other++;
+
+    // Both should point to "fee", but they should be different objects
+    ASSERT_TRUE(check_this->first == value3.first);
+    ASSERT_TRUE(check_other->first == value3.first);
+    ASSERT_TRUE(&*check_this != &*check_other);
+    check_this++;
+    check_other++;
+
+    // Only 'otherStore' should have the 'feed' object
+    ASSERT_TRUE(check_other->first == value5.first);
+    check_other++;
+
+    // Now both should point to the same "fod" node.
+    ASSERT_EQUALS(&*check_this, &*check_other);
+    check_this++;
+    check_other++;
+
+    // Now both should point to the same "foo" node.
+    ASSERT_EQUALS(&*check_this, &*check_other);
+    check_this++;
+    check_other++;
+
+    ASSERT_TRUE(check_this == thisStore.end());
+    ASSERT_TRUE(check_other == otherStore.end());
+}
+
+TEST_F(RadixStoreTest, InsertNonLeafNodeInBranchWithSharedChildrenTest) {
+    value_type value1 = std::make_pair("fed", "1");
+    value_type value2 = std::make_pair("fee", "2");
+    value_type value3 = std::make_pair("feed", "3");
+    value_type value4 = std::make_pair("fod", "4");
+    value_type value5 = std::make_pair("foo", "5");
+
+    thisStore.insert(value_type(value3));
+    thisStore.insert(value_type(value4));
+    thisStore.insert(value_type(value5));
+
+    otherStore = thisStore;
+
+    otherStore.insert(value_type(value1));
+    otherStore.insert(value_type(value2));
+
+    StringStore::const_iterator check_this = thisStore.begin();
+    StringStore::const_iterator check_other = otherStore.begin();
+
+    // Only 'otherStore' should have the 'fed' object, whereas thisStore should point to the 'feed'
+    // node
+    ASSERT_TRUE(check_other->first == value1.first);
+    ASSERT_TRUE(check_this->first == value3.first);
+    check_other++;
+
+    // Only 'otherStore' should have the 'fee' object
+    ASSERT_TRUE(check_other->first == value2.first);
+    check_other++;
+
+    // Now both should point to the same "feed" node.
+    ASSERT_EQUALS(&*check_this, &*check_other);
+    check_this++;
+    check_other++;
+
+    // Now both should point to the same "fod" node.
+    ASSERT_EQUALS(&*check_this, &*check_other);
+    check_this++;
+    check_other++;
+
+    // Now both should point to the same "foo" node.
+    ASSERT_EQUALS(&*check_this, &*check_other);
+    check_this++;
+    check_other++;
+
+    ASSERT_TRUE(check_this == thisStore.end());
+    ASSERT_TRUE(check_other == otherStore.end());
+}
+
+TEST_F(RadixStoreTest, FindTest) {
+    value_type value1 = std::make_pair("foo", "1");
+    value_type value2 = std::make_pair("bar", "2");
+    value_type value3 = std::make_pair("foozeball", "3");
 
     thisStore.insert(value_type(value1));
     thisStore.insert(value_type(value2));
-    auto expected = StringStore::size_type(2);
-    ASSERT_EQ(thisStore.size(), expected);
+    thisStore.insert(value_type(value3));
+    ASSERT_EQ(thisStore.size(), StringStore::size_type(3));
 
-    StringStore::iterator iter1 = thisStore.find(value1.first);
+    StringStore::const_iterator iter1 = thisStore.find(value1.first);
+    ASSERT_FALSE(iter1 == thisStore.end());
     ASSERT_TRUE(*iter1 == value1);
 
-    StringStore::iterator iter2 = thisStore.find("3");
+    StringStore::const_iterator iter2 = thisStore.find("fooze");
     ASSERT_TRUE(iter2 == thisStore.end());
 }
 
-TEST_F(StoreTest, DataSizeTest) {
+TEST_F(RadixStoreTest, UpdateTest) {
+    value_type value1 = std::make_pair("foo", "1");
+    value_type value2 = std::make_pair("bar", "2");
+    value_type value3 = std::make_pair("foz", "3");
+    value_type update = std::make_pair("foo", "test");
+
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value2));
+    thisStore.insert(value_type(value3));
+
+    StringStore copy(thisStore);
+    thisStore.update(value_type(update));
+
+    StringStore::const_iterator it2 = thisStore.begin();
+    StringStore::const_iterator copy_it2 = copy.begin();
+
+    // both should point to the same 'bar' object
+    ASSERT_EQ(&*it2, &*copy_it2);
+    it2++;
+    copy_it2++;
+
+    // the 'foo' object should be different
+    ASSERT_TRUE(it2->second == "test");
+    ASSERT_TRUE(copy_it2->second != "test");
+    ASSERT_TRUE(&*copy_it2 != &*it2);
+    it2++;
+    copy_it2++;
+
+    ASSERT_EQ(&*it2, &*copy_it2);
+    it2++;
+    copy_it2++;
+
+    ASSERT_TRUE(copy_it2 == copy.end());
+    ASSERT_TRUE(it2 == thisStore.end());
+}
+
+TEST_F(RadixStoreTest, UpdateLeafOnSharedNodeTest) {
+    value_type value1 = std::make_pair("foo", "1");
+    value_type value2 = std::make_pair("bar", "2");
+    value_type value3 = std::make_pair("fool", "3");
+    value_type upd = std::make_pair("fool", "test");
+
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value2));
+    thisStore.insert(value_type(value3));
+
+    StringStore copy(thisStore);
+    thisStore.update(value_type(upd));
+
+    StringStore::const_iterator it2 = thisStore.begin();
+    StringStore::const_iterator copy_it2 = copy.begin();
+
+    // both should point to the same 'bar' object
+    ASSERT_EQ(&*it2, &*copy_it2);
+    it2++;
+    copy_it2++;
+
+    // the 'foo' object should be different but have the same value. This is due to the node being
+    // copied since 'fool' was updated
+    ASSERT_TRUE(it2->second == "1");
+    ASSERT_TRUE(copy_it2->second == "1");
+    ASSERT_TRUE(&*copy_it2 != &*it2);
+    it2++;
+    copy_it2++;
+
+    // the 'fool' object should be different
+    ASSERT_TRUE(it2->second == "test");
+    ASSERT_TRUE(copy_it2->second != "test");
+    ASSERT_TRUE(&*copy_it2 != &*it2);
+    it2++;
+    copy_it2++;
+
+    ASSERT_TRUE(copy_it2 == copy.end());
+    ASSERT_TRUE(it2 == thisStore.end());
+}
+
+TEST_F(RadixStoreTest, UpdateSharedBranchNonLeafNodeTest) {
+    value_type value1 = std::make_pair("fee", "1");
+    value_type value2 = std::make_pair("fed", "2");
+    value_type value3 = std::make_pair("feed", "3");
+    value_type value4 = std::make_pair("foo", "4");
+    value_type value5 = std::make_pair("fod", "5");
+    value_type upd_val = std::make_pair("fee", "6");
+
+    thisStore.insert(value_type(value4));
+    thisStore.insert(value_type(value5));
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value3));
+
+    otherStore = thisStore;
+
+    otherStore.insert(value_type(value2));
+    otherStore.update(value_type(upd_val));
+
+    StringStore::const_iterator check_this = thisStore.begin();
+    StringStore::const_iterator check_other = otherStore.begin();
+
+    // Only 'otherStore' should have the 'fed' object, whereas thisStore should point to the 'fee'
+    // node
+    ASSERT_TRUE(check_this->first == value1.first);
+    ASSERT_TRUE(check_other->first == value2.first);
+    check_other++;
+
+    // 'thisStore' should point to the old 'fee' object whereas 'otherStore' should point to the
+    // updated object
+    ASSERT_TRUE(check_this->first == value1.first);
+    ASSERT_TRUE(check_this->second == value1.second);
+    ASSERT_TRUE(check_other->first == value1.first);
+    ASSERT_TRUE(check_other->second == upd_val.second);
+    ASSERT_TRUE(&*check_this != &*check_other);
+    check_this++;
+    check_other++;
+
+    // Now both should point to the same "feed" node.
+    ASSERT_EQUALS(&*check_this, &*check_other);
+    check_this++;
+    check_other++;
+
+    // Now both should point to the same "fod" node.
+    ASSERT_EQUALS(&*check_this, &*check_other);
+    check_this++;
+    check_other++;
+
+    // Now both should point to the same "foo" node.
+    ASSERT_EQUALS(&*check_this, &*check_other);
+    check_this++;
+    check_other++;
+
+    ASSERT_TRUE(check_this == thisStore.end());
+    ASSERT_TRUE(check_other == otherStore.end());
+}
+
+TEST_F(RadixStoreTest, SimpleEraseTest) {
+    value_type value1 = std::make_pair("abc", "1");
+    value_type value2 = std::make_pair("def", "4");
+    value_type value3 = std::make_pair("ghi", "5");
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value2));
+    thisStore.insert(value_type(value3));
+
+    ASSERT_EQ(thisStore.size(), StringStore::size_type(3));
+
+    StringStore::size_type success = thisStore.erase(value1.first);
+    ASSERT_TRUE(success);
+    ASSERT_EQ(thisStore.size(), StringStore::size_type(2));
+
+    auto iter = thisStore.begin();
+    ASSERT_TRUE(*iter == value2);
+    ++iter;
+    ASSERT_TRUE(*iter == value3);
+    ++iter;
+    ASSERT_TRUE(iter == thisStore.end());
+
+    ASSERT_FALSE(thisStore.erase("jkl"));
+}
+
+TEST_F(RadixStoreTest, EraseNodeWithUniquelyOwnedParent) {
+    value_type value1 = std::make_pair("foo", "1");
+    value_type value2 = std::make_pair("fod", "2");
+    value_type value3 = std::make_pair("fed", "3");
+    value_type value4 = std::make_pair("feed", "4");
+
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value2));
+    thisStore.insert(value_type(value4));
+
+    otherStore = thisStore;
+    otherStore.insert(value_type(value3));
+
+    StringStore::size_type success = otherStore.erase(value4.first);
+    ASSERT_TRUE(success);
+    ASSERT_EQ(thisStore.size(), StringStore::size_type(3));
+    ASSERT_EQ(otherStore.size(), StringStore::size_type(3));
+
+    auto this_it = thisStore.begin();
+    auto other_it = otherStore.begin();
+
+    // 'thisStore' should still have the 'feed' object whereas 'otherStore' should point to the
+    // 'fed' object.
+    ASSERT_TRUE(this_it->first == value4.first);
+    ASSERT_TRUE(other_it->first == value3.first);
+    this_it++;
+    other_it++;
+
+    // 'thisStore' and 'otherStore' should point to the same 'fod' object.
+    ASSERT_TRUE(&*this_it == &*other_it);
+    this_it++;
+    other_it++;
+
+    // 'thisStore' and 'otherStore' should point to the same 'foo' object.
+    ASSERT_TRUE(&*this_it == &*other_it);
+    this_it++;
+    other_it++;
+
+    ASSERT_TRUE(this_it == thisStore.end());
+    ASSERT_TRUE(other_it == otherStore.end());
+}
+
+TEST_F(RadixStoreTest, EraseNodeWithSharedParent) {
+    value_type value1 = std::make_pair("foo", "1");
+    value_type value2 = std::make_pair("fod", "2");
+    value_type value5 = std::make_pair("feed", "5");
+
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value2));
+    thisStore.insert(value_type(value5));
+
+    otherStore = thisStore;
+
+    StringStore::size_type success = otherStore.erase(value5.first);
+    ASSERT_TRUE(success);
+    ASSERT_EQ(thisStore.size(), StringStore::size_type(3));
+    ASSERT_EQ(otherStore.size(), StringStore::size_type(2));
+
+    auto this_it = thisStore.begin();
+    auto other_it = otherStore.begin();
+
+    // 'thisStore' should still have the 'feed' object whereas 'otherStore' should point to the
+    // 'fod' object.
+    ASSERT_TRUE(this_it->first == value5.first);
+    ASSERT_TRUE(other_it->first == value2.first);
+    this_it++;
+
+    // Both iterators should point to the same 'fod' object.
+    ASSERT_TRUE(&*this_it == &*other_it);
+    this_it++;
+    other_it++;
+
+    // 'thisStore' and 'otherStore' should point to the same 'foo' object.
+    ASSERT_TRUE(&*this_it == &*other_it);
+    this_it++;
+    other_it++;
+
+    ASSERT_TRUE(this_it == thisStore.end());
+    ASSERT_TRUE(other_it == otherStore.end());
+}
+
+TEST_F(RadixStoreTest, EraseNonLeafNodeWithSharedParent) {
+    value_type value1 = std::make_pair("foo", "1");
+    value_type value2 = std::make_pair("fod", "2");
+    value_type value3 = std::make_pair("fee", "3");
+    value_type value5 = std::make_pair("feed", "5");
+
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value2));
+    thisStore.insert(value_type(value3));
+    thisStore.insert(value_type(value5));
+
+    otherStore = thisStore;
+
+    StringStore::size_type success = otherStore.erase(value3.first);
+
+    ASSERT_TRUE(success);
+    ASSERT_EQ(thisStore.size(), StringStore::size_type(4));
+    ASSERT_EQ(otherStore.size(), StringStore::size_type(3));
+
+    auto this_it = thisStore.begin();
+    auto other_it = otherStore.begin();
+
+    // 'thisStore' should still have the 'fee' object whereas 'otherStore' should point to the
+    // 'feed' object.
+    ASSERT_TRUE(this_it->first == value3.first);
+    ASSERT_TRUE(other_it->first == value5.first);
+    this_it++;
+
+    // Now both iterators should point to the same 'feed' object.
+    ASSERT_TRUE(&*this_it == &*other_it);
+    this_it++;
+    other_it++;
+
+    // 'thisStore' and 'otherStore' should point to the same 'fod' object.
+    ASSERT_TRUE(&*this_it == &*other_it);
+    this_it++;
+    other_it++;
+
+    // 'thisStore' and 'otherStore' should point to the same 'foo' object.
+    ASSERT_TRUE(&*this_it == &*other_it);
+    this_it++;
+    other_it++;
+
+    ASSERT_TRUE(this_it == thisStore.end());
+    ASSERT_TRUE(other_it == otherStore.end());
+}
+
+TEST_F(RadixStoreTest, ErasePrefixOfAnotherKeyOfCopiedStoreTest) {
+    std::string prefix = "bar";
+    std::string prefix2 = "barrista";
+    value_type value1 = std::make_pair(prefix, "1");
+    value_type value2 = std::make_pair(prefix2, "2");
+    baseStore.insert(value_type(value1));
+    baseStore.insert(value_type(value2));
+
+    thisStore = baseStore;
+    StringStore::size_type success = thisStore.erase(prefix);
+
+    ASSERT_TRUE(success);
+    ASSERT_EQ(thisStore.size(), StringStore::size_type(1));
+    ASSERT_EQ(baseStore.size(), StringStore::size_type(2));
+    StringStore::const_iterator iter = thisStore.find(prefix2);
+    ASSERT_TRUE(iter != thisStore.end());
+    ASSERT_EQ(iter->first, prefix2);
+}
+
+TEST_F(RadixStoreTest, ErasePrefixOfAnotherKeyTest) {
+    std::string prefix = "bar";
+    std::string otherKey = "barrista";
+    value_type value1 = std::make_pair(prefix, "2");
+    value_type value2 = std::make_pair(otherKey, "3");
+    value_type value3 = std::make_pair("foz", "4");
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value2));
+    thisStore.insert(value_type(value3));
+
+    ASSERT_EQ(thisStore.size(), StringStore::size_type(3));
+
+    StringStore::size_type success = thisStore.erase(prefix);
+    ASSERT_TRUE(success);
+    ASSERT_EQ(thisStore.size(), StringStore::size_type(2));
+    StringStore::const_iterator iter = thisStore.find(otherKey);
+    ASSERT_TRUE(iter != thisStore.end());
+    ASSERT_EQ(iter->first, otherKey);
+}
+
+TEST_F(RadixStoreTest, EraseKeyWithPrefixStillInStoreTest) {
+    std::string key = "barrista";
+    std::string prefix = "bar";
+    value_type value1 = std::make_pair(prefix, "2");
+    value_type value2 = std::make_pair(key, "3");
+    value_type value3 = std::make_pair("foz", "4");
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value2));
+    thisStore.insert(value_type(value3));
+
+    ASSERT_EQ(thisStore.size(), StringStore::size_type(3));
+
+    StringStore::size_type success = thisStore.erase(key);
+    ASSERT_TRUE(success);
+    ASSERT_EQ(thisStore.size(), StringStore::size_type(2));
+    StringStore::const_iterator iter = thisStore.find(prefix);
+    ASSERT_FALSE(iter == thisStore.end());
+    ASSERT_EQ(iter->first, prefix);
+}
+
+TEST_F(RadixStoreTest, EraseKeyThatOverlapsAnotherKeyTest) {
+    std::string key = "foo";
+    std::string otherKey = "foz";
+    value_type value1 = std::make_pair(key, "1");
+    value_type value2 = std::make_pair(otherKey, "4");
+    value_type value3 = std::make_pair("bar", "5");
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value2));
+    thisStore.insert(value_type(value3));
+
+    ASSERT_EQ(thisStore.size(), StringStore::size_type(3));
+
+    StringStore::size_type success = thisStore.erase(key);
+    ASSERT_TRUE(success);
+    ASSERT_EQ(thisStore.size(), StringStore::size_type(2));
+    StringStore::const_iterator iter = thisStore.find(otherKey);
+    ASSERT_FALSE(iter == thisStore.end());
+    ASSERT_EQ(iter->first, otherKey);
+}
+
+TEST_F(RadixStoreTest, CopyTest) {
+    value_type value1 = std::make_pair("foo", "1");
+    value_type value2 = std::make_pair("bar", "2");
+    value_type value3 = std::make_pair("foz", "3");
+    value_type value4 = std::make_pair("baz", "4");
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value2));
+    thisStore.insert(value_type(value3));
+
+    StringStore copy(thisStore);
+
+    std::pair<StringStore::const_iterator, bool> ins = copy.insert(value_type(value4));
+    StringStore::const_iterator find1 = copy.find(value4.first);
+    ASSERT_EQ(&*find1, &*ins.first);
+
+    StringStore::const_iterator find2 = thisStore.find(value4.first);
+    ASSERT_TRUE(find2 == thisStore.end());
+
+    StringStore::const_iterator iter = thisStore.begin();
+    StringStore::const_iterator copy_iter = copy.begin();
+
+    ASSERT_EQ(&*iter, &*copy_iter);
+
+    iter++;
+    copy_iter++;
+
+    ASSERT_TRUE(copy_iter->first == "baz");
+
+    // Node 'baz' should not be in 'thisStore'
+    ASSERT_FALSE(iter->first == "baz");
+    copy_iter++;
+
+    ASSERT_EQ(&*iter, &*copy_iter);
+
+    iter++;
+    copy_iter++;
+    ASSERT_EQ(&*iter, &*copy_iter);
+
+    iter++;
+    copy_iter++;
+    ASSERT_TRUE(iter == thisStore.end());
+    ASSERT_TRUE(copy_iter == copy.end());
+}
+
+TEST_F(RadixStoreTest, EmptyTest) {
+    value_type value1 = std::make_pair("1", "foo");
+    ASSERT_TRUE(thisStore.empty());
+
+    thisStore.insert(value_type(value1));
+    ASSERT_FALSE(thisStore.empty());
+}
+
+TEST_F(RadixStoreTest, NumElementsTest) {
+    value_type value1 = std::make_pair("1", "foo");
+    auto expected1 = StringStore::size_type(0);
+    ASSERT_EQ(thisStore.size(), expected1);
+
+    thisStore.insert(value_type(value1));
+    auto expected2 = StringStore::size_type(1);
+    ASSERT_EQ(thisStore.size(), expected2);
+}
+
+TEST_F(RadixStoreTest, SimpleStoreEqualityTest) {
+    value_type value1 = std::make_pair("food", "1");
+    value_type value2 = std::make_pair("foo", "2");
+    value_type value3 = std::make_pair("bar", "3");
+
+    otherStore.insert(value_type(value1));
+    otherStore.insert(value_type(value2));
+    otherStore.insert(value_type(value3));
+
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value2));
+    thisStore.insert(value_type(value3));
+
+    ASSERT_TRUE(otherStore == thisStore);
+}
+
+TEST_F(RadixStoreTest, ClearTest) {
+    value_type value1 = std::make_pair("1", "foo");
+
+    thisStore.insert(value_type(value1));
+    ASSERT_FALSE(thisStore.empty());
+
+    thisStore.clear();
+    ASSERT_TRUE(thisStore.empty());
+}
+
+TEST_F(RadixStoreTest, DataSizeTest) {
     std::string str1 = "foo";
     std::string str2 = "bar65";
 
@@ -126,60 +811,61 @@ TEST_F(StoreTest, DataSizeTest) {
     ASSERT_EQ(thisStore.dataSize(), str1.size() + str2.size());
 }
 
-TEST_F(StoreTest, DistanceTest) {
-    value_type value1 = std::make_pair("1", "foo");
-    value_type value2 = std::make_pair("2", "bar");
-    value_type value3 = std::make_pair("3", "foo");
-    value_type value4 = std::make_pair("4", "bar");
+TEST_F(RadixStoreTest, DistanceTest) {
+    value_type value1 = std::make_pair("foo", "1");
+    value_type value2 = std::make_pair("bar", "2");
+    value_type value3 = std::make_pair("faz", "3");
+    value_type value4 = std::make_pair("baz", "4");
 
     thisStore.insert(value_type(value1));
     thisStore.insert(value_type(value2));
     thisStore.insert(value_type(value3));
     thisStore.insert(value_type(value4));
 
-    StringStore::iterator begin = thisStore.begin();
-    StringStore::iterator second = thisStore.begin();
+    StringStore::const_iterator begin = thisStore.begin();
+    StringStore::const_iterator second = thisStore.begin();
     ++second;
-    StringStore::iterator end = thisStore.end();
+    StringStore::const_iterator end = thisStore.end();
 
     ASSERT_EQ(thisStore.distance(begin, end), 4);
     ASSERT_EQ(thisStore.distance(second, end), 3);
 }
 
-TEST_F(StoreTest, MergeNoModifications) {
+TEST_F(RadixStoreTest, MergeNoModifications) {
     value_type value1 = std::make_pair("1", "foo");
     value_type value2 = std::make_pair("2", "bar");
 
-    thisStore.insert(value_type(value1));
-    thisStore.insert(value_type(value2));
-
-    otherStore.insert(value_type(value1));
-    otherStore.insert(value_type(value2));
-
     baseStore.insert(value_type(value1));
     baseStore.insert(value_type(value2));
 
+    thisStore = baseStore;
+    otherStore = baseStore;
+
+    expected.insert(value_type(value1));
+    expected.insert(value_type(value2));
+
     StringStore merged = thisStore.merge3(baseStore, otherStore);
 
-    ASSERT_TRUE(merged == thisStore);
+    ASSERT_TRUE(merged == expected);
 }
 
-TEST_F(StoreTest, MergeModifications) {
+TEST_F(RadixStoreTest, MergeModifications) {
     value_type value1 = std::make_pair("1", "foo");
     value_type value2 = std::make_pair("1", "bar");
 
     value_type value3 = std::make_pair("3", "baz");
     value_type value4 = std::make_pair("3", "faz");
 
-    thisStore.insert(value_type(value2));
-    thisStore.insert(value_type(value3));
-
-    otherStore.insert(value_type(value1));
-    otherStore.insert(value_type(value4));
-
     baseStore.insert(value_type(value1));
     baseStore.insert(value_type(value3));
 
+    thisStore = baseStore;
+    otherStore = baseStore;
+
+    thisStore.update(value_type(value2));
+
+    otherStore.update(value_type(value4));
+
     expected.insert(value_type(value2));
     expected.insert(value_type(value4));
 
@@ -188,25 +874,22 @@ TEST_F(StoreTest, MergeModifications) {
     ASSERT_TRUE(merged == expected);
 }
 
-TEST_F(StoreTest, MergeDeletions) {
+TEST_F(RadixStoreTest, MergeDeletions) {
     value_type value1 = std::make_pair("1", "foo");
     value_type value2 = std::make_pair("2", "moo");
     value_type value3 = std::make_pair("3", "bar");
     value_type value4 = std::make_pair("4", "baz");
-
-    thisStore.insert(value_type(value1));
-    thisStore.insert(value_type(value3));
-    thisStore.insert(value_type(value4));
-
-    otherStore.insert(value_type(value1));
-    otherStore.insert(value_type(value2));
-    otherStore.insert(value_type(value3));
-
     baseStore.insert(value_type(value1));
     baseStore.insert(value_type(value2));
     baseStore.insert(value_type(value3));
     baseStore.insert(value_type(value4));
 
+    thisStore = baseStore;
+    otherStore = baseStore;
+
+    thisStore.erase(value2.first);
+    otherStore.erase(value4.first);
+
     expected.insert(value_type(value1));
     expected.insert(value_type(value3));
 
@@ -215,23 +898,21 @@ TEST_F(StoreTest, MergeDeletions) {
     ASSERT_TRUE(merged == expected);
 }
 
-TEST_F(StoreTest, MergeInsertions) {
+TEST_F(RadixStoreTest, MergeInsertions) {
     value_type value1 = std::make_pair("1", "foo");
     value_type value2 = std::make_pair("2", "foo");
     value_type value3 = std::make_pair("3", "bar");
     value_type value4 = std::make_pair("4", "faz");
 
-    thisStore.insert(value_type(value1));
-    thisStore.insert(value_type(value2));
-    thisStore.insert(value_type(value4));
-
-    otherStore.insert(value_type(value1));
-    otherStore.insert(value_type(value2));
-    otherStore.insert(value_type(value3));
-
     baseStore.insert(value_type(value1));
     baseStore.insert(value_type(value2));
 
+    thisStore = baseStore;
+    otherStore = baseStore;
+
+    thisStore.insert(value_type(value4));
+    otherStore.insert(value_type(value3));
+
     expected.insert(value_type(value1));
     expected.insert(value_type(value2));
     expected.insert(value_type(value3));
@@ -242,9 +923,12 @@ TEST_F(StoreTest, MergeInsertions) {
     ASSERT_TRUE(merged == expected);
 }
 
-TEST_F(StoreTest, MergeEmptyInsertionOther) {
+TEST_F(RadixStoreTest, MergeEmptyInsertionOther) {
     value_type value1 = std::make_pair("1", "foo");
 
+    thisStore = baseStore;
+    otherStore = baseStore;
+
     otherStore.insert(value_type(value1));
 
     StringStore merged = thisStore.merge3(baseStore, otherStore);
@@ -252,10 +936,12 @@ TEST_F(StoreTest, MergeEmptyInsertionOther) {
     ASSERT_TRUE(merged == otherStore);
 }
 
-TEST_F(StoreTest, MergeEmptyInsertionThis) {
+TEST_F(RadixStoreTest, MergeEmptyInsertionThis) {
     value_type value1 = std::make_pair("1", "foo");
 
-    StringStore thisStore;
+    thisStore = baseStore;
+    otherStore = baseStore;
+
     thisStore.insert(value_type(value1));
 
     StringStore merged = thisStore.merge3(baseStore, otherStore);
@@ -263,7 +949,7 @@ TEST_F(StoreTest, MergeEmptyInsertionThis) {
     ASSERT_TRUE(merged == thisStore);
 }
 
-TEST_F(StoreTest, MergeInsertionDeletionModification) {
+TEST_F(RadixStoreTest, MergeInsertionDeletionModification) {
     value_type value1 = std::make_pair("1", "foo");
     value_type value2 = std::make_pair("2", "baz");
     value_type value3 = std::make_pair("3", "bar");
@@ -273,21 +959,22 @@ TEST_F(StoreTest, MergeInsertionDeletionModification) {
     value_type value7 = std::make_pair("1", "modified");
     value_type value8 = std::make_pair("2", "modified2");
 
-    thisStore.insert(value_type(value7));
-    thisStore.insert(value_type(value2));
-    thisStore.insert(value_type(value3));
-    thisStore.insert(value_type(value5));
-
-    otherStore.insert(value_type(value1));
-    otherStore.insert(value_type(value8));
-    otherStore.insert(value_type(value4));
-    otherStore.insert(value_type(value6));
-
     baseStore.insert(value_type(value1));
     baseStore.insert(value_type(value2));
     baseStore.insert(value_type(value3));
     baseStore.insert(value_type(value4));
 
+    thisStore = baseStore;
+    otherStore = baseStore;
+
+    thisStore.update(value_type(value7));
+    thisStore.erase(value4.first);
+    thisStore.insert(value_type(value5));
+
+    otherStore.update(value_type(value8));
+    otherStore.erase(value3.first);
+    otherStore.insert(value_type(value6));
+
     expected.insert(value_type(value7));
     expected.insert(value_type(value8));
     expected.insert(value_type(value5));
@@ -298,46 +985,59 @@ TEST_F(StoreTest, MergeInsertionDeletionModification) {
     ASSERT_TRUE(merged == expected);
 }
 
-TEST_F(StoreTest, MergeConflictingModifications) {
+TEST_F(RadixStoreTest, MergeConflictingModifications) {
     value_type value1 = std::make_pair("1", "foo");
     value_type value2 = std::make_pair("1", "bar");
     value_type value3 = std::make_pair("1", "baz");
 
-    thisStore.insert(value_type(value2));
+    baseStore.insert(value_type(value1));
 
-    otherStore.insert(value_type(value3));
+    thisStore = baseStore;
+    otherStore = baseStore;
 
-    baseStore.insert(value_type(value1));
+    thisStore.update(value_type(value2));
+
+    otherStore.update(value_type(value3));
 
     ASSERT_THROWS(thisStore.merge3(baseStore, otherStore), merge_conflict_exception);
 }
 
-TEST_F(StoreTest, MergeConflictingModifictionOtherAndDeletionThis) {
+TEST_F(RadixStoreTest, MergeConflictingModifictionOtherAndDeletionThis) {
     value_type value1 = std::make_pair("1", "foo");
     value_type value2 = std::make_pair("1", "bar");
 
-    otherStore.insert(value_type(value2));
-
     baseStore.insert(value_type(value1));
 
+    thisStore = baseStore;
+    otherStore = baseStore;
+    thisStore.erase(value1.first);
+    otherStore.update(value_type(value2));
     ASSERT_THROWS(thisStore.merge3(baseStore, otherStore), merge_conflict_exception);
 }
 
-TEST_F(StoreTest, MergeConflictingModifictionThisAndDeletionOther) {
+TEST_F(RadixStoreTest, MergeConflictingModifictionThisAndDeletionOther) {
     value_type value1 = std::make_pair("1", "foo");
     value_type value2 = std::make_pair("1", "bar");
 
-    thisStore.insert(value_type(value2));
-
     baseStore.insert(value_type(value1));
 
+    thisStore = baseStore;
+    otherStore = baseStore;
+
+    thisStore.update(value_type(value2));
+
+    otherStore.erase(value1.first);
+
     ASSERT_THROWS(thisStore.merge3(baseStore, otherStore), merge_conflict_exception);
 }
 
-TEST_F(StoreTest, MergeConflictingInsertions) {
+TEST_F(RadixStoreTest, MergeConflictingInsertions) {
     value_type value1 = std::make_pair("1", "foo");
     value_type value2 = std::make_pair("1", "foo");
 
+    thisStore = baseStore;
+    otherStore = baseStore;
+
     thisStore.insert(value_type(value2));
 
     otherStore.insert(value_type(value1));
@@ -345,58 +1045,206 @@ TEST_F(StoreTest, MergeConflictingInsertions) {
     ASSERT_THROWS(thisStore.merge3(baseStore, otherStore), merge_conflict_exception);
 }
 
-TEST_F(StoreTest, UpperBoundTest) {
-    value_type value1 = std::make_pair("1", "foo");
-    value_type value2 = std::make_pair("2", "bar");
-    value_type value3 = std::make_pair("3", "foo");
-    value_type value4 = std::make_pair("5", "bar");
+TEST_F(RadixStoreTest, UpperBoundTest) {
+    value_type value1 = std::make_pair("foo", "1");
+    value_type value2 = std::make_pair("bar", "2");
+    value_type value3 = std::make_pair("baz", "3");
+    value_type value4 = std::make_pair("fools", "4");
 
     thisStore.insert(value_type(value1));
     thisStore.insert(value_type(value2));
     thisStore.insert(value_type(value3));
     thisStore.insert(value_type(value4));
 
-    StringStore::iterator iter1 = thisStore.upper_bound(value2.first);
-    ASSERT_EQ(iter1->first, "3");
-    StringStore::iterator iter2 = thisStore.upper_bound(value4.first);
-    ASSERT_TRUE(iter2 == thisStore.end());
+    StringStore::const_iterator iter = thisStore.upper_bound(value2.first);
+    ASSERT_EQ(iter->first, "baz");
+
+    iter = thisStore.upper_bound(value4.first);
+    ASSERT_TRUE(iter == thisStore.end());
+
+    iter = thisStore.upper_bound("baa");
+    ASSERT_EQ(iter->first, "bar");
 }
 
-TEST_F(StoreTest, LowerBoundTest) {
-    value_type value1 = std::make_pair("1", "foo");
-    value_type value2 = std::make_pair("2", "bar");
-    value_type value3 = std::make_pair("3", "foo");
-    value_type value4 = std::make_pair("5", "bar");
+TEST_F(RadixStoreTest, LowerBoundTest) {
+    value_type value1 = std::make_pair("baa", "1");
+    value_type value2 = std::make_pair("bad", "2");
+    value_type value3 = std::make_pair("foo", "3");
+    value_type value4 = std::make_pair("fools", "4");
 
+    thisStore.insert(value_type(value3));
     thisStore.insert(value_type(value1));
     thisStore.insert(value_type(value2));
-    thisStore.insert(value_type(value3));
     thisStore.insert(value_type(value4));
 
-    StringStore::iterator iter1 = thisStore.lower_bound(value2.first);
-    ASSERT_EQ(iter1->first, "2");
-    StringStore::iterator iter2 = thisStore.lower_bound("7");
-    ASSERT_TRUE(iter2 == thisStore.end());
+    StringStore::const_iterator iter = thisStore.lower_bound(value1.first);
+    ASSERT_EQ(iter->first, value1.first);
+
+    ++iter;
+    ASSERT_EQ(iter->first, value2.first);
+
+    iter = thisStore.lower_bound("baz");
+    ASSERT_TRUE(iter == thisStore.find("foo"));
 }
 
-TEST_F(StoreTest, ReverseIteratorTest) {
-    value_type value1 = std::make_pair("1", "foo");
-    value_type value2 = std::make_pair("2", "bar");
-    value_type value3 = std::make_pair("3", "foo");
-    value_type value4 = std::make_pair("4", "bar");
+TEST_F(RadixStoreTest, ReverseIteratorTest) {
+    value_type value1 = std::make_pair("foo", "3");
+    value_type value2 = std::make_pair("bar", "1");
+    value_type value3 = std::make_pair("baz", "2");
+    value_type value4 = std::make_pair("fools", "5");
+    value_type value5 = std::make_pair("foods", "4");
 
     thisStore.insert(value_type(value4));
+    thisStore.insert(value_type(value5));
     thisStore.insert(value_type(value1));
     thisStore.insert(value_type(value3));
     thisStore.insert(value_type(value2));
 
-    int cur = 4;
+    int cur = 5;
     for (auto iter = thisStore.rbegin(); iter != thisStore.rend(); ++iter) {
-        ASSERT_EQ(iter->first, std::to_string(cur));
+        ASSERT_EQ(iter->second, std::to_string(cur));
         --cur;
     }
     ASSERT_EQ(cur, 0);
 }
+
+TEST_F(RadixStoreTest, ReverseIteratorFromForwardIteratorTest) {
+    value_type value1 = std::make_pair("foo", "3");
+    value_type value2 = std::make_pair("bar", "1");
+    value_type value3 = std::make_pair("baz", "2");
+    value_type value4 = std::make_pair("fools", "5");
+    value_type value5 = std::make_pair("foods", "4");
+
+    thisStore.insert(value_type(value4));
+    thisStore.insert(value_type(value5));
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value3));
+    thisStore.insert(value_type(value2));
+
+    int cur = 1;
+    auto iter = thisStore.begin();
+    while (iter != thisStore.end()) {
+        ASSERT_EQ(iter->second, std::to_string(cur));
+        ++cur;
+        ++iter;
+    }
+
+    ASSERT_EQ(cur, 6);
+    ASSERT_TRUE(iter == thisStore.end());
+
+    --cur;
+    // This should create a reverse iterator that starts at the very beginning (for the reverse
+    // iterator).
+    StringStore::const_reverse_iterator riter(iter);
+    while (riter != thisStore.rend()) {
+        ASSERT_EQ(riter->second, std::to_string(cur));
+        --cur;
+        ++riter;
+    }
+
+    ASSERT_EQ(cur, 0);
+}
+
+TEST_F(RadixStoreTest, ReverseIteratorFromMiddleOfForwardIteratorTest) {
+    value_type value1 = std::make_pair("foo", "3");
+    value_type value2 = std::make_pair("bar", "1");
+    value_type value3 = std::make_pair("baz", "2");
+    value_type value4 = std::make_pair("fools", "5");
+    value_type value5 = std::make_pair("foods", "4");
+
+    thisStore.insert(value_type(value4));
+    thisStore.insert(value_type(value5));
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value3));
+    thisStore.insert(value_type(value2));
+
+    int cur = 3;
+    auto iter = thisStore.begin();
+    ++iter;
+    ++iter;
+    ++iter;
+
+    // This should create a reverse iterator that starts at the node 'foo'
+    StringStore::const_reverse_iterator riter(iter);
+    while (riter != thisStore.rend()) {
+        ASSERT_EQ(riter->second, std::to_string(cur));
+        --cur;
+        ++riter;
+    }
+
+    ASSERT_EQ(cur, 0);
+}
+
+TEST_F(RadixStoreTest, ReverseIteratorCopyConstructorTest) {
+    value_type value1 = std::make_pair("foo", "3");
+    value_type value2 = std::make_pair("bar", "1");
+    value_type value3 = std::make_pair("baz", "2");
+    value_type value4 = std::make_pair("fools", "5");
+    value_type value5 = std::make_pair("foods", "4");
+
+    thisStore.insert(value_type(value4));
+    thisStore.insert(value_type(value5));
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value3));
+    thisStore.insert(value_type(value2));
+
+    int cur = 3;
+    auto iter = thisStore.begin();
+    auto iter2(iter);
+    ASSERT_EQ(&*iter, &*iter2);
+
+    ++iter;
+    ++iter2;
+    ASSERT_EQ(&*iter, &*iter2);
+
+    ++iter;
+    ++iter2;
+    ASSERT_EQ(&*iter, &*iter2);
+
+    ++iter;
+    ++iter2;
+    ASSERT_EQ(&*iter, &*iter2);
+
+    // This should create a reverse iterator that starts at the node 'foo'
+    StringStore::const_reverse_iterator riter(iter);
+    StringStore::const_reverse_iterator riter2(riter);
+    while (riter != thisStore.rend()) {
+        ASSERT_EQ(&*riter, &*riter2);
+        --cur;
+        ++riter;
+        ++riter2;
+    }
+
+    ASSERT_EQ(cur, 0);
+}
+
+TEST_F(RadixStoreTest, ReverseIteratorAssignmentOpTest) {
+    value_type value1 = std::make_pair("foo", "3");
+    value_type value2 = std::make_pair("bar", "1");
+    value_type value3 = std::make_pair("baz", "2");
+    value_type value4 = std::make_pair("fools", "5");
+    value_type value5 = std::make_pair("foods", "4");
+
+    thisStore.insert(value_type(value4));
+    thisStore.insert(value_type(value5));
+    thisStore.insert(value_type(value1));
+    thisStore.insert(value_type(value3));
+    thisStore.insert(value_type(value2));
+
+    int cur = 5;
+    auto iter = thisStore.begin();
+
+    StringStore::const_reverse_iterator riter(iter);
+    riter = thisStore.rbegin();
+    while (riter != thisStore.rend()) {
+        ASSERT_EQ(riter->second, std::to_string(cur));
+        --cur;
+        ++riter;
+    }
+
+    ASSERT_EQ(cur, 0);
+}
+
 }  // namespace
-}  // namespace biggie
-}  // namespace mongo
+}  // mongo namespace
+}  // biggie namespace