面向字符串的学习索引研究

作     者：周炜鸿 

作者单位：广州大学 

学位级别：硕士

导师姓名：杨世宇

授予年度：2024年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：数据库 数据结构 学习索引 字符串 

摘      要：随着互联网的发展,数据量爆炸性增长,特别是字符串类型的数据,如URL、用户ID等,其处理效率直接关系到数据库性能。传统的索引方法如B树、哈希表等,虽然在某些应用场景下表现良好,但面对大规模、高动态性的字符串数据,这些方法要么索引效率不高,要么空间利用率低。学习索引(Learned Index)作为一种新兴的数据结构,通过机器学习模型预测数据位置,显示出了处理大规模数据集时的潜力,尤其是在数值型数据上的应用成果显著。然而,如何有效地将学习索引应用于字符串类型的数据上,仍是一个待解决的挑战。本研究提出的SLIPP(String Learned Index with Precise Positions)索引通过结合了Trie树结构和学习索引的特点,不同于以往的学习索引将字符串整个作为模型的输入,SLIPP将字符串分割成多个片段,并对每个片段使用独立的机器学习模型进行索引。这种设计不仅充分利用了字符串的局部性特征,降低了用机器学习模型处理字符串类型数据的复杂度,提高了模型推理速度,而且通过精简模型参数,有效降低了内存占用。此外,SLIPP通过精确预测数据的存储位置,从而避免了学习索引的“最后一英里搜索问题,实现了快速的数据访问。为了验证SLIPP索引的性能,本研究在多个数据集上进行了广泛的实验,包括随机生成的字符串数据集和真实世界的URL数据集。实验结果表明,与现有的支持字符串处理的学习索引方法相比,SLIPP在查询效率、空间占用以及索引构建时间上都有显著的优势。特别地,SLIPP显示出了其出色的空间效率。这些实验不仅证实了SLIPP索引的理论设计的有效性,也展示了其在实际应用中的潜力。虽然SLIPP索引在多个方面展现了优异的性能,但在处理具有高度重复前缀的字符串数据时,其性能仍有待优化。未来的研究将进一步探索新的模型优化策略和索引结构调整机制,以提高SLIPP索引在更广泛数据分布情况下的适应性和效率。此外,如何设计高效的并发控制机制以充分利用多核心处理器的硬件资源,也是未来工作的重点之一。 总之,SLIPP索引作为一种新型的面向字符串的学习索引,其高效的数据处理能力和低内存占用特性,使其在现代大规模内存数据库中具有广泛的应用前景。通过持续的优化和改进,有望为数据库索引技术的发展开辟新的方向。