Page 357 - 《软件学报》2025年第8期
P. 357

3780                                                       软件学报  2025  年第  36  卷第  8  期



                                                                                                     (14)
                                                  pos 0 = lea f slope ×k +leaf intercept
                    即便使用模型驱动插入方式插入键, 叶数组模型仍存在预测误差, 导致预测位置                         pos 0 不准确. 因此, 需要进行
                 指数搜索来纠正预测误差. 若指数搜索后返回查询键                 k 的位置  pos 0 =−1, 则说明查询键  k 未存储在叶数组中, 此时
                 开始扫描更新缓冲区; 否则, 说明查询键           k 存储在叶数组中, 可直接返回叶子节点中叶数组对应查询位置                     pos 0 的
                 有效载荷值    leaf A  → payload[pos 0 ] (第  13、14  行).
                    (3) 扫描更新缓冲区     (第  8–12  行). 若未在叶数组中找到查询键       k, 则扫描更新缓冲区. 由于更新缓冲区使用了
                 段间有序、段内无序的分段策略. 首先需要确定查询键                  k 所属的段, 一旦找到包含查询键         k 的段, 就在该段内执行
                 线性扫描以找到查询键         k. 如果找到键   k, 则直接返回叶子节点       leaf 中更新缓冲区对应查询位置        pos 1 的有效载荷
                 leaf B  → payload[pos 1 ]; 否则, 返回−1.
                    算法复杂度分析. 遍历到叶子节点的时间复杂度为                 O(H), 其中  H  是索引树的高度. 指数搜索叶子节点的开销
                 取决于工作负载的类型. 对于只读工作负载, 指数搜索叶子节点的查询成本由两部分组成. 首先, 在叶子数组中执
                 行指数搜索需要      O(logD) 的时间, 其中  D  是叶子模型的预测位置与第         1  个不小于或不大于查询键       k 的键  q  所在位
                 置之间的距离. 其次, 在一个小范围内进行二分搜索需要                 O(logE) 的时间, 其中  E  是键  q  的位置与查询键   k 的实际
                 位置之间的距离. 通常情况下, D>E. 因此, 只读工作负载的总查询时间为                   O(H+logD). 与只读工作负载不同, 读写
                 工作负载还需要考虑扫描更新缓冲区的时间开销. 扫描更新缓冲区的时间开销由两部分组成: 其一是在缓冲区中
                 定位的成本包含查询键         k 的段的遍历开销     O(seg), 其中  seg  是更新缓冲区中段的数量; 其二是在查询建           k 所属段
                 内遍历查询键     k 的开销  O(seg N ), 其中  seg N  是段内数据项的数量. 因此, 对于读写工作负载, 点查询的时间复杂度
                 为  O(H+(1–INSERT_FRAC)(logD)+(INSERT_FRAC)(seg+seg N )), 其中  INSERT_FRAC  是插入操作数占总操作数的
                 比例.

                 4   实验分析
                    本节介绍了实验的设置和详细结果, 并对实验结果进行了分析. 使用                      C++实现了本索引和其他相关的索引结
                 构. 所有实验都在一台      64  位的  Ubuntu 22.04.6 LTS  机器上进行, 该机器配备了一个第     13  代  Intel (R) Core (TM) i7-
                 13700 KF × 16 CPU, 64 GB  内存, 一张  NVIDIA Corporation  的显卡以及一块  4 TB  硬盘.

                 4.1   实验数据
                    本文在   SOSD (search on sorted data benchmark) 框架 (https://github.com/learnedsystems/SOSD) 公开的  5  个数
                 据集上进行实验, 包括      Osmc、Lat、Uniform、Amzn   和  Wiki. 使用键-有效载荷对来执行索引操作, 其中键的长度
                 是  8  字节, 有效载荷是随机生成的固定大小的值. 表           2  给出了数据集各种属性的详细信息.


                                                      表 2 实验数据集

                             数据集         数据量        键类型        有效载荷大小 (Byte)     数据集大小 (GB)
                              Osmc        1B         double          8                16
                              Lat        200M        double          8                3.2
                             Uniform     200M        uint64          8                17.6
                              Amzn       800M        uint64          8                1.7
                              Wiki       200M        uint64          8                1.6
                          注: B表示billion, M表示million

                    Osmc 数据集包含来自      Open Street Maps (https://registry.opendata.aws/osm/) 的世界各地的经度信息; Lat 数据
                 集由复合键组成, 将来自       Open Street Maps 的经度和纬度通过应用转换函数组合在一起, 即键              k=180·经度+纬度,
                 组合后的键分布十分倾斜; Uniform       数据集由人工在范围        [0,1] 之间随机生成, 且遵循均匀分布; Amzn       数据集包含
                 了  800M  亚马逊网站上的图书      id; Wiki 数据集包含维基百科网站上       200M  日志条目的唯一请求时间戳. 由于数据
                 集的数据量不同, 在后续的实验部分都截取              200M  进行测试. 默认的批量加载量为        20M.
   352   353   354   355   356   357   358   359   360   361   362