B+ Tree的毛病

B+树最大的性能问题是会产生大量的随机IO，随着新数据的插入，叶子节点会缓缓决裂，逻辑上间断的叶子节点在物理上往往不间断，甚至拆散的很远，但做范畴查问时，会产生大量随机读IO。
对于大量的随机写也一样，新插入的数据在磁盘上的地位可能相隔很远，会产生大量的随机写IO。

相比B+ Tree，LSM-Tree可能会损失一部分读性能，但换来了微小的写性能的晋升。

LSM-Tree原理

Memtable

当一个Memtable被写满时，它将变为immutable的，前面进来的数据将写入一个新的Memtable。而后盾线程将会将Immutable Memtable flush进一个SST文件，并在flush好后将该Memtable销毁

数据结构

可抉择的数据结构

  • SkipList (Default)
  • HashLinkList
  • HashSkipList
  • Vector

Memtable默认采纳跳表实现
而哈希跳表我之前没有接触过，后果搜寻后发现是先对哈希值取模放入对应的桶中，再在每个哈希桶中保护跳表构造。
这样的话应该会晋升随机单个查问的速度，而范畴查问应该会变慢一点。

此外，依据官网文档，只有SkipList反对并发插入。

Flush

三种状况下会触发flush操作

  1. 当某一个Memtable的大小超出了ColumnFamilyOptions::write_buffer_size
  2. 当所有列族的Memtable的总大小超出了DBOptions::db_write_buffer_size，或者DBOptions::write_buffer_manager收回了flush的信号。这种状况下size最大的那个Memtable将被flush
  3. WAL的大小超过了DBOptions::max_total_wal_size。这种状况下最老的Memtable将被flush，以便清空它相应的WAL中的局部。

Write Ahead Log

RocksDB的每次更新都会写入两个地位：内存中的memtable（稍后将flush到SST文件）和磁盘上的预写日志（WAL）。而当Memtable中的数据flush后，WAL中对应的数据将被删除

WAL被用作故障后复原数据，它默认是开启的。也能够通过配置敞开它。