ALEX:ML-增强的范围索引,功能类似于B+树

2020-06-25 15:06:18

Alex是ML增强的范围索引,在功能上类似于B+树。我们的实现几乎是std::map或std::multimmap的临时替代品。您可以在我们的SIGMOD 2020文章中了解有关Alex的更多信息。

Alex可以用作头文件。所有相关的头文件都在src/core中。你需要至少用C++14标准编译你的程序(例如,-std=c++14)。

一个简单的基准测试,用于测量Alex上运行点查找和插入的吞吐量(下面将详细说明)。

在Windows上,只需将此存储库作为CMake项目加载到Visual Studio中即可。在Linux/Mac上,使用以下命令:

#使用CMake构建,这将创建一个新的构建目录。/build.sh#运行示例程序。/build/example#运行单元测试。/build/test_alex。

但是,要观察Alex的真实性能,我们必须在更大的数据集上运行。您可以从Google Drive下载200M密钥(1.6 GB)的数据集。要在此数据集上运行一个工作负载示例:

您还可以在您自己的数据集上运行此基准测试。您的键需要为二进制格式或文本格式(每行一个键)。如果键的数据类型不是DOUBLE,则需要在src/Benchmark/main.cpp中将#DEFINE KEY_TYPE DOUBLE修改为#DEFINE KEY_TYPE[您的数据类型]。

与B+树一样,ALEX是一种索引排序数据的数据结构,并支持混合了点查找、短范围查询、插入、更新和删除的工作负载。在内部,ALEX使用分层组织成树的线性回归集合来模拟键的分布。ALEX使用此模型按键高效地搜索数据记录。ALEX还自动调整其内部模型和树结构,以有效地支持写入。

Alex的灵感来自于Kraska等人的原始学习索引。然而,该工作只支持读取(即,点查找和范围查询),而Alex还有效地支持写入(即,插入、更新和删除)。

在只读工作负载上,Alex超过了Kraska等人最初学习到的索引。性能提高高达2.2倍,索引大小最多减小15倍。

在各种读写工作负载中,Alex最多可将B+树(由STX B+Tree实施)的性能提高4.1倍,同时将索引大小降低2000倍。

Alex目前在内存、单线程和数字键上操作,我们正在考虑如何向Alex添加对持久性、并发性和字符串键的支持。

Alex的前提是使用一组线性回归对密钥分布进行建模,因此,当密钥分布很难用线性回归建模时,即密钥分布在小范围内高度非线性时,Alex的性能较差,未来可能的研究方向是使用更广泛的建模技术(例如,也考虑多项式回归模型)。

Alex在存在极端异常值的情况下性能可能很差,这可能会导致键域和Alex的树深度变得不必要地大(请参阅本文的第5.1节)。未来可能的研究方向是添加特殊的逻辑来处理极端异常值,或者采用对稀疏密钥空间具有健壮性的建模策略。

Alex是同时支持AlexMap和AlexMultimap的内部实现。它提供了稍微多一点的功能。

键和有效负载(即映射的类型)是分开存储的,因此取消引用迭代器将返回键/有效负载对的副本,而不是引用。我们的迭代器具有直接分别返回对键或有效负载的引用的方法。

目前我们只支持数字键类型,不支持任意的自定义键类型,所以不能更改类模板中的默认比较函数。

这个项目欢迎大家提供意见和建议。大多数投稿需要您同意贡献者许可协议(CLA),声明您有权并且实际上确实授予我们使用您的投稿的权利。欲了解详情,请访问https://cla.opensource.microsoft.com.。

当您提交Pull请求时,CLA机器人将自动确定您是否需要提供CLA并适当地装饰PR(例如,状态检查、评论)。只需按照机器人提供的说明操作即可。使用我们的CLA,您只需在所有报告中执行此操作一次。

此项目已采用Microsoft开放源代码准则。有关更多信息,请参阅行为准则常见问题解答,或联系[email protected]提出任何其他问题或意见。