大数据存储引擎之哈希

• 数据结构就是键值对
• 优点：检索快
• 缺点：不支持范围扫描
• 如果数据都在内存中，那就很快的，比如常用redis 作为缓存组件（数据转到硬盘就另说了）
• 如果要放到硬盘中存储，以bitcask为例，每次操作都是追加文件，在内存中维护一张哈希表，记录主键对应的文件号和value 在文件中的起始位置和长度，还有时间戳（版本号），
• 由于是追加文件的方式写数据，当前只有一个活跃文件可以追加，老文件只可读不可写，文件中的每一条记录，包含了真正的数据内存，时间戳，校验值。
• 每次写的话包括两步：第一步：将数据追加到活跃文件，这一步是顺序写入硬盘是很快的，第二部：更新内存中的索引结构，当然也很快的。

• 每次读的时候也包括两步：第一步：读取内存中的索引找到主键对应的文件号以及value在文件中的位置，第二步就是读文件了

  
  图片.png

大数据存储引擎之B树

• B树是基于二叉树演变，每个节点有多个子节点，节点都是按照顺序组织的。
  因此能够很好支持范围扫描和查询，但是维护B树，子树的合并分裂是个消耗高的操作。
• 大多数关系型数据库采用这种B＋的存储引擎

• 比如mysql 的innodb, 是一种聚集索引，因为叶子节点就是存的真实的数据，非叶子节点是索引信息。

  
  图片.png

大数据存储引擎之LSM

• lsm全称（log structured merge tree）,bigtable hbase等分布式表格采用。
  mongodb的默认存储引擎wiredTiger(3.2版本以后)也是采用的lsm，详细见http://www.mongoing.com/archives/2540
• 主要文件包括内存中可变的mutable memtable,不可变的immutable memtable.硬盘中的多个sstable,多个清单文件，和当前文件，还有操作日志。
• sstable全称sorted string table，是有序，不可写的
• 清单文件维护着sstable信息，包括最小值，最大值等
• sstable 需要定期合并，变化等操作，因此会产生多个清单文件，而当前文件就是指向哪个清单文件是当前有效的。
• 当执行写的时候，采用WAL(write ahead log),将操作顺序写入log（便于容错的恢复数据等）,将数据写到内存中的mutable memtable，当可变的memtable达到一定阈值的时候，就变成了不可变memtable,再有写入会放到一个新的memtable，
• 这些memtable也是有序的，当内存中的memtable足够多的时候会合并生成一个新的sstable储存到硬盘.

• 当然也有后台进程会合并这些sstable,回生成新的文件，老的文件就会废弃，清单文件就记录这些变化。

  
  图片.png