存储与检索

数据直接追加写入速度最快，但是查询时会受到数据规模的影响；为数据精心准备索引之后查询速度加快，但是会拖慢插入的速度，因为要更新索引。

1、驱动数据库的数据结构

1.1 散列索引

散列使用键值对来表示，其中键表示元素的标识，值则表示数据在文件中的存储偏移。

更新：当新的数据被追加写入文件时，更新最新的数据偏移在散列索引当中；
查找：使用散列索引找到对应元素的数据偏移，在文件中寻找该偏移位置并进行数据读取。

如果数据一直写入一个文件中，最终肯定会导致磁盘爆掉，为此可以把文件进行拆分，形成一个个的段（当磁盘占用达到一定的量时使用新的文件存储）。我们就可以对旧的段进行压缩操作了，因为一直在执行写入操作，最新的一条则表示为当前的最新值，之前的同键的记录都可以删除。

并且在合并的过程中如果大量的重复键，最终的段文件变得很小，这个时候又可以合并多个段，来保证一定的数据规模。而合并段的操作可以在后台进行，过程中使用旧段来提供查询操作，等待段合并完成写入新的段文件中，使用新的段来提供查询，删除旧的段。

在涉及过程中还需要考虑几个点：

删除记录：需要删除一个键和相关值时，需要在数据文件中追加一个逻辑记录，用于段合并过程上出当前键所有历史值；
奔溃恢复：散列索引存储在内存中，一旦系统崩溃，需要从磁盘重新建立散列索引，这个过程会非常耗时，因此可以将散列索引保存在磁盘中，恢复时更快的进行加载；
并发控制：一个线程写入，多个线程读取。

散列也存在很大的局限性：

一是散列的映射必须放入内存当中，如果存在特别多的键，崩溃恢复很难搞。
二是范围查询能力弱到没有，无法轻松扫描范围键的数据。

1.2 SSTables&LSM

在段文件的基础上，增加一个改变，要求键值对的序列按键排序，这样就形成了 排序字符串表（sorted string table），从而新增几大优势：

每个段文件的第一个数据是最值，因此可以按照归并排序的思路，即使在内存远远小于段文件时，段的合并操作依旧有效。（针对于相同键的更新，按照顺序写入的特点，最近段的值一定比其他段的数据要新，因此只需要保存最近段的值，而丢弃旧段中的值）。
为了在文件中寻找某一键的值，不需要再维护所有的键值索引，可以根据排序特性，根据邻近键的偏移开始寻找。（散列索引变得稀疏）。
第二条说了稀疏存储，因此可以将这些范围内的记录进行分块，稀疏索引中只需要存储块开始的偏移即可，块还可以被压缩从而减少磁盘占用和IO读取。

虽然在磁盘中也可以进行排序，但是在内存排序比在磁盘中要方便，因此可以通过红黑树或者AVL树等结构在内存中进行保存，之后再录入磁盘当中，如下方式：

增加数据时，将其添加到内存树结构当中（内存表）；
当内存表大于一个阈值时，将其作为一个整体写入到文件中；
查询时按照内存表、最近段文件、邻近段文件的方式进行搜索；
同时，后台合并段文件的将已经覆盖或者删除的键数据丢弃。

涉及到内存到磁盘之间的转换都会存在一个问题，如果内存数据还未写入磁盘时机器宕机，会导致内存数据全部丢失。因此可以使用日志文件的方式记录内存表的写入操作（不用关心日志的顺序写入问题），当内存表中的数据被写入磁盘之后，该日志记录就可以被删除。

当查找不存在的键值时会导致全数据扫描，因此可以通过增加一个布隆过滤器实现优先判断。

1.3 B树

B树将数据库拆分成块（页），一个块的大小传统上为 4kb，和磁盘的页大小保持，因为一次只读取或者写入一个页大小。每个页面都可以用地址或者位置来标识，因此可以在一个页面中通过地址引用另外一个页面。

一个页面对子页面的引用数量称为 分支因子，这个值同存储相关，例如一个分支因子为500的四层B树，在传统的页大小下可以存储 256TB 的数据，通常这个值不会太小，保证树的深度不会过大。

在数据写入时，为了保证可恢复性，增加一个预先写入日志的步骤（redo log），这样会导致每次写入数据时至少写入两次，如果页面分页了还需要再写入一次。同时因为底层写操作是用新数据覆写磁盘上的页面，因此即使几个字节的变化也需要接收整个页面的写入开销。

1.4 其他索引结构

多列索引：

连接索引：将一个列连接到另一个列的后面，索引则按照规定的顺序进行拼接组合。
多维索引：多个主键决定，例如经纬度决定地点（在标准 B 树或者 LSM 树中无法高效处理，一种方法是使用空间填充曲线，将多维转换成数字）

全文搜索：

全文搜索引擎允许搜索目标从一个单词拓展为包括该单词的同义词，忽略单词的语法变体，搜索在相同文档中的近义词，并且支持各种其他取决于文本语言分析功能。

2、事务处理&分析处理

事务处理：根据用户的输入来插入或更新记录，这种交互式的访问模式叫做在线事务处理（OLTP）；

分析处理：进行分析查询，而不是简单将原始数据返回给用户的叫做在线分析处理（OLAP）。

2.1 数据仓库

最开始事务处理和分析处理都使用相同数据库，但是 OLTP 数据库通常要求高可用和低延迟，进行分析的大量查询时会损害执行事物的性能，因此之后转而在单独的数据上进行分析，此类仓库被称为 数据仓库。

数据仓库作为一个独立的数据库，其数据包含各种 OLTP 数据的只读数据副本，为此，在进行数据导入的啥时候需要添加提取数据的转换层，将数据清理并加载到数据仓库当中，整个流程成为 "抽取 - 转换 - 加载"。

2.2 星型和雪花型

在分析型业务当中，数据模型的多样性很少，大多以相当公式化的方式使用，也称为星型模式。

星型模式：有一个事实表和一组维表组成，每个维表都有一个组件共同组成事实表的主键，在事实表中非主键的字段称为事实，一般都是数值或者是可以进行计算的数据。
雪花模式：相对于星型模式，维度表也有其子维度表。

3、列式存储

没有将一行的所有值都存在一起，二是将来自每一列的所有值存储在一起。

3.1 列压缩

通常情况下，一列中不同数值的数量与行数相比要小得多，可以将 n 个数值转换为位图。如果 n 非常小，位图可以将每行压缩成一个比特位，如果 n 很大，就会导致位图变得稀疏，这个时候还需要使用其他的压缩技术（游程编码），使每列的编码更紧凑。

游程编码：（0,0,0,0,1,0,0）---> （4 zero，1 one， rest zero），就是将位图表示的数据按照相同数量压缩。

3.2 排序顺序

对于列式存储而言，对于每一列分别执行排序是没有意义的，因为各个列文件之间的顺序要保持一致，要通过对应行组合出一整行的数据。

采用多列索引的方式，第一个索引键能够很好的的应用压缩，越靠后越混乱，但是能很好的降低扫描数据的难度。

针对于多列索引混乱的问题，有些数据库采用不同的排序顺序，在做高可用的冗余备份时使用不同的排序顺序，查询时调用适合该查询模式的版本，以此来加快访问速度。

3.3 数据写入

列式存储的数据写入时困难的，如果想在排序表的中间插入一行，所有的列文件都会被重写（前面说到的行由列中的位置标识，因此插入必须对所有列进行一致性变更）。

因此需要通过内存进行交换，写操作进入内存中的存储，积累足够多的数据时与磁盘文件进行合并；读操作优先检查内存，并合并磁盘列数据的检索，将两者的结果合并起来。