本发明公开了一种支持高效写的自适应学习索引方法(Aaptive Learned Index Supporting Efficient Writes，EWALI)。EWALI方案基于高效的ShrinkingCone算法，能够根据数据分布进行动态数据分片，保证分片后每个数据片内的数据分布趋于线性。EWALI方案实现数据感知递归模型索引DARMI，能够根据数据分布的变化，自适应进行节点拆分、重训练等操作，动态地调整索引结构。为支持更高效的写操作，EWALI方案设计了采用单缓存设计来处理增量数据，将写操作异步化处理，通过后台线程进行数据合并。读操作按照增量缓存、DARMI的顺序查询记录。写操作直接往增量缓存中写入数据，通过后台线程完成数据的合并操作。
1.一种支持高效写的自适应学习索引方法，其特征在于，包括以下步骤：
(1)接收来自用户的请求，并判断该请求是单点查询请求、范围查询请求、还是写请求，如果是单点查询请求，则进入步骤(3)，如果是范围查询请求，则进入步骤(6)，如果是写请求，则进入步骤(2)；
(2)获取待插入的数据点，将该数据点插入预先建立的缓存的增量缓存中，并判断缓存的增量缓存中保存的数据点个数是否达到预设阈值，如果是则将增量缓存变成不可变增量缓存，重新生成一个增量缓存，并利用后台线程将不可变增量缓存中的数据点与预先建立的数据感知递归模型索引DARMI中的数据片进行批量合并，然后向用户发送写操作成功的通知，过程结束，否则向用户发送写操作成功的通知，过程结束；数据感知递归模型索引DARMI是通过以下子步骤建立得到的：(A1)获取数据集keys＝{(keya,posa),其中a＝1,2,…,n}，设置计数器i＝2，将第1个数据点(key1,pos1)设置为起点(keystart,posstart)，并设置高斜率SLhigh的初始值为∞，低斜率SLlow的初始值为0，其中n表示数据集中数据点的总数，keyi表示第i个数据点的键，posi表示第i个数据点在数据集keys中的位置；
(A2)判断i是否大于数据集中的数据点总数n，如果是则进入步骤(A7)，否则进入步骤(A3)；
(A3)对于第i个数据点，计算该数据点(keyi,posi)与起点(keystart,posstart)之间的斜率Li，并判断是否有Li∈[SLlow,SLhigh]，如果是则进入步骤(A4)；否则将数据点(keyi,posi)设置为新的起点(keystart,posstart)，将高斜率SLhigh的值设置为∞，将低斜率SLlow的值设置为0，并将i设置为第i个数据片分割点，然后进入步骤(A6)；
(A4)根据第i个数据点(keyi,posi)和预先设置的误差阈值生成两个新数据点(keyi,posi+error)、(keyi,posi‑error)，计算该新数据点(keyi,posi+error)与起点(keystart,posstart)的斜率Lpos+error，以及新数据点(keyi,posi‑error)与起点(keystart,posstart)的斜率Lpos‑error；
(A5)根据步骤(A4)得到的斜率Lpos+error更新高斜率SLhigh＝min(SLhigh,Lpos+error)，并根据步骤(A4)得到的斜率Lpos‑error更新低斜率SLlow＝max(SLlow,Lpos‑error)；
(A6)设置计数器i＝i+1，并返回步骤(A2)；
(A7)根据得到的所有数据片分割点将数据集划分为多个数据片；
(A9)判断计数器j是否大于步骤(A7)划分后得到的数据片总数Num，如果是则进入步骤(A12)，否则进入步骤(A10)；
(A10)从数据集中获取第j个数据片，根据该第j个数据片训练对应的线性回归模型，将该线性回归模型作为数据感知递归模型索引DARMI的第j个叶子节点，然后进入步骤(A11)；
(A11)设置计数器j＝j+1，并返回步骤(A9)；
(A12)根据得到的所有叶子节点所管理的数据片的数据范围训练线性回归模型，将该线性回归模型作为数据感知递归模型索引DARMI的根节点；
(3)判断是否能够在缓存的增量缓存中查询到该单点查询请求对应的结果，如果是则返回结果给用户，过程结束，否则进入步骤(4)；
(4)判断是否能够在缓存的不可变增量缓存中查询到该单点查询请求对应的结果，如果是则返回结果给用户，过程结束，否则进入步骤(5)；
(5)判断是否能够在数据感知递归模型索引DARMI中查询到该单点查询请求对应的结果，如果是则返回结果给用户，过程结束，否则返回空结果给用户，过程结束；
(6)获取范围查询请求对应的起始值和终止值，确定起始值在数据感知递归模型索引DARMI中所对应的叶子节点，从该叶子节点开始，遍历数据感知递归模型索引DARMI中其键位于起始值和终止值之间的所有数据点，并将所有数据点保存在结果集合R1中；
(7)遍历缓存中的不可变增量缓存，取出其键位于起始值和终止值之间的所有数据点，并将所有数据点保存在结果集合R2中，将结果集合R2与R1进行合并，以得到新的结果集合R3；
(8)遍历缓存中的增量缓存，取出其键位于起始值和终止值之间的所有数据点，并将所有数据点保存在结果集合R4中，将结果集合R4与R3进行合并，以得到新的结果集合R5。
2.根据权利要求1所述的支持高效写的自适应学习索引方法，其特征在于，
在步骤(A10)的训练过程中，线性回归模型的自变量为第j个数据片中所有数据点的键，因变量为所有数据点在第j个数据片中的位置；
在步骤(A12)的训练过程中，线性回归模型的自变量为每个叶子节点管理的数据片的数据范围下限，若范围下限为‑∞，则用0替换，因变量为叶子节点在根节点的子节点列表中的位置。
3.根据权利要求2所述的支持高效写的自适应学习索引方法，其特征在于，
步骤(2)中的缓存是使用B+Tree创建增量缓存，其初始阶段为空；
当增量缓存中保存的数据点个数达到预设阈值后，增量缓存会变成不可变增量缓存，后台线程将不可变增量缓存中的数据与数据感知递归模型索引DARMI管理的数据片进行批量合并。
4.根据权利要求1所述的支持高效写的自适应学习索引方法，其特征在于，步骤(2)中利用后台线程将不可变增量缓存中的数据点与数据感知递归模型索引DARMI中的数据片进行批量合并这一过程包括以下子步骤：(2‑1)设置计数器k＝1；
(2‑2)判断计数器k是否大于不可变增量缓存中数据点的总数，如果是则过程结束，否则进入步骤(2‑3)；
(2‑3)确定不可变增量缓存中第k个数据点所要被合并的数据感知递归模型索引DARMI中的叶子节点node，创建列表list，并将第k个数据点保存在列表list中；
(2‑4)设置k＝k+1，然后进入步骤(2‑5)；
(2‑5)判断第k个数据点是否在叶子节点node管理的数据片的数据范围内，如果是，则将第k个数据点保存在列表list中，并返回步骤(2‑4)，否则将列表list中的数据点与叶子节点node管理的数据片进行合并，然后进入步骤(2‑7)；
(2‑7)扫描叶子节点node管理的数据片，并根据该数据片训练对应的线性回归模型，使用该线性回归模型替换数据感知递归模型索引DARMI中叶子节点node对应的线性回归模型；
(2‑8)判断叶子节点node管理的数据片的长度是否超过预设的长度阈值，如果是则进入步骤(2‑9)，否则返回步骤(2‑6)；
(2‑9)判断叶子节点node管理的数据片的数据范围是否包含+∞或‑∞，如果是则对该叶子节点node进行水平拆分处理，以得到多个新的叶子节点，然后进入步骤(2‑11)，否则进入步骤(2‑10)；
(2‑10)获取叶子节点node管理的数据片中所有数据点的键的密集度，并判断该密集度是否大于一预设阈值，如果是则对该叶子节点node进行垂直拆分处理，以得到多个新的叶子节点和1个非叶子节点，然后进入步骤(2‑11)，否则对该叶子节点node进行水平拆分处理，以得到多个新的叶子节点，然后进入步骤(2‑11)；
(2‑11)判断数据感知递归模型索引DARMI的高度是否达到预设阈值，如果是则进入步骤(2‑12)，否则过程结束；
(2‑12)扫描所有叶子节点，以获取每个叶子节点管理的数据片的数据范围训练一个线性回归模型，将该线性回归模型作为数据感知递归模型索引DARMI的根节点。
5.根据权利要求4所述的支持高效写的自适应学习索引方法，其特征在于，
对叶子节点node进行水平拆分的过程为，首先将叶子节点node管理的数据片进行拆分处理，以得到多个子数据片，为每个子数据片训练对应的线性回归模型，将该线性回归模型作为数据感知递归模型索引DARMI的新叶子节点，并使用得到的所有新叶子节点替换叶子节点node；
对叶子节点node进行垂直拆分的过程为：首先将叶子节点node管理的数据片进行拆分处理，以得到多个子数据片，为每个子数据片训练对应的线性回归模型，将该线性回归模型作为数据感知递归模型索引DARMI的新叶子节点，根据得到的所有新叶子节点所管理的数据片的数据范围训练一个线性回归模型，将该线性回归模型作为数据感知递归模型索引DARMI的非叶子节点，并使用该非叶子节点替换叶子节点node。
6.根据权利要求4所述的支持高效写的自适应学习索引方法，其特征在于，密集度σ等于：
其中Number表示叶子节点node管理的数据片中包含的数据点总数，keymax表示叶子节点node管理的数据片中包含的数据点中的最大键，keymin表示叶子节点node管理的数据片中包含的数据点中的最小键。
7.根据权利要求1所述的支持高效写的自适应学习索引方法，其特征在于，步骤(5)中，在数据感知递归模型索引DARMI中查询该单点查询请求对应的结果这一过程具体为：首先确定单点查询请求对应的数据点的键在数据感知递归模型索引DARMI中所对应的叶子节点，然后利用该叶子节点对应的线性回归模型计算该数据点的键在叶子节点管理的数据片中的预测位置，最后根据该预测位置以及线性回归模型的误差范围、并利用二分查找方法确定单点查询请求对应的数据点的键在叶子节点管理的数据片中的真实位置，并获取真实位置处的数据点作为查询结果。
8.一种支持高效写的自适应学习索引系统，其特征在于，包括：
第一模块，用于接收来自用户的请求，并判断该请求是单点查询请求、范围查询请求、还是写请求，如果是单点查询请求，则进入第三模块，如果是范围查询请求，则进入第六模块，如果是写请求，则进入第二模块；
第二模块，用于获取待插入的数据点，将该数据点插入预先建立的缓存的增量缓存中，并判断缓存的增量缓存中保存的数据点个数是否达到预设阈值，如果是则将增量缓存变成不可变增量缓存，重新生成一个增量缓存，并利用后台线程将不可变增量缓存中的数据点与预先建立的数据感知递归模型索引DARMI中的数据片进行批量合并，然后向用户发送写操作成功的通知，过程结束，否则向用户发送写操作成功的通知，过程结束；数据感知递归模型索引DARMI是通过以下子步骤建立得到的：(A1)获取数据集keys＝{(keya,posa),其中a＝1,2,…,n}，设置计数器i＝2，将第1个数据点(key1,pos1)设置为起点(keystart,posstart)，并设置高斜率SLhigh的初始值为∞，低斜率SLlow的初始值为0，其中n表示数据集中数据点的总数，keyi表示第i个数据点的键，posi表示第i个数据点在数据集keys中的位置；
(A2)判断i是否大于数据集中的数据点总数n，如果是则进入步骤(A7)，否则进入步骤(A3)；
(A3)对于第i个数据点，计算该数据点(keyi,posi)与起点(keystart,posstart)之间的斜率Li，并判断是否有Li∈[SLlow,SLhigh]，如果是则进入步骤(A4)；否则将数据点(keyi,posi)设置为新的起点(keystart,posstart)，将高斜率SLhigh的值设置为∞，将低斜率SLlow的值设置为0，并将i设置为第i个数据片分割点，然后进入步骤(A6)；
(A4)根据第i个数据点(keyi,posi)和预先设置的误差阈值生成两个新数据点(keyi,posi+error)、(keyi,posi‑error)，计算该新数据点(keyi,posi+error)与起点(keystart,posstart)的斜率Lpos+error，以及新数据点(keyi,posi‑error)与起点(keystart,posstart)的斜率Lpos‑error；
(A5)根据步骤(A4)得到的斜率Lpos+error更新高斜率SLhigh＝min(SLhigh,Lpos+error)，并根据步骤(A4)得到的斜率Lpos‑error更新低斜率SLlow＝max(SLlow,Lpos‑error)；
(A6)设置计数器i＝i+1，并返回步骤(A2)；
(A7)根据得到的所有数据片分割点将数据集划分为多个数据片；
(A9)判断计数器j是否大于步骤(A7)划分后得到的数据片总数Num，如果是则进入步骤(A12)，否则进入步骤(A10)；
(A10)从数据集中获取第j个数据片，根据该第j个数据片训练对应的线性回归模型，将该线性回归模型作为数据感知递归模型索引DARMI的第j个叶子节点，然后进入步骤(A11)；
(A11)设置计数器j＝j+1，并返回步骤(A9)；
(A12)根据得到的所有叶子节点所管理的数据片的数据范围训练线性回归模型，将该线性回归模型作为数据感知递归模型索引DARMI的根节点；
第三模块，用于判断是否能够在缓存的增量缓存中查询到该单点查询请求对应的结果，如果是则返回结果给用户，过程结束，否则进入第四模块；
第四模块，用于判断是否能够在缓存的不可变增量缓存中查询到该单点查询请求对应的结果，如果是则返回结果给用户，过程结束，否则进入第五模块；
第五模块，用于判断是否能够在数据感知递归模型索引DARMI中查询到该单点查询请求对应的结果，如果是则返回结果给用户，过程结束，否则返回空结果给用户，过程结束；
第六模块，用于获取范围查询请求对应的起始值和终止值，确定起始值在数据感知递归模型索引DARMI中所对应的叶子节点，从该叶子节点开始，遍历数据感知递归模型索引DARMI中其键位于起始值和终止值之间的所有数据点，并将所有数据点保存在结果集合R1中；
第七模块，用于遍历缓存中的不可变增量缓存，取出其键位于起始值和终止值之间的所有数据点，并将所有数据点保存在结果集合R2中，将结果集合R2与R1进行合并，以得到新的结果集合R3；
第八模块，用于遍历缓存中的增量缓存，取出其键位于起始值和终止值之间的所有数据点，并将所有数据点保存在结果集合R4中，将结果集合R4与R3进行合并，以得到新的结果集合R5。
一种支持高效写的自适应学习索引方法和系统
技术领域
[0001] 本发明属于计算机数据存储领域，更具体地，涉及一种支持高效写的自适应学习索引方法和系统。
背景技术
[0002] 大数据的发展对索引技术的要求越来越高，需要索引支持高效读写、内存占用低、易于维护等特性。近些年，机器学习领域不断取得新成绩，学习索引开创性地为机器学习在索引优化领域的应用提供了新的方向。学习索引的核心思想是：现有的索引结构都可以用其他类型的模型代替，模型可以学习键的分布，使用此信息能够有效地预测记录的位置或存在。
[0003] 现有的学习索引方法主要是利用递归模型索引(Recursive Model Indexes，简称RMI)来替换B+Tree等范围索引结构。RMI是一种将简单的机器学习模型组合在一起的多层结构，较高级别的模型选择下一层模型，依此类推，叶子节点模型对键的真实位置进行最终预测。
[0004] 相比于传统的范围索引B+Tree，学习索引有更好的读性能，内存占用更小，有很好的应用前景，但也存在一些不可忽略的缺陷：首先，RMI采用均匀的数据分片算法，难以保证同一数据片中数据分布的相似性，使得子模型误差较大，从而影响了学习索引的性能；其次，RMI结构中每个叶子节点管理的是整个有序数组，而不是某一个小数据片，从而会导致RMI可扩展性较差，无法支持高效的写操作，也不支持高效的持久化。
发明内容
[0005] 针对现有技术的以上缺陷或改进需求，本发明提供了一种支持高效写的自适应学习索引方法(Adaptive Learned Index Supporting EfficientWrites，简称EWALI)，其目的在于，解决现有学习索引方法由于采用均匀的数据分片算法，导致难以保证同一数据片中数据分布的相似性，使得子模型误差较大，进而影响学习索引性能的技术问题，以及现有RMI结构由于每个叶子节点管理的是整个有序数组，而不是某一个小数据片，导致RMI可扩展性较差，无法支持高效的写操作，也不支持高效的持久化的技术问题。
[0006] 为实现上述目的，按照本发明的一个方面，提供了一种支持高效写的自适应学习索引方法，包括以下步骤：
[0007] (1)接收来自用户的请求，并判断该请求是单点查询请求、范围查询请求、还是写请求，如果是单点查询请求，则进入步骤(3)，如果是范围查询请求，则进入步骤(6)，如果是写请求，则进入步骤(2)；
[0008] (2)获取待插入的数据点，将该数据点插入预先建立的缓存的增量缓存中，并判断缓存的增量缓存中保存的数据点个数是否达到预设阈值，如果是则将增量缓存变成不可变增量缓存，重新生成一个增量缓存，并利用后台线程将不可变增量缓存中的数据点与预先建立的DARMI中的数据片进行批量合并，然后向用户发送写操作成功的通知，过程结束，否则向用户发送写操作成功的通知，过程结束。
[0009] (3)判断是否能够在缓存的增量缓存中查询到该单点查询请求对应的结果，如果是则返回结果给用户，过程结束，否则进入步骤(4)；
[0010] (4)判断是否能够在缓存的不可变增量缓存中查询到该单点查询请求对应的结果，如果是则返回结果给用户，过程结束，否则进入步骤(5)；
[0011] (5)判断是否能够在DARMI中查询到该单点查询请求对应的结果，如果是则返回结果给用户，过程结束，否则返回空结果给用户，过程结束；
[0012] (6)获取范围查询请求对应的起始值和终止值，确定起始值在DARMI中所对应的叶子节点，从该叶子节点开始，遍历DARMI中其键位于起始值和终止值之间的所有数据点，并将所有数据点保存在结果集合R1中；
[0013] (7)遍历缓存中的不可变增量缓存，取出其键位于起始值和终止值之间的所有数据点，并将所有数据点保存在结果集合R2中，将结果集合R2与R1进行合并，以得到新的结果集合R3。
[0014] (8)遍历缓存中的增量缓存，取出其键位于起始值和终止值之间的所有数据点，并将所有数据点保存在结果集合R4中，将结果集合R4与R3进行合并，以得到新的结果集合R5。
[0015] 优选地，递归模型索引是通过以下子步骤建立得到的：
[0016] (A1)获取数据集keys＝{(keya,posa),其中a＝1,2,…,n}，设置计数器i＝2，将第1个数据点(key1,pos1)设置为起点(keystart,posstart)，并设置高斜率SLhigh的初始值为∞，低斜率SLlow的初始值为0，其中n表示数据集中数据点的总数，keyi表示第i个数据点的键，posi表示第i个数据点在数据集keys中的位置；
[0017] (A2)判断i是否大于数据集中的数据点总数n，如果是则进入步骤(A7)，否则进入步骤(A3)；
[0018] (A3)对于第i个数据点，计算该数据点(keyi,posi)与起点(keystart,posstart)之间的斜率Li，并判断是否有Li∈[SLlow,SLhigh]，如果是则进入步骤(A4)；否则将数据点(keyi,posi)设置为新的起点(keystart,posstart)，将高斜率SLhigh的值设置为∞，将低斜率SLlow的值设置为0，并将i设置为第i个数据片分割点，然后进入步骤(A6)；
[0019] (A4)根据第i个数据点(keyi,posi)和预先设置的误差阈值生成两个新数据点(keyi,posi+error)、(keyi,posi‑error)，计算该新数据点(keyi,posi+error)与起点(keystart,posstart)的斜率Lpos+error，以及新数据点(keyi,posi‑error)与起点(keystart,posstart)的斜率Lpos‑error；
[0020] (A5)根据步骤(A4)得到的斜率Lpos+error更新高斜率SLhigh＝min(SLhigh,Lpos+error)，并根据步骤(A4)得到的斜率Lpos‑error更新低斜率SLlow＝max(SLlow,Lpos‑error)；
[0021] (A6)设置计数器i＝i+1，并返回步骤(A2)；
[0022] (A7)根据得到的所有数据片分割点将数据集划分为多个数据片；
[0023] (A8)设置计数器j＝1；
[0024] (A9)判断计数器j是否大于步骤(A7)划分后得到的数据片总数Num，如果是则进入步骤(A12)，否则进入步骤(A10)；
[0025] (A10)从数据集中获取第j个数据片，根据该第j个数据片训练对应的线性回归模型，将该线性回归模型作为DARMI的第j个叶子节点，然后进入步骤(A11)；
[0026] (A11)设置计数器j＝j+1，并返回步骤(A9)；
[0027] (A12)根据得到的所有叶子节点所管理的数据片的数据范围训练线性回归模型，将该线性回归模型作为DARMI的根节点；
[0028] 优选地，在步骤(A10)的训练过程中，线性回归模型的自变量为第j个数据片中所有数据点的键，因变量为所有数据点在第j个数据片中的位置；
[0029] 在步骤(A12)的训练过程中，线性回归模型的自变量为每个叶子节点管理的数据片的数据范围下限，若范围下限为‑∞，则用0替换，因变量为叶子节点在根节点的子节点列表中的位置。
[0030] 优选地，步骤(2)中的缓存是使用B+Tree创建增量缓存，其初始阶段为空。
[0031] 当增量缓存中保存的数据点个数达到预设阈值后，增量缓存会变成不可变增量缓存，后台线程将不可变增量缓存中的数据与DARMI管理的数据片进行批量合并。
[0032] 优选地，步骤(2)中利用后台线程将不可变增量缓存中的数据点与DARMI中的数据片进行批量合并这一过程包括以下子步骤：
[0033] (2‑1)设置计数器k＝1；
[0034] (2‑2)判断计数器k是否大于不可变增量缓存中数据点的总数，如果是则过程结束，否则进入步骤(2‑3)；
[0035] (2‑3)确定不可变增量缓存中第k个数据点所要被合并的DARMI中的叶子节点node，创建列表list，并将第k个数据点保存在列表list中；
[0036] (2‑4)设置k＝k+1，然后进入步骤(2‑5)；
[0037] (2‑5)判断第k个数据点是否在叶子节点node管理的数据片的数据范围内，如果是，则将第k个数据点保存在列表list中，并返回步骤(2‑4)，否则将列表list中的数据点与叶子节点node管理的数据片进行合并，然后进入步骤(2‑7)；
[0038] (2‑6)k＝k+1、并返回步骤(2‑2)；
[0039] (2‑7)扫描叶子节点node管理的数据片，并根据该数据片训练对应的线性回归模型，使用该线性回归模型替换DARMI中叶子节点node对应的线性回归模型；
[0040] (2‑8)判断叶子节点node管理的数据片的长度是否超过预设的长度阈值，如果是则进入步骤(2‑9)，否则返回步骤(2‑6)；
[0041] (2‑9)判断叶子节点node管理的数据片的数据范围是否包含+∞或‑∞，如果是则对该叶子节点node进行水平拆分处理，以得到多个新的叶子节点，然后进入步骤(2‑11)，否则进入步骤(2‑10)；
[0042] (2‑10)获取叶子节点node管理的数据片中所有数据点的键的密集度，并判断该密集度是否大于一预设阈值，如果是则对该叶子节点node进行垂直拆分处理，以得到多个新的叶子节点和1个非叶子节点，然后进入步骤(2‑11)，否则对该叶子节点node进行水平拆分处理，以得到多个新的叶子节点，然后进入步骤(2‑11)；
[0043] (2‑11)判断DARMI的高度是否达到预设阈值(在本实施方式中，其取值等于5)，如果是则进入步骤(2‑12)，否则过程结束。
[0044] (2‑12)扫描所有叶子节点，以获取每个叶子节点管理的数据片的数据范围训练一个线性回归模型(其过程与上述A12相同，在此不再赘述)，将该线性回归模型作为DARMI的根节点。
[0045] 优选地，对叶子节点node进行水平拆分的过程为，首先将叶子节点node管理的数据片进行拆分处理，以得到多个子数据片，为每个子数据片训练对应的线性回归模型，将该线性回归模型作为DARMI的新叶子节点，并使用得到的所有新叶子节点替换叶子节点node；
[0046] 对叶子节点node进行垂直拆分的过程为：首先将叶子节点node管理的数据片进行拆分处理，以得到多个子数据片，为每个子数据片训练对应的线性回归模型，将该线性回归模型作为DARMI的新叶子节点，根据得到的所有新叶子节点所管理的数据片的数据范围训练一个线性回归模型，将该线性回归模型作为DARMI的非叶子节点，并使用该非叶子节点替换叶子节点node。
[0047] 优选地，密集度σ等于：
[0048]
[0049] 其中Number表示叶子节点node管理的数据片中包含的数据点总数，keymax表示叶子节点node管理的数据片中包含的数据点中的最大键，keymin表示叶子节点node管理的数据片中包含的数据点中的最小键。
[0050] 优选地，步骤(5)中，在DARMI中查询该单点查询请求对应的结果这一过程具体为：首先确定单点查询请求对应的数据点的键在DARMI中所对应的叶子节点，然后利用该叶子节点对应的线性回归模型计算该数据点的键在叶子节点管理的数据片中的预测位置，最后根据该预测位置以及线性回归模型的误差范围、并利用二分查找方法确定单点查询请求对应的数据点的键在叶子节点管理的数据片中的真实位置，并获取真实位置处的数据点作为查询结果。
[0051] 按照本发明的另一方面，提供了一种支持高效写的自适应学习索引系统，包括：
[0052] 第一模块，用于接收来自用户的请求，并判断该请求是单点查询请求、范围查询请求、还是写请求，如果是单点查询请求，则进入第三模块，如果是范围查询请求，则进入第六模块，如果是写请求，则进入第二模块；
[0053] 第二模块，用于获取待插入的数据点，将该数据点插入预先建立的缓存的增量缓存中，并判断缓存的增量缓存中保存的数据点个数是否达到预设阈值，如果是则将增量缓存变成不可变增量缓存，重新生成一个增量缓存，并利用后台线程将不可变增量缓存中的数据点与预先建立的DARMI中的数据片进行批量合并，然后向用户发送写操作成功的通知，过程结束，否则向用户发送写操作成功的通知，过程结束。
[0054] 第三模块，用于判断是否能够在缓存的增量缓存中查询到该单点查询请求对应的结果，如果是则返回结果给用户，过程结束，否则进入第四模块；
[0055] 第四模块，用于判断是否能够在缓存的不可变增量缓存中查询到该单点查询请求对应的结果，如果是则返回结果给用户，过程结束，否则进入第五模块；
[0056] 第五模块，用于判断是否能够在DARMI中查询到该单点查询请求对应的结果，如果是则返回结果给用户，过程结束，否则返回空结果给用户，过程结束；
[0057] 第六模块，用于获取范围查询请求对应的起始值和终止值，确定起始值在DARMI中所对应的叶子节点，从该叶子节点开始，遍历DARMI中其键位于起始值和终止值之间的所有数据点，并将所有数据点保存在结果集合R1中；
[0058] 第七模块，用于遍历缓存中的不可变增量缓存，取出其键位于起始值和终止值之间的所有数据点，并将所有数据点保存在结果集合R2中，将结果集合R2与R1进行合并，以得到新的结果集合R3。
[0059] 第八模块，用于遍历缓存中的增量缓存，取出其键位于起始值和终止值之间的所有数据点，并将所有数据点保存在结果集合R4中，将结果集合R4与R3进行合并，以得到新的结果集合R5。
[0060] 总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够取得下列有益效果：
[0061] (1)本发明由于采用了步骤(A1)到(A7)的ShrinkingCone算法，其能够根据数据分布进行动态数据分片，保证分片后每个数据片内的数据分布趋于线性，因此能够解决现有RMI由于采用均匀的数据分片算法，难以保证同一数据片中数据分布的相似性，使得子模型误差较大，从而影响了学习索引的性能的技术问题；
[0062] (2)本发明由于采用了步骤(3)，其实现数据感知递归模型索引DARMI，能够根据数据分布的变化，自适应进行节点拆分、重训练等操作，动态地调整索引结构DARMI的每个叶子节点管理一个数据分片，具有较高的可拓展性和维护效率，因此能够解决现有RMI可扩展性较差，无法支持高效的写操作，也不支持高效的持久化的技术问题。
[0063] (3)本发明通过采用步骤(3)设计了采用缓存来处理增量数据，利用后台线程将不可变增量缓存中的数据点与DARMI中的数据片进行批量合并，因此支持更高效的写操作。
[0064] (4)本发明通过使用步骤(A12)，DARMI每层模型为简单的线性模型，既能够保证很高的准确度，而且可以加快模型的计算速度，也能够显著降低模型的内存开销。
附图说明
[0065] 图1是本发明支持高效写的自适应学习索引方法的流程示意图；
[0066] 图2是本发明DARMI中叶子节点水平拆分的示意图；
[0067] 图3是本发明DARMI中叶子节点垂直拆分的示意图；
[0068] 图4是本发明在NYCT数据集、Lognormal数据集和OSM数据集上的读压测测试结果；
[0069] 图5是本发明在NYCT数据集、Lognormal数据集和OSM数据集上的写压测测试结果。
具体实施方式
[0070] 为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。
[0071] 以下首先对本发明中的技术术语进行解释和说明：
[0072] 数据感知递归模型索引(Data Aware Recursive‑Model Indexes，DARMI)：其基于动态数据分片算法，根据数据分布进行节点拆分，能够自适应调整索引结构，其叶子节点管理分片后的数据片，写操作只会影响部分节点，因此具有较高的可拓展性。DARMI的每个模型均为线性回归模型，既能保证高的精确度，也能降低内存开销。
[0073] 缓存(Buffer)：用来处理增量数据，支持高效写操作。包含增量缓存(Incremental buffer)和不可变增量缓存(Immutable buffer)，当增量数据的记录数达到一定阈值后，增量缓存会变成不可变增量缓存，后台线程将不可变增量缓存中的数据与DARMI管理的数据片进行批量合并。
[0074] 如图1所示，本发明提供了一种支持高效写的自适应学习索引方法，包括以下步骤：
[0075] (1)接收来自用户的请求，并判断该请求是单点查询请求、范围查询请求、还是写请求，如果是单点查询请求，则进入步骤(3)，如果是范围查询请求，则进入步骤(6)，如果是写请求，则进入步骤(2)；
[0076] 具体而言，本步骤中判断请求的具体类型，是通过查看用户发送该请求的接口来判断，如果是单点查询请求，则用户是通过单点查询接口来发送该请求，如果是范围查询请求，则用户是通过范围查询接口来发送该请求，如果是写请求，则用户是通过写程序接口来发送该请求。
[0077] (2)获取待插入的数据点，将该数据点插入预先建立的缓存的增量缓存中，并判断缓存的增量缓存中保存的数据点个数是否达到预设阈值，如果是则将增量缓存变成不可变增量缓存，重新生成一个增量缓存，并利用后台线程将不可变增量缓存中的数据点与预先建立的DARMI中的数据片进行批量合并，然后向用户发送写操作成功的通知，过程结束，否则向用户发送写操作成功的通知，过程结束；
[0078] 具体而言，递归模型索引是通过以下子步骤建立得到的：
[0079] (A1)获取数据集keys＝{(keya,posa),其中a＝1,2,…,n}，设置计数器i＝2，将第1个数据点(key1,pos1)设置为起点(keystart,posstart)，并设置高斜率SLhigh的初始值为∞，低斜率SLlow的初始值为0，其中n表示数据集中数据点的总数，keyi表示第i个数据点的键，posi表示第i个数据点在数据集keys中的位置；
[0080] (A2)判断i是否大于数据集中的数据点总数n，如果是则进入步骤(A7)，否则进入步骤(A3)；
[0081] (A3)对于第i个数据点，计算该数据点(keyi,posi)与起点(keystart,posstart)之间的斜率Li，并判断是否有Li∈[SLlow,SLhigh]，如果是则进入步骤(A4)；否则将数据点(keyi,posi)设置为新的起点(keystart,posstart)，将高斜率SLhigh的值设置为∞，将低斜率SLlow的值设置为0，并将i设置为第i个数据片分割点，然后进入步骤(A6)；
[0082] (A4)根据第i个数据点(keyi,posi)和预先设置的误差阈值生成两个新数据点(keyi,posi+error)、(keyi,posi‑error)，计算该新数据点(keyi,posi+error)与起点(keystart,posstart)的斜率Lpos+error，以及新数据点(keyi,posi‑error)与起点(keystart,posstart)的斜率Lpos‑error；
[0083] 具体而言，本步骤中的误差阈值是任意自然数，其取值越小，则分片数较多，会影响递归模型索引的性能，其取值越大，则根据数据片训练的模型误差较大，优选为10。
[0084] (A5)根据步骤(A4)得到的斜率Lpos+error更新高斜率SLhigh＝min(SLhigh,Lpos+error)，并根据步骤(A4)得到的斜率Lpos‑error更新低斜率SLlow＝max(SLlow,Lpos‑error)；
[0085] (A6)设置计数器i＝i+1，并返回步骤(A2)；
[0086] (A7)根据得到的所有数据片分割点将数据集划分为多个数据片；
[0087] (A8)设置计数器j＝1；
[0088] (A9)判断计数器j是否大于步骤(A7)划分后得到的数据片总数Num，如果是则进入步骤(A12)，否则进入步骤(A10)；
[0089] (A10)从数据集中获取第j个数据片，根据该第j个数据片训练对应的线性回归模型，将该线性回归模型作为DARMI的第j个叶子节点，然后进入步骤(A11)；
[0090] 在训练过程中，线性回归模型的自变量为第j个数据片中所有数据点的键，因变量为所有数据点在第j个数据片中的位置。
[0091] (A11)设置计数器j＝j+1，并返回步骤(A9)；
[0092] (A12)根据得到的所有叶子节点所管理的数据片的数据范围训练线性回归模型，将该线性回归模型作为DARMI的根节点；
[0093] 在训练过程中，线性回归模型的自变量为每个叶子节点管理的数据片的数据范围下限，若范围下限为‑∞，则用0替换，因变量为叶子节点在根节点的子节点列表中的位置。
[0094] 例如，某个根节点有Num个叶子节点，每个叶子节点管理的数据片的数据范围分别为(‑∞,80],[81,170],[171,1200],…,[20000,+∞)，则训练线性回归模型的数据集为{(0,0),(81,1),(171,2),…,(20000,Num‑1)}。
[0095] 步骤(2)中的缓存的建立过程如下：使用B+Tree创建增量缓存(Incremental Buffer)，其初始阶段为空。
[0096] 增量缓存中保存的是小规模数据，以保证在增量缓存中读写数据的开销很小。
[0097] 当增量缓存中保存的数据点个数达到预设阈值(优选为256)后，增量缓存会变成不可变增量缓存(Immutable Buffer)，后台线程将不可变增量缓存中的数据与DARMI管理的数据片进行批量合并。
[0098] 本步骤中利用后台线程将不可变增量缓存中的数据点与DARMI中的数据片进行批量合并这一过程包括以下子步骤：
[0099] (2‑1)设置计数器k＝1；
[0100] (2‑2)判断计数器k是否大于不可变增量缓存中数据点的总数，如果是则过程结束，否则进入步骤(2‑3)；
[0101] (2‑3)确定不可变增量缓存中第k个数据点所要被合并的DARMI中的叶子节点node，创建列表list，并将第k个数据点保存在列表list中；
[0102] (2‑4)设置k＝k+1，然后进入步骤(2‑5)；
[0103] (2‑5)判断第k个数据点是否在叶子节点node管理的数据片的数据范围内，如果是，则将第k个数据点保存在列表list中，并返回步骤(2‑4)，否则将列表list中的数据点与叶子节点node管理的数据片进行合并，然后进入步骤(2‑7)；
[0104] (2‑6)k＝k+1、并返回步骤(2‑2)；
[0105] (2‑7)扫描叶子节点node管理的数据片，并根据该数据片训练对应的线性回归模型，使用该线性回归模型替换DARMI中叶子节点node对应的线性回归模型；
[0106] (2‑8)判断叶子节点node管理的数据片的长度是否超过预设的长度阈值，如果是则进入步骤(2‑9)，否则返回步骤(2‑6)；
[0107] 在本步骤中，预设的长度阈值等于6144。
[0108] (2‑9)判断叶子节点node管理的数据片的数据范围是否包含+∞或‑∞，如果是则对该叶子节点node进行水平拆分处理，以得到多个新的叶子节点，然后进入步骤(2‑11)，否则进入步骤(2‑10)；
[0109] 对叶子节点node进行水平拆分的过程如图2所示，首先将叶子节点node管理的数据片进行拆分处理，以得到多个子数据片(其过程和上述A1‑A7的完全相同，在此不再赘述)，为每个子数据片训练对应的线性回归模型，将该线性回归模型作为DARMI的新叶子节点，并使用得到的所有新叶子节点替换叶子节点node。
[0110] (2‑10)获取叶子节点node管理的数据片中所有数据点的键的密集度，并判断该密集度是否大于一预设阈值(其等于0.9)，如果是则对该叶子节点node进行垂直拆分处理，以得到多个新的叶子节点和1个非叶子节点，然后进入步骤(2‑11)，否则对该叶子节点node进行水平拆分处理，以得到多个新的叶子节点，然后进入步骤(2‑11)；
[0111] 密集度σ等于：
[0112]
[0113] 其中Number表示叶子节点node管理的数据片中包含的数据点总数，keymax表示叶子节点node管理的数据片中包含的数据点中的最大键，keymin表示叶子节点node管理的数据片中包含的数据点中的最小键。
[0114] 若密集度σ超过阈值，则说明该数据片中的键较为密集，可插入的键较少，后面被再次拆分的可能性较小，此时建议采用垂直拆分方式。反之，若σ没有超过阈值，说明可插入的键较多，后面被再次拆分的可能性较大，此时建议采用水平拆分方式。
[0115] 对叶子节点node进行垂直拆分的过程如图3所示：首先将叶子节点node管理的数据片进行拆分处理，以得到多个子数据片(其过程和上述A1‑A7的完全相同，在此不再赘述)，为每个子数据片训练对应的线性回归模型，将该线性回归模型作为DARMI的新叶子节点，根据得到的所有新叶子节点所管理的数据片的数据范围训练一个线性回归模型(其过程与上述A12相同，在此不再赘述)，将该线性回归模型作为DARMI的非叶子节点，并使用该非叶子节点替换叶子节点node。
[0116] (2‑11)判断DARMI的高度是否达到预设阈值(在本实施方式中，其取值等于5)，如果是则进入步骤(2‑12)，否则过程结束。
[0117] (2‑12)扫描所有叶子节点，以获取每个叶子节点管理的数据片的数据范围训练一个线性回归模型(其过程与上述A12相同，在此不再赘述)，将该线性回归模型作为DARMI的根节点。
[0118] 对步骤(2‑3)得到的DARMI进行重训练，生成新的DARMI重训练。DARMI重训练的触发条件是DARMI的高度达到阈值，因为DARMI高度过大会增加DARMI的计算开销，进而降低索引结构的读写性能。DARMI的重训练只需要重新创建一个新的根节点，训练该根节点的模型即可。重新构建的DARMI和初始化时构建的DARMI类似，只包含两层，第一层为根节点，第二层为叶子节点，每个叶子节点对应一个数据片。重新构建DARMI时，只需要重新构建一个根节点，叶子节点不需要重新创建，叶子节点模型也不需要重新训练，可复用重构前DARMI的所有叶子节点。
[0119] (3)判断是否能够在缓存的增量缓存中查询到该单点查询请求对应的结果，如果是则返回结果给用户，过程结束，否则进入步骤(4)；
[0120] (4)判断是否能够在缓存的不可变增量缓存中查询到该单点查询请求对应的结果，如果是则返回结果给用户，过程结束，否则进入步骤(5)；
[0121] (5)判断是否能够在DARMI中查询到该单点查询请求对应的结果，如果是则返回结果给用户，过程结束，否则返回空结果给用户，过程结束；
[0122] 具体而言，本步骤在DARMI中查询该单点查询请求对应的结果这一过程具体为：首先确定单点查询请求对应的数据点的键在DARMI中所对应的叶子节点，然后利用该叶子节点对应的线性回归模型计算该数据点的键在叶子节点管理的数据片中的预测位置，最后根据该预测位置以及线性回归模型的误差范围、并利用二分查找方法确定单点查询请求对应的数据点的键在叶子节点管理的数据片中的真实位置，并获取真实位置处的数据点作为查询结果。
[0123] (6)获取范围查询请求对应的起始值和终止值，确定起始值在DARMI中所对应的叶子节点，从该叶子节点开始，遍历DARMI中其键位于起始值和终止值之间的所有数据点，并将所有数据点保存在结果集合R1中；
[0124] (7)遍历缓存中的不可变增量缓存，取出其键位于起始值和终止值之间的所有数据点，并将所有数据点保存在结果集合R2中，将结果集合R2与R1进行合并，以得到新的结果集合R3；
[0125] 在本步骤的合并过程中，如果对于同一个数据点而言(即其在结果集合R1和R2中对应的键相同)，则只将结果集合R2中的该数据点保存在R3中。
[0126] (8)遍历缓存中的增量缓存，取出其键位于起始值和终止值之间的所有数据点，并将所有数据点保存在结果集合R4中，将结果集合R4与R3进行合并，以得到新的结果集合R5；
[0127] 在本步骤的合并过程中，如果对于同一个数据点而言(即其在结果集合R3和R4中对应的键相同)，则只将结果集合R4中的该数据点保存在R5中。
[0128] 实验结果
[0129] 本发明实验环境：CPU为8核Inter Xeon(R)@2.4GHz，，内存为64GB DDR4，硬盘容量为2TB，在64位Ubuntu 18.04.5 LTS操作系统下，采用C++编程实现本文系统。具体的参数设置如下：增量缓存保存的记录数阈值设置为256，数据片保存的记录数阈值设置为6144，DARMI高度阈值设置为8，前台线程个数设置为1个，后台线程个数设置为1个。
[0130] 为了说明本发明高效的读写性能，本发明在NYCT、Lognormal和OSM三种数据集上进行了读写压测实验，并记录了模型在不同数据集下的读吞吐率和写吞吐率，图4给出了读压测结果，图5给出了写压测结果。由图可知，本发明方案在保持较好的读性能同时，具有较高的写性能：相比B+Tree，本发明的读性能提升了13.5％，写性能提升了53.4％；相比FITing‑Tree，本发明的读性能提升了17.4％，写性能提升了60.9％；相比只支持读操作的学习索引，在Lognormal数据集下，本发明的读性能提升了94％；相比XIndex，本发明的读性能平均降低了37.2％，但写性能平均提升了22.5％。
[0131] 本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。
