基于动态精确拟合的学习索引构建算法

Learned Index Construction Algorithm Based on Dynamic Precise Fitting

摘要

学习索引具有检索延迟低、存储占用少等突出优点，能有效提升数据读写效率（吞吐量）。然而，现有的学习索引大多采用简单的拟合算法，对动态变化的数据分布缺乏适应性，存在拟合效果差、查询不精确等问题。为解决这些问题，提出了一种基于动态精确拟合的学习索引构建算法（Dynamic Precise Fitting Learned Index， DPFLI），通过三项措施构建高效的索引结构：1） 利用数据差分感知数据分布情况，通过插入适量的空隙节点获得更好的拟合精度，并方便后继的插入操作；2） 将索引内部节点分为正式节点和缓冲区节点，在保证查询效率的情况下有效降低树形索引结构的高度；3） 使用高效的布隆过滤器来快速过滤无效查询请求。实验结果表明，与传统的索引结构（如B+树）和典型的学习索引（如LI、ALEX和LIPP）相比，在多种数据集和负载上，DPFLI在读写效率方面具有显著优势。

Abstract

Learning indexes have prominent advantages such as low retrieval latency and small storage footprint, which can effectively enhance data read and write efficiency (throughput). However, existing learned indexes typically rely on oversimplified fitting algorithms that struggle with evolving data patterns, resulting in inadequate fitting accuracy and imprecise queries. To address these issues, this paper introduces the Dynamic Precise Fitting Learned Index (DPFLI), which builds an efficient index structure through three core strategies: 1) utilizing data differentials to detect distribution shifts and inserting empty nodes at strategic locations to enhance fitting precision and facilitate subsequent insertions; 2) differentiating internal index nodes into formal and buffer nodes, thereby reducing the height of the index tree while maintaining query efficiency; 3) employing an optimized Bloom filter to efficiently exclude invalid query requests. Experimental results show that DPFLI achieves significant improvements in read and write efficiency compared to traditional index structures (e.g., B+ trees) and representative learned indexes (e.g., LI, ALEX, and LIPP) across various datasets and workloads.

Graphical abstract

0　 引 言

索引作为支撑数据库高效读取数据的重要技术之一，在海量数据时代显得愈发重要。目前，数据库领域广泛采用以树形结构为主的索引（如B+树^[1]），通过将数据按一定规则组织成多叉树以提升查询效率。然而，随着数据量的爆发式增长，传统树形结构索引暴露出平均搜索长度较大、占用内存过多的缺陷，需要进一步提升其查询性能。

在此背景下，人工智能技术的迅猛发展为索引技术的革新带来了新机遇。Kraska等^[2]提出了“学习索引”的概念，通过将机器学习方法引入索引构建过程，有效降低了平均搜索长度和内存占用，提升了查询速度。然而，学习索引的构建面临数据拟合和模型选择等多个方面的挑战。现有学习索引中的拟合函数往往不准确，导致查询时模型映射地址与真实位置存在较大误差^[3]。在模型选择方面，通常采用神经网络算法和线性或非线性机器学习算法；Amato等^[4]发现，神经网络算法复杂性高、训练时间长且难以利用GPU加速，不适合需要高吞吐量的索引应用场景；非线性机器学习算法相比于线性机器学习算法而言，拟合能力较强，但拟合时间更长、计算量更大且误差相对不可控，难以满足快速、精确查询的要求^[5]。另外，以往的索引结构未考虑无效查询对性能的影响（如查询一个不存在于索引中的数据键时，需要递归访问到最深层的叶子节点才能判断其不存在，这会大大降低索引的吞吐效率）。随着数据插入，数据分布逐渐变化，节点上的原模型不满足新数据要求，需要定期对存储节点进行模型重训练，重训练的时机和方式也是决定索引整体性能的关键因素之一。

为了解决上述问题，本文提出了基于动态精确拟合的学习索引构建算法(Dynamic Precise Fitting Learned Index, DPFLI)，采用精确查找的树形结构构建方式，自上而下进行索引构建。主要贡献如下：

1) 提出了一种基于数据点差分均值的拟合算法。该算法能够更好地感知数据的分布情况，通过优化数据键的位置，使数据点分布更加接近线性，从而将更多的数据键放置在层次更高的节点上，减少叶子节点的数量，提升索引的性能。

2) 提出将索引节点分为缓冲区节点和正式节点。充分利用两种节点在不同场景下的优势，使用缓冲区节点紧密存储少量数据节约存储空间，正式节点使用模型提升查询效率。

3) DPFLI考虑了无效查询对性能的影响。通过划分请求过滤模块和数据存储模块，结合高效的布隆过滤器^[6]来快速过滤无效查询请求，从而有效提升索引结构的查询吞吐量。

1　 相关研究

学习索引通过学习数据集的数据分布特征，训练出一个模型函数。当查询某个特定的数据键时，模型函数可以返回该值的存储位置。为了解决预测过程中的精度问题，他们采用递归模型索引（Recursive Model Index，RMI）建立了一个模型的层次结构，每个层次可以选择不同的模型来更好地拟合数据分布。在查询过程中，上层模型根据预测结果选择下层的模型，由于模型预测存在不精准的问题，还需要在最底层使用一定范围内的二分搜索来进行查找。与B+树相比，学习索引在中间节点只需要存储模型函数的参数，所需的索引空间大幅减少；同时，由于每个节点可以容纳更多的数据元素，因此在相同数据量的情况下，学习索引的结构更加扁平，从而加快了查询过程。

RMI只能依靠已有的数据构建索引，不支持索引的更新。Ferragina等^[7]提出的PGM（Piecewise Geometrice Model Index）实现了对索引更新操作的支持。PGM使用PLA（Piecewise Linear Approximation）模型拟合数据分布，根据分布将数据键划分为不同的子集。PGM从底部开始构建模型的层次结构，其查询过程与RMI基本相同。在数据插入的实现上，PGM借鉴了LSM-tree（Log-Structured Merge tree）的思想。当进行数据插入时，需要找到一系列非空集合，将它们合并成一个更大的子集，然后在该大子集上构建新的PGM索引。然而，相关实验结果^[8]表明，由于在查询过程中需要遍历多个大小不同的节点，因此PGM在某些情况下的查询效率要低于RMI。

为提高插入操作的效率，Ding等^[3]提出了自适应学习型索引（Adaptive Learned index， ALEX）。ALEX将数据分散到多个不同的分区，并采用线性回归模型对每个分区进行独立的训练，但模型预测仍然存在不精确的问题。ALEX的叶子节点使用GA（Gapped Array）存储键，相邻的键之间填充空隙。当有新的键插入时，ALEX使用模型预测插入位置，如果位置是一个空隙，则直接插入；否则，它使用指数搜索来查找距离当前位置最近的空隙，并在该位置插入键。随着数据量的增加，空隙会被逐渐填满，这时需要进行大量的键移动。在极端情况下，这种移动将会耗费大量的时间。此外，由于PGM和ALEX都使用自下而上的构建方式，仍然存在模型预测不精准的问题，因此索引叶子节点需要使用二分搜索来进行额外查找，这个过程又被称为“最后一英里”^[9]问题，会造成整体吞吐量的下降。

Wu等^[8]提出的LIPP（Updatable Learned Index with Precise Positions）解决了以往学习索引中模型预测不精准的问题。LIPP采用了非平衡的树形结构，每个节点都使用单独的线性回归模型。LIPP将节点中的元素划分为三种类型：DATA（存储数据项）、NULL（空隙项）和NODE（指向下一层孩子节点的指针）。插入数据时，使用当前节点的模型进行预测，并根据预测结果作相应的处理。然而，由于每次发生预测冲突都会创建下一层的节点，随着数据量和冲突次数的增加，LIPP的索引高度也会逐渐增大，极端情况下会形成类似链表的结构。这会导致查询和插入的效率逐渐降低。尽管该文中提出使用索引重建的方式来降低影响，但大量冲突导致的频繁子树重建仍会使得索引整体吞吐量下降。另外，LIPP采用了其提出的FMCD（Fastest Minimum Confilict Degree）线性拟合算法进行索引重建，但此算法的冲突度与新节点和原节点的容量放大倍数紧密相关。为了降低冲突度，LIPP采用了6倍的放大系数。但是，放大系数是根据经验决定的，对数据分布的适应性差，可能导致索引内部产生大量空隙项，从而浪费大量的空间。此外，与其他的学习索引一样，LIPP同样没有考虑无效查询所带来的影响，查询索引中不存在的数据键会导致平均吞吐量的大幅度降低。

2　 算法设计

本文提出了一种基于动态精确拟合的学习索引构建算法DPFLI，如图1所示。DPFLI由两部分组成：请求过滤模块和数据存储模块。请求过滤模块由布隆过滤器实现，能够快速判断某一元素是否存在，且写入和查询的时间和空间复杂度都在常数范围，提升了极端情况下的索引吞吐率。数据存储模块采用树形结构，包含两种类型的节点：缓冲区节点（BN）和正式节点（FN）。缓冲区节点用于临时存放少量数据，内部采用紧密排列的方式，使用数组或链表形式存储数据项，通过二分搜索进行查询。这种设计有助于防止数据冲突导致的树高快速增长，从而提升读写吞吐量。正式节点用于存放拟合后的数据元素，采用数组形式存储数据项、指针项和空隙项。其中，数据项用于存储数据键和对应的数据值；指针项仅指向子节点，不存储数据；空隙项表示节点在建立时预留的空隙，以减少后续插入时冲突的概率。

当缓冲区节点键数量超过阈值时，会被调整为正式节点。正式节点内的元素分为指针项（指向下一层节点）、数据项（存储数据）以及空隙项（暂时空置），对于非空隙项的元素使用额外的比特数组区分元素类型（0表示数据项，1表示指针项），同时正式节点还需要保存模型参数用以预测位置。本文的索引结构自上而下构建，确保节点内模型对数据键位置的预测准确。此外，树形结构会随内部数据变化动态调整，实现更高的吞吐效率。

DPFLI能够同时支持数据插入和查询操作。当数据插入索引后，DPFLI使用数据拟合算法进行模型训练，并在适当时机进行局部重训练和局部索引重建，从而保障高效的数据查询过程。

2.1　数据插入

DPFLI能够支持数据插入。如算法1所示，新数据进入时，从根节点开始逐级访问。若节点类型为缓冲区节点，新数据将按序写入节点内（3~6行）；若节点类型为正式节点，根据节点模型计算新数据的放置位置（7~21行）：若该位置为数据项，表明发生数据冲突，需新建一个缓冲区节点，并将新旧数据有序放入，同时更新该位置为指向缓冲区节点的指针（9~14行）；若该位置为空，则直接插入（15~18行）；若该位置为指针项，则进入下层节点插入（19~20行）。插入成功后，先根据冲突情况判断是否进行重训练（23行），然后将新数据键写入布隆过滤器，用于过滤查询请求（24行）。

本研究实现了一个节点内存池，以应对数据冲突频繁引发的节点创建和销毁操作。在初始化过程中，会预先在内存中创建一批节点。需要新节点时，优先从池中获取；需要销毁节点时，只清空节点内部数据，不释放内存，将其返回内存池中。

2.2　数据拟合

数据拟合可以描述为：对于一组有序数据键K=\{k_{\mathrm{1}},k_{\mathrm{2}},k_{\mathrm{3}},\dots ,k_n\}，拟合目标是将这些数据键置于长度为L的数组\mathrm{A}\mathrm{r}\mathrm{r}上(L>n)。数据键的位置集合P=\{\mathrm{p}\mathrm{o}{\mathrm{s}}_{\mathrm{1}},\mathrm{p}\mathrm{o}{\mathrm{s}}_{\mathrm{2}},\mathrm{p}\mathrm{o}{\mathrm{s}}_{\mathrm{3}},\dots ,\mathrm{p}\mathrm{o}{\mathrm{s}}_n\}，满足。需要找到最优的P和一个函数M，使得落在同一直线上的数据点(k_i,\mathrm{p}\mathrm{o}{\mathrm{s}}_i)最多，即满足\mathrm{p}\mathrm{o}{\mathrm{s}}_i=M(k_i)。当L>n时，经过地址映射后，将产生一些不存放数据的位置，称这些位置为“空隙项”。函数M必须是一个单调非递减函数，且M的次数越高，计算复杂度通常越高。因此，本文选择一次线性函数作为拟合函数。然而，在实际场景中，对于给定数据集很难找到完美的M。尽管LIPP提出了冲突度概念，但它只能描述单一位置上的键冲突数量。为了解决这个问题，本文提出了一种适用于学习索引的数据拟合评价指标T，用于评估学习索引场景下线性拟合模型的优劣程度，如(1)式所示。

T=\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{f}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{t}\_\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}+\mathrm{E}\mathrm{m}\mathrm{p}\mathrm{t}\mathrm{y}\_\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}

\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{f}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{t}\_\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}=\frac{\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{f}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{t}\_\mathrm{n}\mathrm{u}\mathrm{m}}{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}\_\mathrm{n}\mathrm{u}\mathrm{m}}

\mathrm{E}\mathrm{m}\mathrm{p}\mathrm{t}\mathrm{y}\_\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}=\frac{\mathrm{e}\mathrm{m}\mathrm{p}\mathrm{t}\mathrm{y}\_\mathrm{n}\mathrm{u}\mathrm{m}}{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}\_\mathrm{n}\mathrm{u}\mathrm{m}}(1)

式中，\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{f}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{t}\_\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}（冲突率）表示数据根据拟合模型的映射地址插入后出现冲突的情况，\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{f}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{t}\_\mathrm{n}\mathrm{u}\mathrm{m}表示发生冲突的次数，\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}\_\mathrm{n}\mathrm{u}\mathrm{m}表示数据集中的元素数量，\mathrm{E}\mathrm{m}\mathrm{p}\mathrm{t}\mathrm{y}\_\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}（空置率）则表示没有存放数据的地址数量，\mathrm{e}\mathrm{m}\mathrm{p}\mathrm{t}\mathrm{y}\_\mathrm{n}\mathrm{u}\mathrm{m}表示空隙项的个数。该指标强调，在评估模型时，不仅需要考量数据键的冲突率，同时也要关注存储空间的浪费情况。T越小，表示模型的冲突率和空间浪费率都越低，模型效果越好。

为了同时降低冲突率和空置率，本文提出了一种基于数据点差分均值的拟合算法，通过观测数据键的差分值来决定如何插入“空隙项”：差分值越接近，数据点越有可能拟合成一条直线，否则插入一定数量的“空隙项”来调整数据键的位置\mathrm{p}\mathrm{o}{\mathrm{s}}_i，改善数据点的整体分布情况，使数据点分布接近于一条直线（如图2）。

该拟合算法具体如算法2所示。首先对数据键进行分组（6~10行）：计算数据集的平均差分值Avg_Gap，再依次计算数据键偶对的差分值gap，根据其与Avg_Gap的大小关系将数据分为两组并使用堆结构进行存储，差分值gap大于Avg_Gap的数据点进入最小堆(minHeap)；差分值gap小于Avg_Gap的数据点进入最大堆(maxHeap)。

接下来进行“空隙项”插入（11~14行）：每次都选择最小堆中的差分最小偶对（该偶对的连线斜率略大于整体平均斜率），在该偶对之间插入一个空隙项（即将后一个数据点的映射地址向后移动一位），使该偶对之间的连线斜率变缓，这样的插入策略能够使更多的局部斜率接近平均斜率。在真实数据集中，可能存在某些数据点偶对的差分值远大于平均差分值，称之为“离群点”，如果在这样的偶对中插入空隙项，局部斜率仍然与整体平均斜率相差较远，会导致空隙项浪费。

然后，使用(2)式更新平均差分值（15~17行）：插入空隙项后数据集总体的平均差分值（new_avg_gap）等于最大数据键（max_key）与最小数据键（min_key）之差除以插入空隙后的地址空间长度（array_length）。

\mathrm{n}\mathrm{e}\mathrm{w}\_\mathrm{a}\mathrm{v}\mathrm{g}\_\mathrm{g}\mathrm{a}\mathrm{p}=

\frac{(k_{\mathrm{2}}-k_{\mathrm{1}})+(k_{\mathrm{3}}-k_{\mathrm{2}})+\dots +(k_n-k_{n-\mathrm{1}})}{n}=

\frac{k_n-k_{\mathrm{1}}}{n}=\frac{\mathrm{m}\mathrm{a}\mathrm{x}\_\mathrm{k}\mathrm{e}\mathrm{y}-\mathrm{m}\mathrm{i}\mathrm{n}\_\mathrm{k}\mathrm{e}\mathrm{y}}{\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{a}\mathrm{y}\_\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}}(2)

继续选择偶对并持续上述“插入空隙项”和“更新平均差分值”过程，直到所有的空隙项都被插入。然后，移除数据集中差分值最小的ρ个数据点（ρ为系统参数），以避免数据集中差分值过小的“离群点”的影响（18行）。

最后，基于改善分布后的数据集进行最小二乘法拟合（19行），其原理是使预测值与实际值之间的误差平方和最小。对于n个数据点：(k_{\mathrm{1}},\mathrm{p}\mathrm{o}{\mathrm{s}}_{\mathrm{1}}),(k_{\mathrm{2}},\mathrm{p}\mathrm{o}{\mathrm{s}}_{\mathrm{2}}),\dots ,(k_n,\mathrm{p}\mathrm{o}{\mathrm{s}}_n)，找到线性函数y=ax+b拟合这些数据点（a和b分别表示斜率和截距）。定义目标函数E(a,b)={{\displaystyle \sum _{i=\mathrm{1}}^n}\left(\mathrm{p}\mathrm{o}{\mathrm{s}}_i-\left(a{k}_i+b\right)\right)}^{\mathrm{2}}。接着分别对a和b求偏导数得到线性方程组如(3)式所示：

\left\{\begin{array}{l}\frac{\partial E(a,b)}{\partial a}={\displaystyle \sum _{i=\mathrm{1}}^n}\mathrm{2}(\mathrm{p}\mathrm{o}{\mathrm{s}}_i-a{k}_i-b)(-k_i)=\mathrm{0}\\ \frac{\partial E(a,b)}{\partial b}={\displaystyle \sum _{i=\mathrm{1}}^n}\mathrm{2}(\mathrm{p}\mathrm{o}{\mathrm{s}}_i-a{k}_i-b)(-\mathrm{1})=\mathrm{0}\end{array}\right.(3)

根据(3)式得到最小二乘法的解析式，如(4)式所示：

\left\{\begin{array}{l}a=\frac{{\displaystyle \sum _{i=\mathrm{1}}^n}(k_i-\overline{k})(\mathrm{p}\mathrm{o}{\mathrm{s}}_i-\overline{\mathrm{p}\mathrm{o}\mathrm{s}})}{{\displaystyle \sum _{i=\mathrm{1}}^n}(k_i{-\overline{k})}^{\mathrm{2}}}\\ b=\overline{\mathrm{p}\mathrm{o}\mathrm{s}}-a\overline{k}\end{array}\right.(4)

通过以上公式，即可以计算出该数据集对应的模型参数。

2.3　模型重训练

随着数据插入，节点内模型可能逐渐失效，数据冲突增加，此时需要进行模型重训练和节点重建。本文的索引结构在以下两种情况下进行模型重训练：

1） 当前节点类型为缓冲区节点，且节点内元素数超过预定阈值\alpha；

2） 当前节点类型为正式节点，但节点内部已发生冲突次数node.conflict_num，满足(5)式的条件。

\frac{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}.\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{f}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{t}\_\mathrm{n}\mathrm{u}\mathrm{m}}{\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}.\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}\_\mathrm{n}\mathrm{u}\mathrm{m}-\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}.\mathrm{b}\mathrm{u}\mathrm{i}\mathrm{l}\mathrm{d}\_\mathrm{n}\mathrm{u}\mathrm{m}}>\beta(5)

式中，\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}.\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}\_\mathrm{n}\mathrm{u}\mathrm{m}表示节点及其子树的元素总数，\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}.\mathrm{b}\mathrm{u}\mathrm{i}\mathrm{l}\mathrm{d}\_\mathrm{n}\mathrm{u}\mathrm{m}表示节点在建立时的初始元素数量，\beta为预设冲突率阈值。

重训练过程中，首先遍历并收集当前节点及其子节点上的所有数据键值，使用2.2中拟合算法计算得到新模型，并将这些节点插入到一个长度大于原节点长度N的新节点上，然后将原节点的指针指向新节点。由于新模型能更好地拟合数据集，大部分元素会被放入新节点，只有少部分数据进入其子树，从而提升查询和插入效率。

重训练和树重建是索引插入过程中最耗时的部分。通过对算法2中各步骤的时间复杂度分析可知，DPFLI模型拟合算法的时间复杂度为O(n\mathrm{l}\mathrm{o}\mathrm{g}n+\mathrm{n}\_\mathrm{g}\mathrm{a}\mathrm{p})，其中n表示待拟合元素数量，\mathrm{n}\_\mathrm{g}\mathrm{a}\mathrm{p}表示插入空隙项的数量。为了降低重训练和树重建对整体性能的影响，DPFLI采取了两种关键设计：一是引入缓冲区节点，在数据量较少时使用紧密排列的数组代替子树结构，避免了子树高度增长过快和频繁冲突导致的重训练，从而大幅降低树重建和模型训练的频率；二是设计了自底向上的重训练机制，即从叶子节点开始遍历正式节点，仅在必要时进行树重建和模型重训练，最大限度地减少了模型重训练的范围，显著降低了性能开销。

2.4　数据查询

数据查询作为索引的核心功能之一，旨在根据输入的数据键，快速找到其所在位置并返回相应的数据值。DPFLI的查询过程如算法3所示。

首先，将数据键输入请求过滤组件BL。若BL返回False，表明数据键不存在于当前索引中，查询过程立即终止，避免无效请求导致查询吞吐量的降低。若BL返回True，则进入存储模块进行数据查询。

查询过程从索引根节点开始，执行以下操作：

1） 若节点为BN，在节点内部使用二分搜索查找数据键，获取对应数据值（3~6行）。

2） 若当前节点为FN，先使用FN中的模型计算数据键在节点中的位置，然后访问该位置上的元素。若该位置为数据项，直接返回对应数据值；若该位置为指针项，进入指针指向的下层元素继续查询；若该位置为空隙项，表明键不存在于索引结构中，查询结束（7~14行）。

由于索引在构建过程中采用自上而下的方式，可以保证模型输出位置的准确性。在获取数据键位置后，无需向两侧进行进一步查找，从而避免了学习索引中的“最后一英里”问题。

3　 实验结果与分析

3.1　实验设置

数据集 在本研究中，使用了以下4种主流的学习索引评价数据集来测试索引结构的性能：1） Longitudes(LTD)真实数据集^[10]，包含OpenStreetMap地图中的真实世界地理经度数据，其分布是杂乱非线性的；2） Longlat (LLT)真实数据集^[10]，包含OpenStreetMap地图中的真实世界地理经纬度数据，分布是杂乱非线性的；3） Lognormal人工数据集，含有1.9亿个遵循对数正态分布的唯一值数据；4） YCSB人工数据集^[11]，由YCSB基准生成的ID数据集，包含2亿个均匀分布的Int64类型数据。除非特别说明，这些数据集都不包含重复元素，本文通过打乱这些数据集的分布来模拟真实场景下的数据读写。

对比基准 本文将DPFLI与当前先进的索引结构进行对比，包括：1） STX^[12]实现的B+树，这是目前基于内存实现的性能最优版本，扇出值设置为128，因为在这种配置下读写性能最优；2） ALEX，一种基于内存的可更新学习索引，使用间隔数组（Gapped Array）和指数搜索来实现高效插入和读取；3） Learned Index（LI），由两层递归模型构成的学习索引，每层模型都使用线性函数拟合，仅支持只读场景；4） LIPP，一种基于精确查找的学习索引，每层使用不同的线性函数进行拟合。

工作负载 为了全面比较DPFLI与其他索引的性能差异，本文设计了多种工作负载情况：1） 只读负载，使用随机选择的1亿个数据键构建索引结构，并执行只读查询操作；2） 读写均衡负载，插入和查询操作数量各占50%，插入的元素不含重复数据键，查询的数据键完全随机；3） 只写负载，使用随机选择的1亿个数据键，从零开始执行数据插入操作。对于不同的索引和不同的工作负载，分别执行了1亿次的操作，重复5次以计算平均吞吐量。

实验环境 实验在Ubuntu 18.04操作系统上进行，硬件配置为2.6 GHz的英特尔8核i7处理器，内存32 GB，实验使用单线程。

参数设置 在本文的实验中，系统参数设置如下：1） 参数\rho表示在模型训练时被判定为噪声的元素个数，设置为\mathrm{M}\mathrm{i}\mathrm{n}(\frac{n}{\mathrm{100}},\mathrm{64})，其中n表示数据集中的元素个数。这种设置能够有效避免移除过多元素，从而防止模型精度下降，并且在实验中取得了最佳效果。2） 参数\alpha表示缓冲区节点的最大容量，设置为64。主要基于以下考虑：若阈值过低，会频繁触发缓冲区节点向正式节点的转化，增加模型训练次数，进而影响系统性能；若阈值过高，则缓冲区节点内的二分查找效率将低于模型计算的查找效率。实验验证表明，设置该阈值能够在最大程度上发挥缓冲区节点的性能及内存优势。3） 正式节点模型重训练的预设冲突率阈值β设置为4。其设置依据LIPP论文中的最佳配置，经验证可以实现最佳性能。

3.2　结果与分析

图3展示了在只读负载下，DPFLI与B+树、LI、ALEX和LIPP在四种数据集下的性能对比。显而易见，DPFLI在性能上显著优于B+树，吞吐量最高能达到B+树的10.40倍（YCSB数据集）。这主要归功于DPFLI更好地学习了数据的分布，其结构更加符合数据集的特征。相较于LI和ALEX，DPFLI的吞吐量最高能达到LI的17.38倍（LGN数据集），ALEX的3.02倍（YCSB数据集）。在复杂的数据集中，LI和ALEX的自下而上创建方式导致模型的映射地址与实际地址之间存在显著差异，难以实现精确拟合。因此，在查询操作中会出现冗余的顺序遍历，导致所谓的“最后一英里”问题。相比之下，DPFLI采用自上而下的构建方式，通过先拟合模型函数再插入数据，从而确保映射地址与实际地址完全一致，避免了上述问题。这使得DPFLI在所有测试数据集上的吞吐量远高于LI和ALEX。对比LIPP，DPFLI结构能够实现最大超过10%的性能提升（LLT数据集）。这一方面得益于请求过滤模块的有效过滤，减少了无效查询对吞吐量的干扰；另一方面得益于本文提出的拟合算法的优越性能，能够在节点构建时，将更多的数据元素保留在离根节点更近的层级，从而降低了索引的整体高度，提升了性能。

图4展示了在读写均衡负载下（插入操作占比50%）时，DPFLI与ALEX、B+树、LIPP的每秒吞吐量对比。由于LI并不支持插入操作，故未纳入此负载类型的对比。可以看出，当插入操作占比达到50%时，所有索引结构的吞吐量相比于只读负载都有所降低。这是因为在索引中，插入操作通常比较耗时，从而影响整体吞吐量。DPFLI相比于B+树和ALEX，吞吐量最高能达到B+树的5.52倍（YCSB数据集），ALEX的2.86倍（YCSB数据集）。这是因为在自上而下构建索引的过程中，存在一定的空隙项，能够在插入时避免频繁的节点分裂。相比于LIPP，DPFLI在数据集LTD和LLT上的吞吐量与LIPP相当或略优，这是因为在这两类数据集上，本文提出的拟合算法和LIPP的效果相似。然而在LGN和YCSB数据集上，DPFLI相较于LIPP吞吐量明显增大。这是因为本文采用的缓冲区节点能够避免子树的快速生长，同时由于拟合效果更好，使得索引的整体高度更小，从而实现更高的吞吐量。此外，从图3和图4对比DPFLI与DPFLI-NF的吞吐量可以看出：DPFLI的吞吐量优势主要来自其数据存储设计和算法拟合，而请求过滤模块对整体吞吐量的贡献相对较小，这是因为数据集中无效查询请求所占比例较低。然而，在实际应用中，仍需考虑无效查询对索引系统可能造成的潜在影响。

图5展示了在只写负载下，DPFLI与ALEX、B+树、LIPP的每秒吞吐量对比。相较于B+树和ALEX，DPFLI的吞吐量最大能达到B+树的4.85倍（YSCB数据集），ALEX的2.88倍（YCSB数据集），显示出在写入场景下的优越性能。与LIPP的对比中，DPFLI在LTD数据集上的性能略低于LIPP，但在其他数据集上，其性能均能与LIPP持平或略优。这是因为LTD数据集的复杂分布导致了模型在索引构建过程中需要频繁重训练。DPFLI的训练算法时间复杂度O(n\mathrm{l}\mathrm{o}\mathrm{g}n+\mathrm{n}\_\mathrm{g}\mathrm{a}\mathrm{p})略高于LIPP的算法复杂度O(n)，这在一定程度上减慢了写入的平均速度。需要特别说明的是，本文中的请求过滤模块是一个可选功能，专门用于读操作。在纯写入负载的场景中，布隆过滤器的额外写入会降低性能，因此禁用该模块以确保索引的高吞吐量。

图6展示了DPFLI与B+树、ALEX、LIPP在相同数据量情况下的空间开销对比。显然，学习索引相较于B+树具有更小的空间开销，这是因为学习索引的中间节点通常仅需要存储模型参数。DPFLI在空间开销上仅为B+树的47%左右。值得注意的是，ALEX索引结构的空间开销受数据集和数据分布影响较大，因此在多种数据集上的空间开销并不稳定。然而，DPFLI和LIPP的索引结构基本不受数据分布影响，在多数情况下能够保持较低的空间开销。相较于LIPP，DPFLI在各数据集上的空间开销平均降低了8.4%。这主要归因于DPFLI内部划分缓冲区节点和正式节点。正式节点的开销与LIPP类似，而缓冲区节点采用紧密排列的方式，无需额外的空隙项，且无需存储模型参数。同时，本文的拟合算法也为索引节省了大量冗余空间开销，从而使得整体开销更小。

4　 结 语

高效的索引结构是提升数据库性能的关键，因此设计适应海量数据的索引结构一直是数据库领域的重要课题。本文提出了一种基于动态精确拟合的学习索引构建算法DPFLI，能够在海量数据场景下实现高读写吞吐量。本文提出的新型模型拟合算法，利用数据点差分均值来感知数据的分布情况，从而提高数据的拟合效果，降低树形结构的高度以及索引的空间开销。通过划分缓冲区节点和正式节点，以及自上而下构建、精确查找的策略，提升了索引的吞吐量。通过设计请求过滤模块，有效避免无效查询对于平均吞吐量的影响。在未来的研究中，我们将进一步探索非线性拟合算法在学习索引中的应用，通过更精确的拟合算法，减少数据冲突概率，从而进一步提升索引结构的读写性能。

参考文献

[1] BAYER R， MCCREIGHT E. Organization and maintenance of large ordered indices［C］//Proceedings of the 1970 ACM SIGFIDET （now SIGMOD） Workshop on Data Description， Access and Control （SIGFIDET '70）. New York： ACM Press， 1970： 107-141. DOI： 10.1145/1734663.1734671 .

[2] KRASKA T， BEUTEL A， CHI E H， et al. The case for learned index structures［C］//Proceedings of the 2018 International Conference on Management of Data. New York： ACM， 2018： 489-504. DOI： 10.1145/3183713.3196909 .

[3] DING J L， MINHAS U F， YU J， et al. ALEX： An updatable adaptive learned index［C］//Proceedings of the 2020 ACM SIGMOD International Conference on Manage⁃ment of Data. New York： ACM， 2020： 969-984. DOI： 10.1145/3318464.3389711 .

[4] AMATO D， BOSCO G L， GIANCARLO R. On the Suitability of Neural Networks as Building Blocks for the Design of Efficient Learned Indexes［M］//Engineering Applications of Neural Networks. Cham： Springer International Publishing， 2022： 115-127. DOI： 10.1007/978-3-031-08223-8_10 .

[5] 蔡盼， 张少敏， 刘沛然， 等. 智能数据库学习型索引研究综述［J］. 计算机学报， 2023， 46（1）： 51-69. DOI： 10.11897/SP.J.1016.2023.00051 .

[6] CAI P， ZHANG S M， LIU P R， et al. An overview of learned index technologies for intelligent database［J］. Chinese Journal of Computers， 2023， 46（1）： 51-69. DOI： 10.11897/SP.J.1016.2023.00051（Ch ）.

[7] BLOOM B H. Space/time trade-offs in hash coding with allowable errors［J］. Communications of the ACM， 1970， 13（7）： 422-426. DOI： 10.1145/362686.362692 .

[8] FERRAGINA P， VINCIGUERRA G. The PGM-index： A fully-dynamic compressed learned index with provable worst-case bounds［J］. Proceedings of the VLDB Endowment， 2020， 13（8）： 1162-1175. DOI：10.14778/3389133.3389135 .

[9] WU J C， ZHANG Y， CHEN S M， et al. Updatable learned index with precise positions［J］. Proceedings of the VLDB Endowment， 2021， 14（8）： 1276-1288. DOI： 10.14778/3457390.3457393 .

[10] SPECTOR B， KIPF A， VAIDYA K， et al. Bounding the last mile： Efficient learned string indexing［EB/OL］. ［2021-11-29］. DOI: 10.1109/access.2023.3295434 .

[11] AWS. OpenStreetMap［EB/OL］. ［2024-04-16］.

[12] COOPER B F， SILBERSTEIN A， TAM E， et al. Benchmarking cloud serving systems with YCSB［C］//Proceedings of the 1st ACM Symposium on Cloud Computing. New York：ACM Press，2010：143-154.DOI： 10.1145/1807128.1807152 .

[13] TIMO B. STX B+ tree template classes［EB/OL］. ［2007-04-27］.