ToB企服应用市场:ToB评测及商务社交产业平台

标题: 学习型索引结构--ALEX: An Updatable Adaptive Learned Index 论文代码复现 [打印本页]

作者: 万有斥力 时间: 2024-11-12 07:50
标题: 学习型索引结构--ALEX: An Updatable Adaptive Learned Index 论文代码复现
ALEX（An Updatable Adaptive Learned Index）:一种可更新的自适应学习索引

ALEX的根本结构

基于B+树和RMI结构改进，每个结点上有一个线性回归模型和一部分连续存储空间（数组）
非叶节点（内部结点）的数组存储叶节点的指针。
叶结点（数据结点）有两个数组，一个用来存储关键字，另一个生存关键字对应的其他信息。此中关键字数据利用Gapped Array（GA）要保存一些间隔，用来提高数据动态更新时的性能。
结点上的模型用来拟合数组中的数据分布，从而预测输入的Key的位置
每个结点能够在数据更新时根据环境动态的分裂和合并。

ALEX的工作原理

查询

根节点开始，我们迭代地利用该模型来“计算”指针数组中的一个位置，并且我们跟随指针到下一级的子节点，直到我们到达一个数据节点
通过构造，内部节点的模型具有完美的精确性，不存在偏差。我们利用数据节点中的模型来预测搜刮关键字在数组中的位置，如果预测有误则从预测位置开始举行指数搜刮。

插入

对于数据插入，找到插入位置的方式同查询一样
当被插入的数据结点的关键字数组非满时，为了找到新元素的插入位置，利用数据节点中的模型来预测插入位置。如果预测的位置不精确(在此位置插入会破坏关键字的大小排序)，则举行指数搜刮以找到精确的插入位置。如果预测位置是一个间隙，则举行插入。
如果预测位置不是间隙，则将附近元素向迩来的间隙方向移动一个位置，在插入位置形成一个间隙。然后，我们将元素插入到新创建的间隙中。插入关键字后将关键字对应的其他数据放入工作负载空间中。
当被插入的数据结点的空间已满时，必要对结点举行扩展大概分裂两种操作。通过一个代价函数来评估两种操作的代价，选择代价较小的操作。将其转化为在非满结点中插入的环境。

删除/更新/其他操作

查找要删除的关键字的位置，然后删除它及其附加数据。如果一个数据节点中空余间隙太多，应当收缩该数据节点(与扩展数据节点相反)，以制止低空间利用率。
关键字的更新可通过通过组合插入和删除操作来实现的。

相干配置及代码复现

1、下载

这里我直接解压到了C盘，文件路径后面会用到
GitHub - microsoft/ALEX: A library for building an in-memory, Adaptive Learned indEX
2、cmake安装

由于我之前没有安装和配置cmake，于是现下现配。具体的下载安装可以自行搜刮，安装成功之后“win+R”后，表现如图即为安装成功。

3、打开cmd构建项目

win+R打开cmd,cd到项目所在的文件夹，然后运行下面的下令。

mkdir build//在项目文件中创建一个文件夹，用来build工程文件
cd build
cmake ..//执行项目文件夹里面CMakeLists.txt所在的目录

复制代码

这里项目名为ALEX-master，CMakeLists.txt所在的目次地址为："C:\ALEX-master\ALEX-master\CMakeLists.txt"。
输入完以上下令后，CMake工具就会在背后构建这个项目，构建完成后，我们打开build文件夹。注意，不同构建工具天生的文件不同。

执行后的结果：

这样就是成果构建啦，然后我们在项目文件里打开build文件夹。

4、打开VS-运行项目

我们打开.sln这个后缀名的文件，.sln也就是VS中创建的解决方案的后缀名。

上图是我已经配置好的项目的样子，正常进入后，我们要举行一个操作：选中example，右键点击，设置为启动项目（要不然VS会不知道启动哪一个项目），然后编译运行项目。
5、运行结果

由于我的课设必要利用学习索引实现范围查找，所以我修改了项目的main文件，实现了“出版时间”和“评论数目”的索引，利用范围查询筛选出出版时间在2000年至2020年、评论数目大于50000的书籍，并且按照评分排序，输出前十。以下是成功运行的结果：

总结

好啦，本篇文章到这里就结束啦。重要是纪录我从github上运行代码的过程，以后这个技能我应该会经常用到。迩来喜欢上了通过博客纪录自己近期所做的事情，渴望通过这种方式纪录下来自己发展的过程，加油！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)