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