本章主要介绍数据库中常用的一些索引类型
哈希索引
对于key-value数据来说，内存中存储一张索引表，键为数据的key，值为文件中存储相关值的偏移量
为了避免随着时间，单个数据文件过大而导致磁盘被耗尽，将整个数据文件划分为一个个段，将段大小达到一定的数量时，就另起一个段写入日志，并且可以对段内的数据进行压缩，将相同key的kv进行合并
这样一个使用日志追加的方法看上去有点浪费空间，但是有如下的几个优点：
- 只需要进行append操作，顺序IO，速度快
- 段文件是append-only的，利于并发和崩溃恢复，因为所有的新数据都在日志的尾巴处
- 合并旧段可以避免数据文件出现碎片化的问题
但是哈希索引也有如下缺点
- 哈希表必须全部放入内存
- 区间查询效率不高
LSM-Tree 和 SSTable
上述的哈希表索引并不关心插入kv的顺序，导致了它的缺点，如果我们对插入的kv数据进行排序再存储，就可以解决这些问题，这种数据结构就叫做SSTable（排序字符串表），它的优点如下：
- 合并段更加的高校，因为所有的SSTable都是有序的，可以采用归并排序的方法合并段
- 在查找特定键时，不需要整张索引表，只需要这个键周围的一部分，如果需要查找handiwork，只需要载入handbag到handsome之间的索引表，在其中搜索
LSM-Tree的读写流程
写入的流程很简单，首先先写日志，在将数据append到最新的SSTable上，等到SSTable超出阈值大小就另起一个，将原来的写入磁盘并再合适的时候进行合并
读取的过程首先会从内存表中查找数据，如果没有再到磁盘中的SSTable中从新到旧一个一个查，因为这样的效率很低，所以一般使用布隆过滤器和一些其他手段来帮助快速确定元素位置
后台会周期性的进行合并和压缩的过程
B-tree
LSM树将数据分为一个个段，而B树将数据分成固定大小的页，每个b树的节点会有很多的key将值空间分为多个查找区间
每个节点上键的个数称为分支因子，通常都是几百个
B树的读写
b树的读取很简单，只需要顺着索引一路挑选节点走下去就可以了
b树的写入较为复杂，首先要根据key找到位置，根据key是否已经存在分为修改和插入，插入后需要调整page上key的范围，并且需要自底向上的调整它所有父节点的key范围，如果插入的节点导致该页过大了，就需要进行分裂操作，将一个页分裂成两个
为了防止在对b树进行操作的过程中系统突然崩溃导致数据错误，可以采取WAL的方式，先写log，再写数据
b树比起LSM树一大区别就是，b树采用的是原地更改，而LSM仅仅是追加文件，这样带来的问题是，如果多个线程同时访问或修改b树的一个key，会出现问题，需要加锁
B树的优化
- 不采用WAL和原地更改，而采用COW，这种方法对并发控制也有帮助，因为直到写操作完成替换了原来的页，才能读到新数据，否则读的一直是原来的数据
- 保存间的缩略信息，而不是完整的键，这样可以节省也空间，是的一个页中可以存放更多的索引信息，一个典型的例子就是B+树，通过只在叶子节点存储数据，使得树更加扁平，减少了树的层数
- 将逻辑上相邻的页放在磁盘的相邻位置，但是随着数据量的增长很难做到这一点，相比之下，LSM由于是按key排序，可以天然的做到相邻的数据存放在一起
- 添加额外的指针指向兄弟页，更好的支持范围查询
对于LSM-Tree和B-Tree
LSM-Tree的优点如下：
- 写性能良好，吞吐量大
- 更好的支持压缩，LSM树数据文件比B树小很多
LSM-Tree的缺点如下：
- 反复的读取合并SSTable会造成写放大
- 合并过程有时会影响正常的读写操作
- 合并日志的动作会分走磁盘带宽，降低读写操作的性能
B-Tree优点如下：
- 每个键对应唯一的位置
- 更强的事务语义
其他的索引结构
在索引中存储值
通常情况，索引可能存储了数据的引用，还需要根据索引跳转到实际存储数据的地方进行存区，当是有时针对特定的查询，可以直接将部分数据存储在索引中，使得仅仅使用索引就能回答某些查询，这种情况叫做索引覆盖了查询
多列索引
普通索引只是将一个列映射到一个值，但是例如人的姓名（姓，名），地理坐标（经度，纬度）都需要有多个列来确定一个值，标准的B树和LSM树无法解决这个问题，通常会有专门的空间索引，如R树来解决这些问题
全文索引和模糊索引
目前讲述的索引都只支持确定的键，而不能进行模糊搜索，如拼写错误的单词。全文搜索引擎支持对一个单词的所有同义词进行查询，从而支持模糊查询
在内存中保存所有内容
随着内存价格下降，一些内存数据库也逐渐流行，例如redis，他们通常更快，并且由于在内存中，可以实现基于磁盘难以实现的数据模型，例如优先队列，集合等
事务的处理和分析
针对数据库的事务已经分析，逐渐分化出了两种类型的模型OLTP(在线事务处理)和OLAP(在线分析处理)
| 属性 | 事务处理系统 OLTP | 分析系统 OLAP |
|---|---|---|
| 主要读取模式 | 查询少量记录，按键读取 | 在大批量记录上聚合 |
| 主要写入模式 | 随机访问，写入要求低延时 | 批量导入（ETL）或者事件流 |
| 主要用户 | 终端用户，通过 Web 应用 | 内部数据分析师，用于决策支持 |
| 处理的数据 | 数据的最新状态（当前时间点） | 随时间推移的历史事件 |
| 数据集规模 | GB ~ TB | TB ~ PB |
数据仓库
通常为了不影响数据库的性能，不直接在数据库上进行数据分析，而是将它们导入到一个数据仓库中进行分析
星形与雪花型分析模式
OLAP通常采用星形与雪花型分析模式，也成为维度建模，模式的中心是一个事实表，每一行表示特定时间内的一个事件，事实表中的列会引用其他的维度表，维度通常代表时间的who,what,where,when等方面，星形来源于在分析时，事实表位于中间，连接的一系列维度表就像星星的光芒
这个模板的变体被称为雪花模式，其中维度被进一步分解为子维度。例如，品牌和产品类别可能有单独的表格，并且 dim_product 表格中的每一行都可以将品牌和类别作为外键引用，而不是将它们作为字符串存储在 dim_product 表格中。雪花模式比星形模式更规范化，但是星形模式通常是首选，因为分析师使用它更简单
列式存储
因为分析中往往有大量的数据，但是只关心其中的几列，如果按行存储会很慢，不如将每一列单独存在一个文件中
[图片上传失败...(image-c2fd19-1659323003571)]
并且按列存储后因为每个文件中容易出现大量重复的值，可以对文件进行压缩
数据立方体与物化视图
通常会将一些经常使用的分析数据，直接拷贝一份副本，叫做物化视图，常用的方法之一为数据立方体
[图片上传失败...(image-287533-1659323003571)]
