哈希索引
如果数据库存储全副采纳追加式文件组成，能够用 key 示意键值，value 标识偏移量来组成索引。
如果始终追加到一个文件，可能会用尽磁盘，所以须要将日志分解成肯定大小的段，当文件达到肯定大小的时候就敞开它，并将后续文件写入新段中。能够在之前的段上执行压缩，即抛弃多余的键，只保留最每个键的最新值。
解冻的段合并和压缩过程由后盾管制。
哈希索引局限性：
- 哈希表必须全副放入内存，如果有大量的键，则须要把哈希放入磁盘，就会造成随机磁盘 IO 拜访，效率很低。
- 区间查问效率低。
SSTABLE LSM-TREE
SSTable 又称为排序字符表（Sorted String Table），它须要将上文形容的 k - v 对存储按顺序存储，它有以下长处。
- 合并段的时候更高效，能够应用相似于归并排序算法，产生新的案件排序的合并文件段
- 在文件中查找特定键时，不须要保留整个哈希表，能够用稠密索引，几千个字节用一个键就够了
- 读申请须要扫描范畴内多个 k - v 对，能够思考将记录保留到一个块中并压缩，而后稠密索引指向结尾，以缩小 IO。
应用压缩合并的引擎个别都叫 LSM 引擎（Log-Structed-Merge-Tree）
工作流如下：
- 写入时，先保留到内存中的均衡数据结构中（如红黑树）
- 内存表大于某个阈值时，将其作为 SSTable 文件写入（程序写入），并生成一个新的内存表
- 解决读申请，先尝试内存表，而后最新的磁盘段文件，而后次新的段文件
- 后盾过程周期性的执行段合并与压缩，抛弃被笼罩或者删除的值
性能优化
- 查找不存在的数据时，可能要回溯到最旧的文件，能够用布隆过滤器筛选
- 大小分级、分层压缩
B-Tree
这个就不多赘述了，网上材料很多
优化
- 通过预写日志（WAL）的形式存储数据库的操作，避免零碎解体时数据失落。
- 保留键的缩略信息
- 顺序存储页
LSM-tree VS B-tree
LSM 能接受更多写入吞吐，因为它是程序写入。LSM 磁盘文件也比 B -tree 小很多，他没有碎片化空间，定期重写 SSTable 打消碎片化。
LSM 读取性能较弱，当磁盘执行压缩操作时，容易产生读写申请期待，较高百分位数相应工夫可能会很高。不限度写入速率可能会呈现合并速率跟不上写入速率从而造成磁盘空间有余。