作为数据库，在体系资本(CPU、内存、SSD、磁盘等)必定的前提下，我们欲望：
- 存储的数据更多：采取紧缩，这个世界上有各类各样的紧缩算法;
- 拜访的速度更快：更快的紧缩(写)/解压(读)算法、更大年夜的缓存。
几乎所有紧缩算法都严重依附高低文：
- 地位相邻的数据，一般情况下相干性更高，内涵冗余度更大年夜;
- 高低文越大年夜，紧缩率的上限越大年夜(有极限值)。
块紧缩
对于通俗的以数据块/文件为单位的紧缩，传统的(流式)数据紧缩算法工作得不错，时光长了，大年夜家也都习惯了这种数据紧缩的模式。基于这种模式的数据紧缩算法层出不穷，赓续有新的算法实现。包含应用最广泛的gzip、bzip2、Google的Snappy、新秀Zstd等。
- gzip几乎在在所有平台上都有支撑，并且也已经成为一个行业标准，紧缩率、紧缩速度、解压速度都比较均衡;
- bzip2是基于BWT变换的一种紧缩，本质是上对输入分块，每个块零丁紧缩，长处是紧缩率很高，但压休和解压速度都比较慢;
- Snappy是Google出品，长处是压休和解压都很快，缺点是紧缩率比较低，实用于对紧缩率请求不高的及时紧缩场景;
- LZ4是Snappy一个强有力的竞争敌手，速度比Snappy更快，特别是解压速度;
- Zstd是一个紧缩新秀，紧缩率比LZ4和Snappy都高不少，压休和解压速度略低;比拟gzip，紧缩率平起平坐，但紧缩/解压速度要高很多。
对于数据库，在计算机世界的邃古代，为I/O优化的Btree一向是弗成撼动的，为磁盘优化的Btree block/page size比较大年夜，正好让传统数据紧缩算法能获得较大年夜的高低文，于是，基于block/page的紧缩也就天然而然地应用到了各类数据库中。在这个蛮荒时代，内存的机能、容量与磁盘的机能、容量泾渭分明，各类应用对机能的需求也比较小，大年夜家都息事宁人。
如今，我们有了SSD、PCIe SSD、3D XPoint等，内存也越来越大年夜，块紧缩的缺点也日益凸起：
- 块选小了，紧缩率不敷;块选大年夜了，机能没法忍;
- 更致命的是，块紧缩节俭的只是更大年夜更便宜的磁盘、SSD;
- 更贵更小的内存不只没有节俭，反而更浪费了(双缓存问题)。
于是，对于很多及时性请求较高的应用，只能封闭紧缩。
块紧缩的道理
应用通悠揭捉?缩技巧(Snappy、LZ4、zip、bzip2、Zstd等)，按块/页(block/page)进行紧缩(块尺寸平日是4KB~32KB，以紧缩率著称的TokuDB块尺寸是2MB~4MB)，这个块是逻辑块，而不是内存分页、块设备概念中的那种物理块。
这些都导致现有传统数据库在拜访速度和空寄┞芳用上是一个此消彼长、无法彻调果肚９依υ?题，只能采取一些调和。
RocksDB 的块紧缩
以RocksDB为例，RocksDB中的BlockBasedTable就是一个块紧缩的SSTable，应用块紧缩，索引只定位到块，块的尺寸在dboption里设定，一个块中包含多条(key，value)数据，例如M条，如许索引的尺寸就减小到了1/M：
- M越大年夜，索引的尺寸越小;
- M越大年夜，Block的尺寸越大年夜，紧缩算法(gzip、Snappy等)可以获得的高低文也越大年夜，紧缩率也就越高。
创建BlockBasedTable时，Key Value被逐条填入buffer，当buffer尺寸达到预定大年夜小(块尺寸，当然，一般buffer尺寸不会精确地刚好等于预设的块尺寸)，就将buffer紧缩并写入BlockBasedTable文件，并记录文件偏移和buffer中的第一个Key(创建index要用)，如不雅单条数据太大年夜，比预设的块尺寸还大年夜，这条数据就零丁占一个块(单条数据不管多大年夜也不会瓜分成多个块)。所有Key Value写完今后，根据之前记录的每个块的肇端Key和文件偏移，创建一个索引。所以在BlockBasedTable文件中，数据在前，索引在后，文件末尾包含元信息(感化相当于常用的FileHeader，只是地位在文件末尾，所以叫footer)。
搜刮时，先应用searchkey找到searchkey地点的block，然后到DB Cache中搜刮这个块，找到后就进一步在块中搜刮searchkey，如不雅找不到，就大年夜磁盘/SSD攫取这个块，解压后放入DB Cache。RocksDB中的DB Cache有多种实现，常用的包含LRU Cache，别的还有Clock Cache、Counting Cache(用来统计Cache射中率等)，还有其他一些特别的Cache。
一般情况下，操作体系会有文件缓存，所以同一份数据可能既在DB Cache中(解压后的数据)，又在操作体系Cache中(紧缩的数据)。如许会造成内存浪费，所以RocksDB供给了一个调和：在dboption中设置DIRECT_IO选项，绕过操作体系Cache，如许就只有DB Cache，可以节俭一部分内存，但在必定程度上会降低机能。
传统非主流紧缩：FM-Index
FM-Index的全名是Full Text Matching Index，属于Succinct Data Structure家族，对数据有必定的紧缩才能，并且可以直接在紧缩的数据上履行搜刮和拜访。
FM-Index属于Offline算法(一次性紧缩所稀有据，紧缩好之后弗成修改)，一般基于BWT变换(BWT变换基于后缀数组)，紧缩好的FM-Index支撑以下两个最重要的操作：
- data = http://database.51cto.com/art/201706/extract(offset, length)
- {offset} = search(string) ，返回多个匹配string的地位/偏移(offset)
FM-Index的功能异常丰富，汗青也已经相当悠长，不算是一种新技巧，在一些特别场景下也已经获得了广泛应用，然则因为各类原因，一向不温不火。比来几年，FM-Index开端有些活泼，起首是GitHub上有个大年夜牛实现了全套Succinct算法，个中包含FM-Index，其次Berkeley的Succinct项目也应用了FM-Index。
FM-Index还支撑更多其他操作，感兴趣的同伙可以进一步调研。
然则，在笔者看来，FM-Index有几个致命的缺点：
网友点评
精彩导读
科技快报
品牌展示