SERVER-48746 Radix tree merge compresses nodes if needed and does not leave leaf nodes without data

1 files changed, 67 insertions, 0 deletions

diff --git a/src/mongo/db/storage/biggie/store_test.cpp b/src/mongo/db/storage/biggie/store_test.cpp
index a61c1fe978f..5dc07e35df3 100644
--- a/src/mongo/db/storage/biggie/store_test.cpp
+++ b/src/mongo/db/storage/biggie/store_test.cpp
@@ -1649,6 +1649,73 @@ TEST_F(RadixStoreTest, MergeBaseKeyNegativeCharTest) {
     ASSERT_EQ(thisStore.find("aac")->second, "c");
 }
 
+TEST_F(RadixStoreTest, MergeWillRemoveEmptyInternalLeaf) {
+    baseStore.insert({"aa", "a"});
+    baseStore.insert({"ab", "b"});
+    baseStore.insert({"ac", "c"});
+    baseStore.insert({"ad", "d"});
+
+    otherStore = baseStore;
+    otherStore.erase("ac");
+    otherStore.erase("ad");
+
+    thisStore = baseStore;
+    thisStore.erase("aa");
+    thisStore.erase("ab");
+
+    thisStore.merge3(baseStore, otherStore);
+
+    // The store is in a valid state that is traversable and we should find no nodes
+    ASSERT_EQ(std::distance(thisStore.begin(), thisStore.end()), 0);
+}
+
+TEST_F(RadixStoreTest, MergeWillRemoveEmptyInternalLeafWithUnrelatedBranch) {
+    baseStore.insert({"aa", "a"});
+    baseStore.insert({"ab", "b"});
+    baseStore.insert({"ac", "c"});
+    baseStore.insert({"ad", "d"});
+    baseStore.insert({"b", "b"});
+
+    otherStore = baseStore;
+    otherStore.erase("ac");
+    otherStore.erase("ad");
+    otherStore.erase("b");
+
+    thisStore = baseStore;
+    thisStore.erase("aa");
+    thisStore.erase("ab");
+
+    thisStore.merge3(baseStore, otherStore);
+
+    // The store is in a valid state that is traversable and we should find no nodes
+    ASSERT_EQ(std::distance(thisStore.begin(), thisStore.end()), 0);
+}
+
+TEST_F(RadixStoreTest, MergeWillCompressNodes) {
+    baseStore.insert({"aa", "a"});
+    baseStore.insert({"ab", "b"});
+    baseStore.insert({"ac", "c"});
+    baseStore.insert({"ad", "d"});
+
+    otherStore = baseStore;
+    otherStore.erase("ab");
+    otherStore.erase("ac");
+
+    thisStore = baseStore;
+    thisStore.erase("aa");
+
+    thisStore.merge3(baseStore, otherStore);
+
+    // The store is in a valid state that is traversable and we should find a single node
+    ASSERT_EQ(thisStore.find("ad")->second, "d");
+    ASSERT_EQ(std::distance(thisStore.begin(), thisStore.end()), 1);
+
+    // Removing this node should not result in an internal leaf node without data
+    thisStore.erase("ad");
+
+    ASSERT_EQ(std::distance(thisStore.begin(), thisStore.end()), 0);
+}
+
 TEST_F(RadixStoreTest, MergeConflictingModifications) {
     value_type value1 = std::make_pair("foo", "1");
     value_type value2 = std::make_pair("foo", "2");