从最基本的层面看，数据库只需做两件事情：向它插入数据时，它就保存数据；之后查询时，它应该返回那些数据。
本章我们主要从数据库的角度再来探讨同样的问题，即如何存储输入的数据，并在收到查询请求时，怎样重新找到数据。
数据库核心：数据结构
为了高效地查找数据库中特定键的值，需要新的数据结构：索引。本章将介绍一些索引结构并对它们进行比较，它们背后的基本思想都是保留一些额外的元数据，这些元数据作为路标，帮助定位想要的数据。如果希望用几种不同的方式搜索相同的数据，在数据的不同部分，我们可能定义多种不同的索引。
索引时基于原始数据派生而来的额外数据结构。很多数据库允许单独添加和删除索引，而不影响数据库的内容，它知会影响查询性能。维护额外的结构势必会引入开销，特别是在新数据写入时。
哈希索引
最简单的索引策略就是：保存内存中的hash map，把每个键一一映射到数据文件中特定的字节偏移量，这样就可以找到每个值的位置。
如上所述，只追加一个文件，那么如何避免最终用尽磁盘？一个好的解决方案是将日志分解成一定大小的段，当文件达到一定大小时就关闭它，并将后续写入到新的段文件中。然后就可以在老的段上执行压缩（去重）和合并。
追加写的有点：
- 追加和分段合并主要是顺序写，它通常比随机写入快得多，特别是在机械硬盘上。
- 如果段文件时追加的或不可变的，则并发和崩溃恢复要简单得多。
- 合并旧端可以避免随着时间的推移数据文件出现碎片化的问题。
哈希索引的局限：
- 哈希表需要全部放入内存。
- 区间查询效率不高。
SSTable和LSM-Tree
现在简单地该表段文件的格式：要求段中的key-value对的顺序按key排序。这种格式称为排序字符串表，简称SSTable。SSable相比于哈希索引的日志段，具有如下优点：
- 合并段更加简单高效，即使文件大于可用内存（由于各段内部有序，可使用归并排序算法）。
- 在文件中查找特定的键时，不再需要在内存中保存所有键的索引。可采用稀疏索引，一个键可以索引一个区间。
- 可以将段中临近的数据压缩。
构建和维护SSTable
- 当写入时，将新数据添加到内存中的平衡树数据结构中（例如红黑树）。这个内存中的树有时被称为内存表（内存表是最新的表，查询时优先查内存表）。
- 当内存表大于某个阈值（通常为几兆字节）时，将其作为SSTable文件写入磁盘。由于树已经维护了按键排序的key-value对，写磁盘可以比较高效。当写磁盘时，可以新建一个内存表，写入新的数据。
- 为了处理读请求，首先尝试在内存表中查找键，如果找不到，再到磁盘上查最新的SSTable文件，接下来再查次新的SSTable文件，以此类推，直到找到目标，或遍历完所有文件。
- 后台进程周期性地执行段合并与压缩过程，以合并多个段文件，并丢弃哪些已被覆盖或删除的值。
- 如果数据库奔溃，内存表中数据将丢失（还未写入磁盘）。为了避免该问题，可以在磁盘上保留单独的日志，每个写入都会立即追加到该日志，这个日志不需要按key排序。当内存表写入SSTable时，该日志可删除。
上述存储和索引结构呈现出分层的特点，这也是采用这种结构的LevelDB的名字由来。
总结SSTable特点： 1.每个文件内数据按键数据保存； 2.从上到下文件越来越久，查询优先级越来越低（分层）； 3.后台线程适时合并压缩； 4.每个SSTable有自己的内存Hash索引，不过键可以是稀疏的；
从SSTables到LSM-Tree
上述索引结构称为“日志合并树（LSM-Tree）”。基于合并和压缩已排序文件原理的存储引擎都被称为LSM存储引擎。
常见的使用了LSM-Tree的数据库：LevelDB、RocksDB、Casasandra、HBase、Lucene（ES和Solr）。
性能优化
- 当查找数据库中某个不存在的建时，LSM-Tree可能很慢。为了优化这种访问，存储引擎通常使用额外的布隆过滤器。
- 不同的策略决定SSTable的压缩和合并时机。最常见的方式是大小分级和分层压缩。
B-trees
对比B-tree和LSM-tree
根据经验，LSM-tree通常对于写入更快、占用磁盘空间更少，而B-tree被认为对于读取更快、更稳定。
另外，由于B-tree中一个键只对应一个副本，因此更容易实现事务，许多关系型数据库是直接在B-tree上对键加锁的来实现隔离的。
其他索引结构
若有收获，就点个赞吧
0 人点赞
