sware

SWARE：排序感知索引

ICDE 2023 论文提交的源代码：“Indexing for Near Sorted Data”

关于

该存储库包含 B+tree 和 SWARE 实现的源代码。在当前版本的代码中，两种实现都是通用的，但测试这些索引数据结构的应用程序文件仅支持整数数据类型。此外，应用程序文件对每个条目的键和值使用相同的值。代码的未来扩展将支持更大的数据类型。

两种数据结构在运行代码时都需要缓冲池分配，如果需要完全在内存中运行，可以将其扩展到所需的数量。缓冲池分配以块数给出，其中每个块为 4KB。例如，如果您使用 1M 块的分配，那么您将为树数据结构分配 1M*4KB = 4GB 的内存。

SA B+ 树还需要执行程序时其内存缓冲区可以容纳的条目数，以及批量加载时要维护的填充因子。每个条目都是一个键值对。

如何跑

生成摄取工作负载

使用此存储库中的排序数据生成器：https://github.com/BU-DiSC/bods 生成摄取密钥（可以指定有效负载大小 = 0 以仅生成密钥）。如上所述，应用程序文件对每个条目（K，V 对）的键和值使用相同的值。记下生成的工作负载的路径。

B+树

1. 使用命令“make bplustree”进行编译
2. 使用以下格式运行可执行文件：

./ test_base_index < ingestion_workload_path > < output_file_name > < buffer_pool_allocation > < K > < L > < #. queries >

例如，您可以使用：

./ test_base_index createdata_1000000 - elems_100000 - K_100000 - L_1seed1632764083 . dat sample . txt 1000000 100000 100000 200000

在这里，我们摄取 1M 个条目/密钥的工作负载，其中 K=L=100,000。我们使用 1M 块的缓冲池缓存并执行 200,000 个点查询。摄取和点查询的输出延迟均写入“sample.txt”。

SA B+树

1. 使用命令“make satree”进行编译
2. 使用以下格式运行可执行文件：

./ test_satree < ingestion_workload_path > < output_file_name > < buffer_pool_allocation > < K > < L > < #. entries > < swareBuffer allocation > < fill factor % >  < #. queries >

例如，您可以使用：

/ test_satree createdata_1000000 - elems_10 - K_10 - L_1seed1632764083 . dat swaresample . txt 1000000 10 10 1000000 10000 95 200000

在这里，我们摄取 1M 个条目/密钥的工作负载，其中 K=L=100,000（总条目的 10%）。我们使用 1M 块的缓冲池缓存并执行 200,000 个点查询。摄取和点查询的输出延迟均写入“swaresample.txt”。内存缓冲区将容纳 10,000 个条目（1M 的 1%），并且我们保持 95% 的填充因子。