22｜RUM猜想：想要读写快还是存储省？又是三选二
该思维导图由 AI 生成，仅供参考
RUM 猜想
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文深入探讨了数据存储优化的相关观点，重点分析了B+Tree和LSM-Tree两种存储结构在读写存储方面的优劣。文章指出B+Tree适合读操作优化，但在面对大量随机写时会导致存储碎片化和写放大；而LSM-Tree通过将随机写转换为顺序写，提升了写入性能，但却带来了更多的写放大和空间放大。此外，文章还介绍了Leveled策略在LSM-Tree中的应用，以及分布式数据库中的存储结构实现。另外，文章还提到了OceanBase和WiscKey等存储优化的方法。最后，文章还介绍了TiDB和CockroachDB分别推出的自己的单机存储引擎TiTan和Pebble。整体来看，本文通过对比分析不同存储结构在读写存储方面的特点和适用场景，为读者提供了深入了解数据存储优化的视角。文章内容丰富，涉及了存储引擎的工程原因、存储模型的选择、以及存储优化的方法，对于对存储引擎和数据存储优化感兴趣的读者具有很高的参考价值。
《分布式数据库 30 讲》，新⼈⾸单¥59
全部留言(13)
- 最新
- 精选
扩散性百万咸面包思考题： 使用Bloom Filter的改造版，现在不用来判断某个key是否不存在，而判断某个key的前缀是否不存在。比如说我要查300-000 到 300-999的区间，那么他们拥有共同前缀300，我只要判断这个前缀是不是在当前SSTable里即可。作者回复: 说的全中，点赞。
2020-09-2811
Jxin
课后题： 这样问，那就一定是可以了。但很遗憾，能力有限想不到。scan了的话，如果是常规的行式存储,bf起不到作用，毕竟边界不存在不等于边界内部不存在。 22讲下来的感觉: 有种搭建空中楼阁的感觉,费力还容易忘。这篇专栏前边,其实最好有篇实战做铺垫,比如tidb。两相验证虚实结合才能学得扎实。作者回复: 嗯，谢谢，你的建议很中肯。因为这个专栏是中立视角，希望跳出某个具体的产品，讲一些共性的、原理层面的研究进展，然后选择有代表性的产品做一些映射。这样一来，所有的内容就不能与某一款产品完全匹配，会有些抽象，但我相信后面一定会有更多分布式数据库的课程作为补充，做到虚实结合。
2020-09-2823
James想问下老师，就是我查一个键值对的时候，对于L1 往后的层级我是怎么找到对应的key的，我看图中画的是很多个区间，是去顺序遍历一遍这些区间，然后去对应的区间找元素吗（在区间内是通过调表算法来找元素的），还是说用二分法这类的算法来找到是哪个区间呢。PS:这个区间是可以不连续的吧（只要不重合就行）,比如[a,b) [e,f]作者回复: 从L1开始，每层的SSTable的Key值范围是不重叠的。所以简单来说，我们会每次通过文件的区间信息锁定一个文件，也就是当前Key所在的区间，然后在文件内部查找，如果没有对应的数据则继续向L2层查找，如此逐层向下，最终找到Key的对应键值对，或者确定不存在对应数据。
2021-01-2522
kylexy_0817NewSQL的存储数据结构和策略和ES的十分相似。ES确实不是数据库，它不具备数据库应有的特性，例如事务等。之前的留言不严谨😄作者回复: ：）
2020-11-111- licl1008想问一下 写放大和空间放大具体有啥区别 写得多了不是磁盘空间就占用更多了吗？
作者回复: 写入同样数据，空间占用也会有区别。这主要和增量数据的存储模式有关，比如直接update空间就小些，而转换为delete加insert空间就大些。
2020-09-281 
piboye即使不是前缀相同，范围查询也可以一个一个key去尝试，bf是内存操作，还是比磁盘快吧作者回复: 首先范围查询可能是无法穷举的，例如对浮点数的范围查询。另外即使可以穷举，每个都查的时间复杂度就是O(N)了，而磁盘文件是有序的，加上磁盘会做预取，可能还是磁盘快些。
2020-09-281
sanstyleL0 中的 key 是交叉的，所以读取 L0 的所有 SSTable 写入 L1，来保证 L1 开始的 SSTable 都是 key 不重叠的。 在 L1 划分边界的时候，[e, k) 里面是有交叉 key 的，重新划分为 [e, f), [f, k)，怎么保证这两个 SSTable 不交叉？作者回复: 就是在数据誊写（也就是compact）的过程中，控制每个文件写入的数据与边界相符。
2021-05-12
JacksonCockroachDB 也推出了自己的存储引擎 Pebble，主要目的是解决工程问题，包括解决 CGo barrier 问题和避免 Rust 功能膨胀带来的变更风险。—— Rust应该是Rocksdb吧？笔误？作者回复: 应该是Rocksdb，看得很仔细
2021-04-24
可怜大灰狼数据块里是按照顺序存储了很多条数据。我想对数据块建立一级布隆过滤器实例，这样scan定位起始和终止对应的数据块，应该能提速不少。 如果把数据块按照大小分级，类似LSM的level层那样。是不是会更快些？作者回复: 说的很好，点赞。
2020-09-28- 有铭为什么RUM是个猜想而不是个定论呢？这东西第一眼看上去好像CAP理论，不过CAP已经被证明了2020-09-284
