Alex：ML增强的范围索引

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

Alex可用作仅限标头的库。所有相关的标头文件都在src/core中。在此存储库中，我们包括三个您可以编译和运行的程序：

一个简单的基准测试，用于测量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]提出任何其他问题或意见。