数据库常用的索引结构
一个最简单的数据库：
#!/bin/bash
db_set() {
echo "$1, $2" >> database
}
db_get(){
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}
底层存储格式：一个名叫database的纯文本文件。每一行都是一个键值对，每次调用db_set就在文本最后添加新内容，相同键值的旧内容不会被覆盖。db_get查找文件中最后一次出现的键值来找到最新值。
数据库使用的日志也是一个仅支持追加式更新的数据文件。如果使用上述最简单的数据库来保存日志，当日志中保存大量内容时，db_get函数的性能会很差，它是O(n)的。
为了高效查找数据库中特定的键值，需要引入索引。
哈希索引
假设数据存储全部采用追加式文件，那么利用哈希索引来解决上述问题就可以采取如下策略：内存中的HashMap把每个键值一一映射到数据文件中特定的字节偏移量。
在这种策略下，为了获取某个值，只需要一次磁盘寻址就可以将value加载进内存。这种策略非常适合每个键的值频繁更新的场景。
由于我们采用的是追加式的更新，当数据非常多时可能会面临磁盘用尽的情况。解决方案：将日志文件(database文件)分解成固定大小的段，当文件达到一定程度大小时就关闭，并将后续写入到新的段文件中。同时，可以在关闭的文件中进行压缩，消除重复的键，只保留最新的键值对。对于这些段的更新可以交给后台线程完成。
当对日志段进行压缩以后，其大小往往会小于符定段大小，那么还可以对多个被压缩过的日志段进行合并。这个合并过程也可以交给后台线程完成，在这期间被冻结的旧日志段依然可以读写。当合并完成后，后续的读写可以切换到新的合并段上。
在实际使用中，还需要考虑很多其他问题，才能真正使该策略行之有效：
- 文件格式：日志文件采取何种格式
- 记录删除：由于采取追加式更新，需要在日志文件中追加一个特殊的删除标记（墓碑记录）
- 崩溃恢复：数据库重启，内存中的hashmap丢失，可以采取从尾到头读取所有段文件方式，或者将hashmap的快照保存在磁盘上
- 部分写入的数据：需要校验码
- 并发控制：由于写操作是顺序的，所以可以只用一个写线程。可以允许多个线程同时读
追加式日志的好处：
- 追加和合并操作是顺序写，性能比随机写高得多。
- 段文件是追加式的，那么并发和崩溃恢复要更简单
- 旧段的合并可以避免碎片化
局限性：
- 哈希表必须全部放入内存。如果有大量的键，导致需要磁盘介入时，性能大幅降低。哈希表需要大量随机IO访问，哈希表变满时，继续增长代价昂贵，并且哈希冲突时需要复杂处理逻辑。
- 区间查询效率不高。查询区间时，只能采取逐个查找的方式查询每一个键值。
SSTables和LSM-Tree
在哈希索引结构中，日志文件中的每个存储段都是一个键值对序列，键值对按照写入顺序排序，后出现的键值优于之前的值。
SSTable(Sorted String Table)：排序字符串表。将段文件中的键值对按键排序，并且要求每个键在合并的段文件中只能出现一次（段文件压缩过程已经确保了）。
相比哈希索引的优势：
- SSTable索引的日志文件，依然需要进行日志段的合并。但是由于每个段内都是按键排序的，那么合并过程可以并发读取多个段，按照MergeSort中的Merge过程，进行合并。合并操作的代价相比哈希索引日志段更小。
- 在日志中查找特定键时，不需要在内存中保存所有键的索引。内存中只需要保存稀疏索引，由于日志中按键排序，就算不知道具体段和偏移，也可以先根据内存中的稀疏索引，找到距离最近的键，再从该位置开始遍历查找。
- 对于区间查询：由于日志段内数据有序，查询时一次读取一个日志段，就可以将之后所有需要查询的数据加载进内存。区间查询时效率更高，减少IO次数。
构建和维护SSTable
由于写入的键值会以任意顺序出现，需要解决如何将记录排序的问题。
基于磁盘的排序：B-trees
基于内存的排序：红黑树或AVL树
基于内存的红黑树或者AVL树的存储引擎工作流程：
- 写入时，将数据加入到内存中的平衡树数据结构中（内存表）
- 当内存表超过阈值大小时，将它写入磁盘。由于内存表中数据有序，那么写入磁盘后的记录就可以有序。新的SSTable文件成为数据库的最新部分。在写入磁盘的同时，新数据写入内存中的新的内存表实例
- 读操作：首先检查内存表，再查找磁盘上的最新段文件，接下来是次新，直到找到目标
- 后台进程周期性地执行段合并与压缩过程。
为了防止数据库崩溃导致数据出错，还需要在磁盘上保留单独的日志文件。日志文件以记录当前内存表中的操作记录，当内存表被写入磁盘后，日志就可删除。
从SSTable到LSM-Tree
LSM-Tree(Log-Structured Merge Tree)
基于日志和压缩排序文件原理的存储引擎都被称为LSM存储引擎。
性能优化
在LSM-Tree中查找一个不存在的键会很慢：首先搜索内存表，然后回溯所有段文件。优化：布隆过滤器
还有对SSTable压缩和合并具体顺序与时机的优化。
B-trees
是几乎所有关系数据库中的标准索引实现。
B-tree将数据库分解成固定大小的块或页，传统上大小为4KB，页是内部读/写的最小单元。每个页面都可以使用地址或位置进行标识，页面之间依此标识进行相互引用。
某个页面被指定为B-tree的根，所有查询都是从根页面开始的。
B-tree中一个页所包含的子页引用数量成为分支因子。上图中的分支因子为6。
添加新键时，首先找到范围包含该键的页，并将其添加到页面中，如果页面空间不足以容纳新键，则需要将页面分裂为两个半满的页，其父页面需要更新，以包含新分裂的页。
B-tree总是保持平衡的：具有 n 个键的B-tree总是具有O(log n)的深度。
B-tree的基本写操作是使用新数据覆盖磁盘上的旧页。
关于使用B-tree的可靠性：
有些操作需要覆盖多个不同的页，例如，插入操作导致页溢出。这种操作往往比较危险，因为如果数据库在完成部分页写入之后发生崩溃，会导致索引结构破坏。
为了解决数据库崩溃之后数据恢复问题，可以采用预写日志(write-head log WAL)。预写日志是一个仅支持追加修改的文件，每个B-tree的修改必须先更新WAL再修改树本身的页。
优化B-tree
- 一些数据库不采用WAL来进行崩溃恢复，而是使用写时复制技术。
- 保留键的缩略信息，而不是完整的键，节省页空间。
- 尝试把相邻页放在磁盘中的相邻的块上，优化区间查询效率。
- 增加额外的指针指向相邻页
对比LSM-Tree与B-Tree
根据经验，LSM-Tree写入更快，B-Tree查询更快。
LSM-Tree的优点
B-tree索引必须写入两次数据，一次写入预写日志，另一次写入树的页本身。
LSM-tree索引时，由于反复压缩和SSTabel的合并，日志结构索引也会导致重写数据多次。
在数据库内，一次数据写入请求导致的多次磁盘写被称为写放大。
LSM-tree由于以顺序方式写入紧凑的SSTable，而不必重写树中的多个页，所以LSM-tree具有较低的写放大。所以LSM-tree通常能够承受比B-tree更高的写入吞吐量。
LSM-tree可以支持更好的压缩，因此磁盘上的文件比B-tree小很多。B-tree是基于页的，当页被分裂或者当一行内容不能适合现有页时，页中的空间无法使用。LSM-tree可以定期重写SSTable以消除碎片化。
LSM-Tree的缺点
由于LSM-tree的写入吞吐量很高，而磁盘的写入带宽是有限的。磁盘的写入带宽需要在初始写入（记录刷新内存表到磁盘）和后台运行的压缩线程之间共享。
当压缩没有被很好的配置时，就会发生压缩无法匹配新数据写入的情况。即，初始写入数据量太大，而压缩速率太小导致磁盘上未合并的段数量不断增加，导致磁盘空间不足。