ch3 存储与检索

事务性负载 or 分析性
存储引擎：日志结构（log structured）、面向页面（page oriented）例如b树

db的数据结构

最简单的数据库

grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
#grep取$1,开头的行
#sed s/aa/bb/ 把aa替换为bb，这里把$1,替换为空，即删除
#tail 只输出最后一行（相同key，取最后添加的value）

索引：存一些额外元数据，加速查询（会拖慢写入的速度）

哈希索引

1. 例子：磁盘上写如日志，以追加的形式。内存中保留key-value映射，value=「磁盘日志中的byte offset」。
2. 适用于，key较少，value更新频繁。 、
3. 对于日志持续增长，可以分为不同的段文件，每个段维护一个内存的hash映射。对段文件进行压缩，只保留最后一个key的value即可。
4. 应用bitcask。
5. 日志追加的优势：顺序写入快于随机写入；并发和崩溃恢复简单，文件中不会有新值、旧值混在一起。
6. 劣势：散列表必须能放入内存，范围查询，也是对散列一个个查找，效率低。

SSTables和LSM树

SSTable+内存表+稀疏哈希索引

1. 日志规定为排序字符串表 sorted string table，键值对按键排序。（那么现在日志的key就没有重复了）
2. 日志压缩：合并几个SSTable段，只需要归并排序。遇到相同的key，只需保存最晚的段文件中的key。
3. 稀疏哈希索引：由于键是排序的，内存索引可以按日志几千字节存一个key-value（如果日志key-value是定长的，甚至可以不要索引，直接在段文件上二分查找）
4. 构建维护SSTables：在内存中维护树形结构（红黑树或avl），常称为内存表（memtable）。到达一定阈值（几兆字节）按顺序落盘即可。查询时，先找内存表，如果没有，再按时间倒序查磁盘段。为防止db崩溃memtable丢失，磁盘上可以保存对memtable操作的，顺序写入的日志。只要SSTable落盘即可丢弃。
5. 用SSTable制作LSM树：基于上述合并和压缩排序文件原理的存储引擎，叫LSM树（log structured merge tree）。

B树

b树页面+WAL

1. 广泛用于关系型数据库的索引
2. B树将数据库分为固定大小的块或页面（常为4KB）。可以理解为B树索引的页面就是磁盘页面。
3. 每个页面可以用地址标识，这允许一个页面引用另一个页面。可以构建页面树。某个页面会被指定为B树的根，索引查找一个key时从这里开始。
4. 一个页面引用的子页面数量称为分支因子（常为几百个）。有n个键的B树总是有$Olog(n)$的深度。一般一个数据库有3、4层的B树即可。
5. B树底层写操作就是修改页面，与LSM的append不同。有时一个数据插入可能需要拆分几个页面，若中途db崩溃，则会引起索引损坏（孤儿页面）。为此，设计一个预写式日志（write-ahead-log），也叫redo-log，仅以追加的方式，记录每个对b树的操作。用于崩溃时的b树恢复。
6. 并发访问b树时，需要用到锁存器（latches）
7. 每个叶子页面，存左右兄弟的指针，便于顺序扫描。

B树和LSM树

1. db的一次写操作，需要对磁盘多次写入（例如b树需要写页面和WAL）,成为写放大。
2. LSM通常是SSTable在磁盘上的顺序写入，而B树对页面的随机写入，故而LSM通常有较高写入吞吐量。
3. LSM的压缩，占用磁盘空间空间更小。但压缩时会影响正常读写操作。
4. B树一个键只存在于索引中的一个位置，对事务支持更有利。

索引类型

1. 聚簇索引：索引中存储行数据。非聚簇索引：索引中存储对数据的引用。覆盖索引：索引中存储一部分列值，避免回表。
2. 联合索引：通过将一列的值追加在另一列后面。mysql中的最左匹配原则，遇到范围查询就会停止走索引。如果出现例如查找经纬度(a<latidude<b and c<longitude<d)需要多维索引。方法1是利用空间填充曲线将二维位置转换为单个数字，方法2用特殊的空间索引R树。
3. 全文索引、模糊索引
4. 内存索引：redis

事务和分析

1. OLTP online transaction processing, 在线事务处理，查找某几个key并作修改，需要高可用、低延迟。OLAP online analytic processing，在线事务分析，通常扫描全表，每行读取几个字段，并做聚合。
2. 为了保证OLTP性能，把数据只读版本，定期抽取-转换-加载（ETL）到数据仓库，供OLAP。OLAP的数据访问模式不同，所以优化方法与前述建立LSM、B树索引不同。
3. 星型模式：中心为事实表，四周为不同维度属性。事实表可能几百列，行数膨胀的也很快。雪花模式是星型模式的变体，将维度表再细分。
4. 列存储：将事实表的每列，按行的顺序，存于不同文件。（因为事实表的访问常为特定几列，如此可不同加载一整行）
5. 列压缩：进一步通过压缩降低对磁盘吞吐量的需求。数据特征：列的不同值的数量远小于行数（不同商品数量<<交易数量）利用位图编码，不同的值占用一位。如果不同的值很多，还可以用游程编码，使压缩更紧凑。（位图这里不太懂）
6. 列压缩可以通过矢量化处理，提高cpu效率。
7. 指定第一排序列、第二排序列，可以帮助压缩列。可以指定不同的排序顺序，相当于面向行的存储中有多个二级索引。写入列存储，由于有压缩，最好是使用LSM树。
8. 物化视图：缓存一些使用频繁的聚合结果，快，但支持的查询不灵活。适用于olap，因为写操作比较少。

小结

• OLTP 和 OLAP，前者请求多，后者每个请求开销大
• 日志结构派（SSTable, LSM, Cassandra, Lucene, HBase）和 就地更新派 （以B树为代表）