存储引擎有两类
LSM存储引擎
面向页面的存储引擎（基于B树）。
世界上最简单的数据库
Script
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)
另一种方法是去物业的办公室，根据你朋友的名字询问他的门牌号。这就是基于哈希值的索引的工作方式。
基于哈希的索引将键映射到存储值的位置。
现实生活中的例子。
Bit cask（Riak DB的默认存储引擎）使用基于哈希的索引。
Bit cask提供了高性能的读写，受制于所有的键适合在可用的RAM。
分割、合并和去重
磁盘没有空间了
写入操作附加在文件的末尾，它不断变得越来越大，一段时间后会耗尽空间。
分割
当文件大小增加到一个阈值时，关闭该文件以便进一步写入，并创建一个新的分段文件供写入。
去重
扔掉与重复的记录，只保留最新的记录。
合并
分段和去重将不断增加段的数量。所以要定期合并它们。
去重和合并发生在后台线程中。
真实数据库中的问题 实施
文件格式 CSV 还是 二进制格式
删除记录。墓碑被添加到标记一个记录为已删除。
崩溃恢复。Memtable崩溃可以从崩溃时的分段日志中恢复，它不会被排序。
部分书写的记录。在校验和的帮助下，部分写入的记录可以被避免。
并发控制。保持一个单一的写作者线程。
基于哈希值的索引的优势
写入速度更快
并发和崩溃恢复更好
基于哈希的索引的缺点
基于范围的查询是低效的
基于哈希的索引应该适合于内存中
SSTable和LSM
SSTable是指排序字符串表。
在SSTable中，对我们的片段文件进行简单的修改，键是以排序的顺序存储的。
构建SSTable
问题。解释一下SSTable中的下列流程
写到memtable
写入分段
读
崩溃恢复
SS表的优点
合并和去重比较容易。基于合并排序。
索引是稀疏的
范围查询和参照物的位置
基于SSTable的数据库
LSM（日志结构化合并树）
基于压缩和合并排序文件概念的存储引擎被称为LSM（日志结构化合并树）。
LSM树中的性能优化
布鲁姆过滤器
如果一个记录在数据库中不存在，DB必须扫描所有的分段文件。为了改善这一点，我们使用了Bloom过滤器。
去重策略。平坦的去重与大小通吃的去重
规模化去重
平整的去重
B-Tree
B 树是一种用于磁盘访问的数据结构
插入
分支因素
子节点的数量可以从B树的一个节点中引用。
B型树的高度
对数（N），以k（分支因子）为基数
B-树的节点大小
4KB（也可以更大）。
问题
给定一个大小为4的二叉树，分支因子为500，每个节点存储4KB的数据。该二叉树所存储的数据的最大值是多少？
B-树中的可靠性
就地更新：创建一个新的数据节点并更新指针。
崩溃恢复。WAL（写前日志）。
并发性。闩锁
WAL日志的工作
优化B型树
写入时复制
缩略键
顺序访问
兄弟姐妹的联系
B-树与LSM树
拇指规则
LSM树的写入速度更快
B-Tree的读取速度更快
LSM树的优势
写作时只写附录，速度更快。
LSM树的弊端
该磁盘的写入能力有限。
紧凑和合并利用了一些写操作，因此影响了外部写操作。
LSM树存储了同一数据的多个副本。
OLTP（在线交易处理）。
寻找一些记录并根据用户的输入进行更新。
OLAP（在线分析处理）。
数据分析
扫描大量的记录，读取几个字段，并计算出总量。
OLTP数据库是高度可用的，因此数据库管理员不允许分析人员在这个数据库上运行长时间的查询。由于分析性查询是昂贵的，扫描一个大的数据集，影响了性能。
数据仓库
它是一个独立的数据库，分析师可以在这里对其内容进行查询。
ETL
让数据进入数据仓库的过程被称为ETL（提取、转换和加载）。
星级模式
事实表：非常大
尺寸表
面向列的数据库
柱状数据库压缩
