这是一篇有关于计算机应用技术的博士论文代写范文，作为专业的博士论文代写平台，有关于博士论文代写、博士论文辅导、博士帮写论文、博士申请、学位论文代写、中国博士论文代写、博士毕业论文代写/代写博士·毕业论文、科论文代博士作业代写/代写博士论文代写等等，我们都提供最优质的代写服务，此篇文章涵盖信息科技、非易失内存;分离式内存;等研究内容本文以本论文针对不同内存环境中的树形索引技术进行了研究，并提出了三种不 同的索引设计以提升索引的读写性能，但是这些工作还存在值得改进的地方。
第1章绪论
1.1研究背景和意义
随着大数据时代的到来，全世界的数据总量呈现出指数级增长趋势。有统 计显示，2023年全球数据总量已达到120 ZB（1 ZB=102 1字节），预计到2025 年将进一步增长至181 ZB[ 1]。与此同时，上层应用对数据访问性能的需求持续 攀升，在这一背景下，高效管理超大规模数据已成为数据库系统领域的核心挑 战。一方面，数据库系统需确保超大规模数据存储的安全性与可靠性；另一方 面，系统必须提供更高的读写性能和更低的访问延迟，以满足现代应用的需求。 存储技术的进步推动了大规模数据管理的发展。机械硬盘（Hard Disk Drive，简 称HDD）技术的演进和市场规模效应使得存储设备成本不断降低。有研究表明， 2024年HDD的单位存储成本已经下降至0.01美元/GB[ 2]，单设备存储容量预 计在2025年达到40 TB[ 3]，这为超大规模数据的存储提供了可能。传统数据库 通常以HDD为主要存储介质，并将数据及索引结构存储于HDD中。然而，由 于HDD设备吞吐量较低且访问延迟较高，这一架构已逐渐无法满足现代应用对 高吞吐和低延迟的需求。为克服这一瓶颈，研究者们越来越倾向于将数据存储 于带宽更高、访问延迟更低的内存设备中，从而推动了内存数据库（In-Memory Database，简称IMDB）技术的快速发展。近年来，内存数据库已被广泛应用于 工业领域，如Redis[ 4]、SAP HANA [5]、VoltDB [6]和Hekaton [7]等，它们凭借卓 越的读写性能和极低的访问延迟，在大数据场景中发挥了至关重要的作用。
目录
创新性说明
摘要
abstract
第1章 绪论
1.1 研究背景和意义
1.2 国内外研究现状
1.3 论文研究内容
1.4 论文组织结构
第2章 面向传统DRAM内存的变长键学习索引
2.1 研究动机
2.2 相关工作
2.3 LISK索引结构
2.4 LISK操作算法
2.5 性能评测
2.6 本章小结
第3章 面向新型NVM的树形索引
3.1 研究动机
3.2 相关工作
3.3 NOBtree 索引结构
3.4 NOBtree 操作算法
3.5 性能评测
3.6 本章小结
第4章 面向分离式内存的树形索引
4.1 研究动机
4.2 相关工作
4.3 SEPtree 索引结构
4.4 SEPtree 同步机制
4.5 SEPtree 操作算法
4.6 性能评测
4.7 本章小结
第5章 总结与展望
5.1 论文工作总结
5.2 未来工作与展望
参考文献
新型内存技术为高性能数据库系统的构建带来了前所未有的机遇，但也引 入了一系列技术挑战。例如，NVM断电不丢失数据的存储特性和高读写带宽使 其成为极具吸引力的持久性存储介质，然而，使用NVM的应用需要采用新的编 程模型，并引入崩溃一致性（Crash Consistency）机制，以确保系统崩溃时数据 的完整性和一致性，这也使得NVM的应用推广进程缓慢。分离式内存的架构改 变了传统计算机系统的软件设计方法，同时引入了新的编程范式，目前的分离式 内存主要基于远程直接内存访问（Remote Direct Memory Access，简称RDMA） 技术实现，其对于结构的操作均基于RDMA原语，在这种环境中，数据库系统 的核心组件（如索引、日志、缓存管理等）均需要在架构以及编程范式上进行适 配，才能充分发挥其性能优势。
1.2国内外研究现状
本论文的研究内容主要涉及不同内存环境下的树形索引，包括传统内存、非 易失内存以及分离式内存。本节将对国内外相关研究现状进行总结，首先概述索 引技术的重要地位及其主要分类，然后介绍面向传统内存的学习索引技术，之后 总结针对非易失内存的树形索引技术，最后探讨分离式内存中的树形索引技术， 并对索引研究存在的主要挑战进行归纳总结。
1.2.1数据库索引技术概述
索引是数据库系统中的关键组件，主要用于加速数据查询，从而提升数据 库的整体存取性能。数据库索引种类繁多，不同的存储介质、存储架构和数据类 型均催生了针对性的索引优化方案。常见的存储介质包括机械硬盘（Hard Disk Drive，简称HDD）、固态硬盘（Solid-State Drive，简称SSD）、非易失内存（NVM） 以及传统内存（DRAM）等；存储架构则包括单机架构、分布式架构和分离式架 构；而数据类型则涉及一维数据、高维数据、空间数据和时序数据等。如此丰富 多样的索引种类充分体现了索引在数据库系统中的重要地位。本论文从存储介 质和存储架构两个方面进行索引研究，存储介质包括非易失内存和传统内存，存 储架构则包括单机架构以及分离式架构。接下来将对本论文关注的主要索引结 构进行简要的概括与总结。
索引的核心思想是通过构建高效的数据结构，在搜索键与物理存储地址之 间建立映射关系，从而提升数据的查询效率。根据映射关系构建方法的不同，索 引可分为两大类：哈希索引和树形索引。
1.2.2面向传统DRAM内存的学习索引
学习索引是一种利用机器学习技术进行优化的新型索引结构，其核心思想 在于将机器学习技术与传统索引技术相结合，以实现更高效的数据查询。该思想 源自于对B+树索引搜索过程的观察与抽象。正如前文所述，B+树索引通过遍 历其树形结构不断缩小搜索范围，最终在叶子节点中进行局部搜索，从而确定数 据的精确位置。这一过程可以概括为“映射+局部搜索”两个阶段：内部节点构 建了键到叶子节点的映射关系，叶子节点则限定了局部搜索的范围。研究者们发 现，学习模型同样能够学习出键到物理地址的映射，并保证在一定误差范围内能 够通过局部搜索定位到目标数据，同时该映射机制更加直接高效。基于这一观察 与思考，Kraska等人于2018年SIGMOD会议上首次提出以模型替代B+树索引 的方案，启发了后续工作对于学习索引这一全新索引范式的探索[ 13]。目前的学 习索引主要面向传统DRAM内存设计。
使用单一的复杂机器学习模型来预测数据位置非常低效，其在大规模数据 集上难以保证预测准确度，同时会带来高昂的训练成本。Kraska等人提出了递归 模型索引（Recursive Model Index，简称RMI）以解决这一问题[ 13]。图1.2展示 了RMI的结构，该索引由多层模型组成：第一层的根模型对整个数据集进行拟 合，并根据模型预测结果将数据划分为若干子集；随后，在每个子集上递归训练 后续模型，直至达到设定的层数。为了在性能、空间消耗和训练代价之间取得平 衡，RMI通常采用混合模型策略：第一层模型由于需要拟合全局数据，所以采用 复杂的神经网络模型，而下层模型则可采用简单的线性回归模型。如果最底层模 型始终无法满足预设的误差要求，还可以用B+树节点进行替换。
1.3论文研究内容
索引技术对于数据库系统的性能至关重要。在如今数据规模不断增长的背 景下，索引性能的提升已成为数据库系统性能研究中的核心课题之一。本论文旨 在对树形索引进行性能优化，目标是提升索引在不同内存环境中的读写性能和 实用性，为高性能内存数据库的发展提供坚实的性能基础。图1.4展示了本论文 研究内容的总体框架，主要包含三个方面：面向传统DRAM内存的变长键学习 索引、面向新型NVM的树形索引以及面向分离式内存的树形索引。
1.3.1面向传统DRAM内存的变长键学习索引
变长键在现实世界中广泛存在，而现有的学习索引仍难以有效支持其检索。 现有的变长键学习索引通常采用两种基本方案来处理变长键数据：（1）第一种 方案将学习索引与字典树索引结合，在字典树节点的分片数据上构建学习索引， 从而解决简单模型无法拟合变长键的问题。目前采用这种方案的研究工作普遍 引入编码机制对数据进行编码与平滑操作，以提升模型的拟合能力。（2）第二种 方案则将变长键视为高维向量，利用矩阵形式的线性模型来实现数据拟合。
1.3.2面向新型NVM的树形索引
NVM存在严重的NUMA效应，针对英特尔傲腾持久性内存的实验研究表 明，在NUMA环境下，NVM的带宽会受到严重限制[ 53]，这主要是因为跨NUMA 节点访问的高昂代价。对于NVM索引而言，NUMA效应会严重影响并发性能。 然而，目前的研究大多没有考虑NUMA效应，已有的优化工作主要通过DRAM 缓存热点数据来缓解NVM索引的NUMA效应[ 93]。虽然引入缓存能够有效提升 索引性能，但这也带来了额外的内存开销，并使得索引操作流程更加复杂。因此， 本论文提出了一种面向纯NVM架构的B+树索引NOBtree（NUMA Optimized B+tree）。
1.3.3面向分离式内存的树形索引
由于分离式内存系统能够动态增加计算节点，因此可以拥有大量的计算资 源，这对分离式内存索引的并发性能提出了更高的要求，因为其可能面临更频 繁的并发访问。DM索引的远程同步机制是其并发性能的主要瓶颈。现有的研 究提出了各种优化的RDMA锁机制来提升DM索引的并发性能，但这些方案仍 无法彻底消除远程同步代价。本论文提出了一种面向分离式内存的B+树索引 SEPtree（SEParate B+tree）。
SEPtree的主要目标是消除索引的远程同步代价，同时缓解本地缓存管理结 构的并发瓶颈，以提升索引的并发性能。SEPtree提出了以下几个关键设计：
（1）分离式的索引结构：与其他将索引结构完全存放在远程内存中的方法不 同，SEPtree将索引分为本地索引和远程索引两个部分。远程索引存放在远程内 存中，由一系列高度受限的B+树子索引组成，其根节点通过指针连接，主要负 责保证数据存储的正确性。而本地索引则由计算节点根据远程索引的根节点信 息构建，经过内存优化，主要负责加速查询。
（2）无冲突的逻辑分区：SEPtree使用了一种特殊的分区技术，通过对计算 节点进行逻辑分区，同时将分区的最小粒度设为远程子索引粒度，避免了不同计 算节点之间的数据访问冲突，从而彻底消除了远程同步代价。 （3）高并发的缓存管理：SEPtree采用了一种高并发的缓存管理技术，在保 证缓存命中率的前提下，缓解缓存换入/换出过程中的并发瓶颈，从而进一步提 升了索引的并发性能。
1.4论文组织结构
本论文的后续内容安排如下：
第2章“面向传统DRAM内存的变长键学习索引”。本章主要介绍支持变 长键的学习索引LISK。本章首先讨论LISK的研究动机和相关工作，然后介绍 LISK的索引结构设计，包括LISK索引总体结构，TLS的索引构建方法、数据 划分方法以及溢出节点设计等。接着详细讨论LISK的索引操作实现，包括点查 询、插入以及范围查询。最后，在多种负载与真实数据集上，全面测评LISK的 性能并与现有的变长键学习索引进行对比。
第3章“面向新型NVM的树形索引”。本章主要介绍面向非易失内存的B+ 树索引NOBtree。本章首先介绍NOBtree的研究动机和相关工作，然后详细阐述 NOBtree的索引结构、索引的NUMA优化技术以及NVM分配器的设计。之后 讨论NOBtree的索引操作实现，包括点查询、插入以及范围查询。最后，在多种 负载下全面测评NOBtree的性能并与现有的NVM索引进行对比。
第4章“面向分离式内存的树形索引”。本章主要介绍面向分离式内存的B+ 树索引SEPtree。本章首先介绍SEPtree的研究动机和相关工作，然后详细讨论 SEPtree的索引结构、索引分区机制和缓存管理机制。之后讨论SEPtree的索引 操作实现，包括点查询、插入以及范围查询。最后，在多种负载下对SEPtree进 行全面性能测评并与现有的索引进行比较。
第5章“总结与展望”。本章总结了本论文三个研究工作的主要内容与贡献， 并对树形索引的未来研究方向进行了展望。
第2章面向传统DRAM内存的变长键学习索引
变长键（如字符串）是一种常见的数据类型，在现实应用中广泛存在，例如 社交网站的用户名称、网页上的文字、网站的网址等均以字符串形式存储。然 而，现有的学习索引在处理字符串等变长键时存在局限性。虽然复杂的学习模型 具有更强的拟合能力，但其训练和预测的代价更高，对于追求高吞吐、低延迟的 索引结构来说，其计算开销是难以接受的。因此，现有的学习索引普遍采用简单 的线性模型来拟合数据。然而，这种模型的拟合能力有限，只能拟合数值数据， 无法处理字符串等变长键，从而限制了学习索引对于变长键的检索。总体而言， 变长键在实际应用中具有重要意义，但学习索引无法实现有效检索，从而限制了 其实用性。如何让学习索引有效支持变长键检索，已成为亟待解决的关键问题。
针对这一问题，本章提出了一种新型学习索引LISK（Learned Index for String Keys）。LISK采用了混合索引结构，将字典树、学习索引与B+树进行了有效结 合，从而实现对变长键的高效检索。为了提升索引性能，LISK提出了一种适应 变长键数据分布特点的学习型子索引结构TLS（Two-layer Learned Sub-index）。 TLS针对变长键提出了三种性能优化设计：两阶段的索引构建方法、基于二阶导 数的数据划分方法以及缓存友好的溢出节点设计。通过这些优化，LISK显著提 升了索引在变长键场景下的性能，并在实验评测中表现优异。
本章后续内容首先分析现有变长键学习索引面临的主要问题，从而引出 LISK的研究动机，然后介绍相关工作。之后详细描述LISK的索引结构、优 化技术以及具体的操作算法。最后进行全面的性能评测。
2.1研究动机
学习索引在变长键检索方面存在局限，主要是因为模型有限的拟合能力。目 前，大多数学习索引出于性能考虑，仅采用简单的线性模型拟合数据，但这类模 型只能处理定长的数值型数据。然而，变长键的长度通常比数值数据更长，且不 固定（常见的字符串长度从2 B至1 KB不等[ 28]），这种特性使其无法直接带入 线性模型中进行计算，导致模型无法进行数据拟合。目前有两种方案解决这一问 题：（1）将学习索引与字典树索引相结合。利用字典树索引的特性，在定长的数 据分片上构建学习索引，从而解决学习索引无法拟合变长键的问题。（2）将变长 键视为高维向量数据，利用矩阵形式的线性回归模型进行拟合，从而支持变长键 检索。由于字典树索引在检索变长键方面具有天然的优势，因此采用字典树与学 习索引相结合的方案往往能取得更优异的性能。然而，现有研究工作主要侧重于通过特殊编码机制来优化索引的整体性能，而未能对学习索引结构本身进行深 入优化。例如，LIVAK[ 40]和LITS [28]是目前最先进的两种变长键学习索引，它们 均采用了字典树的整体结构，并将字典树节点组织成学习索引以提升检索效率。 其中，LIVAK使用了COLIN[ 33]的结构，而LITS则基于LIPP [19]。这两项工作 均提出了一种基于统计的数据编码机制，在构建索引之前，会根据数据集的统计 信息构建编码表，通过编码数据提升数据的信息密度和数据分布的平滑性，从而 优化索引性能。
然而，使用编码机制优化性能的学习索引存在两个明显的局限性。首先，使 用编码机制需要在构建索引之前对数据集进行扫描，并统计必要的信息以构建 编码表，因此索引的构建代价较高；其次，使用编码机制的学习索引无法有效适 应动态负载，因为新插入的数据可能会导致数据的分布发生变化，从而导致编码 机制的失效，此时索引性能会受到严重的影响，需要重新构建编码表并重建整个 索引才能维持索引的性能，正如前文所言，索引的构建具有较高的代价，因此重 建索引在实际应用中是难以接受的。为了避免这些问题，本论文从索引结构的角 度出发，对学习索引的结构进行优化，在不使用编码机制的前提下提升索引的读 写性能与灵活性。
在利用字典树结构处理变长键的前提下，变长键学习索引的主要挑战来自 于变长键复杂的数据分布特点。与传统数值数据相比，由字符串分片转换而来的 数值往往呈现出更为复杂的分布，这主要源于信息密度的差异。字符串数据不仅 长度较长，而且常常出现前缀倾斜现象，即大量字符串共享较长的相同前缀，导 致其信息密度较低。图2.1展示了三组字符串数据的累积分布图，其数据通过提 取前8字节分片后转换得到。random数据集为随机生成的字符串，而reddit和 titles则代表两类常见的真实数据集。从图中可见，字符串数据的分布呈现出明 显的阶梯状特性，并且存在大量分布突变现象；此外，两种真实数据集在整体和 局部层面均展现出难以拟合的分布特点。这种复杂的分布特点大大增加了学习 索引的数据拟合难度。因此，设计一种能够适应这种分布特点的学习索引结构显 得尤为迫切。需要注意的是，后文中所提及的“变长键的数据分布”均指代其分 片数据的分布。
2.2相关工作
2.2.1传统的变长键索引
针对变长键数据，字典树索引具有天然优势，其整体的结构特征在第1.2.1 节中已有介绍。与B+树、红黑树等数据结构不同，字典树的每个节点仅存储键 的部分片段（例如字符串中的一个字符），而不需要保存完整的键。在查询过程 中，只需要利用与节点位置相匹配的键分片进行比较，即可定位到下一层节点， 这种搜索方式避免了完整键比较带来的高昂代价，而且搜索复杂度仅与数据长 度有关。因此，相较于B+树索引，字典树在处理变长键时具有明显的性能优势。
字典树的一个重要概念是节点跨度（Span），即节点内存储的键片段长度。 简单字典树中每个节点只存储一个字符，其节点跨度为1字节（8比特）。节点 跨度决定了整棵树的高度及其最大扇出（即每个节点的分支数目），索引设计者 可以根据需求设定适当的节点跨度。
简单字典树的节点跨度为1字节，其为每个字符构建一个节点，从而导致 查询和空间开销较高，后续研究者提出了多种改进方案提升索引性能和空间效 率[ 94-100]。由于相关研究众多，且其中部分研究的优化技术已经被广泛采用，此 处仅介绍与本论文工作最相关的几篇研究。
Masstree[ 41]是一类特殊的字典树索引，其将节点跨度设为8字节，并将每个 节点组织成一棵内存B+树，从而实现节点内的快速索引。Masstree的特殊设计 降低了指针代价，同时提高了缓存效率。此外，Masstree还使用了缓存行预取指 令和细粒度的并发控制进一步提升整体性能。
ART（Adaptive Radix Tree）[ 11]是一种可动态调整节点扇出（Fanout）的字典 树，其节点跨度固定为1字节，但是节点扇出会在4、16、48或256之间自适应 变化。扇出的增加可以提升插入和查询性能，但会降低空间效率。ART通过在这 四种节点类型间进行自适应调整，并结合自适应前缀压缩技术，实现了时间和空 间效率之间的平衡。
HOT（Height Optimized Trie）[ 12]针对ART在稀疏数据集下查询效率和存储 效率较低的问题进行了优化。HOT的主要目标是使节点扇出保持在一个稳定范 围内，从而降低整棵树的高度并提升性能。为此，HOT提出了根据数据分布动 态调整节点跨度的技术，使得每个节点的扇出稳定在约32左右；同时，通过精 心设计的物理节点结构、缓存预取以及SIMD指令等手段，HOT进一步提升了 索引的缓存效率和读写性能。
2.2.2变长键学习索引
尽管目前已有大量针对学习索引的研究，但针对变长键进行优化的工作相 对较少。如前文所述，目前主要有两种方案，下面分别介绍基于这两种方案的相 关工作。
字典树与学习索引的混合结构：这一类方案利用字典树仅检索数据分片的 特点，将字典树的节点构建为学习索引结构，从而解决模型拟合的问题，该方案 通常还会使用编码机制对数据进行转换，从而增强模型的拟合效果。
RSS[ 39]的整体结构与Masstree [41]类似。其将字符串数据切分为8字节或 16字节的分片，并在分片数据上构建RadixSpline[ 103]。随后，RSS按照字典树 的连接方式将各个学习索引连接起来。RSS所采用的RadixSpline是一种静态索 引结构，能够控制模型预测误差的上限，RSS在此基础上引入了哈希纠正机制 （Hash Corrector）以提升查询性能。然而，由于RadixSpline不支持插入操作，RSS 本质上也是静态索引，这也限制了其实用性。
LIVAK[ 40]同样采用混合结构，其利用数据分片构建学习索引，并将其连接 成字典树的整体结构。LIVAK本质上是一个索引框架，其内部的学习索引可以 采用任意现有结构，论文中选择了COLIN[ 33]作为其学习索引。此外，LIVAK基 于对现实世界字符串中字符使用频率的观察提出了一种编码机制（例如常见的 可打印字符频繁出现，而扩展字符和控制字符较少），该机制对数据集中出现频 率的64个字符进行重新编码，从而在降低数据长度的同时平滑数据分布。
2.3 LISK索引结构
LISK是一种混合结构的变长键学习索引，采用字典树的整体结构处理变长 键，并使用高性能的学习索引结构提升整体读写效率。其性能优势源于适应变 长键数据分布的学习型子索引结构：TLS。TLS通过一系列优化技术提升了模型 预测的精度，降低了索引读写代价，从而提升索引性能。其优化技术包括两阶段 的索引构建方法、基于二阶导数的数据划分方法以及缓存友好的溢出节点设计。 本章首先介绍LISK的整体结构，随后详细介绍TLS的各项优化技术。
2.3.1总体结构
图2.2展示了LISK的索引结构，其由一系列子索引构成。LISK中存在两类 子索引：TLS学习型子索引和B+树子索引，子索引之间通过指针连接形成类似 字典树的整体结构。每个子索引只需要负责检索8字节的数据分片。例如，图中 所示第一层的子索引负责检索0–7字节数据，第二层子索引则负责检索8–15字 节数据。LISK中的子索引基于数据分片转换后的数值进行构建，其中B+树子 索引采用常用的内存B+树结构（节点大小设为1024字节），而TLS学习型子索 引则针对数据分布特点进行了优化，其具体结构和优化设计将在第2.3.2节中详 细介绍。LISK的目标在于利用学习索引结构提升索引的整体读写性能，为实现 这一目标，LISK的结构设计需要解决两个关键挑战：（1）如何选择合理的子索 引结构；（2）如何构建索引。
（1）子索引类型的选择：尽管现有研究普遍认为学习索引的性能优于B+树 索引，但在LISK的结构中情况却有所不同。LISK的每个子索引均基于数据分 片构建，现实中的字符串数据往往分布较为稀疏，且存在前缀倾斜现象，导致每 个子索引中存储的数据量可能非常有限。此外，由字符串分片转换而来的数值数 据分布异常复杂，导致学习索引无法进行有效拟合。相比之下，B+树索引的查 询过程无需考虑数据分布，其查询复杂度主要由数据规模决定，因此数据量越小 其查询效率越高。
由此可见，在LISK结构中，学习索引无法始终均优于B+树索引。为达到 最佳读写性能，LISK需要根据子索引内的数据特征选择合适的子索引结构。分 析表明，B+树索引更适用于数据量较小且分布复杂的数据，而学习索引则适合 数据量较大且易于拟合的情况。LISK则采用基于数据量的方法来确定子索引结 构，当数据量低于设定阈值时，选择B+树作为子索引；否则，采用TLS作为子 索引。在后续的实验评估中，该阈值被设为4096以达到最佳性能（该阈值通过 实验测试得出）。
需要说明的是，LISK中的每一个子索引实际上都是完整的索引结构，其存 放的键为变长键特定的8字节数据分片，值则为指向键值对或者指向下一层子索引的指针。从另一个角度来说，LISK是一种类似Masstree的特殊字典树索引， 其节点跨度为8字节，同时将字典树索引的节点组织成了B+树或者学习索引， 从而实现索引性能的提升。
（2）索引的构建：由于学习索引无法有效支持从零开始插入，所以LISK采 用了批量加载的方式来构建索引。构建过程中LISK首先利用前缀信息对数据集 进行划分，然后在具有相同前缀的子数据集上自上而下递归构建子索引。具体来 说，LISK首先从整个数据集中提取每条记录的首个8字节前缀，将其转换为数 值后去除重复值，从而构建出根部的子索引结构。此时，该前缀信息将整个数据 集划分为多个子数据集，每个子数据集中的数据均共享相同的前缀。随后，在每 个子数据集上继续提取后续8字节的前缀，从而构建下一层子索引。在子索引的 构建过程中，LISK根据每个子数据集内的数据量动态选择合适的子索引类型。
值得注意的是，LISK同样支持从零插入的场景。在这种情况下，LISK会将 每个子索引的初始类型设为B+树，当子索引内存放的数据量达到设定阈值（例 如4096条记录）时再将其替换为学习型子索引TLS。由于模型训练存在较高的 代价，所以LISK在构建阶段主要采用批量加载的策略。
LISK的混合索引结构能够根据数据特征选择合适的子索引类型，从而提升 索引的整体性能。为了进一步降低搜索和空间代价，LISK还使用了后缀压缩技 术[ 41]。该技术的核心思想在于，仅在数据发生前缀冲突时才构建下一层节点，否 则只需要存储后缀信息。举例来说，如果一个键的长度为80字节，且前缀不被 其他键共享，则该键可以直接存放在第一层的子索引中，无需构造10层索引结 构进行存储，查询时，在第一层即可检索到目标数据。该种方法降低了索引的整 体高度，也减少了不必要的节点创建，从而提升了查询效率和空间效率。
2.4 LISK操作算法
本节将介绍LISK各种操作算法的实现细节，包括点查询、插入以及范围查 询操作。
（1）键分片获取与转换：每次进行子索引查询时，首先调用GetSlice()函数 获取当前层（由depth指示当前层数）的键分片，并将该分片转换为数值。由于 节点跨度设置为8字节，因此每完成一次子索引查询，depth就增加8（第10行）， 以便在下一层使用正确的键分片。
（2）子索引查询：子索引内部的查询操作根据子索引类型选择相应的查询函 数。对于B+树子索引，其结构为常见的内存B+树，此处不做详细描述；学习 型子索引TLS的搜索过程将在后文中详细介绍。子索引查询可能返回三种结果： 如果返回下一层子索引根节点的地址，此时查询会继续递归向下进行。如果返回 键的存储地址，表示找到了目标键，查询过程跳出循环并进行验证。如果返回查 询失败，则直接返回NULL（第12-13行）。
（3）最后的验证：当子索引查询返回了键的存储地址时，还需进行最后一步 验证。首先需要通过存储地址获取完整的键（第14行）；然后检查是否存在后缀 压缩，并验证存储键的后缀是否与查询键匹配（第15行）。如果后缀不一致，则 返回NULL；否则，查询成功，返回键的存储地址。
2.5性能评测
本节将对LISK进行全面的性能评测。后续的内容首先介绍实验设置，包括 实验运行环境、对比对象、实验数据集以及实验负载；随后分别评测索引的读写 吞吐、尾延迟、空间效率以及批量加载性能；最后进行索引的敏感度分析并探究 索引的各项设计对性能的影响。
第3章 面向新型NVM的树形索引
3.1 研究动机
3.2 相关工作
3.3 NOBtree 索引结构
3.4 NOBtree 操作算法
3.5 性能评测
3.6 本章小结
第4章面向分离式内存的树形索引
分离式内存（DM）在现代数据中心越来越受到关注，有研究表明，现代的 数据中心中，服务器的内存成本可能占到50%左右，而传统的一体式架构往往 面临内存容量限制和内存利用率低的问题，导致数据中心的总体拥有成本上升。 为了解决这一问题，研究者们提出了分离式内存方案，通过将内存资源与计算资 源进行解耦，实现了内存容量的扩展和资源的高效利用。在分离式内存系统中， 内存资源集中部署于内存节点中，计算资源则集中在计算节点上，二者之间通过 高速网络技术（本论文聚焦使用RDMA技术实现的分离式内存）相互连接，从 而实现资源的解耦。
DM树形索引是研究者们重点关注的研究方向，因为索引是影响系统性能 的关键因素。如今DM树形索引的研究主要关注降低索引同步代价和提升缓存 利用效率两个方面。本论文同样从这两个方面针对分离式内存环境下的B+树 索引进行了优化。具体而言，本论文提出了一种新的树形索引SEPtree（Separate Tree）。SEPtree采用分离式的索引结构，并引入了特殊的逻辑分区技术，完全避 免了DM索引的远程同步开销。同时，SEPtree还提出了一种高并发缓存管理机 制，在保证缓存命中率的前提下，有效缓解缓存替换过程中的并发瓶颈。通过这 几项关键技术，SEPtree有效提升了索引的并发性能。
本章后续内容首先介绍现有DM树形索引面临的主要挑战，从而引出SEP tree的研究动机，然后介绍已有的解决方案。之后详细描述SEPtree的索引结构、 各项优化技术以及具体的索引操作算法。最后在真实的分离式内存环境对其性 能进行全面评测。
4.1研究动机
图4.1展示了DM树形索引的通用结构特点：索引的整体结构存放在内存节 点的远程内存中，计算节点中的线程通过RDMA单边原语实现索引的访问与操 作。为了提升读写效率，计算节点通常会在本地维护一份索引缓存以加速索引操 作。在这种架构下，索引操作主要面临两个关键挑战：一是不同计算节点间的远 程同步问题，二是缓存管理问题。
远程同步问题主要源自于不同计算节点之间的数据冲突。由于DM索引结 构完全存放在远程内存中，并被多个计算节点共享访问，因此在进行并发操作 时会产生数据冲突。为了保证索引操作的正确性，DM索引通常使用锁机制保护 索引结构，确保并发操作之间的正确同步。在传统的内存环境中，索引通常使用 内存原子指令实现互斥锁，从而避免数据竞争；而在分离式内存中，索引则依赖。
DM树形索引的缓存管理面临两个主要挑战：（1）不同计算节点之间的缓存 一致性；（2）缓存管理过程中的并发瓶颈问题。由于多个计算节点可能会同时缓 存相同的索引节点，因此索引操作过程中需要保证缓存的一致性。但传统的缓存 一致性协议（如目录协议或广播协议）在DM架构中无法使用，因为这些协议需 要频繁的RDMA通信，从而带来极高的开销。因此，目前常用的策略是仅缓存 索引的内部节点，并且不保证强一致性。这样做的主要依据是：树形索引内部节 点的缓存过期现象不会影响索引操作的正确性，只会导致节点定位错误，而该种 错误可以通过重试机制进行纠正。然而使用该种方法也限制了索引的性能上限， 因为每次索引操作需要至少一次远程访问以获取叶子节点。缓存管理对索引的 并发性能也会产生较大影响，因为每次索引操作都需要优先访问缓存，而缓存的 换入/换出操作会涉及缓存管理结构的修改[ 89]，容易造成并发访问瓶颈，从而影 响索引的性能。
针对这两个挑战，本论文设计了一种新型树形索引SEPtree。SEPtree的主要 设计目标为：（1）消除索引操作中的远程同步代价；（2）提升索引缓存的并发访 问性能。为了达到这两个目标，SEPtree提出了分离式索引结构，同时引入了逻 辑分区技术和高并发缓存管理机制，从而提升索引的并发性能。
4.2相关工作
在分离式内存系统的概念被提出之前，已经存在众多针对RDMA网络设计 的分布式树形索引结构[ 45,83,116-117]，但这些索引大多采用远程过程调用（RemoteProcedure Call，简称RPC）来实现索引操作。RPC需要使用服务器的CPU资源 执行命令，这在分离式内存架构下无法有效实现，因为存放索引的内存节点通常 只提供有限的计算资源，难以满足高并发访问的需求。
2019年，Tobias等人[ 83]探讨了基于RDMA技术的分布式B+树索引的设 计，并提出了两种实现方法：CG（Coarse-Grained Distribution）模式和FG（Fine Grained Distribution）模式。CG模式将整个索引划分为多个分区，每个分区存放 在同一内存服务器中，并通过RPC实现索引操作；FG模式则将索引的各个节点 随机分散存储在不同的内存服务器中，完全依赖RDMA单边原语来完成索引操 作，并利用RDMA原子指令实现互斥锁以支持并发写操作。对于分离式内存系 统而言，FG模式更符合系统特点，其结构能够被轻易移植到分离式内存系统中， 因此其设计思路也被后续的DM树形索引研究工作广泛采用。
Sherman[ 84]针对FG模式下的索引写性能进行了优化，其针对的主要问题是 低效的RDMA锁机制导致的索引并发写入瓶颈。Sherman设计了一种高效的锁 机制，利用RDMA网卡的硬件资源和多级锁表实现高效并发操作。Sherman针 对锁机制的优化主要有两点：首先其利用RDMA网卡上的片上内存加速锁操作， 将B+树节点中的锁数据结构分离出来并存放在网卡内存中，从而显著降低加解 锁的开销；其次Sherman还在计算节点本地维护锁表协调本地线程之间的冲突， 并支持锁资源的移交，进一步减少远程加锁的代价。此外，Sherman将内部节点 缓存在本地，并使用跳表结构维护靠近根部的两层节点，从而加速索引操作。
SMART[ 85]则关注B+树索引在分离式内存环境下的读写放大问题。作者认 为，在分离式内存环境中，B+树的每次操作都需要传输一个完整的索引节点，造 成了严重的读写放大并且会迅速耗尽内存节点的网络带宽。因此SMART将一种 常用的高性能字典树索引ART移植到了分离式内存中，利用ART节点空间占用 小的优势有效缓解了读写放大问题。SMART同时提出了一种混合并发机制，允 许内部节点进行无锁操作，从而提升索引的并发性能。SMART同样将内部节点 缓存在本地以加速索引操作。
CHIME[ 87]针对SMART的缓存效率问题进行了改进。虽然SMART的小节 点能够有效缓解操作过程中的读写放大问题，但是过多的索引节点会占用大量 内存空间，从而影响缓存效率，后续的研究工作[ 88,92]表明SMART在本地缓存 空间不足的条件下性能严重受限。CHIME则在解决读写放大问题的前提下提升 缓存效率，其采用了B+树与跳房子哈希相结合的结构：CHIME的内部节点采 用B+树节点结构，而叶子节点被组织成了跳房子哈希表。CHIME的B+树结构 能够有效减少索引节点的数量，从而提升缓存的利用效率；哈希表设计的叶子节 点结构则缓解了读写放大问题。CHIME设计了多粒度的乐观并发控制机制以提 升索引的并发性能，还提出了一系列优化方案以降低混合结构带来的操作代价。
4.3 SEPtree索引结构
SEPtree是一种面向分离式内存的类B+树索引，其主要目标是降低DM索引 中高昂的远程同步代价和缓存管理开销，从而提升索引的并发读写性能。SEPtree 通过三项关键技术实现了这一目标，包括分离式的索引结构、无冲突的逻辑分区 以及高并发的缓存管理。本节首先介绍了SEPtree的特殊索引结构，随后详细介 绍了其逻辑分区策略以及高性能缓存管理机制。这些设计使得SEPtree能够在分 离式内存系统中实现更高的并发读写性能，为DM树形索引提供了一种高效的 解决方案。
4.4 SEPtree同步机制
得益于无冲突的逻辑分区技术，SEPtree的同步机制被大大简化，所有的操 作均不需要考虑远程内存结构的同步，避免了RDMA锁操作。SEPtree的同步机 制被限制在了计算节点中的Ltree和Rtree的缓存结构中，本节将对SEPtree的同 步机制进行详细的介绍，主要包括Ltree的同步、Rtree缓存节点的同步、地址映 射表的同步以及冷却状态表的同步。
4.5 SEPtree操作算法
4.5.1点查询
算法4.1展示了SEPtree的点查询整体流程，该流程主要分为两个部分：Ltree 查询和Rtree查询。算法首先查询Ltree获取目标Rtree根节点，具体查询流程在 第4.3.1节中已经介绍，此处不再赘述。
获得目标根节点之后则进入Rtree的查询阶段（第8-45行），整体流程与传 统B+树查询流程相似，需要注意的主要有以下几点：（1）首先，每次对节点进 行搜索前，需要在本地缓存中查找节点数据；如果缓存未命中，则通过RDMA 读操作将该节点读入缓存（第10-13行，29-32行）；（2）其次，整个查询流程 严格遵守乐观锁耦合机制保证操作的正确性（第18-21行，24-26行，33-36行， 38-40行，42-44行）；（3）最后，查询算法需要对根节点进行特殊处理，当发现 查询键大于当前根节点的最大值时（第14-17行），需要通过指针跳转到兄弟节 点。这是为了应对Ltree插入失败可能引发的根节点定位错误，确保最终能够定 位到正确的叶子节点。
由于SEPtree使用了指针混写技术，search_in_cache()操作并非每次都需要 通过地址映射表获取缓存地址。如果指针被混写，则仅需通过位操作清除混写 标识，即可获取缓存节点的地址，这显著降低了缓存访问代价。由于每个Rtree 节点会被它的父亲节点（对于Rtree的根节点来说则是Ltree）和兄弟节点同时 指向，为了保证索引操作的正确性和操作逻辑的清晰，并降低解除指针混写的代 价，所有兄弟指针均不会使用指针混写技术，确保从父亲节点和兄弟节点获得的 地址保持一致。
从整个查询算法可以看出，SEPtree几乎所有的操作均在计算节点本地完成， 只有在缓存缺失时才会触发RDMA读取操作（第5行），得益于SEPtree分离式
4.5.2插入
SEPtree的插入算法主要包括三个阶段：（1）通过查询Ltree定位目标根节 点；（2）获得目标根节点之后进入Rtree插入流程；（3）根据Rtree插入的结果， 执行Ltree的插入并判断是否需要执行Ltree的重建过程。
第一阶段的流程不再赘述。对于第二阶段，插入操作可能会导致节点分裂， 因此从根节点到叶子节点的遍历过程中，算法会检测沿途节点是否已满，如果发 现某节点已满，则立即执行节点分裂操作，将分裂生成的新节点插入父节点中， 并从根节点重新开始插入过程。需要注意的是，分裂出的新节点首先被存放在远 程内存中，不会立即被缓存。整个插入流程遵循乐观锁耦合机制。在进行节点分 裂时先对父节点加锁，再获取当前节点的锁；分裂完成后按相反顺序解锁，以保 证操作正确性。
第三阶段根据Rtree插入的结果判断是否需要执行Ltree的插入与重建，Rtree 的插入有三种结果：（1）Rtree根节点未发生分裂，此时无需进行任何操作。（2） Rtree根节点发生分裂，但是其高度尚未达到设定阈值，此时生成新的根节点，并 在Ltree中将原根节点地址更新为新的根节点地址。（3）Rtree根节点发生分裂， 且高度已经达到设定阈值，此时则需要将分裂出的根节点插入Ltree中。
Ltree的插入可能会失败，为了加速后续Ltree的重建过程，插入失败的键 值数据将被保存在一个临时数组中。该临时数组用于存储所有未能成功插入的 Rtree根节点信息，在Ltree重建时仅需将临时数组中的数据与现有Ltree中的数 据进行合并即可获取全部的Rtree根节点信息，避免了链表遍历带来的高昂扫描 开销。
此外，在Rtree的插入过程中，还会记录通过兄弟根节点跳转以定位正确根 节点所需的步数。当平均跳转步数达到设定阈值（该阈值通过实验设为1，即平 均每次插入都需要通过兄弟根节点跳转时），表明Ltree插入失败对索引性能产 生了较大影响，此时会触发Ltree的整体重建操作，以保持索引性能的稳定性。
4.6性能评测
本节将对SEPtree进行全面的性能评测。接下来首先介绍实验设置，包括运 行环境、对比对象和实验负载等；之后展示实验结果，包括索引的读写吞吐以及 尾延迟；最后对索引进行敏感度分析。
4.7本章小结
本章提出了一种新型分离式内存索引SEPtree，其主要设计目标在于提升B+ 树在分离式内存系统中的并发性能。为实现这一目标，SEPtree采用了三项关键 技术：分离式的索引结构、无冲突的逻辑分区以及高并发的缓存管理。SEPtree 特殊的索引结构结合分区机制使得其完全避免了远程RDMA锁机制的使用，将 所有的同步局限在了计算节点本地，简化了同步机制，从而提升了索引在高并发 环境下的性能。同时，其使用了高并发的缓存管理，有效缓解了缓存换入/换出 过程中的并发瓶颈，进一步提升了的索引的并发性能。
本章详细介绍了SEPtree的整体索引结构、各项关键技术的实现原理以及索 引操作流程，并在多种工作负载下对其性能进行了全面的实验评估。实验结果表明，与最先进的DEX和Sherman相比，SEPtree在读写性能上取得了较大优势， 充分验证了其各项设计的有效性。
第5章总结与展望
5.1论文工作总结
近年来，上层应用持续攀升的性能需求使得内存数据库受到了越来越广泛 的关注，内存数据库将所有数据存放在内存中，从而实现高读写吞吐、低访问延 迟，然而受限于传统DRAM内存的存储密度问题和计算机系统架构问题，内存 数据库的存储容量始终无法满足快速增长的数据规模，新型内存技术（如非易失 内存、分离式内存）的发展为内存数据库带来了新的机遇：非易失内存具有更高 的存储密度，并支持数据的持久存储；分离式内存则打破了传统的一体式服务器 架构，为创建大规模内存存储系统提供了可能。内存索引作为内存数据库的关键 组件，其读写性能是系统整体性能的关键因素，因而受到广泛的关注。本论文针 对树形索引进行了研究，以提升树形索引的读写性能为目标，提出了三种新型索 引结构。具体而言，针对传统内存DRAM中的树形索引，论文提出了一种支持 变长键的学习索引LISK；针对非易失内存NVM中的树形索引，论文提出了一 种NUMA优化的B+树索引NOBtree；针对分离式内存中的树形索引，论文提出 了一种高并发B+树索引SEPtree。本论文的主要研究内容可以总结为以下三点：
（1）现实应用中字符串等变长键十分常见，但受限于模型拟合能力，学习索引
无法有效支持变长键的检索，从而限制了其应用范围。针对学习索引的变 长键支持问题，本论文提出了一种新的学习索引LISK。LISK提出了基于 混合节点的字典树索引结构解决学习索引无法检索变长键的问题，并设计 了适应变长键数据分布的学习型子索引TLS以提升索引整体性能。TLS采 用两阶段的索引构建方法，并结合基于二阶导数的数据划分方法，有效提 升了对复杂数据分布的拟合能力；同时，TLS采用了一种缓存友好的溢出 节点设计，有效降低了局部搜索代价。实验结果表明，LISK在4种真实数 据集和6种不同的读写负载下均取得了优异的性能，相较于最先进的字典 树索引和变长键学习索引，LISK的读写吞吐平均提升了1倍（最高提升 了6.87倍）；与最先进的变长键学习索引LITS相比，读写吞吐平均提升了 42.8%（最高提升了90.6%）。
（2）跨节点NVM访问的高昂代价使得NVM索引面临严重的NUMA效应，从而严重限制了索引的并发性能。为了解决这一问题，本论文提出了一种面 向纯NVM架构的B+树索引NOBtree。NOBtree采用解耦合的两层索引结 构，并提出了上层索引的节点副本机制和下层索引的节点迁移机制，有效 减少远程NVM访问；同时，NOBtree还设计了专用的NUMA感知的NVM 分配器，以支持各项机制的有效实现，并提升索引的插入性能。实验结果表明，与现有最新的NVM索引相比，NOBtree的读性能平均提升了1.5倍 （最高提升了2.2倍）；写性能平均提升了2.3倍（最高提升了4.1倍）。
（3）受限于高昂的远程同步代价，DM索引常面临严重的并发瓶颈问题。针对
DM索引的并发性能瓶颈，本论文提出了一种面向分离式内存的B+树索 引SEPtree。SEPtree采用分离式的索引结构，并引入了无冲突的逻辑分区 技术，简化了索引的同步机制，完全避免了远程同步，从而提升了索引的 并发性能；同时，SEPtree还设计了高并发的缓存管理机制，有效缓解了缓 存换入/换出过程中可能出现的并发瓶颈问题。实验结果表明，与其他最先 进的DM索引相比，SEPtree的读性能平均提升了1.5倍（最高提升了2.5 倍）；写性能平均提升了1.9倍（最高提升了3.6倍）。
5.2未来工作与展望
本论文针对不同内存环境中的树形索引技术进行了研究，并提出了三种不 同的索引设计以提升索引的读写性能，但是这些工作还存在值得改进的地方。在 本论文的研究基础之上，进一步的研究工作包含以下几个方面： （1）LISK的多线程支持与空间效率优化。目前的LISK仅支持单线程操作，这限制了其在多核环境下的应用。未来工作可通过引入细粒度锁和乐观并发 控制等机制，实现并发版本的LISK，从而提升其实用性。此外，LISK虽然 在读写性能上取得了较大的优势，但是其空间效率与经过内存优化的字典 树索引还存在差距，在未来的工作中，可以通过引入前缀压缩和节点编码 等技术进一步提升索引的空间效率。同时，目前的LISK仅在传统的DRAM 内存上进行了实现，未来可以考虑将其与NVM技术或者DM技术结合，以 适应混合内存系统架构。 （2）NOBtree在混合内存架构下的进一步优化。NOBtree在纯NVM架构下对索引的NUMA效应进行了优化，但是目前使用NVM的存储系统中通常使 用DRAM+NVM的混合内存架构，在未来的工作中，NOBtree也可以利 用DRAM进行进一步优化，例如上层索引存放在DRAM中，与Nap机制 结合等。
（3）SEPtree的性能优化和负载均衡问题。目前SEPtree在计算节点本地维护的
是一棵简单的k-叉树，虽然具有良好的性能和空间效率，但是仍有提升空 间。未来可以将学习索引与现有设计结合，利用学习索引高读写性能和低 空间代价的优势，进一步优化索引的读写性能。同时，SEPtree所采用的分 区技术在实际应用中可能面临负载不均衡的问题，如何在计算节点之间实 现负载均衡也是一个重要的研究方向。
（4）真实系统环境的集成与应用。目前本文提出的三种索引技术均未在真实的
数据库系统环境中实现，在未来的研究过程中可以将其集成在开源的数据 库系统中（例如PostgreSQL、OpenGauss数据库等），并使用真实世界中的 负载，在不同的运行平台上进行测试与评估，以验证索引的鲁棒性与普适 性。
（5）新型硬件的发展与适配。随着CXL等新一代互联技术的发展，在未来的系统中，内存容量不再受到限制，内存访问也不再是CPU的专长，GPU、 FPGA等异构处理器都能够访问统一的内存设备，并且处理器之间的缓存 一致性将对用户透明化。这为树形索引的发展提供了巨大的机遇，如何利 用大容量的内存，同时充分利用多样的处理器设备的特性，以构建出高并 发性能、高内存效率的内存索引，为大规模内存存储系统提供坚实的性能 保障，也是未来研究的重要方向。
参考文献 略