Designing Data-Intensive Applica
B树和LSM树的对比
整体来说,B树的实现比LSM更成熟,LSM在写上明显更快,但是B树在读上会比LSM快很多,因为LSM树需要去确认多个SSTable是否包含某个key。但是评测结果往往因为负载不同特点而差异很大。还是需要根据自己的应用来测试得到不同存储引擎的具体性能,这章简单对比一下2个数据结构的优势和劣势。
LSM树的优势
从底层算法层来说,B树索引每次写都要至少写两次磁盘,一次写WAL,一次写索引对应的页,即使很少的字段更新也需要把一整页数据写到磁盘。这种数据库一次写请求对应多次写磁盘的现象，被称作write amplification, 当你的底层用的是SSD的时候，这个值就尤为重要，因为SSD的写次数是有限的。
从速度来说，LSM树写更快,因为首先他写的次数就比B树少，另他还是顺序写,这个比B树的随机写快无数倍
从磁盘利用率来说, LSM更节省磁盘资源,因为他都是一个连续写的文件，所以相比一页一页的B树来说，有更高的压缩比。另外因为B树都是一页一页的，每个页当中是有空间浪费的，因为你并没有把这个页数据全部填满。
虽然很多SSD在内部硬件中会把随机写转化成顺序写,以使得刚才说的速度上的差异没有想象的那么大，但是这个仍然是一个隐患，更为密集的数据能够让有限大带宽服务更多的读写请求
LSM树的劣势
LSM的问题主要在合并带来的各类副作用上。
从速度来说, 因为文件合并需要和数据库的写入同时操作磁盘,这个时候就会出现读写请求只有在等待一个合并操作完成后才能继续写磁盘。虽然平均来说，这种影响很小,但是如果我们考虑百分比时间，这个时候你会发现你的慢请求很慢……，但是相比B树的读写时间就更可控一些。另外B树的读更快，因为一个key只在一个地方，不需要想LSM一样去多个文件索引里面找。
合并带来的另外一个问题是这样,还是刚才说的合并需要和数据库的读写同时读写磁盘，你的数据库越大，合并所消耗的资源就越多,留给线上的服务的IO带宽就越少，当你的数据库很大的时候，你就发现一直在合并,留给线上服务的请求就很少了。另外一个问题是，如果写请求特别高，有可能会发现你的合并速度跟不上写的速度，导致有更多的小文件出来，这会造成两个影响，1是磁盘可能会因为越来越多的文件被用光，2是线上查询速度会因为文件变多而变慢。
B树还有一个优点,因为他的key只存在一个地方，不想LSM那样可能有多个地方,所以他可以做到强事务。在关系数据库中，往往用锁来保证事务一致性，不会因为多线程出错，在B树中，这些锁可以直接跟树中对应的节点关联。
其他索引结构
到目前为止我们讨论的索引可以理解成关系数据库中的主键，他能独一无二的表示一条数据，其他数据可以根据主键找到对应的数据。在很多时候其实还需要所谓的“第二索引”，或者普通索引。这个和之前的kv索引很像，只是key不再唯一，或者说一个key对应多个value。有两种解决方法，第一种是把对应value的主键构成一个列表，把这个list写到key的value中。第二种是通过把key改造成key+主键的方式，把key又变成唯一的了
索引当中的值应该如何存?
索引其实还是一个kv结构,v其实细说有两种存法,第一种value就是value的内容,第二种是value存的是value在磁盘当中的地址。我们管存储数据地址的数据结构叫Heap File, 他是一个无序的数据结构。heap file在日常中很常见，因为他他避免了如果有多个索引指向同一条数据，当数据更新时，你就不需要更新这个索引的内容了。因为索引只是存了一个指针，而数据只存了一份。
但是这样做会使读性能下降很多，因为他需要多找一次heap file， 所以我们更希望数据存储的时候就能够自索引的而不需要索引，这就是聚集索引。比如Mysql当中的主键就是聚集索引。
对于聚集索引和非聚集索引而言，一个折中方案是覆盖索引(covering index), 覆盖索引就是把数据的某些列直接写到key对应的value里面，而不是存对应的数据的主键，这样如果你只查这些列，就可以直接返回而不是拿到一个数据的主键，然后再去对应磁盘找去。
其实索引相当于对数据在某种程度上做了一层复制,或者说给数据加了额外的信息，这能让查询加快，但是同时给写数据加了额外的负担。
多列索引
目前我们讲的都是给一个key，或者说某一列数据建索引,但是如果我们要查多列的时候就不够用了。最简单的方法是把所有需要索引的列按照指定顺序拼接起来构成一个大的key，然后就变成单列索引了。
当需要根据多列进行查询的时候，多维度索引一种更普遍的方式，这对于地理信息的数据库就特别有意义。举个例子，数据库中存储了每家饭店的经纬度，当我们查询的时候，需要查找给定经纬度范围内的饭店，sql类似这样, SELECT * FROM restaurants WHERE latitude>51.4946 AND latitude<51.5079 AND longitude> -0.1162 AND longitude< -0.1004;
传统的B树或者LSM树都无法直接支持这种查询，简单的方法是把经纬度经过某种算法，例如space-filling 曲线，转换成一个数字.然后用前面的方法搞。更为常见的方法是用空间索引,比如R树，这货就不细讲了，简介可以看这个。其实多维度的查询还有很多应用，比如说颜色查询(RGB)等等
全文搜索和模糊索引
前文谈到的所有索引都是精确索引,也就是说你需要知道准确的key才能查。对于模糊查询是不支持的，如果你把key拼错了就查不到了。如果要支持，就需要模糊索引，而这个用到了与之前全然不同的技术。
举个例子，全文搜索会支持搜索同义词, 各种词性，时态等等语言学上跟这个词有关的各种特征。针对拼错这种问题，Lucene还可以搜与query有特定编辑距离(海明距离)的内容。实现方式比较有意思,Lucene在内存中维护了一个针对单词的有限状态自动机，自动机的转换为一个levenshtein自动机, 也就是说两个状态之间有关系表示编辑距离为1。这样就可以给1个key,根据这个状态机很快找到指定编辑距离的所有可能的key，然后去搜。
如果所有内容全在内存会怎么样？
这一节讨论的数据结构其实都是在给磁盘擦屁股。跟内存相比，磁盘实在是很难用，但是他就2个好处，第一个是持久化，机器重启数据不丢，第二是便宜。但是因为现在内存越来越便宜，而且很多时候我们的数据量没有那么多，所以我们可以聊聊内存数据库。
有些内存数据库只用来做cache，机器重启数据就丢了，比如Memcached。还有些做的更好，他会把数据备份写入磁盘或者发给备机以做到持久化。重启的时候可以从磁盘或者备机当中恢复状态,尽管他还是要写磁盘，但是他依然是个内存数据库，因为磁盘只是在恢复数据的时候才会用到。
VoltDB, MemSQL, and Oracle TimesTen这类都是关系型内存数据库，数据库提供商宣称因为抹去了所有关系磁盘数据相关的包袱，数据库性能有显著提高。RAMCloud是一个开源的数据库，同时支持持久化。Redis 和 Couchbase也支持持久化，但是不严格保证，因为他是异步把数据写到磁盘，一旦挂了，就有可能有部分数据丢了。
我们总认为内存数据库变快是因为不用读写磁盘了，其实事实不是这样。因为虽然是一个依靠磁盘的存储引擎，如果你有足够大的内存，你也是不需要读写磁盘的。因为操作系统会把磁盘上的一部分数据缓存到内存。其实快的原因是你不需要再把数据组成可以序列化到磁盘的格式。也就是说你省掉了序列化、反序列化的时间。
另外一个好处是，由于不需要序列化，你可以用一些更复杂的数据结构，比如redis提供对于集合，优先级队列这种复杂数据结构的操作。
