BTree-based baselines for IRS and Range queries

2 files changed, 34 insertions, 3 deletions

diff --git a/benchmarks/include/bench.h b/benchmarks/include/bench.h
index e0f4c1d..28c1e97 100644
--- a/benchmarks/include/bench.h
+++ b/benchmarks/include/bench.h
@@ -49,7 +49,11 @@ static bool insert_tput_bench(DE &de_index, std::fstream &file, size_t insert_cn
         for (size_t i=0; i<insert_vec.size(); i++) {
             // process a delete if necessary
             if (applied_deletes < delete_cnt && delete_idx < delete_vec.size() && gsl_rng_uniform(g_rng) < delete_prop) {
-                de_index.erase(delete_vec[delete_idx++]);
+                if constexpr (std::is_same_v<TreeMap, DE>) {
+                    de_index.erase_one(delete_vec[delete_idx++].key);
+                } else {
+                    de_index.erase(delete_vec[delete_idx++]);
+                }
                 applied_deletes++;
             }
 
diff --git a/benchmarks/include/bench_utility.h b/benchmarks/include/bench_utility.h
index a5f5e0b..cc926a3 100644
--- a/benchmarks/include/bench_utility.h
+++ b/benchmarks/include/bench_utility.h
@@ -14,6 +14,7 @@
 #include "shard/PGM.h"
 #include "shard/TrieSpline.h"
 #include "shard/WIRS.h"
+#include "ds/BTree.h"
 
 #include <cstdlib>
 #include <cstdio>
@@ -42,6 +43,28 @@ typedef de::DynamicExtension<Rec, de::PGM<Rec>, de::PGMRangeQuery<Rec>> Extended
 typedef de::DynamicExtension<Rec, de::MemISAM<Rec>, de::IRSQuery<Rec>> ExtendedISAM_IRS;
 typedef de::DynamicExtension<Rec, de::MemISAM<Rec>, de::ISAMRangeQuery<Rec>> ExtendedISAM_RQ;
 
+struct btree_record {
+    key_type key;
+    value_type value;
+
+   inline bool operator<(const btree_record& other) const {
+        return key < other.key || (key == other.key && value < other.value);
+    }
+
+    inline bool operator==(const btree_record& other) const {
+        return key == other.key && value == other.value;
+    }
+};
+
+struct btree_key_extract {
+    static const key_type &get(const btree_record &v) {
+        return v.key;
+    }
+};
+
+typedef tlx::BTree<key_type, btree_record, btree_key_extract> TreeMap;
+
+
 static gsl_rng *g_rng;
 static std::set<WRec> *g_to_delete;
 static bool g_osm_data;
@@ -246,7 +269,7 @@ static bool warmup(std::fstream &file, DE &extended_index, size_t count,
 
     size_t inserted = 0;
     size_t delete_idx = 0;
-    
+
     double last_percent = 0;
     while (inserted < count) {
         // Build vector of records to insert and potentially delete
@@ -259,7 +282,11 @@ static bool warmup(std::fstream &file, DE &extended_index, size_t count,
         for (size_t i=0; i<insert_vec.size(); i++) {
             // process a delete if necessary
             if (delete_idx < delete_vec.size() && gsl_rng_uniform(g_rng) < delete_prop) {
-                extended_index.erase(delete_vec[delete_idx++]);
+                if constexpr (std::is_same_v<TreeMap, DE>) {
+                    extended_index.erase_one(delete_vec[delete_idx++].key);
+                } else {
+                    extended_index.erase(delete_vec[delete_idx++]);
+                }
             }
 
             // insert the record;