翻译内容
3. Cost-Performance and the Multi-Component LSM-Tree
本章分析LSM执行性能，以两个组件的LSM开始。
我们将lsm-树与提供相同的插入功能的b-树进行类比，比较用于大量新插入的I/O资源。（有道翻译）
在第五章讨论，其他基于磁盘的插入操作方法于B-tree的I/O性能消耗情况。
最主要比较LSM-tree和B-tree的原因是容易比较，都是数据索引包含在叶子节点，上层目录信息书一个page大小的节点。（待确定翻译）
通过类比效率较低但易于理解的b -树行为，可以有效地说明对lsm -树插入新条目的I/O优势的分析。（有道翻译）
在接下来的3.2节中，我们比较了I/O插入成本，并演示了由两个组件组成的lsm树与b树的成本的小比例是两个因素的乘积。第一个因素，COSTπ/ cost，对应于在lsm树中通过在多页块中执行所有I/O而获得的优势，从而通过节省大量寻道和旋转延迟时间而更有效地利用磁盘臂。cost π表示作为多页块的一部分在磁盘上读或写一个页的磁盘代价，而cost p表示随机读或写一个页的代价。决定LSM-树和b -树之间I/O成本比率的第二个因素为1/M，表示在合并步骤中获得的批处理效率。M是从C0合并到C1页大小的叶节点的平均条目数。在每个叶节点插入多个条目比(大)b树更有优势，在b树中，插入的每个条目通常需要两个I/ o来读写它所在的叶节点。由于5分钟规则，在示例1.2中，从B-tree中读入的叶页不太可能在它留在缓冲区的短时间内被重新引用，以便进行第二次插入。因此，在B-tree索引中没有批处理效果:读入每个叶节点，执行插入新条目的操作，然后再次将其写出来。然而，在lsm -树中，只要C0组分相对于C1组分足够大，就会有重要的批处理效应。例如，对于16字节的索引项，我们可以预期在一个完全打包的4kbyte节点中有250个条目。如果C0组件的大小是C1组件的1/25，那么在一个节点I/O期间，我们预计(大约)将有10个新条目进入每个250个条目的新C1节点。显然，由于这两个因素，lsm -树比b -树具有效率优势，而“滚动合并”过程是获得这种优势的基础。（有道翻译）
对应于多页块与单页I/O的效率比率的因子COSTπ/ cost是一个常数，我们不能对lsm树结构进行任何操作来对它产生任何影响。而归并步骤的配料效率1/M与C0和C1组分的大小之比成正比;与C1组分相比，C0组分越大，合并效率越高;在某种程度上，这意味着我们可以通过使用更大的C0组件来节省磁盘臂成本，但这需要更大的内存成本来包含C0组件。有一个优化的大小组合，可以最小化磁盘臂和内存容量的总成本，但是对于大型C0来说，这个解决方案在内存方面可能非常昂贵。正是这种考虑激发了对多组件lsm树的需求，这将在第3.3节中进行研究。一个有三个组件的lsm树有内存驻留组件C0和磁盘驻留组件C1和C2，其中组件的大小随着下标的增加而增加。在C0和C1之间有一个滚动合并过程，在C1和C2之间也有一个单独的滚动合并过程，每次较小的组件超过其阈值时，将条目从较小的组件移动到较大的组件。三组分lsm树的优点是通过选择C1来优化C0与C1的组合比例和C1与C2之间的补间，可以在几何上提高批处理效率。因此，C0内存组件的大小与总索引的比例可以大大降低，从而大大提高了成本。（有道翻译）
第3.4节导出了一个数学过程，该过程用于获得多组件lsm树中不同组件的最佳相对大小，以最小化内存和磁盘的总成本。（有道翻译）
todo：自己翻译，仔细看一遍
