Lsm

LSM Tree 是 Log Structured Merge Tree 的缩写，这种 Tree 数据结构的特点就是”Log Structured“ 和 ”Merge“。LSM Tree 主要用在各种新兴的数据库，作为底层数据结构。 提供了比 B+ 树/ISAM 更好的写性能。 本文是一篇读书笔记，作为以后再次阅读的提纲，此外，原文旁征博引有不少参考资料，值得一读。 原文传送门。 Some Background 核心： 硬盘（无论是磁盘，SSD 甚至是内存）随机读写性能太差，但是顺序读写性能非常高，所以要充分利用一点。 这篇文章指出，磁盘的顺序访问甚至比内存的随机访问还快！ 所以，如果我们对写性能要求高，怎么办？ 一种方法是写数据的时候只 append（添加在文件尾部）。通常我们把这种叫做写日志，logging。 但是，简单的 log 结构无法满足复杂的需求，为了满足类似搜索、kv 之类的场景，需要在 logging 基础上加上额外的数据结构，比如 binary search, hash, B+ or external。 Search Sorted File: save data to a file, sorted by key. If data has defined widths use Binary search. If not use a page index + scan. Hash: split the data into buckets using a hash function, which can later be used to direct reads. B+: use navigable file organisation such as a B+ tree, ISAM etc. External file: leave the data as a log/heap and create a separate hash or tree index into it. 以上 4 种方法都可以改善读性能。 ...