数据库存储引擎从0到1

存储引擎有两大类

• LSM 存储引擎
• 面向页面的存储引擎（基于 B-Tree）

世界上最简单的数据库

set(key, value) {    echo "${key},${value}" > test.db}

get(key) {    grep "^${key}," test.db | sed -e "s/^${key},//" | tail -n 1}

数据库集在文件末尾附加记录，复杂度 O(1)。性能杠杠的。

读取性能

在最坏的情况下，要搜索记录必须遍历数据库中的所有记录。时间复杂度为 O(n)

如何提高读取性能？

在主要内容上建立索引，影响查询的性能。

• 索引可提高读取性能
• 索引会降低写入性能。

哈希索引

你想见朋友，你知道他的社区名称，但忘记了公寓号码。

一种方法是去每个家庭，询问那所房子是否属于你的朋友。最坏情况 O(N)

另一种方法是去社区居委会，根据他的名字询问你朋友的门牌号码。这就是基于哈希的索引的工作原理。

基于哈希的索引将键映射到存储值的位置。

分段、合并和压缩

磁盘空间不足

写入操作追加在文件末尾，它不断变大，一段时间后会耗尽空间。

分割

当文件大小增加阈值时，关闭文件并创建新的段文件以进行写入。

压缩

压缩重复的记录，只保留最新的记录。

合并

分段和压缩将继续增加分段的数量。所以定期合并它们。

对文件进行顺序追加必然导致大量数据冗余，如何解决？

一般的解决方式是用后台线程，对文件进行定时的压缩合并，对于相同的键，只保留最新的值。

那么删除数据呢？

删除数据在对应的数据上标记一个墓碑，在进行合并日志段时，一旦发现标记墓碑，就会丢弃该记录。

崩溃恢复：

由于是对文件进行追加写，内存中的索引文件会丢失但是具体的数据文件不会。我们可以通过扫描磁盘文件重新建立索引，但由于是O（n）操作，在文件过大时会消耗大量时间。

基于哈希的索引的优势

• 写入速度更快
• 并发和崩溃恢复更好

基于哈希的索引缺点

• 基于范围的查询效率低下
• 哈希索引适合基于内存

SSTable 和 LSM

SSTable 全称 Sorted String Table，顾名思义，里面的 key-value 都是有序保存的

SStable在功能上只是对hash加入了一个按键值排序。

SSTable的构建

解释SSTable中的以下流程

• 写入内存表
• 写入段（磁盘）
• 读（先内存，再磁盘）
• 后台排序归并

SSTable的优点

• 合并和压缩更容易：基于合并排序。

• 索引稀疏

基于 SSTable 的数据库

如果使用sstable，先进行内存写，所以我们也要考虑日志系统，类似innodb里redolog方式来保证持久性。

LSM-Tree 全名叫Log-Structured Merge Tree，最早建立在日志结构文件之上，现在基于合并和压缩排序文件原理的存储引擎都统称为LSM存储引擎。

LSM树，即日志结构合并树(Log-Structured Merge-Tree)。其实它并不属于一个具体的数据结构，它更多是一种数据结构的设计思想。

LSM（日志结构合并树）

LSM 中的性能优化

布隆过滤器

如果数据库中不存在记录，则 DB 必须扫描所有段文件。为了改进这个布隆过滤器被使用。

压缩策略：Leveled vs Sized-Tired compaction

Size-tired compaction

Leveled compaction

B树

由于传统的机械磁盘具有快速顺序读写，慢速随机读写的访问特性，为了改变这个特性，文件系统或数据系统通常会对数据进行排序后存储，加快数据检索速度，这就需要保证数据在不断更新、插入、删除保持依然有序，目前最广泛的做法就是使用B+树和LSM树。

B+树

B+树是一种专门针对磁盘存储而优化的N叉排序树，以树节点为单位存储在磁盘中，从根开始查找所需数据所在的节点编号和磁盘位置，将起加载到内存中然后继续查找，直到找到所需的数据。

插入

WAL日志的工作

B 树与 LSM 树

经验法则

1、当写比读多时，LSM树相比于B+树有更好的性能，因为随着insert操作，为了维护B+树结构，节点分裂。读磁盘的随机读写概率会变大，性能会逐渐减弱。 LSM树相比于B+树，多次单页随机写变成一次多页随机写,复用了磁盘寻道时间，极大提高写性能。不过付出代价就是放弃部分读性能。

2、B+ 树每次都需要查询到叶子节点，查询性能稳定，叶子节点形成有序链表，范围查询方便