3.3 Multi-Component LSM-Trees
对于给定的LSM-tree，参数M代表了rolling merge过程中插入到每个C1树的叶子节点中的C0树的平均记录数。在merge到C1树的节点中之前，这些新记录会首先在C0中积累一段时间，因此通常我们认为M是大于1的。但是，通过公式(3.2){! M=(Sp/Se)·(S0/(S0+S1))}能够看出，如果与C0树相比C1树足够大，或者是单条记录非常大以至于单个page中只能放下很少的记录，那么M的值就可能会小于1。这样的一个M值意味着，为了能将C0中的一条记录移出内存将不得不读入多个C1的page。根据公式(3.4){! COST(LSM-ins)/ COST(B-ins)=K1·(COSTπ/COSTp)·(1/M)}，在M< K1·(COSTπ/COSTp)的情况下，将会抵消掉multi-page的批处理效果，此时对于插入操作来说使用B-树要比使用LSM-tree更划算。
为了避免得到一个太小的M值，对于两组件LSM-tree来说，只能通过增加C0对C1的相对大小来解决。考虑一个叶子节点总大小为S(S=S0+S1，一个近似稳定的值)的两组件LSM-tree，同时假设新节点以一个不变的速率R(以bytes/秒为单位)插入到C0中。为简化起见，我们假设在被移入到C1中之前，没有记录会被删除，因此这些记录也必须以与它们被插入到C0中的相同的速率被移入到C1，以保证C0的值总是维持在阈值大小附近。(由于总大小S基本上是不变的，这也暗示着与插入到C0的速率相比，也需要一个与之平衡的从C1中进行删除的速率，比如可能使用了断言式删除)。当我们改变C0的大小时，也会影响到merge游标的循环周期。由于到C1的移出速率(每秒的字节数)需要保持不变，这样就要求游标每秒所扫描的数据保持不变，在C0大小减少时，很明显游标从最小值到最大值的扫描频率必须要加快；这样就导致C1中用于rolling merge过程的multi-page block IO也必须要加快。极端情况下，比如C0大小只能存下一条记录，这样对于每个新插入的记录，都需要完整地将C1扫描一遍，这将产生大量的IO需求。此时，这种将C0和C1进行merge的方式，与B-树中为每个新插入记录只需访问相关节点的方式相比，将会带来更大的性能瓶颈。与之相比，C0越大将越能增大merge游标的扫描周期，从而降低插入所需的IO开销。但是，这也会增加所需的内存开销。
通常情况下，可以通过最小化LSM-tree的总开销(用于C0的内存开销加上用于C1的磁盘空间/IO能力开销)来确定C0的大小。为了达到这种最小化的开销，我们通常从一个比较大的C0组件开始，同时让C1组件大小接近于所需空间的大小。在C0组件足够大的情况下，对于C1的IO压力就会很小。现在，我们可以开始试着通过减少C0的大小，来在昂贵的内存和廉价磁盘之间进行权衡，直到减低到当前C1所能提供的IO能力完全被利用为止。此时，如果再降低C0的内存开销，将会导致磁盘存储开销的增加，因为需要扩充C1组件以应对磁盘负载的增加，最终将会达到一个最小开销点。现在，对于两组件LSM-tree来说，这个典型的C0组件大小从内存使用的角度上看开销仍是比较高的。一个改进的方案是，采用一个三组件或者多组件LSM-tree。简单来说，如果C0太大以至于内存开销成为主要因素，那么我们可以考虑在两组件LSM-tree的C0和C1之间加入一个中间大小的基于磁盘的组件，这就允许我们在降低了C0大小的同时还能够限制住磁盘磁臂的开销。
通常，一个具有K+1个组件的LSM-tree具有组件C0,C1,C2…,Ck-1和Ck，组件大小依次递增；C0组件是基于内存的，其他都是基于磁盘的(对于那些经常访问的页面来说会被缓存在内存中)。在所有的组件对(Ci-1,Ci)之间都存在一个异步的rolling merge过程，它负责在Ci-1超过阈值大小时，将记录从较小的组件中移入到较大的组件中。当一个生命期很长的记录被插入到LSM-tree之后，它首先会进入C0树，然后通过这一系列的K个异步rolling merge过程，最终将被移出到Ck。
这里我们主要关注插入性能，因为我们假设LSM-tree通常使用在插入为主的场景中。对于三组件或者多组件LSM-tree来说，查找操作性能上会有降低，通常一个磁盘组件将会带来一次额外的页面IO。
3.4 LSM-trees：Component Sizes
在本节中，我们将会推导出具有多个组件的LSM-tree插入操作的IO开销，同时会在数学上论证如何来为各个组件选择最优的阈值大小。同时会对例3.3进行一些扩展，用来说明B-树的系统开销，采用两组件LSM-tree所带来的改进后的系统开销，以及三组件LSM-tree带来的更大的节省。
我们将LSM-tree组件的大小，S(Ci)，定义为该组件叶子级别的记录的字节数；同时用Si来作为组件Ci的大小的缩写，S(Ci)=Si，同时S代表所有组件的叶子级别的记录的总大小，S=Sum(Si)。我们假设对于C0来说具有相对平稳的插入速率R，单位是bytes/秒，为了简化起见，假设所有新插入的记录都会存活下来并会通过一系列的rolling merge步骤被移出到Ck。同时假设组件C0,C1,C2…,Ck-1，都具有一个与当前分析所确定的最大阈值近似的大小。同时假设组件Ck具有一个相对稳定的大小，因为在一定的时间段内，删除会将插入抵消掉。
给定一个具有固定总大小为S及C0组件大小为S0的K组件LSM-tree，该树就可以通过变量ri(i=1,…k，代表了相邻组件的大小之比，ri=Si/Si-1)来完整地描述了。如下所述，执行一个组件对(Ci-1,Ci)之间的正在进行中的merge操作的页面IO频率可以表示为R(向C0中的插入的频率)和ri的函数。同时我们假设不同组件的blocks将会混合的方式来使用不同的磁盘以达到磁盘磁臂利用率的平衡，这样最小化H就等价于最小化总的磁盘磁臂开销(至少在磁盘磁臂开销而非磁盘容量在成本中起决定性作用的情况下是这样的)。这样对于给定的R，找到可以使总的IO请求率H最小化的ri值的问题，就变成了一个标准了微积分最小化问题。在总大小S固定不变的假设下，由于ri值之间的复杂的递归关系将会使它变成一个很难解的问题。但是如果我们假设Sk是固定不变的(S0也是固定不变的)，如Theorem3.1，当所有的ri值等于某个常数r时，就可以取得最小值。同时我们也通过Theorem3.2给出了在总大小S为常量时的，关于ri值的一个更为精确的解，同时也可以看到对于ri所取常量r值，基本上已经给出了非常类似的结果。假设所有的ri都取r值，那么就有Si=(r^i)·S0。同时总大小可以表示为各组件的大小之和，S=S0+r·S0+(r^2)·S0+…+(r^k)·S0，因此我们就可以用S和S0来表示r。
根据Theorem3.1，对于给定的Sk，S0和插入频率R，为了最小化多组件LSM-tree的总的IO频率，我们需要让最大组件Sk和最小组件S0之间的组件大小具有几何级数的增长关系。另外我们将会发现，对于两组件LSM-tree的情况，如果我们令R和Sk保存不变，而允许S0可变，那么H就可以表示为S0的函数，同时随着S0的减小H会增大。现在我们可以通过改变S0的大小，来最小化LSM-tree的总开销(内存+磁盘磁臂开销)。例3.3演示了如何根据给定数目的组件来获得最优的总开销。现在总开销中剩下的唯一的自变量就是组件数目，K+1了。在本节的最后我们会讨论如何调节这个值。
Theorem3.1 给定一个最大组件大小为Sk，插入频率为R和内存组件大小为S0的具有K+1个组件的LSM-tree，在比率ri=Si/Si-1等于同一个值r时，执行所有merge的总的页面IO频率H将可以取得最小值。这样总大小S就可以表示为各组件大小之和：
(3.5) S=S0+r·S0+(r^2)·S0+…+(r^k)·S0
这样我们就可以将r用S和S0表示出来。类似的，总的页面IO频率H可以表示为：
(3.6)H=(2R/Sp)·(K·(1+r)-1/2)，Sp代表每个页面的字节数
证明：因为我们已经假设在记录到达组件Ck之前都不会删除，很明显从组件Ci-1到Ci的rolling merge过程的记录移出率应与插入到C0的频率R(以bytes/秒为单位)是一致的，对于所有的i，0<i<=K。考虑Ci-1为磁盘组件的情况，从Ci-1到Ci的rolling merge过程将会包含从Ci-1中以每秒R/Sp个page的multi-page block读取，此处Sp代表每个页面的字节数(通过假设所有碰到的记录都会从Ci-1中删除，我们根据R计算出了每秒从Ci-1中移出的记录数目；在普通情况下，其他的假设也是可能的)。该merge过程还会包含从Ci中以每秒ri·(R/Sp)个page的multi-page block读取(这是因为rolling merge游标在扫描到的Ci中的page个数是Ci-1中的ri=Si/Si-1倍)。最后该merge过程还会引入每秒(ri+1)·(R/Sp)个page的multi-page磁盘写入来将属于Ci的merge出的新数据写出。需要注意的是，在这里我们考虑到了因为merge引起的Ci组件的增大{!数据从ri·(R/Sp)变成了(ri+1)·(R/Sp)个page}。将所有磁盘组件的Ci对应值相加，就可以得到总的multi-page IO大小H(以每秒的pages数为单位)：
(3.7)H=(R/Sp)·((2·r1+2) + (2·r2+2) + … +(2·rk-1+2) + (2·rk+1))
每一项的(2·ri+k)代表了在组件Ci上的所有IO：ri·(R/Sp)用于为从Ci-1到Ci的merge读入属于Ci中的数据，(ri+1)·(R/Sp)用于为该merge将数据写出到Ci，而R/S0则用于为从Ci到Ci+1的merge而读入属于Ci的数据。很明显对于C0来说，没有该项开销，而对于Ck来说则没有最后的那一项R/S0。因此公式(3.7)可以重新改写为：
(3.8)H=(2R/Sp)( Σ(ri)+k-1/2)，i为[1…k]
我们希望可以在如下条件下：Π(ri)=(Sk/S0)=C，, i为[1…k]{!根据之前的假设，我们知道S0和Sk均为常数，而Sk=(r1·r2…rk)·S0，故(r1·r2…rk)也是一个常数}，可以最小化该函数值。为了解决这个问题，需要最小化Σ(ri)，我们将rk使用C·Π(1/ri)，i为[1…k-1]来替换掉{!根据Π(ri)=C，即可得rk= C·Π(1/ri)}。然后对每个自变量rj，j=1,…k-1计算其偏导数，同时令它们等于0，我们将会得到如下形式的一系列等式：0=1-(1/rj) C·Π(1/ri)，i=1,…k-1，很明显，当所有的rj(包括rk)等于C·Π(1/ri) 时，i=1,…k-1，或C^(1/k)时有解。
{!上面的问题本质上是如下的一个问题，K个正数的乘积为一定值，求这K个数的和的最小值，具体推导过程如下：
Σ(r1…rk)
= Σ(r1…rk-1)+ C·1/Π(r1…rk-1) //使用C·Π(1/ri)替换rk
= Σ(r1…rk-1)+ 1/rj·C·1/Π(r1…rj-1,rj+1…rk-1) //将rj提到前面
=1-(1/(rj·rj)) C·1/Π(r1…rj-1,rj+1…rk-1) //对rj进行求导
=1-(1/rj) C·Π(1/ri) //将其中一个rj放到后面
}
Theorem3.2 现在我们修改Theorem3.1中关于Sk大小为常数的假设，而是设总大小S为常数。这个最小化问题就变得更困难了，但是依然是可以通过拉格朗日乘数来解的。结果可以表示如下：
rk-1=rk+1
rk-2=rk-1+1/rk-1
rk-3=rk-2+1/(rk-1·rk-2)
我们忽略其证明过程。
正如我们通常所见到的，ri的值通常都是比较大的，比如是20或者更大，因此这个最大组件的大小，Sk通常占据了总大小S的绝大部分。因此对于Theorem3.2来说，每个ri只是与它相邻的那个ri+1有个细微的差异。因此，在下面的例子中，我们还是基于Theorem3.1的结果来进行说明。
最小化总开销
通过Theorem3.1，可以看出如果让R和Sk保存不变，而允许S0变化，那么就可以将总的IO频率H表示为S0的函数。
根据公式(3.5) S=S0+r·S0+(r^2)·S0+…+(r^k)·S0，r会伴随着S0的减小而增大，
又根据(3.6) H=(2R/Sp)·(K·(1+r)-1/2)，H与r成正比
很明显H会随着S0的减小而增大。现在我们可以看下如何通过在昂贵内存与廉价磁盘间进行权衡，来让两组件LSM-tree的总开销最小化。我们需要计算出用于存储LSM-tree所需的磁盘空间，以及可以让磁盘磁臂完全被利用所需要的总IO频率H，同时我们将此作为我们用于决定可以最小化开销的S0大小的计算的起点{!即先确定出一个H的初始值，而因为H与S0相互之间具有固定的关系，然后就可以根据这个H再计算出S0的一个初始值}。从这个点开始，如果我们继续减少C0大小，那么磁盘介质的开销就需要增加了，因为此时磁盘磁臂开销已经成为了限制因素。下面的例3.3就针对两组件和三组件LSM-tree，解释了这样的一个过程。在讲这个例子之前，我们首先针对两组件情况进行一些分析。
总开销是内存开销，COSTm·S0，和磁盘开销，磁盘开销是由磁盘存储和IO开销中的最大值决定的，在这里IO开销基于multi-page block访问频率H(以pages/秒为单位)：
COSTtot= COSTm·S0+max[COSTd·S1，COSTπ·H]
考虑两组件的情况，对于公式(3.6)，k=1，r=S1/S0。令：
s= (COSTm·S0)/(COSTd·S1)=内存开销与S1数据的存储开销之比
t=2·((R/Sp)/S1)·(COSTπ/COSTd)·(COSTm/COSTd)
C=COSTtot/(COSTd·S1)=总开销与S1数据的存储开销之比
那么，利用式(3.6)进行替换和简化后，同时假设S0/S1值很小，可以得出如下的近似等式：
C≈s+max(1,t/s)
{!推导过程如下：
C=COSTtot/(COSTd·S1)
= (COSTm·S0+max[COSTd·S1，COSTπ·H])/( COSTd·S1)
=(COSTm·S0) /( COSTd·S1)+max[1, COSTπ·H/( COSTd·S1)]
将H=2(R/Sp)(r+1/2)代入
=s+max[1,2((R/Sp)/S1)( COSTπ/COSTd)(r+1/2)]
=s+max[1,2((R/Sp)/S1)( COSTπ/COSTd)(COSTm/COSTd)(COSTd/COSTm)(r+1/2)]
= s+max[1,t(COSTd/COSTm)(r+1/2)
又r=S1/S0
≈s+max[1,t(COSTd/COSTm)(S1/S0)
≈s+max[1,t(COSTd·S1)/(COSTm·S0)]
≈s+max[1,t/s]
同时这也意味着COSTπ·H/( COSTd·S1)≈t/s
}
这样相对开销C就是变量t和s的函数；变量t实际上是应用程序所需的multi-page block IO频度的某种形式化表示{!可以看到对于t来说，COSTπ/COSTd体现的是磁盘IO与空间开销之比，COSTm/COSTd 体现的内存开销与磁盘开销之比，这两个值是两个常量，而((R/Sp)/S1)则体现的是数据的访问密度，如果R越大，则t越大}。s则代表了为实现LSM-tree我们所需要提供的内存大小。为确定S0的大小，最简单地规则就是,沿着s=t这个分界线，此时C=s+1，同时磁盘存储和IO能力都已被完全利用{!s=t，根据COSTπ·H/( COSTd·S1)≈t/s说明此时COSTd·S1= COSTπ·H也就是说磁盘存储空间所具有的IO能力已完全被利用 }。对于t<=1时，在s=t时可以取得最小值，但是对于t>1，C的最小值是沿着曲线s=t^(1/2)的，此时C=2·t^(1/2)，将该结论代入到我们前面的等式中，可得到，对于t>=1：
(3.8)COSTmin=2[(COSTm·S1)(2·COST·R/Sp)]^(1/2)
{!COSTmin即min(COSTtot)}
因此在t>=1的情况下，LSM-tree的总开销看起来是(足以将所有LSM数据保存下来的所需内存的开销，这是一个很高的值，即COSTm·S1)和(用于支持将插入数据写入到磁盘所需的multi-page block IO的磁盘开销，这是一个很低的值，即2·COST·R/Sp)的几何平均数的2倍。总开销中的一半将会被用于S0的内存开销，剩下的一半用于对于S1的IO访问开销。磁盘存储空间的开销并没有体现出来，因为t>=1保证了数据是足够热的足以让IO开销占据磁盘开销的主导。
在t<=1的情况下，数据较冷的情况下，在s=t时可取得最小化开销，此时C=t+1<2。这意味着这种情况下的总开销总是不会超过用于将S1存储在磁盘上的开销的两倍。在这种情况下，我们会根据存储开销来决定磁盘大小，然后通过利用起它所有的IO能力来最小化内存使用。
{!我们可以将上面的分析过程转换为一个更纯粹的数学问题。t基本上可以看做一个常量，t与R是直接相关的，它标识了数据访问的热度，因此对于C的最小值计算实际上是在求如下曲线的最小值
C≈s+max(1,t/s)
C≈max(s+1,s+t/s)
由于t可看做一常量，这样我们就可以将上面等式用平面坐标系中的曲线进行表示。y=x+1和y=x+c/x，根据解析几何知识可知，y=x+1是直线，而y=x+c/x则是如下形状曲线。
当x->正无穷时，c/x->0，所以曲线无限接近y=x，而在x->0时，c/x->正无穷。最小值点可以通过对其求导数求得，在x=c^(1/2)时取得，此时y=2 c^(1/2)。下面需要求的则是y=max(x+1,x+c/x)，因此需要将该曲线y= x+c/x与y=x+1进行比较。
x+1>x+c/x，可得x>c
x+1<x+c/x，可得x<c
也就是说以x=c作为分界点，y=max(x+1,x+c/x)取值如下：
在x>c时，y =x+1，而
在x<c时，y=x+c/x。
即y=max(x+1,x+c/x)就变成了一个分段函数，在x=c处分成了两个函数。那么下面的事情就是要看如何计算该分段函数的最小值了。
对于该分段函数来说，其在哪点取得最小值实际上就是与c的取值相关了,同时最小值点只有两种可能：一是在y=x+1和y=x+c/x的交点处，一是在y=x+c/x的最小值点处。如果c=1，那么y=x+1和y=x+c/x的交点就刚好是y=x+c/x的极值点，也就是说此时在x=c处即是最小值点，而在c<1时，二者交点在(c,c+1)处，但y=x+c/x的极值点在(c^(1/2),2 c^(1/2))，同时由于c<1故c^(1/2)>c，而我们的分段函数，在x>c处，曲线是y=x+1，因此此时的最小值应是在(c,c+1)处。只有当c>1时，c^(1/2)<c，此时分段函数曲线才是y=x+c/x，同时2c^(1/2)<c+1，因此此时的最小值点应是(c^(1/2),2 c^(1/2))。
}
例3.3 我们来考虑下例3.1中涉及的Account-ID||Timestamp索引。下面的分析只是计算出了在插入速率R为16,000bytes/秒(1000个16字节的索引记录，忽略其他开销，这样所产生的20天的索引数据将具有576,000,000个记录，总大小约9.2GBytes)时，对应插入操作的开销。
如我们在例3.1中所见，如果使用B-树来进行索引支持，那么磁盘IO会成为限制因素—叶级数据是warm的。即使假设所有的非叶子节点都是驻留在内存中的，仍然需要我们提供足够的磁盘空间以支持H=2,000个随机IO/秒，来满足叶级节点随机性的页面更新的需求。如果采用3.1节里的COSTp=$25，可以算出IO开销是H·COSTp=$50,000。下面我们再计算下用于将上层节点缓存在内存的开销。假设叶节点是70%满的，那么每个叶节点就有0.7·(4K/16)=180个记录，因此在叶级节点之上大概会有576,000,000/180=3,200,000个节点指向下面的叶子节点。如果我们采用一些前缀压缩，那么我们就可以在该级别上的每个节点中放下200条记录，这意味着将会有16,000{!3,200,000/200}个4Kbytes大小的页面，总大小为64Mbytes，按照COSTm=$100/Mbytes算的话，就是$6400。我们忽略在该级别之上的那些节点的相对较小的缓存开销，那么B-树的总开销就是由$50,000的磁盘开销和$6400的内存开销组成，合起来就是$56,400。
对于一个具有两个组件C0和C1的LSM-tree来说，我们需要一个大小S1=9.2GB的磁盘来保存记录，开销就是COSTd·S1=$9,200。我们会将数据在磁盘上紧密放置，同时计算出在这个容量大小下的磁盘在使用multi-page block IO的情况下所能支持的总IO速率H，实际上H=9200/COSTπ=3700pages/秒。现在根据这个H值，以及R=16,000bytes/秒，Sp=4K，再结合公式(3.6)，就可以解出r。
{!(3.6)H=(2R/Sp)·(K·(1+r)-1/2)，对于两组件LSM-tree来说K=1，代入已知参数可得3700=(2·16,000/4000)·(r+1/2)，解之得：r=3700/8-1/2=460}
根据r=S1/S0=460，以及S1=9.2GB，可得S0为20Mbytes，就需要$2000。这就是简单地令s=t的情况下的解，总的开销就是$11,200，同时磁盘的容量和IO已经被完全利用。因为此时t=0.22，故还属于<1的情况因此这个解也就是最优解。我们可以再增加$200来为正在被merge的block购置2Mbytes的内存，那么总的开销就达到了$11,400。与B-树的$56,400相比已经是非常大的改进了。
更详细地说，插入速率R=16,000bytes/秒，意味着每秒需要有4个页面(每个页面4KB)从C0 merge到C1。因为C1大小大概是C0的460倍，那么C0中的每条记录merge时平均需要牵连到C1中的460条记录。因此将C0中的一个页面的merge需要读写C1中的460个页面，每秒就是3680(C0每秒4个，4·460·2=3680)个页面。这也是9.2个磁盘在使用multi-page block IO的情况下所能提供的IO能力，每个提供了400pages/秒{!根据前面所述，单磁盘随机IO大概是40pages/秒，multi-page block IO大概是普通随机IO的10倍}。
由于这个例子已经表明在具有两个组件时，磁盘资源已经被完全利用，因此这里也就没有必要引入三组件LSM-tree。下面的例子展示了一个三组件LSM-tree可以为纯插入负载提供更少的开销的情况。
例3.4 考虑例3.3，令R增长10倍。现在B-树解决方案为支持H=20,000IO/秒的IO频率要花费$500,000来购买500GB的磁盘；其中有491GB的空间将会是空闲的。但是B-树本身的大小是相同的，因此我们仍然需要为将目录节点缓存下来而支付$6400，这样总开销就是$506,400。对于LSM-tree来说，如果R增长了10倍，意味着t也增长了同样的倍数，即从0.22增长到了2.2。因此现在t就是大于1的了，那么此时最优的两组件解决方案已无法利用起所有的磁盘能力{?为何？}。我们利用公式(3.8)来计算出两组件LSM-tree的最小开销为$27,000，其中一半用于13.5GB的磁盘，一半用于135MB的内存。此时，仍有4.3GB的磁盘空间未被使用，加上用于缓存的2MB内存，总开销是$27,200。
更详细地来说，插入频率R=160,000bytes/秒，意味着每秒需要有40个页面(每个页面4KB)从C0 merge到C1。因为C1大小大概是C0的68倍，因此将C0中的一个页面的merge需要读写C1中的68个页面，每秒就是5440(C0每秒40个，40·68·2=5440)个页面。这也是13.5个磁盘在使用multi-page block IO的情况下所能提供的IO能力。
对于使用一个三组件LSM-tree来处理这种R=160,000bytes/秒的情况，可以按照两组件的那种方式先计算出最大的那个磁盘组件的一个开销以及IO频率的一个开销平衡点。根据理论3.1，我们有Si/Si-1=r，i=1,2，我们可以计算出r=23并且S0=17MB(内存开销就是$1700)。
{!与例3.3类似的计算方法，根据(3.6)H=(2R/Sp)·(K·(1+r)-1/2)，对于三组件LSM-tree来说K=2，代入已知参数可得:
3700+3700/r=(2·160,000/4000)·(2·(1+r)-1/2)，
解这个二元一次方程得：r=23，S0=S2/(23·23)=17MB，为存放下所有数据S2=9.2GB}
现在从这个点开始继续增加内存的大小不会得到更好的性价比，因为内存大小的降低，将会导致相应的磁盘开销的平方级别的增长。因此我们可以得到一个针对三组件的类似的s=t解决方案。在加一个4MB内存用于为两个rolling merge过程缓存数据，需要$400，这样对于三组件LSM-tree的总开销就是$9200的磁盘开销，加上$2100的内存开销，总共就是$11,300，又比两组件LSM-tree的开销降低了很多。
更详细地来说，内存组件C0大小为17MB，稍小的那个磁盘组件大小C1是它的23倍，大概是400MB，C2又比C1大23倍，是9.2GB。那么每个页面在从C0 merge到C1时，将会引入23个页面读和23个页面写操作，这样每秒就需要读写1840(40*23*2)个页面。类似的，每秒也需要有40个页面从C1 merge到C2，每个页面也会引入23个页面读和23个页面写操作，这样每秒也会需要读写1840(40*23*2)个页面{!?有些疑问，按照之前的说法，rolling merge过程，组件越大需要的IO量应该是越多，为何此处变成一样了呢？}。这样总的IO频率就是3680，刚好是9.2G的磁盘在使用multi-page block IO的情况下所能提供的IO能力。
与普通B-树相比，对于查询操作来说，两组件或三组件LSM-tree需要更多的IO。对于它们来说，最大的那个组件就非常像一个独立的B-树结构，但是对于LSM-tree的情况，我们还没有付出为缓存那些索引中的叶级以上的节点而产生的$6400的内存开销。因为在树中的那些很高层的节点相对很少，基本可以忽略，同时我们还可以假设它们已经被缓存了。但是，如果查询频率足够高我们也很乐意花钱来将所有的目录节点缓存起来。在三组件的情况下，我们还需要考虑C1组件。因为它比最大的那个组件小23倍，因此我们也可以很容易地缓存它的所有非叶子节点，同时我们把这个开销计入到我们的分析中。在某个C2中的记录被查找时，如果访问到C1中的一个未被缓存的节点将会引入一次额外的读，同时也需要决定是否缓存C2的目录节点。因此，对于三组件情况来说，查询操作将可能会需要读取一些额外的页面而超过简单B-树结构所需的2次IO。对于两组件的情况，可能需要一次额外的读。如果我们为缓存LSM-tree组件的那些非叶子节点购置了足够的内存，那么对于两组件的情况我们就能达到B-树的访问速度，对于三组件的情况可能只在某些时候需要一次额外的读。加上缓存的开销后，三组件LSM-tree的开销就变成了$17,700，仍然远小于B-树。但是可能可以以更好的方式来用这些钱：一个充分的分析需要能够最小化在所有工作负载(包括更新和查询)上的总开销。
我们已经根据定理3.1通过改变ri的大小来达到了使得merge操作的所需的IO的最小化。然后又通过选择S0来使得总开销最小化，以得到最好的磁盘磁臂和内存开销。现在对于LSM-tree来说，唯一可变的就是组件个数，K+1了。实际证明，当我们增加组件个数的时候，S0将会不断减少直到到达某个固定点，此时组件间的大小比率将会达到一个值e=2.71…….，或者直到到达cold-data区域。但是，通过例3.4可以看出，随着组件数的增加，S0对总开销的影响将会越来越小；在三组件LSM-tree的情况下，S0的大小已经降低到17MB。此外，随着组件数目的增长还会伴随着其他的开销：需要有更多的CPU来执行更多的rolling merge过程，需要有更多的内存来缓存这些merge过程中的节点(甚至可能会查过C0的内存开销)。此外查询操作将需要在所有的组件树中进行查找。如上这些原因就对组件的数目加上了很多限制，通常实际中最常见的的就是三组件的情况。