看了这三章，我最大的收货并不是说学到了什么新的知识，而是对以前通过各种渠道所掌握的知识重新进行了梳理和归纳，使它们有种脉络相通的感觉。
一、驱动你的数据库的数据结构
这也许是世界上最简单的数据库实现：
db_set () {
echo "$1,$2" >> database
}
db_get () {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}db_set的性能很好，每次都是在文件最后加一个log（这本书中的log指的是append-only的一个记录的序列），但是读的性能很差，每次都需要遍历文件，是O(n)的。 为了提高读的性能，我们需要索引来帮助我们做查询。本节会讲到各种索引结构以及它们的对比，它们背后的通用思想就是保存一些额外的元信息，在查数据的时候扮演一个路标的角色。
虽然索引加快了读，但是毫无疑问的增加了写的消耗（毕竟上文的写实现是最简单的）。出于这种原因，数据库一般不会默认把所有的东西都加上索引。
下面我们就来看看有哪些索引类型：
1. 哈希索引
1.1 基本概念和实现
对于只有少量的key但是value的值频繁变更的场景，我们可以考虑使用一个in-memory的hash表来处理： 
在我们目前讨论的范围内，每次写操作我们都是在文件后面append一条记录，那我们怎么处理磁盘耗尽的问题呢？
一个好的解决方案是，当文件片的大小到达一定的阈值时，后续的写操作就append到一个新的文件片，我们就可以对多个文件片做压缩的操作：把重复的key丢弃，只保留最近的更改：
在对多个文件做压缩时，可以在后台完成这个操作，等到完成后，把读请求切换到新的segment file，然后老的文件片就可以被删除啦！现在每个segment file都有自己的一个in-memory的哈希表，在做查询的时候，只要从最近的哈希表开始检查key在不在就行了，因为文件片数很少，所以不会消耗太多时间。
1.2实际使用时的考虑点
当然，在实际使用这种思想的时候，有一些细节的地方还是要考虑的：
- 文件格式： CSV不是log的最佳格式，二进制格式更简单更快捷： 先把字符串的长度编码成（多个）字节，然后后面跟着原始的字符串（这样就不需要什么分隔符了）
- 删除记录：如果想要删除一个key，我们需要在文件后面加一个特殊的删除记录，当log片在做合并压缩的时候，这个记录就意味着丢弃这个key先前所有的值。
- 宕机重启：如果数据库重启了，那in-memory的哈希表也就丢失了。原则上，我们可以从头读整个的segment文件来恢复，但这样会花很长的时间。我们可以在磁盘上存储一份哈希表的快照，这样重启就快了很多。
- 被写了一部分的log： 数据库可能在写log到一半的时候挂掉。我们可以加个check sum，在检查到这样的log时就丢弃或忽略。
- 并发控制： 因为写log是一个严格序列排序的操作，通常的实现是只有一个写线程。而数据文件分片是append-only、不可变的，因此可以有多个读线程。
1.3 why append-only
append-only log第一眼看上去是一个很废的操作： 为什么不直接update呢? 因为有如下好处：
- 顺序写比随机写快多了（就算是SSD硬盘，也更推荐顺序写，我们下文在说到B树和LSM Tree的时候会继续讨论这个问题）
- 并发和宕机重启都更简单（比如我们不需要考虑某个文件在被修改时宕机了，然后这个文件就包含了一部分新数据和一部分老数据）
1.4哈希索引的限制
哈希索引也有它自己的限制：
- 内容有限，装不下很多key。原则上讲，你可以在磁盘上维护一个hashmap，但是这样的话性能很差，需要一大堆的随机IO操作。而且处理哈希碰撞也很麻烦。
- 没法做范围查询
下面我们来看几个没有这些限制的索引结构。
2.SSTable和LSM Tree
2.1 SSTable的基本概念和实现
SSTables的全称是Sorted String Table，它与前面哈希索引的log片段相比，要求键值对是根据key来排序的，这就有了如下的好处：
- 对多个文件做压缩变的很简单，只需要做归并排序就可以了。（即使文件比内存还大）
- 不需要把所有的key的索引都存在内存中了，只需要保存一部分。比如索引了a和e，那么查b就只要在a和e之间查就好了。
- 我们可以把两个索引中间的内容压缩起来，这样既节省了磁盘，又减少了读请求时的磁盘IO带宽
那么，我们怎么做到key的有序呢？可以这么做：
- 当收到写请求时，把它加到内存中的一颗平衡树上（比如红黑树），我们有时候也叫它memtable
- 当memtable的大小到达一定阈值时（一般是几MB），把它写到磁盘中，作为一个SSTable文件。在写磁盘的时候，新的写请求可以写到一个新的memtable实例中
- 处理一个读请求时，首先查memtable，然后查磁盘中最近的segment，然后接着往前查，直到找到为止
- 后台一直有一个进程来把segment文件做合并压缩
- 这种方案的唯一问题是，数据库crash的时候，memtable中的数据就丢了。因此，可以在写到memtable中的时候，额外写到一个log file里（append-only），每次写SSTable的时候把那个log file删了就好了。
上面描述的算法也正是LevelDB和RocksDB（两个key-value存储引擎的lib）所使用的，这种索引结构最早被提出时，叫Log-Structured Merge-Tree。
2.2 性能优化
在把算法落实到实际中时，有很多问题需要考虑。
比如上述的LSM Tree，如果我们用来查找一个不存在的key，那就需要查memtable和所有的segment file，这无疑是非常低效的。
因此我们很容易想到用额外的布隆过滤器来判断key存不存在。
除此之外，SSTables何时、如何做合并也有很多不同的策略，最常见的如size-tiered和 leveled compaction。 LevelDB and RocksDB使用的leveled compaction，HBase用的是size-tiered，Cassandra则两种都支持。在size-tiered compaction中，更新、更小的SSTables被合并成更老、更大的SSTables。在leveled compaction中，key的范围被分为更小的SSTables， 而更老的数据被移动到另外的“层”中。
ps：关于两种压缩策略的区别，可以参考cassandra的压缩策略。
3. B树
上文谈到的LSM Tree到目前为止已经获得了很多的认可，然后它并不是最普遍的索引结构。最普遍的索引结构是B树。（忘了B树长啥B样的，看看下面的图回忆一下，一点B数都没有的，请翻数据结构书！！）
和SSTable一样，B树中的key也是有序的，但是它们的相似性到这也就结束了：它们的设计哲学完全不一样！
我们前面看到的log-structured的索引把数据库分为一些大小不一样的片段，一般是几个MB或者更大一些， 在写的时候经常是顺序写的。相反地，B树把数据库分为固定大小的块或者页，一般是4KB（有时候更大一些），每次读写都只操作一页。这种设计与底层的硬件相近，因为磁盘常常是按照固定的块大小来管理的。
3.1 让B树变得可靠
当我们在修改一个值时，可能会触发多个页的变动，以及改变父页的ref。这是个危险的操作，因为在这个过程中如果数据库挂了，那可能整个索引就错了。因此，数据库通常会用一份额外的redo-log来记录操作，这样当数据库挂了之后重启时，可以用redo log来重建index。
B树的另一个问题是更新时的并发控制。对于LSM Tree而言，就简单很多。因为merge操作都是后台做的，不需要和前台收到的query交互，最后segment的swap也是cas操作。
4. LSM Tree和B树的比较
4.1 LSM Tree的优势
B树索引在更新时通常需要至少两次的写: 一次是redo log， 一次是更新树自己的页（可能还会触发页的切分）。而且就算每次只改动一点点内容，也需要把整页重新写一遍。
LSM Tree通常会有一个更高的写的带宽，因为它是顺序写的，而不需要重写树中的多个页。这种特性在磁性硬盘上尤为重要， 因为在那上面顺序写比随机写快得多。
LSM Tree还可以被更好的压缩，因此通常比B树索引更小一些。 B树存储引擎常常会导致磁盘碎片：当一个页被切分或是一行装不进一页时，页中的一些空间就没有被利用起来。LSM Tree不是面向页的，而且会时不时的做压缩，因此磁盘消耗更低一些（特别是使用leveled compaction策略时）。
在SSD上面，硬件内部使用了log-structured算法来把随机写转换成了顺序写，因此对应用而言，随机写和顺序写差别就不明显了。但是，更少的空间消耗和磁盘碎片在SSD上也是很有优势的。
4.2 LSM Tree的劣势
尽管大多数LSM Tree的存储引擎实现都尝试增量压缩、避免影响并发访问，但是磁盘的资源是有限的，所以经常会发生一个请求需要等待磁盘完成昂贵的压缩操作的情况。这种对平均的吞吐量和响应时间影响不大，但是对于999百分线之类的性能影响还是很大的（因为有的请求就会撞到压缩事件的发生）。 相比之下，B树的性能则是可以预测的。
如果写的throughput很高，而且compaction策略没有很好的被配置，可能发生compaction跟不上新进来的写的情况。这样的话，读的性能也会降低： 因为需要读更多的segment file。一般来说，基于SSTable的存储引擎不会对写的速率做限流，因此我们需要自己详细地监控这种情况的发生。
B树另外的一个好处是，每个key在数据库中都确切只存在一个地方。这使得需要强“事物”语义的数据库格外青睐B树。 因为在很多关系型数据库中，事物的隔离是通过对一个范围内的key加锁来实现的， 在B树中，这种锁可以被直接加到树上。（在第七章我们会详细讨论这一点）
5.其他的索引结构
5.1 把值和索引存在一起
索引指向的值有两种可能： 第一种是确切的值，第二种是指向值的一个指针。第二种情况很普遍，因为避免了存在多个二级索引（ps： 比如mysql中的非聚簇索引就是二级索引）时的数据冗余问题。
当更新key的value时，如果value没有变得更大，那update就很高效：直接原地改就行了；如果value变大了，这个value很有可能就需要被移动到一个有足够空间的地方。在这种情况下，要么把所有的索引都更新，指向新的地址；要么在原有的地方做forward，指向新的地方。
做额外的一次跳转在一些对读性能要求特别高的情况下是不能接受的，因此我们可以考虑直接把值存在索引的地方，也就是所谓的聚簇索引。比如在MySQL的InnoDB引擎下，每个表的主键都是聚簇索引，二级索引指向主键。
5.2 多列索引
就拿mysql中的多列索引（复合索引）举例，在搜索时，先用第一个field确定范围，再比较第二个…… 与此相关还有一个最左匹配原则的概念。 多列索引的数据结构可能长下面这个样子： 
5.3 全文搜索和模糊索引
前面提到的索引都只能支持我们查询某个确定的key或是某个范围的key，而不能让我们查找相似的key。
Lucene可以支持我们查询一段文字，允许有一定的edit distance (一个edit distance的意思是一个字母被增加、删除或替换）。Lucene 使用了一种类似SSTable的数据结构来存储它的字典，但是不同于LevelDB之类的是，它的索引是一个字母的有限状态机（ps：关于有限状态机，我的认知只是编译原理里面的那些东西： 比如一个start点，可以跳到a、b、c，这三个点又可以直接到end点，且a还可以到b，b还可以到c，这样的话，无论用户输入a还是ab还是abc，都可以到end。不知道lucene和这个是否一致，以后可以细细看看lucene。我猜测它所谓的edit distance就是还允许a直接到c这样子。）。
5.4 把所有东西都放在内存里
前面的部分我们都只讨论了磁盘的限制，磁盘相比内存而言更难对付。但是因为它非易失、更便宜，所以我们也就忍了。但是随着内存越来越便宜，以及有的应用不需要那么大量的数据存储，因此慢慢地有些内存数据库的诞生。
最近这方面的研究方向是学习操作系统那样的LRU方法，当内存不够时，把一部分最不常用的扔到磁盘里。
二、分析型处理与列式存储
在早期的时候，一些SQL数据库同时被用来做OLTP和OLAP，后来，人们渐渐的用数据仓库来做OLAP的操作（在数据仓库中，一个fact表往往有上百个字段）。OLAP往往只需要一行记录的某几个字段，而不需要整条记录。如果用传统的关系型数据库来做的话，有很大的浪费，且性能也很差。因此，列式存储的概念就被提出了。（但是不是所有的数据仓库都用列式存储）
1.列式存储的概念
列式存储的思想很简单： 不把一行记录的值存在一起，而是把一列的值存在一起。如果一列的值存在一个单独的文件里，那么对该列做分析就只需要读这个文件就好了。如下图所示： 
2.列的压缩
除了把列的值存在一起，还可以对它们做压缩来减少对磁盘带宽的消耗。如果看上图的话，发现一列的值有很多重复，这对于压缩来说是非常有利的。