散列索引
保留一个内存中的散列映射，其中每个键都映射到数据文件中的一个字节偏移量，指明了可以找到对应值的位置，如 图 3-1
所示。当你将新的键值对追加写入文件中时，还要更新散列映射，以反映刚刚写入的数据的偏移量（这同时适用于插入新键与更新现有键）。当你想查找一个值时，使用散列映射来查找数据文件中的偏移量，寻找（seek）
该位置并读取该值即可。
SSTables
键值对的序列按键排序 要求每个键只在每个合并的段文件中出现一次
因为key有顺序 所以有一个系数内存的索引就可以实现查找操作
b树
不追加，按照固定大小分 block/page(4k)
列式存储
不要将所有来自一行的值存储在一起，而是将来自每一列的所有值存储在一起。如果每个列式存储在一个单独的文件中，查询只需要读取和解析查询中使用的那些列，这可以节省大量的工作
b树优化
由于 B 树已经存在了很久，所以并不奇怪这么多年下来有很多优化的设计被开发出来，仅举几例：
- 一些数据库（如 LMDB）使用写时复制方案【21】，而不是覆盖页面并维护 WAL 以支持崩溃恢复。修改的页面被写入到不同的位置，并且还在树中创建了父页面的新版本，以指向新的位置。这种方法对于并发控制也很有用，我们将在 “快照隔离和可重复读” 中看到。
- 我们可以通过不存储整个键，而是缩短其大小，来节省页面空间。特别是在树内部的页面上，键只需要提供足够的信息来充当键范围之间的边界。在页面中包含更多的键允许树具有更高的分支因子，因此也就允许更少的层级 [^iii]。
- 通常，页面可以放置在硬盘上的任何位置；没有什么要求相邻键范围的页面也放在硬盘上相邻的区域。如果某个查询需要按照排序顺序扫描大部分的键范围，那么这种按页面存储的布局可能会效率低下，因为每次页面读取可能都需要进行硬盘查找。因此，许多 B 树的实现在布局树时会尽量使叶子页面按顺序出现在硬盘上。但是，随着树的增长，要维持这个顺序是很困难的。相比之下，由于 LSM 树在合并过程中一次又一次地重写存储的大部分，所以它们更容易使顺序键在硬盘上彼此靠近。
- 额外的指针已被添加到树中。例如，每个叶子页面可以引用其左边和右边的兄弟页面，使得不用跳回父页面就能按顺序对键进行扫描。
- B 树的变体如分形树（fractal tree）【22】借用一些日志结构的思想来减少硬盘查找（而且它们与分形无关）。
[^iii]: 这个变种有时被称为 B+ 树，但因为这个优化已被广泛使用，所以经常无法区分于其它的 B 树变种。
数据立方体
数据立方的两个维度，通过求和聚合
想象一下，现在每个事实都只有两个维度表的外键 —— 在 图 3-12 中分别是日期和产品。你现在可以绘制一个二维表格，一个轴线上是日期，另一个轴线上是产品。每个单元格包含具有该日期 - 产品组合的所有事实的属性（例如
net_price）的聚集（例如 SUM）。然后，你可以沿着每行或每列应用相同的汇总，并获得减少了一个维度的汇总（按产品的销售额，无论日期，或者按日期的销售额，无论产品）。一般来说，事实往往有两个以上的维度。在图 3-9 中有五个维度：日期、产品、商店、促销和客户。要想象一个五维超立方体是什么样子是很困难的，但是原理是一样的：每个单元格都包含特定日期 - 产品 - 商店 - 促销 - 客户组合的销售额。这些值可以在每个维度上求和汇总。
物化数据立方体的优点是可以让某些查询变得非常快，因为它们已经被有效地预先计算了。例如，如果你想知道每个商店的总销售额，则只需查看合适维度的总计，而无需扫描数百万行的原始数据。
数据立方体的缺点是不具有查询原始数据的灵活性。例如，没有办法计算有多少比例的销售来自成本超过 100 美元的项目，因为价格不是其中的一个维度。因此，大多数数据仓库试图保留尽可能多的原始数据，并将聚合数据（如数据立方体）仅用作某些查询的性能提升手段。
总结
- OLTP 系统通常面向最终用户，这意味着系统可能会收到大量的请求。为了处理负载，应用程序在每个查询中通常只访问少量的记录。应用程序使用某种键来请求记录，存储引擎使用索引来查找所请求的键的数据。硬盘查找时间往往是这里的瓶颈。
- 数据仓库和类似的分析系统会低调一些，因为它们主要由业务分析人员使用，而不是最终用户。它们的查询量要比 OLTP 系统少得多，但通常每个查询开销高昂，需要在短时间内扫描数百万条记录。硬盘带宽（而不是查找时间）往往是瓶颈，列式存储是针对这种工作负载的日益流行的解决方案。
在 OLTP 这一边，我们能看到两派主流的存储引擎：
- 日志结构学派：只允许追加到文件和删除过时的文件，但不会更新已经写入的文件。Bitcask、SSTables、LSM 树、LevelDB、Cassandra、HBase、Lucene 等都属于这个类别。
- 就地更新学派：将硬盘视为一组可以覆写的固定大小的页面。 B 树是这种理念的典范，用在所有主要的关系数据库和许多非关系型数据库中。
日志结构的存储引擎是相对较新的技术。他们的主要想法是，通过系统性地将随机访问写入转换为硬盘上的顺序写入，由于硬盘驱动器和固态硬盘的性能特点，可以实现更高的写入吞吐量。
.png?table=collection&id=15236490-582e-8193-9b2a-000b631ec71c&t=15236490-582e-8193-9b2a-000b631ec71c&width=800&cache=v2)
