Paper

摘要

B树是数据库和存储系统中内存索引的首选数据结构。B树支持点操作（即插入和查找）以及范围操作（即迭代器和映射）。然而点操作和范围操作之间存在权衡。点操作的最佳节点大小远小于范围操作的最佳节点大小。现有的实现通常使用相对较小的节点大小，以提高点操作的速度。代价是降低了范围操作的吞吐量。

本文提出了BP树，它是B树的一种变体，克服了传统B树中长期存在的点操作与范围操作的权衡问题。在BP树中，叶子节点的大小远大于内部节点，以支持更快的范围扫描。为了避免因叶子节点过大而导致点操作变慢，本文引入了一种新的插入优化数组，称为缓冲分区数组（buffered partitioned array，BPA），以高效地组织叶子节点中的数据。BPA通过延迟排序数组中的键来支持快速插入。这使得BP树在提供更快的范围操作的同时，也能加快点操作的速度。

实验表明，在48个超线程上，基于YCSB生成的工作负载下，BP树在点操作吞吐量方面表现与Masstree和OpenBw-tree这两个最先进的内存键值存储系统相当或更快（0.94到1.2倍）。在短扫描的YCSB工作负载下，BP树比Masstree快约7.4倍，比OpenBw-tree快1.6倍。此外，本文扩展了YCSB以添加大型范围工作负载，这在数据库应用程序中很常见，并显示BP树比Masstree快30倍，比OpenBw-tree快2.5倍。

本文还提供了一个并发B+树的参考实现，发现BP树在点操作方面比B+树的最佳配置快（提高了1.03到1.2倍），同时在短范围操作方面表现相似（约为0.95倍），在长范围操作方面更快（约为1.3倍）。

背景

• 传统B+树在点操作和范围操作性能之间存在tradeoff，本文目标是能够克服该tradeoff

方法

• 每个节点当成一棵2层的子B树以及日志 (节点更大，减少范围操作访问节点数)
• 日志满了flush到子B树 (日志利于点操作)
• 节点满了就分裂