返回主题:存储常用数据结构

知识卡片

普通读书笔记卡 · 2280.j.2

SSTable的排序收益

理解等级:未标注

针对[[哈希索引与段压缩]]的局限,只需让段文件中的键值对按键排序、每个键在合并后的段中只出现一次,这就是 SSTable。好处有二:合并段像归并排序,并排读取各段,相同键保留较新段的值,文件大于内存也不必把键全载入内存;内存索引可以稀疏,知道 handbag 与 handsome 的偏移量,就能推断 handiwork 在二者之间,跳到前者后扫描即可。一次排序同时解决了合并效率和索引内存两个问题。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《数据密集型应用系统设计》第三章《存储与检索》"SSTables和LSM树"(源文件:_epub-src/ch3_split_002.html) - 结论依据:原文说明SSTable要求键值对按键排序,合并段可以用归并排序思路高效完成 即使文件大于可用内存,且由于排序特性,内存索引可以是稀疏的(每几千字节一个索引 条目),直接支撑本卡片关于SSTable两大优势的结论。 - 原始内容:我们把这个格式称为排序字符串表……与使用散列索引的日志段相比,SSTable有几个很大的优势:合并段是简单而高效的,即使文件大于可用内存……为了在文件中找到一个特定的键,你不再需要保存内存中所有键的索引……它可能很稀疏:每几千字节的段文件就有一个键就足够了