百科问答小站 logo
百科问答小站 font logo



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

  

user avatar   guodongxiaren 网友的相关建议: 
      

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。

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




  

相关话题

  Cache 和 Buffer 都是缓存,主要区别是什么? 
  如何获得中国所有火车班次时刻表数据? 
  电商网站中,50W-100W高并发,秒杀功能是怎么实现的? 
  有些上古程序猿一直坚持反对使用redis怎么办? 
  Cache 和 Buffer 都是缓存,主要区别是什么? 
  新浪微博「点赞功能」数据库如何设计的? 
  怎样理解分析王垠文章《SQL,NoSQL 以及数据库的实质》的观点? 
  2015年6月30日 闰秒 为什么世界多一秒钟会有这么大影响? 
  数据分析人员需要掌握sql到什么程度? 
  设计 MySQL 数据表的时候一般都有一列为自增 ID,这样设计原因是什么,有什么好处? 

前一个讨论
如何把战锤40k做成一个电影宇宙?
下一个讨论
同样是大国,为什么美国是分布式电网,而中国不是?





© 2024-11-22 - tinynew.org. All Rights Reserved.
© 2024-11-22 - tinynew.org. 保留所有权利