Page 358 - 《软件学报》2026年第2期
P. 358

姬涛 等: AI 赋能的关系型数据库系统研究: 标准化、技术与挑战                                                837


                 处理, 临时缓冲区虽然可让学习索引更快捷地插入但是查询时需要对缓冲区数据进行扫描, 缓冲区满或者系统空
                 闲时需要将缓冲区的数据合并到索引, 这带来了查询和合并的额外开销.
                    删除键也可能会更改索引结构            (例如, 节点合并), 或者模型的重新训练. 键删除的处理方式与键插入类似, 有
                 时为了避免索引结构的频繁改变, 只标记删除的键值                 (如  ALEX [163] ), 系统空闲或者删除数据到达一定条件再对删
                 除数据进行处理, 删除过程可能涉及索引结构重新调整或节点模型的重新训练.
                    块加载就是一次性为一批<键, 位置>对构建学习索引. 主要包含有两种类型的方法. 自上而下的方法, 如
                 RMI [159] 、ALEX [163] 、LIPP [165] , 首先初始化根节点, 然后将根节点拆分为子节点, 并以递归方式处理子节点中的数
                 据. ALEX  使用基于代价函数的方法从上到下按照代价函数最小的方法批量加载构建索引. LIPP                          也是从上到下块
                 加载, LIPP  以遇到数据冲突时分裂节点的方式批加载. 自下而上的方法则是将数据拆分为叶节点, 递归从每个节
                 点中提取最小和最大键构建父节点, 直到根节点, 从而构建整棵树. 为了决定如何拆分数据, 有许多算法会考虑拆
                 分开销以有效地构建树结构. 其中          XIndex [160] 采取先均匀划分数据, 然后依据数据块组成的叶节点向上构建整棵树
                 的策略.
                    (2) 多维学习索引
                    随着大数据发展, 呈几何倍数增长的空间数据的数量和多维数据对数据库查询速度也有了更高的要求. 学习
                 多维索引在学习的一维索引的基础上将其结构进行扩展使其支持多维数据, 同时需要支持特定的空间查询                                      (如
                 kNN  查询). 这些方法大多采用将多维数据降维的方法, 然后利用一维学习索引学习降维后的数据和其位置关系.
                 如表  6  所示, 根据索引的构建方法不同, 本文将现有的多维索引分为基于映射的多维索引、基于空间划分的多维

                 索引和基于格的多维索引, 最后我们总结了一些针对多维学习索引的增强方法.


                                                     表 6 多维学习索引

                   索引方法         类型          ML方法            数据空间         点查询   范围查询     kNN查询   更新/删除
                  ZM-Index [166]  基于映射  神经网络, 线性模型        填充曲线映射         精确      精确      不支持     不支持
                  ML-Index [167]  基于映射      神经网络            映射函数         精确      精确       精确     不支持
                   LISA [168]  基于映射          格回归            映射函数         精确      精确       精确      支持
                  IF-Index [169]  基于空间划分    线性插值            原本空间         精确      精确      不支持     不支持
                   RSMI [170]  基于空间划分       神经网络        原本空间 (映射排序)      精确      近似       近似      支持
                  QD-Tree [171]  基于空间划分     强化学习            原本空间         精确      精确      不支持     不支持
                   Flood [172]  基于格     分段线性模型, RMI         原本空间         精确      精确      不支持     不支持
                  Tsunami [173]  基于格        线性模型            原本空间         精确      精确      不支持     不支持

                    基于映射的多维索引就是使用降维方法将多维数据映射到一维空间, 基于映射值对这些多维数据进行排序,
                 然后使用一维索引的方法索引这些映射后的数据点. 在查询时, 只需要使用对应的映射函数对数据进行映射, 然后
                 使用学习索引进行查询. 值得注意的是, 为保证查询的正确性, 需要保证映射函数的单调性.
                    ZM-Index  [166] 是第  1  个多维学习索引, 该方法选择  Z  阶曲线作为映射函数. ZM-Index     将数据空间划分为网格
                 从而有效快速地计算键的         Z  阶曲线映射值. 为了处理范围查询, ZM-Index        将查询范围分解为       Z  曲线的地址区间,
                 查询通过索引模型找到相应的网格从而找到对应的存储位置. ML-Index                   [167] 采用改进的  iDistance [174] 函数来投影多
                 维数据, iDistance 通常用于索引高维数据以进行高效的最近邻搜索. ML-Index              首先使用聚类方法选定一组参考点,
                 并将数据依据参考点进行划分, 然后使用             iDistance 方法进行映射和排序, ML-Index    同时使用类似     iDistance 的方
                 法构建   B+树维护   iDistance 值. LISA [168] 主要解决了基于填充曲线的多维索引会访问与查询矩形无关的数据块问
                 题. 为了解决这个问题, LISA     采用了基于网格的投影方法. 首先将多维数据划分为等深的格, 将格内的键值使用勒
                 贝格测度与整个格的测度的比值进行映射. 然后使用一个单调的分片预测函数                       (格回归) 将每个点映射到其分片        (Shard)
                 的编号. 最后, 属于同一分片的点被存储到数据页中, 并训练本地模型来定位正确的数据页. 除此之外, Z-Index                          [175] ,
                 LMSFC [176] , WaZI [177] 也是基于映射的学习索引. 这些方法从索引的构建代价, 空间划分或者更新对基于映射的多
   353   354   355   356   357   358   359   360   361   362   363