概要
数据库核心：数据结构
最简单的数据库
#!/bin/bash
db_set () {
echo "$1,$2" >> database
}
db_get () {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}
文本文件存储，每行是k-v，写入时追加写，像日志一样，日志机制非常重要。
大数据量查找，效率慢，需要更高效的数据结构：索引。
存储系统重要的权衡设计：
- 适当的索引可加快查询，但多出来的索引会影响写入性能
需要手动选择索引，保证加速查询，又不带来过多的开销。
hash索引
所有数据顺序追加到磁盘，为了加快查询，构建在内存中的hashmap
- k-key
- v-文件中特定的字节偏移量
写入时，追加数据到文件，并更新hashmap中数据的偏移量。
查找时，使用hashmap找到对应key的偏移量（存储位置），然后读取内容
这就是Bitcask的核心做法。
适用场景：
key能全量放在内存中，并且单个key更新频繁。书中举例，key为视频url，value为播放量。
问题：
单个文件越写越大，耗尽磁盘空间怎么办
应对思路：
单文件到一个大小后，新建文件写入（分段），原文件变为只读，并且原文件重写丢弃重复更新的key，只保存最新的（就像redis的aof重写）。并且压缩的段更小，可以在压缩时合并多个段。
看似可行，但是达到工业可用，仍需要解决的问题
- 日志格式，csv格式并不紧凑，可以用二进制，如len+record
- 删除记录，需要支持delete，但是日志文件不支持删除，可以标记为已删除（墓碑），后续压缩时，发现墓碑标记，就丢弃
- 崩溃恢复，宕机重启后，内存中的hashmap会丢失。可以全量扫描重新创建，但是可行的优化是，持久化每个段的hashmap快照，重启时，可更快加载。
- 记录写坏，校验值，发现损坏部分并丢弃
- 并发控制，只有一个进行追加写，写入并发度只有1，但是已写文件是只读的，所以可以并发读取和压缩
乍一看，基于日志的存储结构存在折不少浪费：需要以追加进行更新和删除。但日志结构有几个原地更新结构无法做的优点：
当然，基于内存的哈希索引也有其局限：
后面讲的 LSM-Tree 和 B+ 树，都能部分规避上述问题。
SSTables和LSM-Tree
对于前面的kv数据，整体是
- 磁盘，日志分段
- 内存，hashmap
磁盘上的是追加写入，key是无序的。而**SSTable(Sorted String Table)**就是按key进行排序。
由于段文件合并，所以每个合并的段文件中，单个key只会出现一次。
对比hash索引的优点
- 高效文件合并。有序文件归并外排，顺序读写，对于不同文件的相同key，保留最新段，丢弃旧的段
- 无需内存中保存全量key的索引，即变为了稀疏索引。根据每个文件的记录界限，根据key的有序性，在对应的段内，进行二分查找即可
- 分块压缩，节省空间，减少IO。具有相同前缀key的放到一块，称为block，内存中只记录block的索引。
构建和维护SSTable
对于实际数据，key是乱序写进来的，如何保证key的有序呢？
问题拆解：
- 如何构建
- 如何维护
构建SSTable：磁盘整理数据较难，内存整理是方便的。
维护SSTable：为什么需要维护呢？首先要问，对于上述结构，我们怎么进行查询：
如果 SSTable 文件越来越多，则查找代价会越来越大。因此需要将多个 SSTable 文件合并，以减少文件数量，同时进行 紧缩（ Compaction）。
缺陷：
崩溃时，内存中数据会丢失。解决方案，每个写入追加到单独的日志文件。这不就是wal？有意思
从SSTable到LSM-Tree
前面的内容结合起来，便是LSM-Tree****（ Log-Structured MergeTree****），日志结构的合并树，因此，基于合并和压缩排序文件原理的存储引擎通常被称为LSM存储引擎
Elasticsearch 和 Solr 的索引引擎 Lucene，也使用类似 LSM-Tree 存储结构。但其数据模型不是 KV，但类似：word → document list。
性能优化
实际工程仍需对LSM-Tree做的性能优化
- 优化查找 。 对于不存在的键，需要先找内存表，然后从磁盘可能是很多个段按时间读取，最后读完发现不存在。可以用布隆过滤器
- 层级组织SSTable。不同的策略会影响SSTable压缩和合并的具体顺序和时机。 常见的思路有：大小分级和分层压缩。
核心思想：保存合理组织的，后台合并的SSTables，范围查询好，顺序写入
B-Trees
B 树于 1970 年被 R. Bayer and E. McCreight 提出后，便迅速流行了起来。现在几乎所有的关系型数据中，它都是数据索引标准一般的实现。
与 LSM-Tree 一样，它也支持高效的点查和范围查。但却使用了完全不同的组织方式。
其特点有：
查找。从根节点出发，进行二分查找，然后加载新的页到内存中，继续二分，直到命中或者到叶子节点。查找复杂度，树的高度—— O(lgn)，影响树高度的因素：分支因子（分叉数，通常是几百个）。
插入 or 更新。和查找过程一样，定位到原 Key 所在页，插入或者更新后，将页完整写回。如果页剩余空间不够，则分裂后写入。
分裂 or 合并。级联分裂和合并。
- 一个记录大于一个 page 怎么办？ 树的节点是逻辑概念，page or block 是物理概念。一个逻辑节点可以对应多个物理 page。
让B-Tree更可靠
b树会原地修改数据文件，当出现分裂时，要修改两个叶子节点，并更新父节点的叶子指针，这可能发生在崩溃时，导致恢复后出现错误。
解决：同样是WAL，mysql中就是redo咯
多线程访问
加锁，LSM-Tree在后台执行合并，并且旧段可以被并发读取
优化B-Tree
其他的优化
- 一些数据库用写时复制，而不是WAL来进行崩溃恢复。同时方便了并发控制
- 保留单个页中键的缩略信息，而不是完整信息，节省空间，可让一个页分更多的岔，有更少的层数。比如树中间页，可以只记录key的起始范围，可以将更多的键压入页中
- 为了优化范围扫描，有些采用写入时保证叶子节点的顺序保存在磁盘，但是这个成本很高。需要时刻保证有序性
- 为叶子节点增加兄弟指针，以避免顺序遍历时的回溯。即 B+ 树的做法
- B 树的变种，分形树，从 LSM-tree 借鉴了一些思想以优化 磁盘寻址
B-Tree对比LSM-Tree
存储引擎
B-Tree
LSM-Tree
备注
优势
读取更快
写入更快
写放大
1. 数据和 WAL
2. 更改数据时多次覆盖整个 Page
1. 数据和 WAL
2. 紧缩
SSD 不能过多擦除。因此 SSD 内部的固件中也多用日志结构来减少随机小写。
写吞吐
相对较低：
1. 大量随机写。
相对较高：
1. 较低的写放大（取决于数据和配置）
2. 顺序写入。
3. 更为紧凑。
压缩率
1. 存在较多内部碎片。
1. 更加紧凑，没有内部碎片。
2. 压缩潜力更大（共享前缀）。
但紧缩不及时会造成 LSM-Tree 存在很多垃圾
后台流量
1. 更稳定可预测，不会受后台 compaction 突发流量影响。
1. 写吞吐过高，compaction 跟不上，会进一步加重读放大。
2. 由于外存总带宽有限，compaction 会影响读写吞吐。
3. 随着数据越来越多，compaction 对正常写影响越来越大。
RocksDB 写入太过快会引起 write stall，即限制写入，以期尽快 compaction 将数据下沉。
存储放大
1. 有些 Page 没有用满
1. 同一个 Key 存多遍
并发控制
1. 同一个 Key 只存在一个地方
2. 树结构容易加范围锁。
同一个 Key 会存多遍，一般使用 MVCC 进行控制。
其他索引结构
二级索引
非主键的其他属性到该元素（SQL 中的行，MongoDB 中的文档和图数据库中的点和边）的映射
聚集索引和非聚集索引
索引可以加快查询速度，但需要占用额外空间，并且牺牲了部分写入开销，且需要维持某种一致性
多列索引
现实场景中，多个字段联合查询更为常见
SELECT * FROM restaurants WHERE latitude > 51.4946 AND latitude -0.1162 AND longitude
