本文将 RUM（读/更新/内存开销）权衡确定为访问方法面临的主要权衡，探讨了现有数据结构如何探索权衡空间，并展望了未来，RUM 猜想将创造一种趋势，即构建能够高效地访问的方法。变形以支持不断变化的需求和不同的软件和硬件环境。
本文来自 EDBT 2016。数据库资深人士会知道这里提到的权衡，但是这篇“知识系统化”论文非常有用，因为它为该领域的新手提供了一个很好的心理框架，并且看到明确陈述的实际/隐式权衡可以创建即使是退伍军人也能顿悟。
RUM（读/更新/内存开销）权衡如下：
- 读取开销 (RO) 是访问方法的数据总量（包括辅助数据（例如，为遍历 B+ 树而读取的数据）和基本数据）之间的比率，除以检索到的基本数据量数据。
- 更新开销 (UO)（又名写放大）由除了主数据更新之外还应用于辅助数据的更新量给出。对于 B+ 树示例，通过将更新的数据大小（基础和辅助 B+ 树节点数据）除以更新的基础数据的大小来计算 UO。
- 内存开销（MO）（又名空间放大）是由存储辅助数据引起的空间开销。对于 B+ 树示例，MO 是通过将 B+ 树的总体大小除以基础数据大小来计算的。
本文预设一个假设前提：如果一种访问方法在读取、更新和内存开销中的某一项达到最优，那么其余两项开销都无法达到最优值。
RUM 猜想定义：一种访问方法，如果能为读取、更新和内存开销中的两项设置上限，那么第三项开销就会产生一个硬下限，而且无法进一步降低。（三分之二，复杂度）
读取优化
读取优化的访问方法示例包括具有恒定时间访问的索引，例如基于散列的索引或对数时间结构，例如 B 树、Tries、前缀 B 树和 Skiplist。
编写优化的访问方法可合并更新并将其批量应用到基础数据。示例包括日志结构合并树、分区 B 树、物化排序合并 (MaSM) 算法、步进合并算法和位置差分树。LA-Tree 和 FD-Tree 旨在利用闪存存储的优点并弥补闪存的缺点。
空间优化访问方法包括压缩技术和有损索引结构（例如布隆过滤器）、基于有损哈希的索引（例如计数最小草图）、有损编码的位图以及近似树索引。稀疏索引是轻量级二级索引，例如 ZoneMaps、Small Materialized Aggregates 和 Column Imprints 都属于同一类别。
自适应访问方法由灵活的数据结构组成，旨在通过使用工作负载访问模式作为指导来逐渐平衡 RUM 权衡。
大多数现有的数据结构都提供了可调整的参数，可用于平衡离线 RUM 权衡，然而，自适应访问方法可在设计空间的更大范围内平衡在线权衡。
著名的建议有数据库破解、自适应合并和自适应索引，这些方法可以平衡读取性能和创建索引的开销。
- 传入的查询决定了索引的哪一部分应该完全填充和调整。
- 创建索引的开销会在一段时间内摊销，逐渐减少读取开销，同时增加更新开销，并缓慢增加内存开销。
理想的 RUM 访问方法将能够在三个极端之间无缝过渡：读优化、写优化和空间优化，这些可能包括：
- B+-Tree 具有动态调整参数，包括树高、节点大小和分割条件，以便在运行时调整树大小、读取成本和更新成本。
- 通过将更新吸收到可更新的概率数据结构（如商过滤器）中，近似（树）索引支持低读取性能开销的更新。
- 变形访问方法，一次组合多个形状。通过传入查询逐渐向数据添加结构，并在进一步的数据重组变得不可行时构建支持索引结构。
- 更新友好的位图索引，其中使用附加的、高度可压缩的、逐渐合并的位向量来吸收更新。
- 概率数据结构增强了迭代日志的访问方法，避免以额外空间为代价访问不必要的数据，从而实现更高效的读取和更新。
讨论
- RUM 猜想是针对单节点数据库/数据存储讨论的，而不是针对分布式系统。
- 我确定我会选择 RUM 三难的哪两个方面，RU？SSD 对显着扭曲权衡领域有很大帮助，但内存成本仍然是一个问题，因此对于 RU 系统来说可能不是那么明确。
- 自动调整访问方法的可以来自容错和负载管理，甚至可能处理亚稳态问题。