作为后端程序员，选择合适的数据库与存储引擎，对于数据库与引擎进行调优是基本的素养。

针对事务处理和针对分析的存储引擎优化具有较大的差异。

存储引擎包含两个大的家族：日志结构的存储引擎和面向页的存储引擎。

数据库核心：数据结构

首先通过bash脚本配合追加以及grep等操作，构建一个基本的键值型数据库，而用于存储追加数据的文件就是日志，日志指仅支持追加式更新的文件。

如果一个日志中保存了大量的数据，每次查找时的全文扫描效率即为低下，因此需要新的数据结构：索引，索引能够提升查询的性能，但会降低写的性能。

哈希索引

键/值数据通常可采用哈希表等作为索引，哈希表可以保存于内存中，可以利用内存中的哈希表对于磁盘中的数据进行索引，也就是哈希索引。

Bitcask通过磁盘上的仅追加文件（日志）进行数据记录，利用内存中的哈希表记录数据的偏移量，新写入的数据追加至日志文件中，利用哈希表记录该记录在文件中的偏移。Bitcask非常适合执行多写操作，仅追加的方式相比于原地修改能够大幅提升写入性能，并且Bitcask具有压缩功能，使得较早的重复记录被覆盖。

Bitcask还需要考虑一些其他问题：

• 文件格式：应用二进制格式相比CSV有更好的效率
• 删除记录：利用墓碑节点即可
• 崩溃恢复：重启后重新读取日志文件恢复哈希表
• 部分写入记录：添加校验码，随时删除损毁的部分
• 并发控制：只采用一个写入进程

Bitcask的局限性：

• 哈希表体积：哈希表放置于内存时性能较好，若放置于磁盘则性能十分糟糕，因此哈希表性能十分受限于内存容量
• 区间查询效率：哈希表注定区间查询效率不行

SSTables和LSM-Tree

在Bitcask中键/值对无需排序，且同一文件中可能存在相同的键。

SSTables则要求每个键/值对的键在其所处的段文件中只出现一次，并且每个段文件中所有键/值对按照键的顺序排列，SSTables相比于Bitcask具有以下优点：

• 段文件的合并更加高效：各个段文件可通过归并的方式高效合并

• 无需存储所有键的索引：只需要少量索引配合二分查找就可以高效查询

• 易于压缩：各个块在写入磁盘之前可以压缩，减少文件体积和I/O带宽占用

构建和维护SSTables

SSTables相比于Bitcask需要维护排序结构，而如果为了维护排序结构频繁读写磁盘显然不合理，因此排序结构被保存在内存中，可通过红黑树、AVL、跳表等方式实现，通常其工作流程如下：

1. 在写入（增删改）时，将新的数据添加到内存中的跳表，称之为**内存表**
2. 当内存表大于某个固定阈值后，将其形成**SSTables**并写入磁盘，写入旧的内存表后，建立一个新的内存表
3. 在查找时，先行查找内存表，再查找最近的SSTables，接下来是次新的，以此类推
4. 后台周期执行SSTables的合并与压缩

除此之外，还需要防止程序崩溃导致的内存表丢失问题，通常采用预写日志（Work Ahead Log）

从SSTables到LSM-Tree

基于以上逻辑，就构成了日志结构合并树（Log-Structure Merge Tree）的出行，被应用于LevelDB、RocksDB等数据库。

性能优化

查找LSM-Tree中不存在的键可能造成大量的读取，采用布隆过滤器进行优化

设计合理的压缩与合并策略，将SSTables分层并设定为不同的大小，设计基于体积或访问落空次数的合并策略

LSM-Tree的魅力在于保存远大于内存的数据，牺牲较少的读取性能获得较大的写入性能

B-tree

Bitcask和LSM-Tree都属于基于日志的索引，但是B-tree才是最为常见的索引，是关系型数据库的基石。B-tree是一种基于页的索引结构，页通常是磁盘读写的最小单元，大小一般为4KB，每个页通过地址或者位置进行标识。

B-tree中某一个页被指定为B-tree的根，B-tree是一种多路查找树，除叶子节点外的每个页指向多个页，即具有多个子节点，每个页包含的引用数量称为分支因子，对于B-tree中某个项进行查询，需要递归的进行操作，各种查询的时间复杂度都为对数时间复杂度。

是B-tree可靠

由于B-tree中插入导致的页溢出等问题，同样需要机制保证数据库能够从崩溃中恢复，常见的方式为预写日志即WAL。

除此之外B-tree具有并发问题，需要通过锁等手段进行控制

优化B-tree

典型措施如：

• 保存键的缩略信息，节省页空间，使得分支因子增加，从而减少树的层数
• 尝试将相邻叶子的页面在磁盘上顺序保存
• 对于叶子节点，添加前后的引用，增加范围性能
• 运用写时复制

对比B-tree和LSM-tree

总体来看，通常认为B-tree适合读而LSM-tree适合写

LSM-tree的优点

B-tree写入至少包括两次：对日志写入，对树中页的写入，即便是少量内容修改也需要对于整个块进行覆盖，具有较大的写放大，写放大指一次写请求引发磁盘的内部多次写入的现象，对于写密集应用，性能瓶颈很可能在于写入速率，可以认为LSM-tree相比B-tree写放大更小（本人对此处存疑），这对于写入效率和磁盘寿命都有好处。

LSM-tree更易于压缩，LSM-tree不是面向页以及定期重写的特性适合进行压缩。

LSM-tree的缺点

压缩占用磁盘带宽的问题

B-tree面向页的特性使得其很适合事务

其他索引结构

以上只讨论了键/值索引，就像关系模型中的主键，用于标识关系（表）中的一行。

除开主键索引，二级索引也很常见，通过CREATE INDEX命令在某个字段之上建立，二级索引可以基于各种键/值索引构建，B-tree，LSM-tree都可以用于二级索引。

在索引中存储值

可以将数据行直接存储于索引之中即为聚簇索引，在InnoDB中主键采用聚簇索引，而二级索引引用主键即为非聚簇索引。

聚簇索引和非聚簇索引具有一个折中——覆盖索引，支持在索引中只保存部分列的信息。

增加索引虽然可以提升查询效率，但是增大了写入开销，并且事务更难实现。

多列索引

通过多个列进行排序的联合索引

适用于地理空间等特殊数据的多维索引

全文搜索和模糊索引

并非所有的查询都有确切的数据，对于搜索引擎等需要模糊的搜索

在内存中保存所有内容

Memcached、Redis等内存中的键/值存储可以作为缓存，提升效率。

事务处理与分析处理

以上所说的索引技术通常面向博客、游戏、电商的事务处理，该模式通常称为在线事务处理（online transaction processing, OLTP），而对于企业用户可能会有数据分析的需求，改模式称为在线分析处理（online analystic processing, OLAP）,相比之下OLAP具有数据规模大，对大量数据进行汇总，访问频率较低等特点，因此通常应用特别的数据系统进行分析工作，这个数据系统称为数据仓库。

数据仓库

一般来说让数据分析人员在OLTP数据库中进行分析通常并不合适，需要单独的数据仓库

OLTP数据库与数据仓库之间的差异

数据仓库和OLTP都往往采用SQL进行查询，而SQL只是声明式的查询，数据仓库和OLTP区别在于对于SQL的优化差别很大

星型与雪花性分析模式

OLAP中通常具有一个非常庞大的事实表，保存了海量记录，可能具有几百个字段，围绕事实表还有许多维度表，事实表中的列可能引用维度表中的外键。

事实表周围围绕维度表构成了星型分析模式，如果维度表还具有维度表，那么就形成了雪花型分析模式。

列式存储

在OLTP数据库中，通常按照行进行存储，而由于OLAP的诸多特性，OLAP将每列中的所有值存储在一起，称为列式存储。

列压缩

由于某个列中可能有上千万条数据，但数据取值只有固定几种情况，因此可以进行压缩，如果某列有n种取值共计m行，其基本流程如下：

1. 对n种取值作one hot处理，将一个列拆分为n个列
2. 每个列用长度为m的bitmap，形成了共计n个bitmap
3. 采用游程编码压缩每个bitmap

内存带宽与矢量化处理

涉及到cache、乱序执行等问题

列存储中的排序

如果只是排序单独的一列没有意义，必须关联好所有行才有意义。

OLAP应用可以指定多个列进行排列，类似于联合索引。

排序好的列可以极大的提升压缩（游程编码）的效率

几种不同的排序

对于同一个表，可以存储多种排序方式形成的表，相当于具有多种二级索引，可以提升处理效率。

列存储的写操作

直接对于压缩的列进行写入是不可能的，通常借助于LSM-tree的思想，先将所有的写入添加至内存，并将其添加到列存储中，此时执行查询需要结合列数据和内存最近的写入。

聚合：数据立方体与物化视图

OLAP应用中可能设计到大量的聚合操作，如COUNT，SUM、AVG、MIN等，因此可以对于常见的计数总和进行缓存，常见的一种方式为物化视图。物化视图还有一种特殊方式为数据立方体，在特定的维度上存储聚合数据。

小结

本章讨论遵循以下逻辑进行：

• 面向事务处理（OLTP）
  • 面向日志结构
    • 哈希索引与Bitcask
    • SSTables与LSM-Tree
  • 面向页
    • B-Tree
• 面向分析处理（OLAP）
  • 列存储