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所在的目录
输入完以上下令后，CMake工具就会在背后构建这个项目，构建完成后，我们打开build文件夹。注意，不同构建工具天生的文件不同。
执行后的结果：
这样就是成果构建啦，然后我们在项目文件里打开build文件夹。
4、打开VS-运行项目
我们打开.sln这个后缀名的文件，.sln也就是VS中创建的解决方案的后缀名。
上图是我已经配置好的项目的样子，正常进入后，我们要举行一个操作：选中example，右键点击，设置为启动项目（要不然VS会不知道启动哪一个项目），然后编译运行项目。
5、运行结果
由于我的课设必要利用学习索引实现范围查找，所以我修改了项目的main文件，实现了“出版时间”和“评论数目”的索引，利用范围查询筛选出出版时间在2000年至2020年、评论数目大于50000的书籍，并且按照评分排序，输出前十。以下是成功运行的结果：
总结
好啦，本篇文章到这里就结束啦。重要是纪录我从github上运行代码的过程，以后这个技能我应该会经常用到。迩来喜欢上了通过博客纪录自己近期所做的事情，渴望通过这种方式纪录下来自己发展的过程，加油！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
