《Designing Access Methods: The RUM Conjecture》

这篇论文从读、写、存储空间开销角度总结了access method设计，并提出了一个RUM猜想，认为针对其中两个开销优化，则会导致第三个优化困难。

就RUM猜想本身的可信程度而言，我个人觉得一般，不过这种三角可视化的总结非常有趣，可以一读。

What is RUM Conjecture

作者总结了Access Method的一些trade off，审视了RUM三种开销：R是read overhead，U是update overhead，M是memory(or storage) overhead，提出了RUM猜想：

designing access methods that set an upper bound for two of the RUM overheads, leads to a hard lower bound for the third overhead which cannot be further reduced。

就是说，如果你的access method能够确保RUM中的任意两个开销的最坏情况的上限，那么剩下的那个开销的最好的情况就很难优化的很好。

论文提到，某些access method会将索引压缩存放，那么通过引入computation / engineering这种场外信息，RUM猜想的可信程度会有些折扣。不过RUM猜想作为一个对access method的RUM三种开销总结，仍然有些价值。只是我们在遇到新的access method设计问题的时候，不能轻易放弃探索“全面好”的方案，尤其是遇到特定场景下的问题，相反RUM猜想可以视为一个探索的工具。

RUM in Practice

每个access method设计在RUM空间占一个点或者（允许通过调优）占一个区域。

• Read-optimized Access Method: Hash, B-Tree, Tries, Prefix B-Tree, Skiplist etc
• Write-optimized Differential Structures: LSM Tree, Partitioned B-Tree, Materialized Sort-Merge algorithm, Stepped Merge algorithm, Positional Diffferential Tree, LA-Tree, FD-Tree etc.
• Space-efficient access method: compression tech, lossy index(such as Blomm filters), Space indexes(ZoneMaps) etc.

其他略。