作为一个K-V数据库，levelDB索引为什么要使用LSM树实现，而不采用哈希索引？ 第1页

DDIA第三章写的很清楚了，建议楼主读一读。

Hash有个问题就是在内存里能高效存取，但是在磁盘上不行。这就是为什么关系型数据库要用B树做索引了。因为索引结构是要持久化在磁盘上的。

磁盘这个硬件和内存不同，对随机访问的支持很弱。需要寻道等等。

题主只考虑了，通过一个key来查其value的情况。但如果是范围遍历。key在hash结构中并不有序。Hash就很难满足了。

这一点来看Hash做磁盘索引结构是不明智的。

另外我觉得用LSM直接和Hash来做比较是不太合适的。因为LSM、B树这种都是稍高维度的数据结构。LSM和B树还有的比较。因为LSM不仅描述了结构，还描述了更新读写的各个策略，并且它其实不是一种数据结构，而是三个小结构的组合（磁盘上顺序追加写入的log+内存有序MemTable+磁盘上有序SSTable）。

hash则是更为基础的一种思想，就比如用下面的LSM的图来说。Memtable和SStable的存储的KV，不也是Hash么？

LSM当然有局限，LevelDB适用于写多读少的场景，并且写操作实际是追加型的写入，而不是随机写。也就是同一个key，写入多次。其实会存储多份。占用空间会多些。

对于读极端情况下，确实比较慢。因为可能要一层一层的向下遍历。但整体来说内存中的MemTable和磁盘上的SSTable都是有序的了。

没有一种数据结构是万能的，关键还是看场景。一切都是Trade-Off。

另外就是要多关注一下硬件的部分。我们印象中学习的数据结构都是大都是内存场景的，换个环境很多结论都不成立。