Hash存储的结构

目前主要的单机存储引擎有：

1、哈希存储：hash的CRUD是快的。但缺点是不支持顺序扫描。bitcask是一个基于hash表结构的存储系统。他将写操作（包括删除标识）追加到文件尾。并定期合并新老文件&记录。

2、B树：既支持随机读取又支持范围查找的系统。查找时间复杂度为logd(n)（d为每个节点的出度）。Mysql的InnoDB的引擎和OS的文件系统使用的就是B+树。（为什么选择使用B树的变种B+树，读者有兴趣可以去探究下。提示：磁盘读取）

3、LSM树(Log Structured Merge Tree)：由B+数改进而来。其思想为：将增量写操作保存在内存中，超过阈值时刷入磁盘，从而减少随机写磁盘操作。读操作则需要合并磁盘数据和内存中的写操作。通过Memtable/SSTable实现，实现细节在此不做深入探究。比较适合写操作较多的业务场景。BigTable/HBase/Cassandra中的列簇的数据存储方式采用的即是LSM树。