什么是数据库

原始数据库最基本的功能：将数据存入库 和 将数据从库里取出

数据结构的处理

由此引出了我们存入库和取出库时对于数据结构的处理 分为了静态与动态处理

  • 静态:如mysql 存进去的时候就已经
    限定好了一个是一个二维的对象
  • 动态:如文档型数据库 里边的内容拿出来
    的时候要自定义解析的情况

如何存储

世界上最简单的数据库

#!/bin/bash
db_set () {
  echo "$1,$2" >> database
}

db_get () {
  grep "^$1," database | sed -e 
"s/^$1,//" | tail -n 1
}

上述的代码完成了一个极极极极简的数据库,存入数据时的复杂度是O(n),相当于一个单向链表，也相当于是一个日志

在DDIA中日志并非指的是我们在后端项目中用于记录各种操作的日志文件,指的其实是一份仅追加文件

散列索引

因为在上述的简单数据库中，取出数据的时候只能使用从头到尾扫描的方式，当数据量十分大的时候，时间就会变得很长。这时便引出了一个了个快速查找的问题

这时候我们便引出了本节的主题————索引

索引的本质上是一个空间换时间的典型，通过使用更多的存储空间来记录数据的文字，从而减少查找时间的损耗，同时，增加索引也就意味着更多的写入，导致了写入时间上的增大

最常用的是散列索引即常用的hash表的方式

内存散列表指的是 日志中将键映射到文件偏移量

写入的时候先更新散列映射，然后再追加至文件中

在名为Bitcask的存储引擎中
在内存中保留散列队列来，获得
更快的查找速度（这点与使用的redis比较类似）。同时允许内容被
存放至硬盘空间中。

存储

与此同时，我们在考虑索引的过程中
没有注意相应的存储问题，在当前的数据中我们都是通过追加的方式写入一个文件，也就意味着他会无限制的
增长-直到最后用完了所有的硬盘空间。

分段以及实现

我们可以采用分段的形式来防止空间耗尽：当日志增长到一定尺寸的时候关闭当前文件，并且开始写入一个新的段文件

单个段文件使用压缩，丢弃重复的键只保留每个键最近的更新，减小段文件的体积

同时压缩段文件，因为在归档之后将段文件进行了压缩 所以每个段文件会变得很小此时我们可以对段文件进行合并，减少段文件的数量，就可以减少对存储在磁盘中的IO存储，增加速度

实现

要从多个维度讨论

  1. 使用什么格式？二进制的格式，因为读出来的时候是有机器处理的可以转换成人类易读的方式
    但存的时候就不必考虑这类的关系了，因为是存在机器里的，更加简单->使用长度+字符
  2. 删除了记录：给予一个特殊的删除记录，然后在段文件合并的时候会通过这个记录知道
  3. 崩溃恢复：最简单的办法是-直接读取所有段文件 但是会使得时间很长，因为要检索段文件在硬盘
    中的位置，但我们可以将段文件的散列在内存中
  4. 部分写入记录，如何校验检测与忽略日志中损坏的部分？因为是追加，不会出现内存修改一部分的情
    况，要么就是文件末尾写完了，要么就是残缺的，很方便检测文件完整性
  5. 并发控制-因为仅仅追加到日志 所以常见的实现只有一个写入线程

为什么使用的是仅追加日志：

  • 追加和分段都是顺序写入 比随机写入更快‘
  • 因为段文件仅追加的特性（通常只会有一个写入线程）所以崩溃的时候 不会存在旧值和新值各自一
    部分的情况
  • 合并旧段的处理也能避免数据文件随着时间的推移而碎片化

分段存储的局限性：

散列表必须能放进内存。如果你有非常多的键，那真是倒霉。原则上可以在硬盘上维护一个散列映射，
不幸的是硬盘散列映射很难表现优秀。它需要大量的随机访问 I/O，而后者耗尽时想要再扩充是很昂贵
的，并且需要很烦琐的逻辑去解决散列冲突。

使用SSTables与LSM树

特性：要求键值对按照键的字符顺序排序即——排序字符串表（sorted String Table）

优势：

  1. 即使是文件大于可用的内存也方便排序，因为有顺序的原因，在加载文件内存的时候不必加载所有，就可以进行类似多链表合并的合并，并且合并后的内容依旧有序，但是追加型文件要全扫描才能确定好该键优先
  2. 无需保存所有键的索引，因为有序，所以可以快速确定范围
    3.由于读取请求无论如何都需要扫描所请求范围内的多个键值对，因此可以将这些记录分组为块（block），并在将其写入硬盘之前对其进行压缩。除了节省硬盘空间之外，压缩还可以减少对 I/O 带宽的使用

构建与维护SSTable

  • 在细节上，如何使得键值对是按照规律排序的——使用B树来维护
  • 有新的写入时 加入到b树中 这个内存书有时候被称为内存表当内存表大于某个阈值的时
    候写入到硬盘内
  • 收到读取请求时，首先尝试在内存表中找到对应的键，如果没有就在最近的硬盘段中寻找，
    如果还没有就在下一个较旧的段中继续寻找，以此类推
  • 时不时地，在后台运行一个合并和压缩过程，以合并段文件并将已覆盖或已删除的值丢弃掉

问题：在遇到崩溃的时候 最近的写入会丢失

解决：我们可以在硬盘上保存一个单独的日志，每个写入都会立即被追加。当对应的内存表写入到SSTable的时候，相应的日志都可以被丢弃

构建LSM树

在完成了SSTable之后 我们可以使用其制作LSM树LSM树相当于是一个存储引擎，承担的是数据的管理 而SSTable是组成LSM树的一部分，因为树还包含着内存中的数据部分。

在性能优化上：
查找数据库中不存在的键的时候，LSM树算法要先检测内存表，然后去到硬盘检查每一个SSTable段文件，才能确定不存在，而为了优化这个访问，我们通常会使用，布隆过滤器。
还有一些不同的策略来确定，SSTables被压缩和合并的顺序和时间。最常见的选择是 size-tiered 和 leveled compaction对于sized-tiered，较新和较小的 SSTables 相继被合并到较旧的和较大的 SSTable 中。对于 leveled compaction，key （按照分布范围）被拆分到较小的 SSTables，而较旧的数据被移动到单独的层级（level）。