针对事务型工作负载（OLTP）优化的存储引擎，与针对分析型工作负载优化的存储引擎之间存在巨大差异。
OLTP存储引擎的两大类，写出不可变数据文件的 日志结构 存储引擎，以及B树这样就地更新数据的存储引擎。
最简单的数据库可以用两个 Bash 函数实现：
#!/bin/bash
db_set () {
echo "$1,$2" >> database
}
db_get () {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}实现了键值存储，麻雀虽小，五脏俱全：
$ db_set 12 '{"name":"London","attractions":["Big Ben","London Eye"]}'
$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}每次调用set，都会向文件末尾追加记录，多次更新一个键时，旧版本的值不会被覆盖，要找到最新值，必须 查看这个键在文件中最后一次出现的位置。
文件末尾追加写入通常非常高效，真正的数据库还要处理更多问题，例如 并发写入、回收磁盘空间以免日志无限增长，以及崩溃恢复时处理只写了一部分的记录。
索引是从主数据衍生出的 额外 结构。许多数据库允许添加和删除索引，这不会影响数据库的内容，只会影响查询性能。维护额外结构会产生开销，特别是在写入时。任何类型的索引通常都会拖慢写入速度，因为每次写入数据时还必须更新索引。
假设仍要把数据保存在仅追加文件中，只是加快读取速度，最简单的索引策略是保留一个内存中的哈希映射，其中每个键都映射到数据文件里的一个字节偏移量，指明该键最新的值位于何处。
每当向文件追加新的键值对时，还要更新哈希映射，使它指向刚刚写入的数据。查找一个值时，先用哈希映射找到日志文件中的偏移量，再寻道至该位置读取即可。如果数据文件的这一部分已经在文件系统缓存中，读取甚至完全不需要磁盘 I/O。
存在问题：
数据库索引很少采用哈希表，常见的做法是把数据保存在 按键排序 的结构中。
排序字符串表（Sorted String Table），这种文件格式同样存储键值对，但保证键值对案键排序，而且每个键在文件中只出现一次。
这样不必在内存中保存所有键，把SSTable中的键值对分成若干个几千字节大小的 块 block， 索引只存储每个块的第一个键。这种只收录部分键的索引称为 稀疏索引（sparse index） ， 索引保存在 SSTable 的一个独立区域中，可以采用不可变 B 树、字典树或其他能快速查找特定键的数据结构。
SSTable 文件格式比仅追加日志更利于读取，却让写入变得困难。不能直接向文件末尾追加，否则文件就不再有序（除非键碰巧按升序写入）。如果每次在文件中间插入一个键都要重写整个 SSTable，写入成本又会高得无法接受。
解决办法是采用 日志结构 方法，将仅追加日志与排序文件结合起来：
段的合并类似于 归并排序 算法，并行读取各个输入文件，比较每个文件当前的第一个键，把排序最靠前的键复制到输出文件，然后不断重复。如果同一个键出现在多个输入文件中，只保留较新的值。这样生成的新段仍按键排序，每个键只保留一个值；
为了避免数据库崩溃时丢失内存表中数据，存储引擎在磁盘上保存一个单独的日志，每次写入都会立即追加到这个日志，在崩溃时按日志写入顺序可以恢复内存表。
删除一个键及其关联的值，必须向数据文件追加一种称为 墓碑（tombstone）的特殊删除记录，日志段合并时， 墓碑会指士合并过程丢弃这个键此前的所有值，墓碑一旦合并进最旧的段，自身也就可以删除。
算法 日志结构合并树（Log-Structured Merge-Tree），简称 LSM 树，凡是以合并、压实有序文件为基本原理的存储引擎，通常都称为LSM存储引擎。
在 LSM 存储中，读取很久以前才更新过的键，或读取根本不存在的键，可能十分缓慢，因为存储引擎必须检查多个段文件。为了加快这类读取，LSM 存储引擎通常会为每个段配备一个 布隆过滤器（Bloom filter） ，用来快速、近似地判断某个键是否出现在某个 SSTable 中。
对 SSTable 中的每个键计算哈希函数，会得到一组数字，再将这些数字解释为位数组中的下标。把这些位置上的位设为 1，其余位保持为 0。例如，键 handbag 的哈希结果是 (2, 9, 4)，于是将第 2、9、4 位设为 1。得到的位图会与稀疏键索引一起存入 SSTable。
判断某个键是否在SSTable中，计算键哈希，然后检查对应下标，只要其中至少一位为0，就能确定 SSTable 中绝对没有这个键。不然就要详细查一查了。
按大小分层压实（size-tiered compaction）：
将较新、较小的 SSTable 逐步合并到较旧、较大的 SSTable 中。保存旧数据的 SSTable 可能变得非常大，合并时需要大量临时磁盘空间。这种策略的优点是能应对很高的写入吞吐量。
分级压实（leveled compaction）：
将键范围拆分到较小的 SSTable 中，并把较旧的数据移入不同的“层级”。这样可以更增量地进行压实，所需磁盘空间也少于按大小分层策略。分级压实的读取效率更高，因为存储引擎只需检查较少的 SSTable，就能判断其中是否含有所需的键。
LSM 树的基本思想，保存一系列在后台合并的SSTable。
B 树按键保存有序的键值对，因而能够高效地查找键值和执行范围查询
B 树把数据库分成大小固定的 块 或 页，并允许就地覆盖页。传统的页大小是 4 KiB，不过 PostgreSQL 目前默认使用 8 KiB，MySQL 默认使用 16 KiB。
叶页或者直接保存每个键的值，或者保存指向值所在页的引用。B 树一页中对子页的引用数称为 分支因子（branching factor） 。实践中的分支因子取决于页引用和范围边界所需的空间，不过通常可达几百。
更新 B 树中已有键的值，就先找到包含该键的叶页，再用含有新值的版本覆盖磁盘上的这一页。
添加新键，则找到范围涵盖该键的页，并把键加入其中。如果页内没有足够的空闲空间容纳新键，就把它拆成两个半满的页，并更新父页，以反映键范围的新划分。这种拆分可能一路向上传播到树根。根页拆分时，则在其上方创建一个新根。
删除键还可能需要合并节点，处理起来更加复杂。
这个算法可以确保树始终 平衡（balanced）：包含 n 个键的 B 树深度总是
O(log n)。大多数数据库只需要三四层深的 B
树，因此不必沿着很多页引用就能找到目标页。（一棵四层深、页大小为 4
KiB、分支因子为 500 的树，最多可以存储 250 TB 数据。）
一次覆写多个页，例如拆分页时，是很危险的操作。如果数据库只写完其中一部分就崩溃，最终会留下损坏的树（例如出现不属于任何父页的 孤儿页，orphan page）。如果硬件不能原子地写入整页，还可能留下只写了一部分的页，这称为 页撕裂（torn page）。
让数据库能够从崩溃中恢复，B 树实现通常会在磁盘上维护一个额外的数据结构：预写日志（write-ahead log，WAL） 。这是一个仅追加文件；对 B 树的每项修改，都必须先写入 WAL，才能应用到树本身的页上。数据库在崩溃后重新启动时，会用这个日志把 B 树恢复到一致状态。文件系统中的对应机制称为 日志机制（journaling） 。
为了提高性能，B 树实现通常不会立刻把每个修改过的页写入磁盘，而是先把
B
树页在内存中缓冲一段时间。此时，预写日志还负责确保崩溃时不丢数据：只要数据已写入
WAL，并通过 fsync()
系统调用刷到磁盘，它就是持久的，因为数据库能够在崩溃后将它恢复出来。
B 树已经存在很久，多年发展出了很多变体：
LSM 树更适合写入密集型应用，B树的读取通常更快。存储引擎有时会融合两种方法的特点，例如维护多棵 B 树，再用 LSM 风格将它们合并。
B 树中查找键，需要在树的每一层读取一页。由于层数通常很少，B 树读取一般很快，性能也比较容易预测。
LSM 存储引擎往往需要检查处于不同压实阶段的多个 SSTable，不过布隆过滤器能减少实际需要执行的磁盘 I/O 次数。
B 树本身有序，因此范围查询简单而快速。LSM 存储也能利用 SSTable 的排序，但必须并行扫描所有段，再把结果合并起来。布隆过滤器对范围查询无能为力，因为不可能计算范围内每个潜在键的哈希；所以在 LSM 存储中，范围查询的成本高于点查询 。
日志结构存储引擎可能存在，高写入吞吐量太高，导致压实速度赶不上新增写入，暂停所有读写，直到内存表写入磁盘。
数量多、规模小而位置分散的写入模式（如 B 树）称为 随机写入（random write）；
数量少、规模较大的写入模式（如 LSM 树）则称为 顺序写入（sequential write）。
无论采用哪种存储引擎，应用发出的一次写请求都会转化为底层磁盘上的多次 I/O。
LSM 树而言，一个值首先写入日志以确保持久性；内存表写入磁盘时又写一次；此后每次所在的键值对参与压实，还要再次写入。
B 树索引也必须把每份数据至少写两次：一次写入预写日志，一次写入树页本身。
把某个工作负载实际写入磁盘的总字节数，除以不带索引、只写仅追加日志时所需的字节数，得到的比值就是 写放大（write amplification） 。
写放大除了影响吞吐量，也关系到 SSD 的磨损：存储引擎的写放大越低，SSD 损耗得就越慢。
B 树可能随着时间推移逐渐 碎片化 。例如，删除大量键之后，数据库文件里可能留下许多 B 树不再使用的页。以后向 B 树添加数据时可以复用这些空闲页，但它们位于文件中间，很难归还给操作系统，所以仍会占用文件系统空间。
数据库需要后台进程搬移并重新整理这些页，例如 PostgreSQL 的清理（vacuum）进程。
碎片化对 LSM 树来说问题较小，因为压实过程本来就会定期重写数据文件，而且 SSTable 中不存在留有空闲空间的页。
关系模型中的 主键索引 。主键唯一标识关系表中的一行、文档数据库中的一个文档，或图数据库中的一个顶点。
在关系数据库中，可以用 CREATE INDEX 命令在同一张表上创建多个 二级索引 ，从而按主键以外的列进行搜索。二级索引中的被索引值不一定唯一。B 树一类就地更新的存储引擎和日志结构存储都可以实现二级索引。
索引中的键是查询要搜索的内容，而值可以采用以下几种形式：
更新值但不改变键时，只要新值不大于旧值，堆文件就能就地覆写记录。
如果新值更大，情况会复杂一些：记录可能必须移到堆内空间足够的新位置。此时，要么更新所有索引，使其指向记录在堆中的新位置；要么在旧位置留下一个转发指针。
有些内存键值存储（如 Memcached）仅用于缓存，机器重启时丢失数据也无妨。但另一些内存数据库以持久性为目标，可以借助特殊硬件（如电池供电的 RAM）、把变更日志写入磁盘、定期把快照写入磁盘，或把内存状态复制到其他机器来实现。
内存数据库重启时，需要从磁盘或通过网络从副本重新加载状态（使用特殊硬件时除外）
VoltDB、SingleStore 和 Oracle TimesTen 等产品是采用关系模型的内存数据库。Redis 和 Couchbase 通过异步写入磁盘提供弱持久性。
除了性能之外，内存数据库还有一个有趣之处：它可以提供很难用磁盘索引实现的数据模型。例如，Redis 为优先队列、集合等各种数据结构提供了类似数据库的接口。由于所有数据都放在内存中，实现起来相对简单。
数据仓库最常采用关系数据模型，SQL很适合分析查询。
数据仓库与关系型OLTP数据库很相似，都有SQL查询接口，但背后内部实现可能非常不一样，两者针对的查询模式完全不同。
Microsoft SQL Server、SAP HANA 和 SingleStore 等数据库在同一产品中同时支持事务处理和数据仓库。
Google Cloud BigQuery、Amazon Redshift 和 Snowflake 等新一代云数据仓库也得到广泛采用。与传统数据仓库不同，云数据仓库会利用对象存储、无服务器计算平台等可伸缩的云基础设施。
许多云数据仓库支持自动摄取日志，并且可以轻松接入 Google Cloud Dataflow、Amazon Web Services Kinesis 等数据处理框架。
Apache Hive、Trino 和 Apache Spark 等开源数据仓库也随着云计算共同演进。分析数据存储迁入对象存储上的数据湖之后，开源数据仓库开始拆分、解耦 55。过去集成在 Apache Hive 这类单一系统中的功能，如今往往由以下独立组件实现：
数据仓库通常采用关系模式：一张巨大的事实表通过外键引用各张维度表。如果事实表有数万亿行、数 PB 数据，如何高效存储和查询就成了严峻挑战。
尽管事实表通常有 100 多列，但典型的数据仓库查询一次只访问其中 4、5
列，分析查询很少需要 SELECT *
# 分析人们在一周中的哪一天更倾向于购买新鲜水果或糖果
SELECT
dim_date.weekday, dim_product.category,
SUM(fact_sales.quantity) AS quantity_sold
FROM fact_sales
JOIN dim_date ON fact_sales.date_key = dim_date.date_key
JOIN dim_product ON fact_sales.product_sk = dim_product.product_sk
WHERE
dim_date.year = 2024 AND
dim_product.category IN ('Fresh fruit', 'Candy')
GROUP BY
dim_date.weekday, dim_product.category;OLTP 数据库大部分 都以 面向行（row-oriented）的方式布置存储：表中同一行的所有值相邻存放。文档数据库也很相似，通常把整个文档存成一段连续的字节序列。
虽然可以为列加索引，但面向行的存储引擎仍要把这些完整的行（每行有 100 多个属性）从磁盘载入内存，逐一解析，再过滤掉不满足条件的行。这个过程可能十分耗时。
面向列（column-oriented，或 列式，columnar）存储 背后的想法很简单：不要把同一行中的所有值放在一起，而要把同一 列 中的所有值放在一起。每列分别存储后，查询只需读取和解析自己用到的列，能省下大量工作。
几乎所有分析数据库都采用列式存储：从 Snowflake 这样的大型云数据仓库，到 DuckDB 这样的单节点嵌入式数据库，再到 Pinot、Druid 等产品分析系统。Parquet、ORC、Lance 和 Nimble 等存储格式，以及 Apache Arrow 、pandas/NumPy 等内存分析格式，也都采用列式布局。InfluxDB IOx、TimescaleDB 等时间序列数据库同样以列式存储为基础。
除了只从磁盘加载查询需要的列，还可以压缩数据，进一步降低对磁盘吞吐量和网络带宽的需求。列式存储通常很适合压缩。
一列中不同值的数量远小于总行数，把一个具有 n 个不同值的列转换成 n 张独立位图：每个不同值对应一张位图，每一行对应其中一位。如果该行取这个值，对应位就是 1，否则为 0。
位图索引非常适合数据仓库中，如
WHERE product_sk IN (31, 68, 69) 这样的查询。
列式存储中，行的存储顺序并不一定重要。最简单的方式是按插入顺序存放，因为插入新行时只需向每一列追加数据。
也可以像此前处理 SSTable 那样，为数据指定某种顺序，并把这种顺序用作索引机制。
分别对每一列独立排序毫无意义，因为那样就再也不知道不同列中的哪些项属于同一行。之所以能够重建一行，是因为一列中的第 k 项与另一列中的第 k 项属于同一行。数据按列存储，排序也必须以整行为单位。
可以按多个列按顺序排，先用某列，把前面列相同的再用另一个列继续排。
数据仓库的读取通常要聚合大量行；列式存储、压缩和排序都能加快这类读查询。数据仓库的写入则往往是批量导入数据，通常通过 ETL 流程完成。
列式存储而言，在有序表的中间插入单独一行非常低效，因为从插入位置开始，所有压缩列都必须重写。但一次批量写入很多行，可以分摊重写这些列的成本，因而效率很高。
批量写入通常采用日志结构方法，先写入一个面向行、有序的内存存储，积累够多写入后，再与磁盘上的列编码文件合并，并成批写入新文件。旧文件保持不可变，新文件一次写成，所以对象存储很适合保存这些文件。
查询必须同时检查磁盘上的列数据和内存中的近期写入，再把两部分结果合并起来。查询执行引擎会向用户隐藏这项区别。在分析师看来，插入、更新或删除的数据会立刻反映在后续查询中。Snowflake、Vertica、Apache Pinot、Apache Druid 等许多系统都是这样做的。
复杂的分析型 SQL 查询会被分解成一个 查询计划（query plan），其中包含多个称为 算子（operator） 的执行阶段；
这些算子可能分布到多台机器上并行执行。查询规划器 可以决定选用哪些算子、以什么顺序执行，以及每个算子在哪里运行，从而完成大量优化。
查询编译（query compilation）:
查询引擎根据 SQL 查询生成执行代码。代码逐行迭代，读取相关列中的值，完成所需的比较或计算；如果条件满足，就把必要的值复制到输出缓冲区。随后，查询引擎把生成的代码编译成机器码（往往借助 LLVM 等现有编译器），再对已经载入内存的列编码数据运行。这种代码生成方式类似 Java 虚拟机（JVM）等运行时采用的即时（JIT）编译。
向量化处理（vectorized processing）:
查询仍然采用解释执行，而非编译执行；但它不再逐行迭代，而是成批处理一列中的许多值，从而提高速度。数据库内置一组固定的预定义算子，向算子传入参数，就会得到一批结果。
按位与可以得到 product_sk=30 且 store_sk=3
的行。
物化视图 是实际写入磁盘的查询结果副本，而 虚拟视图 只是编写查询的快捷方式。从虚拟视图读取时，SQL 引擎会即时把它展开成底层查询，再处理展开后的查询。
底层数据变化时，物化视图也必须随之更新。有些数据库可以自动完成这项工作，Materialize 等系统则专门负责维护物化视图。更新视图会增加写入工作量，但如果工作负载反复执行相同查询，物化视图可以改善读取性能。
物化聚合（materialized aggregate）是一类对数据仓库很有用的物化视图。如前所述，数据仓库查询经常使用 SQL 中的 COUNT、SUM、AVG、MIN 或 MAX 等聚合函数。如果许多查询都使用相同的聚合，每次重新处理原始数据就太浪费了，何不把最常用的计数或总和缓存起来。
多维数据集（data cube，或 OLAP 多维数据集，OLAP cube）会创建一个按不同维度分组的聚合网格，正是为了实现这种缓存。
上面的是两个维度的，更高维三维、四维、五维都可以。如 每个单元格保存特定“日期—产品—门店—促销—客户”组合的销售额，随后可以沿每个维度反复汇总这些值。
B 树和 LSM 树，可以对单个属性执行范围查询。但有时，只按一个属性搜索并不够用。
最常见的多列索引称为 联合索引（concatenated index）。它把一列接在另一列之后，将多个字段组合成一个键；字段的连接顺序由索引定义指定。
多维索引（multidimensional index）则允许同时查询多个列。
SELECT * FROM restaurants WHERE latitude > 51.4946 AND latitude < 51.5079
AND longitude > -0.1162 AND longitude < -0.1004;一种办法是使用空间填充曲线把二维位置转换成单个数字，再建立普通的 B 树索引。
全文检索（full-text search）允许按关键词搜索一组文本文档（网页、产品描述等），关键词可以出现在文本中的任意位置。
全文检索也可以视为一种多维查询：文本中可能出现的每个词（即一个 词项，term）都是一个维度。包含词项 x 的文档在维度 x 上取值为 1，不包含 x 则取值为 0。搜索提到“红苹果”的文档，就是同时寻找 红 维度和 苹果 维度都为 1 的文档。这样一来，维度数可能非常庞大。
许多搜索引擎使用 倒排索引（inverted index）回答这类查询。它是一种键值结构：键是词项，值是所有包含该词项的文档 ID 列表，即 倒排列表（postings list）。如果文档 ID 是连续数字，倒排列表也可以表示成那样的稀疏位图：如果 ID 为 n 的文档包含词项 x，那么词项 x 的位图中第 n 位就是 1 。
Elasticsearch 和 Solr 使用的全文索引引擎 Lucene 就采用这种方法。它把从词项到倒排列表的映射保存在类似 SSTable 的有序文件中，再使用本章前面介绍的日志结构方法，在后台合并这些文件。PostgreSQL 的 GIN 索引也通过倒排列表支持全文检索，以及 JSON 文档内部的索引。
语义搜索不只处理同义词和拼写错误，还试图理解文档表达的概念和用户的意图。例如，帮助中心有一页标题是“取消订阅”，那么用户搜索“如何关闭账户”或“终止合同”时也应当找到它：这些说法用词完全不同，意思却十分接近。
为了理解文档的语义，也就是它表达的含义，语义搜索索引会使用嵌入模型，把文档转换成由浮点数组成的向量，称为 向量嵌入（vector embedding）。这个向量表示多维空间中的一个点，每个浮点数表示文档在某一维坐标轴上的位置。如果输入文档的语义相似，嵌入模型就会生成在多维空间中彼此接近的向量。
一篇介绍农业的维基百科页面，其三维向量嵌入可能是
[0.1, 0.22, 0.11]。介绍蔬菜的页面应该离它很近，向量或许是
[0.13, 0.19, 0.24]。介绍星型模式的页面则可能得到
[0.82, 0.39, -0.74]，距离相对很远。只看数字也能发现，前两个向量比第三个更接近。
实际的嵌入模型使用大得多的向量，往往包含 1,000
多个数字，但原理相同。我们不会试图理解每个数字各自代表什么；它们只是嵌入模型用来指向抽象多维空间中某个位置的方式。搜索引擎通过
余弦相似度、欧几里得距离
等距离函数衡量向量间的距离。余弦相似度计算两个向量夹角的余弦，判断它们有多接近；欧几里得距离则计算空间中两点间的直线距离。
Word2Vec、BERT 和 GPT 等许多早期嵌入模型都处理文本数据，通常以神经网络实现。后来，研究者又为视频、音频和图像创建了嵌入模型。近来，模型架构进一步走向 多模态（multimodal） ：同一个模型可以为文本、图像等多种模态生成向量嵌入。
用户输入查询时，语义搜索引擎会把查询及其相关上下文（例如用户位置）交给嵌入模型，生成查询的向量嵌入。随后，搜索引擎还必须通过向量索引，找出向量嵌入与查询相似的文档。
需要专门的向量索引，例如：
许多流行的向量数据库都实现了 IVF 和 HNSW 索引。Facebook 的 Faiss 库为两者提供了许多变体，PostgreSQL 的 pgvector 也同时支持这两种索引。