1. 数据库核心：数据结构

1.1. Append-Only Write with Hash Index

a) Append-Only

任何修改都直接写到文件的最后，即任何修改，只会执行append操作。

这种设计有一些好处：

追加和分段是顺序写，更快
并发和崩溃恢复简单
合并旧段可避免碎片化问题

这种设计有一些问题需要解决，也有对应的解决方法：

文件过大
- 将文件分段，当一段到达一定大小后将其合并压缩（丢弃重复的键，保留最新的）
- 压缩过的多个段也可以进行合并
格式问题
- CSV不是最好的，纯字节保存应该更好
崩溃恢复
- 内容可从头到尾扫描恢复
- 索引需要存储快照到磁盘
删除记录
- 插入墓碑标识（即插入undo/delete操作标识）
部分写入的记录
- 插入的值有校验值，提供校验
并发控制
- 写一般单线程，读可多线程

b) Hash索引

使用K-V的Hashmap，索引值是键在存储介质中的位置。

提供$O(1)$的访问时间，但是有一些问题：

需要将表全部放到内存中，即使放入磁盘，由于随机访问过多，性能不好（对于大表）
区间查询效率不高，需要全表扫描

1.2. SSTables and LSM-Tree

a) SSTables

本节下，写入的文件格式会按照键的顺序排序，这种格式为SSTable（字符串排序表）。

SSTable比Append-only with hash index的好处：

合并更加简单高效，算法只需要对归并排序进行修改即可。而归并排序是外排序的基础，可解决文件大而内存小的问题。
不需要保存所有键的索引，可以是稀疏的，然后通过有序性定位范围，进行查找。

构建和维护

先将记录写入内存中的平衡树（这个树为内存表）中
内存表大小到达上限后，将其作为SSTable段文件，写入磁盘
读请求到来，首先查找内存表，然后查找最新的段，其次查找次新的段，递归下去
后台进程周期性执行段的合并与压缩
应对崩溃恢复，额外添加append-only log，从这个日志中恢复，而SSTable写入磁盘后，对于的append-only log可被删除

b) LSM-Tree

日志结构合并树。而上述的“构建与维护”小节即LSM Tree本质的思想。具体的实现会有多种，如：

LevelDB，Cassandra采用层级合并（经典LSM只有2层，一层在内存，一层在磁盘）
HBase采用大小分级合并

性能优化

如：

添加一层Bloom Filter，减少不必要的读
层级合并（旧数据会被分级到单独一层/下一层，层数一般有限制）和大小分级

1.3. B-trees

B-trees是一类树的集合，如B+树等，常用于数据库索引中。

索引值往往是页/块标识符，因为这更适合于存储硬件特点。

a) 维护可靠性

通常使用Write-ahead Log（append-only），写入树之前先写日志，以便于崩溃恢复

b) 优化

如：

不使用WAL进行崩溃恢复，而使用copy-on-write（利于并发控制）
保存键的缩略信息，而非完整信息，减少存储大小
让相邻叶子页按顺序保存在磁盘上，叶子页添加额外指针指向前后结点（B+树）
变体，如分形树，借鉴日志结构的思想

1.4. LSM-Tree与B-Trees的对比

a) LSM-Tree

优点：

写放大少（写次数越多，可用带宽越少），写入吞吐量大；
更好支持压缩，碎片少，存储开销小。

缺点：

压缩时影响正常的读写操作（压缩需要配置带宽限制）
每个键在索引中有多个副本位置

b) B Tree

优点：

每个键唯一对应索引中的某个位置，能提供更强大的事务语义

缺点：

至少写2次（一次write-ahead log，另一次树页本身），且几字节的修改要承受整个页的开销
面向页面存储，会有碎片多的问题，存储开销大

1.5. 其它索引与优化

a) 二级/辅助索引

键可以不唯一，可通过将索引的每个值成为位置的列表，或给键增加额外标识使其唯一。

b) 索引存值

将索引行存在索引中（聚集索引），增加局部性。

聚集索引：在索引中直接存储行数据，因此，索引的键顺序和实际物理存储的行顺序相同
非聚集索引：在索引中存储行的引用（顺序一般不一样）
覆盖索引/包含列索引：前两者折中设计，索引中包含一部分列的值

c) 多列索引

将多个列作为键的索引，适合查询多个字段。

级联索引：将一列追加到另一列，组合成一个键
多维索引：如R树（专门用于地理空间的所有）

d) 全文搜索和模糊索引

常见的工具有：Lucene。其类似于SSTable，索引是键中的字符序列的有限状态机。

e) 在内存中存储所有内容

不使用磁盘，直接使用内存来加速（内存数据库），有些内存数据库提供持久化的能力，也有的提供类似于OS的页面置入置出的能力。

2. OLTP与OLAP

事务：一个逻辑单元，包含一组读写操作。

事务处理：不一定有ACID性质，只意味允许客户端进行低延迟的读取和写入（交互式的事务处理即OLTP）

分析处理：汇总/聚合信息，不返回原始数据（OLAP）

	OLTP	OLAP
Read	基于键，返回少量记录	对大量记录汇总
Write	随机访问，低延迟写入	批量导入或事件流
场景	终端用户	内部分析师提供决策
数据表征	最新的数据状态	随时间变化的所有事件历史
数据规模	GB~TB	TB~PB

数据仓库

单独的一个数据库，其包含OLTP系统的只读副本，它周期从OLTP数据库提取数据，或者通过更新流拉取，然后转化成分析友好的格式，执行数据清理，然后导入到数据仓库以便于查询，以不影响OLTP系统的运行。

a) 星型分析模式

即维度建模。

中心是基于一个事实表（通常很宽），记录事件。每一列都代表一个属性，可能是外键，对应的表就是维度表（可能也很宽）。

这样，一系列维度表包围了一个事实表，类似于星星。

b) 雪花分析模式

星型模式的变体，维度可进一步细分（作为外键），即上述的维度表可以是多级的（而星型模式是一级的）。

更加规范化，但常用的还是第一种。

3. 列式存储

不以行存储数据，而是以一列为整体存储数据（一列数据存储到一起）。

通常一列单独存在一个文件中，当只读取解析该列时，只需读这个文件，降低消耗

对于数据仓库而言，事实表通常很大，且查询时通常只针对少数几个的维度，因此这种场景下，列式存储有优势。（如压缩、空间局部性、缓存友好等）

对于OLAP系统而言，对于某个属性的聚合，只需顺序扫描一列而不需扫描整个行，有很好的效率（存储开销低、局部性好）

对于顺序扫描而言，索引影响不大，最重要的是数据的紧凑性（减少数据量）

3.1. 列压缩

可通过压缩数据降低磁盘吞吐量的要求，而列式存储非常适合。

常见的压缩有：位图压缩。

3.2. 排序

仍需要根据行位置约束，进行一次整行的排序。

它还能帮助进一步压缩列，降低存储消耗。

3.3. 写操作

写入更加困难，对于压缩的列，不能进行原地更新的方式（像B Tree一样）。

因此，类似与LSM Tree一样，首先写入内存存储区并将其添加到排序的结构中，接着写入磁盘，当积累足够的写入时进行列文件的合并，并批量写入新文件。

查询时要结合内存和磁盘的数据。

3.4. 聚合：数据立方体/物化视图

类似于RDBMS的物化视图，聚合的物化视图在底层变化的情况下会进行更新。

其常见的特殊情况是数据立方体/OLAP立方体，是由不同维度分组的聚合网格，每个维度都是一个外键（见维度表）。沿着一个维度扫描汇总得到一个减少一个维度的汇总值。

优点：

查询很快，不用扫描大量的行，只需查看对应维度的总和

缺点：

缺乏查询原始数据的灵活性

DDIA-数据存储与检索