百科问答小站 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。

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




  

相关话题

  数据库中将物理删除改为逻辑删除,如何不改变之前的SQL语句呢? 
  C# 为何MySQL无法打开连接? 
  为何没有国家建立全民DNA数据库 (真正意义上的全部人而非仅仅包括犯罪嫌疑人)? 
  数据库的冗余度是不是越小越好? 
  数据库 与 数据仓库的本质区别是什么? 
  数据库 与 数据仓库的本质区别是什么? 
  研究生研究数据库研究方向有前景吗?想写一个国产的数据库,类似mysql这种? 
  LBS数据库的架构是怎样的? 
  淘宝研发的 OceanBase 相比其他开源的 noSQL 数据库有什么独特的优点? 
  图数据库的应用有哪些优点? 

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





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