有哪些有趣的B树优化实验案例可以分享？

本文共计4244个文字，预计阅读时间需要17分钟。

LSM-tree和B+-tree是两种流行的数据库索引结构。LSM-tree在读写性能上有其独特优势，能够换取更小的写放大以及更低的存储成本，但前提是建立在对读取性能的适当权衡。

作为目前数据库引擎的两种主要数据结构，LSM-tree和B+-tree在业界已经有非常广泛的研究。相比B+-tree，LSM-tree牺牲一定的读性能以换取更小的写放大以及更低的存储成本，但这必须建立在已有的HDD和SSD的基础上。

探索前沿研究，聚焦技术创新，本期DB·洞见由腾讯云数据库高级工程师王宏博进行分享，主要介绍一篇2022年FAST的论文，主题为“基于硬件透明压缩的B+树优化”。本次分享的论文针对可计算存储SSD（支持硬件透明压缩）提出了三种有趣的设计方法，从而极大地减少了B+-tree的写放大（10X）以使其接近甚至超越LSM-tree。以下为分享实录：

完整视频：v.qq.com/x/page/p3342om19py.html

一、论文简介

本期分享的是2022年FAST的一篇论文，主题是基于硬件透明压缩的B+树优化，该论文在内容上主要分为三个部分：

第一部分是背景介绍，作者分别介绍了现有的B+树及其软件压缩、存储硬件透明压缩、B+树和LSM-tree的简要对比以及B+树写放大的构成分析。

第二部分是算法部分，作者针对性地提出了三种设计来优化B+树的写放大:
确定性的page shadowing来解决页面原子写引入的写放大。
通过页面本地增量日志来减少刷脏页引入的写放大。
通过稀疏日志来减少redo日志引入的写放大。
第三部分是实验部分，作者通过前面所述的三个方法实现了一个新的B+树（我们称之为B−-tree为以示区别），并详细比较了多种条件下的测试结果。