A simple KV database implementation
- asm murmur3 perf
- clean code
- unit, benchmark test
- LSM 日志结构存储引擎,核心点在于顺序写日志,这样就能保证超快的写速度;
- 内存索引,KV红黑树实现,内存索引有大小限制;
- 超过内存限制(threshold)后,会将内存数据刷新到磁盘段文件中(segment file);
- 在内存中保存了索引、数据方便快速查询,如果仍查不到则去搜索段文件;
- 如果一个 key 被写了多次,那么就会有很多重复的行,因此需要合并他们(compact);
- 当需要刷内存索引至磁盘时,会先将磁盘中的段文件进行合并(compact);
- 引入布隆过滤器来加快文件数据查询,不存在的 key 直接返回,避免读文件;
- sparse index(稀疏索引) 保存了部分 segment-file-offset 信息,方便在文件中搜索;
- 稀疏索引查询的时候找到比 key 小(对于二叉树的左孩子节点)的文件和索引,然后遍历文件,就能提升效率;
- WAL 日志用来恢复 memtable;