此篇记录数据库的文件存储结构及索引相关的知识。

1.最简单原始的结构:追加式日志文件存储

  这个应该是最简单无脑存储结构，每一行都是一个key-value对——key当然就是物理主键——每次有新的写入则直接在文件尾部追加写入（不管是insert还是update），同时检索是也是从尾部开始检索（为了避免查询update过后的数据拿到旧的），而删除时则对对应行的数据增加一个墓碑。
  为了保证检索的效率，可以根据数据表所定义的结构而规定每一行的长度都是固定的，则检索时指针只需要移动固定的位置，而不需要进行动态的计算。
  如下两个图，下图数据行不定长，需要一个*号作为每行的分隔符，确定一行数据需要单个字符去扫描以确定一行完整的数据：

不定长数据行检索时效率不高

  数据行长度固定，则不需要分隔符，且可以进行跳跃式扫描，同时节省大量的逻辑运算。

固定长度的数据行可以跳跃式进行扫描

  追加式写的存储效率很高，因为与磁盘的物理特征有关系，顺序往下写恰巧对应磁头的顺序移动；而如果使用覆盖式update，硬盘需要进行随机写入的话反而会影响效率，算是一种空间换时间的做法。
  但是追加式写会带来文件无限制变大，冗余数据过多的问题，为了解决这两个问题，需要将文件分段存储，规定每个分段文件的大小，满了之后则顺序创建新的存储文件；另外考虑到数据大量更新后占据过多的冗余空间，所以需要定时（或定量，根据段文件的数量考虑等）对段文件进行合并压缩，合并时相同的key只保留最近写入的行，而丢弃所有相同key的旧行以及被墓碑（删除标记）所标记的行。

2.最基础的索引结构:哈希索引

  哈希索引即最基础的key-value索引，效率很高，但索引只能再内存中维护，如果放入磁盘中维护会因为需要大量的随机IO而影响效率，同时服务重启是需要全表扫描重新维护索引，如果表体积太大则会影响开机时间。

3.日志式存储升级版，排序字符串表SSTable（LSM-TREE日志结构的合并树）

  SSTable其实也是日志追加式存储，只是在写文件的时候是对key进行排序后写入的。
  ①按序写入带来的一个好处是，合并段的时候更加高效，不需要整段读入内存，只需要为需要合并的两个或多个段各分配一个指针按行顺序扫描，每一轮将多个指针中最小且最新的一个取出，写入到新的段文件尾部。需要注意的是需要对多个相同key的输入端筛选出最新的写入，合并过程参考下图。

SSTable合并段文件过程

  ②检索特定的key时效率更高，不需要扫描全部文件，将每个段记录自己key的开始与结束，然后直接通过二分法检索到对应的段文件，然后同样在相应区间的段文件使用二分法检索，时间复杂度仅为O(log2 N)。

检索key的过程

  值得注意的是，写入请求是无序的，如果想要持久化后有序，则写磁盘之前需要在内存中建立一个缓冲块，在某段时间内的写入维护在内存中的一个有序的数据集合（常用红黑树或AVL树），达到一定的大小后再整块写入磁盘；为了避免这块缓冲区丢失，会在写内存同时，写入到磁盘中单独维护的一块持久化缓存区按请求顺序维护，作为恢复的备份。
P.S.目前使用上述存储算法作为引擎的有LevelDB和RocksDB。

3.B-trees存储/索引结构

  B-tree(平衡树)是目前最广泛的数据库存储结构。
  与平时在一般场景编程时一个数据对象作为一个节点不一样的是，在数据库使用B-tree作为索引时是使用一个一个小型的数据集作为一个节点的，通常称为一页或一块（平时与他人讨论时大多习惯叫页）。一页内通常也是一个有序的list，list中除了存储数据行之外，还会存储子节点的指针（磁盘指针而不是一般说的内存指针），当一页写满后，会根据情况将本页分裂成2个新的页，或将新的数据行写入本页的某个子节点页中。

B-trees举例

  由于该树属于一个平衡树，因此总是能保持很高的检索效率，大多数数据库会保持树维持3~4层的高度，来保证效率。当分支因子为500的4KB也的四级树，可以存储高达256TB的数据。

可靠性保证
  B-tree存储结构与LSM-tree不一样的另一个地方是，B-tree在写入时会对定位到的页进行原地覆盖式写入，因此也需要不一样的意外预防手段。
  1）由于写数据页的时候有可能因为各种原因导致崩溃，所以通常会在真正写入页之间将数据写到【预写日志（write-ahead log,WAL）】,用于作为系统在数据库崩溃后恢复的依据。
  2）另外由于是原地更新页，所以并发写时需要对也加锁。
其他一些有意思的优化
  1）有部分数据库不对页使用覆盖写（因此也无需WAL预防崩溃），而是使用写时覆盖方案。修改的页会在新的位置创建写入，并修改指针指向新的页（详细得看后面了）。
  2）保存键的缩略信息以节省空间（大概是用了什么方法压缩）。

B-tree与LSM-tree的一些对比

  简单从算法上来理解的话，普遍认为B-tree读取更快，而LSM-写入更快，这是基于它们的实现上的特点而推理的：

1）对于B-tree来说，每次写入需要写WAL之后覆盖写整个页，因此会造成较大的写放大；尽管LSM-tree也有类似于WAL的备份日志，但LSM-tree每次仅写一行，开销比B-tree小得多，同时也因为它的顺序写符合磁盘硬件的运作方式。

2）对于LSM-tree来说，尽管后台需要周期性地进行排序与合并，但读取时也可能需要在多个不同的数据块进行检索。而B-tree只需要在树上进行检索即可读取到需要的信息。

3）另一方面，尽管LSM-tree可以承受更高的写入吞吐量，但由于其需要周期性合并的特性，合并段的时候需要与写入的请求竞争磁盘的写入带宽，加入在高负载的情况下，写入请求被分配了更高的优先级，长时间的高负载则会造成磁盘上大量的段无法被分配带宽进行读取合并，最终有耗尽磁盘空间的风险。