ZB~(+)-tree：一种ZNS SSD感知的新型索引结构

作者：刘扬; 金培权

来源：计算机研究与发展, 2022, 1-15.

• ZNS SSD
• B+树
• 数据库索引
• +-tree&apos
• ,&apos
• &apos
• SYiY1k_y1FZilSnX9Qo_KjFQ_oJucGj7tl8Emuj9ch6pUTof7T7jdyUPjSQe2tzG&apos
• )
• &#xA
• &quot
• &gt
• CoW B+-tree
• 分区存储

ZNS SSD是近年来提出的一种新型固态硬盘（solid state drive，SSD），它以Zone（分区）的方式管理和存取SSD内的数据.相比于传统SSD，ZNS SSD可以有效提升SSD的读写吞吐，降低写放大，减少SSD的预留空间.但是，ZNS SSD要求Zone内必须采用顺序写模式，并且Zone上的存储分配、垃圾回收等任务都需要用户自行控制.ZNS SSD的这些特性对于传统数据库系统的存储管理、索引、缓存等技术均提出了新的挑战.针对如何使传统的B+-tree索引结构适配ZNS SSD的问题，提出了一种ZNS SSD感知的新型索引结构——ZB+-tree (ZNS-aware B+-tree).ZB+-tree是目前已知的首个ZNS SSD感知的索引.它以B+-tree为基础，利用ZNS SSD内部支持少量随机写的常规Zone（conventional zone）和只支持顺序写的顺序Zone（sequential zone），通过常规Zone来吸收对Zone的随机写操作.ZB+-tree将索引节点分散存储在常规Zone和顺序Zone中，并为2种Zone内的节点分别设计了节点结构，使ZB+-tree不仅能够吸收对索引的随机写操作，而且又可以保证顺序Zone内的顺序写要求.在实验中利用null＿blk和libzbd模拟ZNS SSD设备，并将现有的CoW B+-tree修改后作为对比索引.结果表明，ZB+-tree在运行时间、空间利用率等多个指标上均优于CoW B+-tree.

• 单位
  中国科学院; 中国科学技术大学