CMU数据库导论-1

关系模型

关系型数据库（Relational Database，RDB）是一种基于关系模型（Relational Model）来组织和管理数据的数据库。它由Edgar F. Codd于 1970 年提出，其核心思想是将数据组织成二维表（Table），并利用数学中的关系代数来操作数据。但是论文中的表述是完全数学化的。

IBM发明了第一个查询语言叫做SQUARE，但是这种语言写起来很怪，没有人真正实现它。

然后SEQUEL被发明了，由于版权原因被改名为了SQL。

SQL在86年就被标准化了，但是规范仍然会不停的更新。这些变化是为了适应人们编写应用的方式，以及对查询语言需求的变化。XML在90年代末20年代初很火，所以增加了XML的支持，Json在2010年火，所以增加了JSON。2023年增加了对图查询的支持，因此neo4j，可以通过SQL，在表的基础上进行图的遍历。

如今要构建一个新系统，只少需要支持SQL92，它支持了常见的功能，比如select，from，group by，聚合函数等。平均每10年都有人说SQL要死了，但是它们从未发生。

SQL分为

DML，DDL，DCL。

数据存储

文件

数据库可以分为多层

查询计划-操作执行-访问方法-缓存管理-磁盘管理

这一章讨论磁盘管理

我们数据库会假设，在数据库管理系统中，数据主要存储在非易失性存储上。系统本质上是在协调数据在非易失性存储和内存上移动。磁盘数据需要加载到内存中才能提取答案。

中间这条线以上的任何存储都是按照字节寻址的。

按字节寻址意味着，每一个内存地址对应1Byte的数据。

地址 数据
0x1000 0x11
0x1001 0x22
0x1002 0x33
0x1003 0x44

地址0x1000保存1个字节，地址0x1001保存1个字节，地址0x1002保存1个字节。。。。

这里和操作系统的位数不同

32位CPU	CPU寄存器宽度、指针宽度、地址宽度主要为32位
64位CPU	CPU寄存器宽度、指针宽度、地址宽度主要为64位
32位操作系统	运行在32位架构上，使用32位指针和地址空间
64位操作系统	运行在64位架构上，使用64位指针和地址空间

在non-volatile上存储的数据都是按块存储的。我们必须以块为单位访问整个页面，通常4KB。

现代的存储设备，普遍采用4KB作为物理扇区，以前的硬盘很多是512byte现在通常是4096bytes。如果物理社区大小为4KB

每个数据块需要刚好都落在4KB扇区内。如果一条数据跨越了俩个物理扇区，则需要进行多一次的内存读写。这就是为什么需要4k对齐。

这将决定我们使用什么数据结构和算法。但是现代计算机中这些界限正在变模糊。现在SSD和HDD中出现了fast network storage，不存储在本地，但可以进行快速的访问，而且它是持久的。此外傲腾其实介于内存和磁盘之间。然而2022年傲腾被砍掉了。傲腾是一种特殊的硬件，向dram一样插在DIMM插槽中，但是如果拔掉电源可以保存存储的内容。如果intel没有砍掉它，很多课程中的内容将会消失，因为我们不再需要DRAM和磁盘之间来回移动数据了。

现在替代傲腾的CXL3，是一种字节寻址的内存，它可能并不在你本地的物理机上。三星会售卖这种插在PCIE插槽上的设备，它就像是扩展了DRAM插槽的数量。它就像扩展了DRAM插槽的数量。CXL本身也不能解决断点数据保存。

NVDIMM，运行时和普通内存一样，断电时电池继续供电，然后将数据写入磁盘，但是其也没有得到广泛的使用，在部分细分市场。

随机访问通常比顺序访问来的慢。即便是SSD，真正读写的是page，顺序访问可以充分利用并行性，现代SSD内部其实有很多Flash芯片，多个channel同时工作，顺序读取几乎能跑满PCIE贷款。随机访问很难形成连续流水，假设读取4KB，可能在chip0,7,3。控制器需要查FTL，找到物理地址，发送命令，等待Flash响应，每一次都有固定的延迟。

这意味着我们在设计数据库系统时，劲量选择顺序算法，因为顺序写入比随机写入块。我们假设系统运行在现成的文件系统上，并且我们只是在读取和操作这些文件。

页

在数据库系统和计算机中，实际上有三种页面概念

在最低级别，有一个硬件页面，这是硬件公开的，实际可以执行的原子写入操作的最大大小，通常是4KB

原子写入：要么写入完成，要么写入全部失败，不会出现中间状态。

OS层级页会有page的概念，以为这是x86在80年代的做法。默认是4kb，在更新的版本中可以使用巨页（huge page）是2mb甚至1GB。

在数据库中，基于操作系统页面，我们可以使用不同大小的页面。页面大小因数据库而异。

sqlite、oracle、IMBDB2、rocksdb、wiredtiger（mongodb的默认存储引擎）都是4kb。sqlserver，pgsql是8kb，mysql是16kb。

这些只是默认配置，是可以修改的。在DB2中，甚至可以给每一个表设置不同的page大小。mysql和pgsql则不能这样做。

如果数据库页面很大，比如64kb但是只更新了1kb，我们必须将64kb全部写入数据库。因为我们不能只写入小部分的更新。如果读取操作很多，需要对数据进行大量顺序的扫描，那么我非常需要大的页，因为我要读取页面内的所有数据。我希望以此顺序读取，将一个大页面带入缓冲池，然后快速处理。

我们还需要额外元数据来跟踪在文件系统上的物理位置以及其他可用的空间。如果我们的数据是单个文件，那么我们需要维护的元数据对于页面查找来说就非常简单，比如我们想要访问第二页，我们就可以通过简单的算数得出，如果想要第二页，需要的偏移量是什么。sqlite就是这样做的，所有的表都存储在一个文件中。

如果有多个文件，我们想获取23页，我们不知道哪个文件可能包含该页面，假设它们属于同一个表，我们要先通过页目录来访问多一次的跳转。页面目录类似一个hash表，不同数据系统有不同的实现方式。每个数据对象都有一个页面目录，或者说，页面目录中会有一个条目。这个条路会记录对于索引y，应该去哪里查找文件，跳转到哪个偏移量。这个页面目录就像是数据库的索引，因为记录有哪些文件，以及它们的位置。我们需要确保这个目录本身也是磁盘上的页面，并且在写入数据页面的同时以安全的方式同步磁盘。我们需要跟踪每个页面的可用空间，这样有新数据插入时，我们不需要顺序扫描所有页面来查找空闲槽或者闲置空间位置。

SELECT * FROM pg_freespace('student');

我们可以通过这个语句来查询pgsql维护的可用空间映射。

我们可以使用vacuum命令来整理空间，本质上是锁定原本的数据表，然后将所有数据页复制到新的数据页中。

pgsql使用单独的文件来存储空闲页。

每一个页面，都有一个页面头告诉我们关于该页面的信息。

假设我们现在将所有数据连续存储为一行，我们先假设单个元组的所有属性都能放入单个页面。

一个不太好的初步方案是当元组插入数据库时，我们计算一下，然后跳转到页面中空闲的位置。然后开始写入，直到空间用完。但如果我们删除一条数据呢？如果是固定长度的数据还好，直接插入下一个空闲插槽就可以了。但如果数据长度是可变的，每个元组大小都不同，这很常见。在页里如何处理呢？

更好的方法是使用lotted pages，槽页。这是几乎所有面向行的数据库都会采用的。从高层来啊看，他们都有一个槽数组，会移动数据，工作方式基本相同。

页面的起始处有个槽数组，固定长度全部指向页面内的位置。页面底部，是所有固定长度或可变长度的元组数据（行记录），当我们新添加元组时，会将它们追加到页面末尾，所以它会从末尾向头部扩展。当空间耗尽时，它们会在中间相遇。

所以这个槽数组存储这页面内的偏移量，指示位置1的元组在此偏移处。

如果扇出了3，我们只需要在槽数组中标记为元组3已删除，并在header中说明此位置已经清空即可。我们实际可以不将数据进行删除。一些系统会决定，如果这里有空闲的空间，就进行压缩。我们对页的所有操作其实是在内存中进行的，是快速的。

在关系模型下，表内的数据是没有顺序的。在元组中存储页码和槽号是没有意义的，因为它已经在那个槽的页面里了。

PGsql中存在ctid，是pgsql特有的一个系统列，ctid表示一行数据在表中的物理位置。ctid由俩部分组成，分别是

（block_id，tuple_index），第一个为数据页的编号，第二代表改页中的第几行。

sqlite中存在rowid。为每个行自动生成唯一标识（不过不是物理地址）。

fn_PhysLocFormatter(%%physloc%%) 是 SQL Server 中一个未公开（undocumented）的内部函数，用于把隐藏列 %%physloc%% 转换成人类可读的格式。

它的作用和 PostgreSQL 的 ctid 非常相似：显示一行记录当前的物理存储位置。

它会显示三元组

FileID：数据文件编号
PageID：数据页编号
SlotID：该页中的槽号（Slot）

这个记录id或者叫行id，就是元组的物理地址。数据库知道如何把表示记录的id字节数组转换为文件号，页号和偏移量。

oracle的槽号是从0开始，pgsql的槽号是从1 开始的。

如果需要更新现有元组，我们需要获取它的记录ID。

可能存在更新一条记录时，当前页剩下的空间不足以放下这条记录，那么会先从当前页删除，在其他页插入。有些系统可能会通过整理空闲位置腾出空间，来尝试能否放入修改后的数据。

LSM

上面的访问方式存在一些缺陷

问题：

1. 槽数据和元组数据向俩端增长，总会出现一些没有被使用的数据。
2. 存在无意义的磁盘I/O操作：如果我需要更新一个元组，即使一个页面可以存储1000个元组，我也必须获取整个页面。
3. 如果更新多个元组，比如10个，而它们又不在同一个页面上，可能产生大量不需要的io

这引出了LSM数据结构。其核心思想是我们假设只能向块和页面追加数据。浙会加快写入速度，读取速度会因此便慢。

日志存储结构的核心思想是，不再使用原地更新的槽页，而是数据库系统维护一个日志，类似于一个账本，记录对元组的所有修改。每个日志条目表示一个put操作，例如插入一条记录，或者一个删除操作。这是最低层级，可以在日志结构存储上执行的唯一基本操作。

LSM tree中会有一个叫mem表的内存数据结构，我们用它来对数据表进行原地更新。但这个数据结构不会包含或总结所有可能的键。它只包含工作集，也就是最新的更改。当mem表在某个时候满了时，会转换为一个叫做SSTable的数据结构。这几本上是将内存中的数据结构转换成日志记录。这些SSTable存在荣誉信息，所以会定期对他们进行压缩。

Rocksdb中使用跳表作为memtable的实现。如果程序要写入数据，我们只能执行put和delete操作。

我们需要设置一个key作为唯一id

根据键对这些条目进行排序，这个排序本身可以从叶子节点获得，它会记录下这是日志条目。由于SkipList是有序的，可以直接顺序扫描，然后构造SSTable。

如果有太多的SStable，那么我们需要把他们进行压缩，这本质上就是在进行归并排序。我们将Level0的多个SStable合并为一个更大的Level1的SSTable。

这里需要找到SSTable中不同key的最新条目，因为我们知道它们发生的时间顺序。就这样逐层往下。

现在写入可以很快，插入一条记录不需要查找页面来放置。此外我们为内存表维护者一个单独的预写日志，一旦崩溃，就可以从预写日志中恢复。

但是读取会很慢，如果在内存中没有找到，需要从0级开始，在每个ss表中进行二分查找。

SSTable中真正可以二分的是index，

实际数据长这样

Data Blocks
Index Block
Filter Block
Footer

index本身就是

(key, offset)
(key, offset)
(key, offset)

在最坏的情况下要扫描全部层级。因此它通过摘要表（summary table）来解决这个问题。

摘要表会告诉你Primary index的 哪一部分可能包含目标的key。

此外我们还可以通过布隆过滤器来判断某个key不会在，每个SStable都会有一个布隆过滤器。

Rocksdb，leveldb，hbase，tidb，yugabytedb，clickhouse，cockroachdb，cassandra，neon，wiredtiger都是基于LSM树。

其实部分原因是不同的数据库系统都广泛使用了rocksdb。rocksdb是leveldb的fork，leveldb来自google。Facebook在forkleveldb创建rocksdb时第一件事情就是去掉了nmap，因为谷歌让操作系统管理页面。rocksdb对其进行了正确的重写，并拥有了自己的buffable manager。

LSM tree的缺点是写放大，如果对一条记录进行一次写入，它会被多次重写到存储中。比如从level0层到最后的level8，可能要将其写入数十次甚至数百次。

插入操作非常快，因为不需要任何数据充足，但是后台必须要多次压缩归并这些数据。

索引

索引分为很多种，最常见的B+树索引，一个page仍然按上文方式组织，但是页面中的数据不一定有序，但是槽是有序的，因此我们可以进行二分查找。现在当我想基于该键查找记录时，我会遍历数据结构，达到叶节点，获取页面，然后在页头第一个数组中的键上进行二分查找。

元组

数据库是如何组织元组的呢？

如果我们知道行记录的具体数据结构，和他的起始位置，就可以进行访问。然后执行类似reinterpret cast的操作，将任意字节数组转换为我需要的类型。

现代cpu希望数据按字大小对齐。因此现代处理器通常用64位，有时还需要考虑将数据保存在64字节的缓存行内。

对于现代64位的cpu来说，一次最自然的处理数据宽度通常是64bit=8byte

因此创建的表包含无法与这些边界对其的混合类型，就会出现问题，我们需要采取措施，否则访问速度就会很慢。

假设需要访问跨缓存行的数据。cpu会帮你隐藏问题，并返回你想要打包对其的数据

但本质上需要进行俩次内存或缓存行访问来获取数据。在旧的cpu中，你实际上会收到一个中断，告诉你不能这样做，那是错误的，但现在的x86或者arm都会隐藏这一点。现在在CDATE中的成本会是对其的俩倍，意味着数据库会运行的更慢。

最简单的解决方式是增加一些空的空间。当想访问这些不同的属性时，知道如何跳转到字节数组中正确的偏移地址，来获取所需数据。这是最常用的方法。

另一个方法是我们可以重新排列字节顺序中这些属性的布局，以便更好的打包到字节数组中，我们可能不能总是能节省空间，但是我们避免了跨字边界的访问数据

对于varchar可变长度数据，或者text，blobs这样的大数据。通常会在元组头部存储一个与其数据内联的头部信息老记录数据的大小。时间戳可以用不同的方式排序最常见的方法是存储unix 纪元以来的毫秒数或者微秒数，还需要考虑时区信息。

空值

1. 有三种主流的方式表示null值，在每一行数据的头部维护一个bitmap，只需要1bit表示一列是否为空，空间录用率高，所有null信息集中存储容易管理，pgsql和sqlserver用的是这种方式。
2. 特殊值：使用某个数据类型指定一个特殊值表示为null，不需要额外存储null来进行标记，查询速度快，但是会损失一个合法取值
3. 每个字段旁边都放一个flag，实现简单，但是每个字段都要增加一个标志。但是完全不推荐这种做法，因为浪费空间，影响对齐。

逻辑上null不等于null。如果写

select null =null;

没有返回，但是如果写

select null is null

返回为true

如何处理大数值呢？比如一个列的大小可能超过了一个page能存放的空间。比如我们要存储一个文本字段，这个文本字段超过了一个page的大小。我们要做的是有一个溢出页，其与其余数据一起存储内联属性。现在将包含大小和位置信息，这个位置信息是指向溢出页的指针。

必须通过该指针重新定向一次，来找的哦啊实际的值，如果新的页面也不够存储该数据，那么就需要添加另一个指向移出区域的指针，并标明剩余部分的位置。当然对于这么大的数据，你可以在磁盘上对其进行压缩，读取时进行解压缩，因为文本字段，压缩效果通常会非常好。数据库不管理溢出页面，而是操作系统文件来管理。

列存与行存

概要

有一种负载是只读查询，比如分析操作视图从拥有的现有数据中得出新的信息。

在这些查询中，我们不关心如何让删除插入尽可能的快。只关心查询。

数据库的主要负载分为，

1. OLTP：ON-Line Transaction processing
2. OLAP：On-Line analytical Processing
3. HTAP：Hybrid Transaction+Analytical Processing

相比于其他的负载，OTLP通常更偏重于写入操作。查询不会一次性处理大量的数据。

但是如果我们需要提取一些数据模式，或者信息，进行更加复杂的分析查询，早期大部分数据库都是OLTP的。因为只有数据达到一定规模时，OLAP才有意义。

关系模型并未规定数据在表或元组中的存储方式。当然也不会规定单个元组的数据必须在同一个页面。

比如我们要找一个以特定标志结尾的字符串，我需要扫描所有的记录。

存储模型被分为

1. N-ary Storage Model（NSM）通常被称为行存
2. Decomposition Storage Model（DSM） 分解存储模型通常被称为列存
3. Hybrid Storage Model（PAX）混合模型，间距NSM和DSM的特点

按行存储对于分析查询是灾难，因为它可能会造成全表扫描。

DSM的基本思想是不将一个元组的所有属性连续存储在一个列中，而是将数学的所有元组的值连续存储在同一页中。

比如，所有主机名存储在一起，所有的登录时间存储在一起。

其他所有列都用相似的方式进行处理。列存在1984年就被提出，直到21世纪人们才意识到这是一个好主意。

列存中如何知道A列第二个值，和B列的第二个值属于同一条记录？

第一个选择是固定长度偏移。意思是每一列的数据长度固定。如果每一个age都占用4bytes，因为每个元素长度一样，第i个元素就是滴i个tuple，所以不需要存元组的id。因此不需要额外的空间，查询非常快，但是只能适合固定长度数据结构。

另一种选择是嵌入元组的id，每个值都带一个元组的id。对于可变长度的数据来说，不能直接用偏移量，因此最简单的方式就是额外增加一个元组id。（最好不要用这种方式）

现代数据库几乎都采用value buffer+offset array

Alice
Bob
Christopher
Tom

会保存为

Characters

AliceBobChristopherTom

旁边保存

Offsets

0
5
8
19
22

最后一个offset表示字符串结束。这个唯一的row id插入数据的时候自然产生的。

DSM模型缓解了IO操作，因为我们只需要读取实际上需要的数据。

CPU希望你一条接着一条执行指令，避免分支和跳转。但是如果表有1000个属性，插入一个元组就需要写1000个页面。PAX将在一定程度上解决这个问题。

在某些系统中会使用一个类似日志结构的系统作为写入的缓冲区，所有的插入更新删除操作都在缓冲区中进行。只有达到一定阈值才会刷新到磁盘上，这些变动会通过日志进行记录以便宕机时进行恢复。因此可以在内存中行存，在存储时列存。

有很多不同的方法可以将列存储的概念引入数据库中。

pgsql允许每个表最多有16000列。oracle中允许1000列，其实曾经是100（这是一个硬编码的值）

我们想要一种方法能获得列存的优势，又能保证同一列的属性值在多个元组中是连续存储的。这就是PAX存储模型的作用。

PAX

Partition Attributes Access（PAX）是一个物理存储模型。基本思想是，我们不是在表内存储，而是讲数据分成迷你块或者更大的块。他结余行存和列存之间。

它被称为rogues，指的是更大数据区域，我们在其中以列的形式存储数据。但单个元组的数据仍然会相对接近。大多生成是列存的系统世纪上都会采用这种方式。

PAX解决的问题是，有没有一种方法也之间还是Row Store，但是页内部像Column Store

在PAX中，我们首先将元组水平划分为行组。然后在每个行组内，我们将元组垂直划分为块。

它的工作方式是元数据不存储在文件头中，二色存储在文件的页脚footer里。因为创建行组填充文件时，会记录放入的内容，然后当文件完成时，把收集到的信息都放入页脚。所以要打开文件先要看页脚，它会告诉你上面有什么内容。pgsql等系统中，它总是在header中，因为那些是动态更新。

虽然扫描文件时，还是需要将一整页写入到内存中，然后才能读取，但是只需要读取内存中一部分数据，这对CPU缓存非常友好。

在现代数据库中，大量热点数据都已经驻留在 Buffer Pool 中。真正耗时间的不一定是磁盘，而可能是：CPU Cache Miss

PAX 并不是为了减少 Page 的读取，而是为了让已经读进内存的 Page 更符合 CPU 的访问模式。

现代主流列存数据库很少直接采用 PAX（Partition Attributes Across）作为核心存储架构，大多数采用的是 DSM（Decomposition Storage Model，纯列存）或者其变种。

数据压缩

数据压缩有三个目标

1. 必须产出固定长度的值
2. 在查询执行期间尽可能长时间地推迟解压缩
3. 必须是无损的模式

压缩可以有不同的粒度

1. 块级
2. 元组（记录）级（不常用）
3. 属性级（不常用）
4. 列级

块级压缩在OTLP和行存中会更常见。元组级别的压缩可以在sqlserver中完成。有一个terarch的系统，是rocksdb的衍生版本。

mysql和mysql默认不启用块压缩。但是mysql可以通过创建表是来设置块压缩算法来启动。

几乎每一个列式存储系统，每个采用PAX架构的系统都会进行某种类型的列式压缩。

块级压缩

对于块级压缩，可以使用任何压缩算法。比如LZ4，LZO，Snappy，Zstd。

数据库天然以page为单位读写，既然Page本身就是I/O单位，那么压缩整个Page最合理。

比如16KB的数据，被压缩到6KB读取的时候只需要读取8KB（文件有4K对齐）块级压缩减少的是磁盘上传输的数据量，而不是改变数据库逻辑页的大小。这是能提升I/O的主要原因。

我们还需要考虑实际解压时的具体情况，以及如何与缓存池配合。

但是如果频繁进行读后写，写后读操作，导致反复压缩和解压缩，性能上会很糟糕。但总的来说，大多数即便是行存负载中也偏向于读取。header不会被压缩。此外header中有一些元数据，比如只想执行select count*，那么只需要在header中读取数量即可。无需解压缩。

但是行存算法的压缩率通常不会很高。对于压缩算法来说，最佳的情况是一连串的0 。如果尝试用zip压缩一个mp4电影，效果往往会很差。

我们希望直接在压缩的数据上进行操作，而无需进行解压缩。我们可以直接在压缩的数据上进行查询。

列级压缩

相比行存数据库来说，列存数据库更容易压缩。它们数据类型一致，相邻值类似。

游程编码 RLE是一种最简单的无损数据压缩方式，核心思想是如果数据中有很多相同的元素，RLE可以显著减少存储空间；如果数据变化频繁，反而可能使得数据变得更长。

例如

11111112222333333344444

编码为

(1,7)(2,4)(3,7)(4,5)

如果我们根据进行又成编码的列排序，可以获得巨大的优势。这样我们就可以让所有相同的值出现在一起。

排序有些复杂，因为我们需要确保偏移量都匹配。如果对表进行排序，假设表有俩列。需要先对第一列进行排序，然后计算出新的偏移量，然后确保第二列那些偏移量也要相应的移动。为了获取最佳的压缩效果，一个好的方法可能是首先对这一列进行排序，但这实际上可能不是对另一列进行排序的最佳方法。因此数据库会尝试找出最佳的排序方式。

上图情况下我们没有获得显著的压缩效果，甚至最后的数据比原始数据还要大，因为他们是混合排列的。

但是对于查询 select isDead，count(*) from user group by isDead来说，我们可以快速遍历压缩数据，只需要计算重复的次数，就能快速得到答案。

但是如果排序后，压缩的数据就只有俩个三元组

另外一个方案叫做bit packing有的时候也被称为bit shaving。基本思想是如果列中的所有制都远小于其最大可能值，那么就不需要存储那些未使用的位。

bit packing的一个问题是，可能会出现异常值，因此需要用到一个叫做patching的技术。

此外还有bitmap encoding。为每个不同的值建立bitmap。然后位每一个row id编号，如果为当前值就设置为1，不为当前值就 设置为0。但是这种编码对于可能出现多个结果的列并不友好。实际上有一些压缩的位图对稀疏数据集非常有用，比如roaring bitmaps。

大多数列存数据库，默认都会启用某种压缩，但不是必须依赖某种压缩。比如parquest，clickhouse。

Delta encoding（差分编码）是一种数据压缩与表示方法，其核心思想是：不存储原始值，而是存储相邻数据之间的“变化量（delta）”。比如温度通常变化不会特别多。我们还可以在差分编码的基础上用RLE进行进一步的压缩。还有类似的一类计数被称为参考帧编码，在列中存储在一个全局值，列中的其他值都是对该值的增量。

字典压缩：用一个“字典（dictionary）”来存储重复出现的字符串/片段，然后用更短的“引用（reference）”替代原始数据。

内存与磁盘的移动

在冯诺依曼架构的计算机下，我们不能直接操作磁盘中的数据，必须每次都转移到内存中（除了一些特殊硬件）。

我们尝试优化俩件事情，

• 我们希望将一起使用的数据存储在磁盘上，也许不一定在同一页上，而是连续的页面。这样我们可以尝试进行顺序访问通过一次I/O获取操作，读取更多的数据。
• 我们希望优化时间局部性，尽可能长的将数据保留，以供尽可能多的查询或者操作使用

缓冲池

在buffer poll中，内存数组中用于重复利用的固定大小站位区域通常称之为帧，大小和数据库页相同。当数据库需要读取一个磁盘page，查看page手放在buffer pool中。如果不在找一个空闲的frame，根据替换算法淘汰一个frame，把磁盘page加载进去。内存中数据的排列顺序不必与磁盘上的顺序相匹配。

除了跟踪这些帧外，我们的持久管理器重还会有一个额外的数据结构，叫做页表，本质上是一个从页面ID到你可以在缓冲管理器内存中找到该页面的位置映射。有一个页面ID到帧号的映射。

我们需要跟踪元数据的脏位，来确定该页面是否被系统的某个部分写入。

会有一个引用计数器指示，有多少的其他部分现在持有指向这些页面的指针。

latch是一种用于保护内存中的共享数据机构的轻量级同步机制，和锁很像但是用途不同。Lock 用于保护数据库逻辑数据（事务并发控制），Latch 用于保护数据库内部内存结构（线程并发访问）。

1. 线程 A 正在修改 Buffer Pool 中的一个 page
2. 线程 B 正在读取同一个 page
3. 线程 C 正在修改 B+Tree 索引节点

没有同步可能导致

线程A:
读取page
修改page中的slot数组

线程B:
同时读取slot数组

latch也可以是通过mutex机制或者futex机制实现的。

• 页目录（page directory）：将页面ID映射到数据库文件中的页面位置。每当我们进行更改，比如像表添加更多页面时，我们都必须更新页目录。如果重新启动，我们会重新加载页目录，并且需要确保它与实际文件同步。header中不存放每条记录的起始位置，只存放管理槽的数量。页目录位于页的尾部，是一个槽（Slot）数组。每个槽占 2 字节，存放的是页内某条记录的页内偏移量。
• 页表（page table）：是我们在缓冲区管理器内存中维护的一种临时数据结构。

MMAP

操作系统会有MMAP的功能，将文件内容直接映射到应用程序的内存空间。而且它会采用懒加载的方式，不会将文件的所有内容都加载到内存。它会根据文件大小提供一个起始点和结束点。如果访问到不在内存中的内容，就会发生页错误，然后操作系统会将其读回。操作系统试图对用户保持透明，让你感觉不到，你想要的数据其实不在内存里。它会直接阻止你，停止运行，取消的调度，然后获取你需要的数据，载入内存。一旦数据进入内存，你就能获得访问它的指针。

操作系统隐藏了如何在磁盘和内存之间移动数据的机制，这样做的目的是给你一种拥有的内存比实际多的错觉。

操作系统可以随时刷新脏页。如果我现在崩溃并返回，我们必须弄清操作系统在实际崩溃前写入了什么东西。但我实际上不知道它写了什么，它在底层做了这一切。用户不知道内存中有哪些脏页，因为操作系统为我们管理所有这些。无法在操作系统的页表中查看并说出实际上在内存或不在内存中的内容。操作系统为了维护这些映射会有自己的页表。

问题：

1. 事务安全
2. IO阻塞
3. 错误处理
4. 性能问题

可以使用madvise给哦操作系统一些提示，说明你将如何读取某些页面。比如顺序读取，随机读取。调用mlock，告诉操作系统某些区域不能被换出。然后调用msync，等同于fsync，指示将内存区域刷新到磁盘。视图使用这些所有技巧，让MMAP达到我们在缓冲区管理中想要的效果。但实际上效果会更差，程序也会变得很复杂。

数据库总是比系统更了解如何使用数据。

mongodb一开始使用mmap（MMAPv1），但是现在已经放弃（WiredTiger）。singlestore，weaviate也是一开始使用mmap，后来删除了。一开始用mmap是因为快速且容易，但是性能受限。Elasticsearch，sqlite，他们用MMAP主要是服务于只读的工作负载。LMDB喜欢使用MMAP，甚至给其他数据系统发邮件，告诉它们为什么做错了，应该使用mmap（suck）。

论文：Are you sure you want to use mmap in your database Management system

置换算法

我们需要有一个有限的缓冲置换算法。这将是区分开源系统和高端昂贵的企业系统的关键因素之一。它们投入了数百万美元和数百小时的工程时间来优化这些东西。企业系统会比开源系统有更复杂的功能，但是他们是闭源的。最常用的缓冲池替换策略

最常见缓存置换算法是LRU，简单性能也好。对于每个页面，都记录最后一次被访问的时间，我们可以用不同数据结构维护页面访问的顺序，比如链表，B+树，trie树。

CLock算法：它被认为是LRU算法的近似实现。把所有的页面组成一个环形，看起来就像钟表。每一个页面都有一个reference bit。只有俩个值。0代表最近没有被访问，1代表最近北方问过。如果buffer pool已满需要淘汰一个页面，时钟指针不断前走，如果最近被访问过，就不进行淘汰，如何变为0 。如果位0代表很久没人访问，就进行淘汰。

但是如果查询需要对整个表进行顺序扫描，比如在进行join操作。那么这会严重影响缓冲池效率，并干扰我们用于跟踪页面使用情况的元数据，因为所有页面看起来都像最近被访问过的。它会丢弃那些非常热门我们应该保留的页面。因此有时最近使用的页面反而是你想要最先滔天的。

LRU和CLock算法只存储少量信息，即上次访问的时间。无法告诉你访问的次数，因此无法做出是否将该页面保存在内存中的有效决策。

一个简单的方法是使用LRUK技术（作者是发明了LSM树的人）。这里的写法是保留一些额外的元数据，来跟踪页面之前被访问的最后k个时间戳。当决定驱逐哪个时，会查看历史记录，并选择间隔最长的那个。此外pgsql还有技术追踪访问是否在同一个事务中，比如一个事务中读取了俩次相同的数据，可以在逻辑上只被视为一次。sqlserver可以区分页面访问的上下文，并将其添加到额外的元数据中，以追踪之前的访问记录。

另一个问题是冷启动，如果系统重启，我将丢失所有页面访问时间的元数据。

mysql使用一种称为approximate LRU-K的技术。这里的想法是，它仍然是个单链表，用来白送页面被访问的顺序。在LRU中位列表设置了俩个部分。Young list，old list。

我们不会直接将其添加到LRU的开始位置，二十将首次访问时添加到旧链的head中。淘汰从后开始，也就是page8的位置。

如果再次访问这个页面6，页面将会被放到young list头部。它类似于LRU2或者K=2的LRUK。mysql这样做是因为它比pgsql和sql server的实现更简单。需要的元数据更少，是LRU的一个简单扩展。

脏页

如果要驱逐的页面是脏页，我们必须保证脏页写入磁盘，并且在磁盘上安全后才能重用该帧。

快路径：页不是脏的，直接删除

慢路径：页是藏的，数据库必须协会磁盘确保修改持久化。

为了优化慢路径，我们可以在后台增加写入器，会定期让工作现场查看缓冲池，找到脏页，如何刷新并写入磁盘。该页仍然在内存中，因为我们没有进行置换操作。一旦写入完成，我们清楚脏位。

这类似操作系统底层为我们做的事情，但是操作系统不了解事务，也不了解我们系统中其他部分正在进行的操作。如果没有这个后台程序，那么任何需要驱逐内容时，查询都会被阻塞。因为必须先刷新脏页。在刷脏页时，可以优先刷新即将被驱逐的页，而不是随机刷新页面。

在写入磁盘时，操作系统中的硬件会使用一些技巧，通过创新排序和批量处理I/O请求来最大化硬件带宽。现代m2驱动器和MVME驱动器快的原因是，你可以在它们上面执行大量并行操作，并从中获取非常好的吞吐量。但是操作系统并不知道这些I/O请求之间的关系。它不知道哪个请求更重要，因为它知道看需要读取的文件或数据块。

大多数据库有自己的调度器，因此会建议你关闭Linux提供的其他调度，简单的使用戒指时间或者FIFO调度器。

Linux有一个叫做IOuring的机制，提供缓冲区，允许提交请求并接受通知（首次出现在2019年）。

system call

如果在操作系统上执行fread，它会命中内核允许的文件系统，内核说好的，你想从磁盘读取整个数据块或数据页，它实际上会先检查操作系统的页缓存。所以如果使用操作系统页缓存，每次fread都会产生页面的俩个副本，一份在用户空间给数据库使用，一份在内核中。

因此，大多数数据库系统会使用direct I/O，在调用FOpen的时候传递O_direct标志。这会告知操作系统绕过其缓存页。任何Fread操作会直接通过文件系统到达硬件。现在只有一份从内核到用户态的副本，这样可以避免荣誉副本。操作系统缓存页有自己的驱逐策略，我们不想受其影响。

一个著名的数据库系统以依赖操作系统页缓存而闻名，pgsql会告诉你，当你为pgsql分配内存时，他们会建议你使用系统中可用内存的25%。其他数据库系统会建议，为缓冲池使用内存的80%。pg只建议用25%-30%，剩余的内存用于操作系统的页面缓存。这意味着pg可能会从缓冲池逐出某些内容，但它仍然会存在于操作系统的页缓存中。在以为微软负责pgsql的开发人员尝试关闭操作系统的页面缓存，让pg使用driectIO。

如果一个数据库调用fwrite系统会先写入缓冲，然后缓冲机制在底层运行刷入磁盘。但是如果崩溃了，fwrite可能会导致数据丢失。所以必须调用fsync，让操作系统向硬件发出指令，确保数据被刷新。当调用fsync得到一个错误信号，你就不知道哪些写入成功了，哪些没有成功。在linux中第二次调用fsync肯定会成功，但这可能是操作系统在欺骗你。（linux担心有人插入了usb存储后拔出，这样fsync可能永远不会成功，但是这不是数据库期望的行为）。

2018年爆出了丑闻，很多数据库存在了20年的bug，不只是pgsql，mysql，mongodb和其他数据库，就是fsync导致的问题，你可能丢失数据但是没有发现。

优化手段

Multi Buffer Pool（多缓冲池） 是现代数据库中一种常见的 Buffer Pool 管理技术。它的核心思想是不要吧所有数据也都放到一个统一的buffer pool中管理，二十分成多个buffer pool。这是为了解决高并发下buffer pool的锁竞争问题。在企业级系统中可以在每个buffer pool指定淘汰算法。

那么如何知道数据页放到哪个buffer pool中呢？可以使用hash或者轮询，保证无论哪个现场访问相同的id都会访问同一页面，因为一个页面不能同时存在于多个缓冲池。

另一个优化手段是预取（prefetching），我们可以尝试基于查询计划提前识别出未来需要访问的页面，并进行预取。这对于顺序扫描来说很简单，在扫描page1和page2的时候可以预取page3。但是我们不能进行索引预取，操作系统不知道这些页面代表什么，不知道他们是如何连接的，

另一个技巧是扫描共享，有时候也被称为同步扫描。如果有俩个或多个查询同时运行，并访问相同的页面，没必要让他们呢从头都扫一遍，二十让他们一起共享这次扫描。我们可以重用查询访问的页面，比如一个查询统计平均值，一个查询统计最大值，就可以让他们共享页面。这是pgsql相较于其他查询的优势，oracle也支持，这这种机制，但是只有查询完全一致的情况下才能重用结果（hash字符串）。

缓冲池旁路（buffer pool bypass），有的时候被称为轻量扫描（light scans）。某些数据访问不经过数据库的buffer pool，二十直接在磁盘和用户空间之间进行IO。它目的是为了避免缓冲池污染，提高整体性能。当一个查询读取多个页面，把页面放在只有查询能看到的小缓冲当中，避免污染全局的buffer pool。

Hashtable

有俩中哈希表，静态哈希，方案，这种方案假设数据结构里有固定数量的元素，也就是键值对。还有一种是动态哈希方案允许哈希表可以增长。

在数据库中给定一个key，无论是主键，还是辅助键，我们都希望通过这个键来找到对应的元组。

在静态hash中由于长度是固定的带来俩个严重的问题

• 预估困难：预分配太大浪费内存，太小则冲突剧烈，性能从O(1)退化到O(n)。
• 无法动态增长：数据量超过预期，表就满了（尤其是开放寻址法）。

静态哈希

完美哈希：第一层用常规hash将n个键映射到m个桶里，这层允许冲突。第二级，定制完美哈希，为每个桶里的k个键，专门构造一个无冲突的二级哈希函数，所有键值都存入这个二级哈希表。查询经过俩步，是严格的O（1）时间复杂度。

在计算哈希函数我们要权衡速度和冲突率。在hash表中大部分情况下，返回一个32位或者64位的整数。pgsql实现了自己的哈希函数。最常见的hash函数是face book的xxxhash（对于恶意攻击不抗碰撞）。

rocksdb使用了xxhash。

为了解决hahs冲突诞生了很多算法

线性探测哈希是开放寻址法的一种实现：当插入冲突时，向后查找空暇的桶，直到找到为止。

但是线性探测需要遇到空位才能停止，删除操作还需要打上额外的墓碑标记。这让删除操作变得很麻烦。但是在数据库中，有时候不需要进行删除操作，比如进行hash join，只需要插入和读取。如果它的大小和负载因子都 很合理，是不太需要进行多次扫描的。我们还可以做一些额外的优化，比如存储哈希值，这样比较相等之前可以先比较哈希值来判断是否相同。大部分情况下hash值会不同。

一个不好的方法是在删除时将下方的数据重新哈希，并向上移动。这样做的化必须重新hash很多数据，因此大部分情况使用删除标记。墓碑需要作为负载因子的一部分。

当一个key对应多个value时，我们可以给每个value存一个链表，也可以重复存储多次。

布谷鸟哈希是准备多个哈希函数，占用不同的哈希槽。那么如果多次哈希后，如果所有的槽都被占用，那么就需要从其他位置偷一个槽（把原有的值给踢掉）。如果踢掉成环了，那么就要进行扩容操作。IBM的DB2加速器是使用了该算法。布谷鸟哈希牺牲了插入速度换取读取速度。

Clickhouse中甚至有20种哈希表。

动态哈希

动态哈希的理念是，逐步调整自身大小，无需重新哈希所有内容加载到第二个哈希表。最常见的是链式哈希（chained hash），可扩展哈希和线性哈希是更高级的替代方案。动态哈希的思想是只复制指针，不复制数据。

在桶头中，我们可能仍然想维护一个指向哈希表开头的指针，在其前防止一个过滤的数据结构，用于判断该键是否存在于桶链当中，用于判断这个key是否真的存在（比如布隆过滤器）。一般链式哈希的负载因子是按照所有元素算的，而不是按照被占用的数组算。

可扩展哈希是一种动态哈希技术，能随着数据量增长平滑地扩展空间。

它由俩部分组成，本质是一个大小为2^d的数组，存放指向桶的指针，d称为全局变量，哈希值的前d为决定了使用桶中的哪个项。

桶是真正存储数据的地方，有固定的容量，通常是2-4个记录，每个桶都有一个局部深度d'，表示这个同理记录哈希值的前d'位都相同。显然d'<=d

可以这样理解，目录是一张索引表，通过哈希值的前几位来索引到对应的桶。

假设桶容量为2，全局深度d=1，目录有2^d=2个项。所有数据存入俩个桶，它们的局部深度也是1。

插入两条哈希为 00... 和 01... 的记录到桶A，没问题。插入第三条 0... 记录时，桶A满了。

目录               桶
[0]  -----> [桶 A (d'=1)]  存放哈希值0开头的记录
[1]  -----> [桶 B (d'=1)]  存放哈希值1开头的记录

次数需要分裂桶A：

1. 桶A的局部深度d'增加：从1变为2,。意味着区分更细了，现在要用钱俩位来区分桶A里的记录。
2. 创建新桶C：局部深度也为2，存放前俩位01的记录。
3. 重分配数据：把原桶A的记录，按其哈希值的前两位重新分配到桶A（前两位00）和桶C（前两位01）。
4. 更新目录：因为全局深度d=1小于桶的新局部深度，目录需要扩大一倍。目录从2变成4，全局深度d变为2,。新目录的指针根据前缀指向正确的桶。

目录 (d=2)          桶
[00] -----> [桶 A (d'=2)]  存放00开头的记录
[01] -----> [桶 C (d'=2)]  存放01开头的记录
[10] -----> [桶 B (d'=1)]  存放1开头的记录（10和11都指向它）
[11] -----> [桶 B (d'=1)]  

可以看到，目录的扩展是成倍增长的，但数据只在新分裂的桶之间重新匹配，不影响其他的桶。

为什么（10和11都指向它）呢？因为这里b桶还没有满，不需要进行分裂。

查询：

1. 计算哈希值，取钱d位作为索引
2. 到目录中该索引位置，拿到指向桶的指针。
3. 在桶内顺序搜索。

查询最多只需要俩次磁盘I/O一次读取目录，一次读取桶。效率很高

优点：

• 性能稳定：查询最多2次磁盘访问，不会因数据量增大而明显变差。
• 扩容代价小：只影响单个溢出桶，是平滑的、局部的调整。
• 实现相对简单：思想非常清晰。

缺点：

• 目录空间可能很大：目录大小按 2^d 指数增长，当数据分布极不均匀或数据量巨大时，目录本身会占用大量连续内存。
• 桶容量固定：如果选择的桶容量太小，分裂会很频繁；太大则退化为顺序搜索。

pgsql用的是线性哈希，源码里称之为dynahash

1. 使用一组哈希函数：它不依赖单个哈希函数，而是使用一个函数族 h0, h1, h2, ...。这些函数的计算范围是逐步翻倍的。例如，h0 把键映射到 N 个桶，h1 则映射到 2N 个桶，以此类推。这样，系统就可以在多个“版本”的映射规则下工作。

2. 维护一个“分裂指针”：这是最关键的设计。系统维护一个指针，指向下一个要被“分裂”（即扩容）的桶。

   • 何时分裂：当某个桶的负载（比如存储的记录数）超过预设阈值时，就会触发一次分裂操作。
   • 分裂哪个桶：注意，被分裂的桶并非刚刚变满的那个，而是当前“分裂指针”所指向的那个桶。这种“轮转”式的处理保证了扩容是线性、均匀地遍历所有桶。
   • 如何分裂：系统会申请一个新桶，然后将“分裂指针”指向的旧桶中的一部分记录（通过新的哈希函数 h1 计算）移动到新桶中。之后，指针就移到下一个桶。

这听起来很奇怪，因为在拆分的不是溢出的桶，而是在拆分当前指向的任何存储桶，但是我们最终会处理到那个桶。

删除操作理论上可以重新让拆分指针会到之前的位置。

在我们创建索引的时候可以指定索引的类型，比如hash索引。

B+ tree

大部分情况下，创建索引是指b+树索引。有些系统完全基于哈希表构建本质上得到的就是哈希表（Redis ）。

B+树属于一个名为B树的数据结构族，有个特定的数据结构叫做b tree。这俩者之间是有区别的。大部分数据库系统实现的都是b+ tree。但是大多数人没按照70年代的定义来实现B+ tree，而是使用了各种优化技术。

b+树是平衡的，每个叶子节点到根节点的距离都相同。意味着向下遍历的时间复杂度为log n。此外除了根节点之外，每个节点都是半满的。

B+树存在兄弟指针，最初的B+树定义是在底部有兄弟指针（叶子节点之间）。但是b-link树的论文也添加了内部节点的兄弟指针。在进行数据扫描的时候不需要总是回到根节点。

对于空值可以放在开头或者结尾。因为空值之间无法比较。B+树中没有子节点指向父节点的指针，我们只能在数据结构中单项遍历树，也就是从上到下。这样就不会出现死锁了，不会有从底部向上访问的情况。兄弟指针也会带来一些问题，有些系统之在单方向上使用兄弟指针链表，因此不会出现死锁。

另一种方法实际上是更好的方法，将键和连续地存储，然后让值数组也连续地单独存储。这样类似之前谈到的链式存储。

这样存储可以快速获取需要的key对应的数据。

对于主键索引，叶节点直接存储数据元组本身，对于二级索引，叶子接地啊你通常会包含指向元组的主键。

在B+树中真正关心的数据只会在叶子节点中找到，内部节点只是我们达到底部的路标而已。这意味着我们可能会删除一个键，它会从叶子节点移出，但可能仍然存在于内部节点中。内部节点不清理也没有问题，因为它只是用来帮助我们到达底部。如果我在B+树中进行遍历，我会跳过所有内部节点，除非是扫描，否则永远不需要往上走了。这意味着，只需要验证叶子节点按顺序遍历，就可以找到我正在查找的所有数据，这会最大程度提高顺序访问效率。我们可以通过一些方式，比如预分配一些叶子节点，确保它们在物理上也是连续的。

对于插入操作，我们向查找一样访问B+树，如果空间足够，直接存放，但是如果空间不足，我们就要进行页分裂。创建一个新节点，把要拆分的节点一半的key放进去，也就是新的节点，另一半留在原处。然后需要更新父节点，这可能会递归更新树的其余部分，根据布局来重新分配。

在删除的情况下B+树要从其他兄弟节点借走元素，确保自己是半满的，这是为了保证树的平衡。这可能导致会需要再次更新父节点。在借不到兄弟节点的元素的情况下，可能需要将父节点和当前节点进行合并，来维持半满。所以在进行删除操作时，可能导致树结构坍塌，并且最多让树的高度减少1。通常只会问相邻的兄弟节点借元素。b+树删除之后可以不清理内部节点的元素，但是b树不允许这样。向下遍历的时候可以维护指针的堆栈，这样就可以直接访问父节点。

为了处理重复的key，最常见的一种是实际上隐式的将记录ID作为索引键的一部分进行存储。pgsql是这样做的。mysql直接将主键追加到二级索引的后面。来保证索引的唯一。在搜索时这种搜索方式本质上也是前缀查询。

对于变长结构我们可以通过使用slot进行二分。

前缀查询也是可以进行二分的。

另一种方式是移除叶节点，识别出有重复的地方，像类似链式哈希那样，不断在末尾附加更多的页，但这很糟糕，如果分布不均匀，最终可能会得到一个很长的链。

默认情况下，PGsql中的主键索引存储的是TID，TID = (BlockNumber, OffsetNumber)。因此PostgreSQL 的主键索引叶子节点存储的是 TID，而不是整行数据。

但是PGsql提供了CLUSTER，CLUSTER user USING user_pkey;按

它会：

1. 按 user_pkey 的顺序
2. 重写整个 Heap Table

如果数据是无需的，索引会按照某种顺序加载。然后堆文件或者其他任何页面，它们都是完全无序的。浙江导致扫描索引然后抓取页面将会变成随机访问。

一个非常简单的优化是扫描索引时，实际上不获取任何元组，而是对我们想要的索引在的物理位置进行排序。然后扫描并获取元组时，每个页面只检索一次。PGsql称之为bitmap heap scan，在mysql中类似MRR（但mrr是根据主键进行排序）bitmap heap scan是默认开启的，但是mysql是不开启的。

优化手段

B+树甚至有一本专门的书来讲这个数据结构（红黑树可没有）

B+树的很多参数取决于硬件设备，比如设备速度越慢，页面越大越好，因为当需要读取时，希望最大化顺序访问。（如果需要修改页面大小，需要重新编译PG数据库，但是mysql不需要）。如果速度很慢使用1mb甚至更大的页面，如果速度很快，512字节的页面大小就比较合适。

事实上，如果B+树正在经历反复的删除和插入，有可能导致反复进行拆分和合并。为了避免这种情况，理论上可以放宽这个约束，允许节点小于半满，以便操作不会反复的折返。但是会导致B+树是非平衡的。

另一个技巧是叶子节点的大小可以和内部节点不同。比如内部节点比叶子节点稍大一些。（但是mysql和pg中都是固定大小）

在页内查询时，我们可以用SIMD优化，单指令多数据。在SIMD中可以依赖硬件来允许处理一个数值向量，如何使用专门的向量化质量对向量内所有数值执行相同操作。我们可以在一条指令内，将包含四个数值向量进行比较，用0和1表示是否匹配。使用AVX512等指令集可以处理更多的数值

如果没有匹配就继续查找，直到找到目标。

另一个方法是进行二分查找。

最快的方法是插值搜索，单它仅存在于学术文献中，实际应用很少。可以看作是二分查找的改进版。二分查找不在意数据的分布。（但是由于数据库中剪枝分布通常不均匀，很难满足于近似均匀分布，所以没有被使用。）

压缩：

按照字典序排序的数据，相邻的数据前缀很可能非常隐近似的，因此我们可以采用前缀压缩技术。这样表中不同属性的分散值，就变成了单个属性的连续值。我们可以存储相同的前缀一份，和不同的后缀多份。在进行查找时按需查看前缀，如果没有匹配性则仅查看剩余后缀。

我们还可以对重复的数据进行删除（deduplication），只保留该键一次，然后跟上一个可能的较小的数字，来表示该键会出现多少次。Pgsql在三年前的B+树上增加了此功能，显著减少了空间占用。当然实际上也可以对值做该操作，而不仅仅是key。比如邮政编码就有大量的重复。

suffix truncation：我们可以对内部节点进行后缀截断。假设有俩个很长的字符串，但是我们只需要第一个字母来判断是否需要向左或者向右，那么我们就可以只存放第一个字母。只存储那个，而不是全部内容。只能在B+树中进行该操作，因为b+树的内部节点不存储实际的值。理论上可以在内部节点存储任何东西，只要能正确的向左或向右移动即可。随着时间的更新前缀可能会产生改变，到时候进行更新即可。

pointer swizzling：指针交换，这实际上会打破数据库系统中关于页面ID和记录ID的良好抽象层，并实际存储原始内存指针。每次访问的时候，原本我们需要根据页面在磁盘上的位置来获取在内存中的位置，但是这种技术会将原始内存指针存储在页面中，这样遍历时就无需访问缓存池管理器了。比如我们可以对根节点进行这个操作，这样访问根节点不需要访问buffer pool了。但是我们要小心这一点，因为我们将内存地址直接存储在页面本身中，页面是在内存里的。我们需要保持它被锁定，在刷新磁盘时我们需要跟踪这个操作。我们不能直接写入内存地址，因为当再次读取时这个内存地址可能就无效了。虽然这里需要更多的工作，但是我们避免了额外的查找工作，不需要每次都访问buffer pool了。

批量插入：在某些情况下，你可能已经预先知道了所有的key，因此在加载表的时候，通常建议先删除全部索引（除非有唯一性约束要确保数据完整性）。然后批量加载数据，最后创建索引。增量更新索引的总时间比创建索引慢很多，而且创建索引可以并行处理。如果预先知道所有的key，最好先排序，然后用兄弟指针填充叶节点，然后侯建索引的方式就不是自顶向下，而是自底向上。这样数据结构就能达到最紧凑的状态。

增量维护B+树很昂贵，因为需要进行拆分合并。最坏的开启是一个插入操作要重新平衡整棵树。有一种方式可以吸收对b+树的更新，然后在必要时批量更新。这被称作写优化B+树，有的时候被称作分形树。分形树树种每个节点都有一个mod日志，插入时，如果空间足够就写入mod日志，无需完全遍历到叶节点。删除操作和插入都写在这个节点旁边的mod中，进行查询时会先从mod中招，如果没找到，就按B+树的正常流程做左右遍历，当modlog的空间不足时，我们会响应的应用或向下推送内容。目前SplinterDB正在使用类似的数据结构。对于写密集的工作负载，这种结构会比b+树快很多。

其他常见结构

其他

典型的过滤器

1. counting bloom filter
2. cuckoo filter（Redis明确提供Cuckoo过滤器）
3. succinct range filter（SuRF）

跳表是另一个数据结构，在链表中每次插入节点，通过抛硬币来决定它能出现在哪几层索引中，具体规则是：

1. 每个节点必定出现在最底层（第0层）。
2. 从第0层开始，每个节点独立地以 1/2 的概率（抛硬币正面）决定是否也出现在上一层。
3. 如果出现在上一层，就继续抛硬币，决定是否再往上出现一层……以此类推，直到抛到反面为止。

优点：相对于b+树用更少的内存，插入和扇出不需要重平衡

缺点：对于磁盘和缓存不友好，因为它们不优化局部性。对于反向查找不友好。

另一种结构比b+树法更加早叫做trie（1970）。

通过前缀匹配查找字符串。时间复杂度进位O(L)，L为字符串长度。

它由极值的前缀匹配效率。

但是内存占用较大， 构建成本较高。

Radix tree是tire树的压缩版本。如果存储

在经典 Trie 里，如果存储 abc、abd、abcd，前三个字符 a->b->c 都是单支路径，每个字符都要单独创建一个节点，每个节点又都带着 26 个空指针，极其浪费。

Radix Tree 的做法是：“单行道”全部合并。
它会把那些“只有一个子节点”的连续路径，直接压缩成一个字符串片段（Edge label）。

• 经典 Trie：a -> b -> c -> d （4个节点，每个节点带一堆空指针）
• Radix Tree：abc -> d （只有2个节点，把共享的前缀 abc 直接挂在一条边上）

插入过程的核心规则：当新单词和旧单词共享部分前缀时，Radix Tree 会把原来合并的字符串“劈开（Split）”。
比如先插入 abcd（树里压缩成 abcd 一个节点），再插入 abce。发现两者共享 abc，但到 d 和 e 处分叉了。此时树会分裂成：abc (公共父节点) -> d (左子) 和 e (右子)。

优点：内存站原地，查询依然搞笑，插入删除更稳定

缺点：实现较为复杂，更新开销更大，插入一个新词导致节点分裂，需要重新分割父节点上的字符串重新分配内存。不适合极短的字符串。

Linux内核用 Radix Tree（具体是基数树变种）管理文件系统的页缓存，用来快速通过文件偏移量找到对应的物理内存页。

IP路由表的前缀匹配也是使用Radix Tree来查询的。此外，duckdb，hyper，umbra，solidDB内部也使用了该结构。

倒排索引

倒排索引一般包含俩个部分

dictionary和posting lists

这里的字典就是所有被提取的术语词汇。字典会维护所有术语，已经这些术语的出现概率。每个术语都有一个指向发布列表的指针。发布列表中是包含了该术语的id。倒排索引很多情况下会存储词频，类似：

“苹果” → [ (文档1, 词频=3, 位置=[5,12,20]), 
            (文档3, 词频=1, 位置=[8]) ]

rust写的tanivi，java写的lucene，c++写的zapien。有许多系统使用这些倒排索引库，围绕它们构建更强大的数据库系统。比如ES，Solr，Splunk，Vespa。OpenSearch是亚马逊的ES分支。

FST（finite state transducer）有限状态转换器是一种核心的数据结构。用来构建倒排索引的词向索引。它可以看做前缀树（tire）的升级版本。不仅共享词项的共同前缀，还能共享共同后缀。极大压缩了存储空间。目标是，让你能用极快的速度，查到一个词是否存在以及它对应中的值。

FST会将keu拆分成单个数字。但数据结构的叶节点不是指向目标位置的指针，而是边上的权重。它会告诉我们如何计算到达目标位置的偏移量。它们会为插入数据库的每条记录创建增量字典。这样每个字典树都只针对一部分文档。这样每个字典都只针对一部分文档。然后在后台，它们会进行类似日志结构合并树的压缩操作，将段合并成更大的字典，减少冗余和重复值。

Pgsql有一个叫做gin的东西。也就是通过倒排索引。本质上他们使用的数据结构是一个树的森林。也就是说使用B+树来存储字典。其中的值，或者说术语（term）会是整个键。初始B+树的值会根据posting list中对应的记录数量而变化。

如果一条记录出现了过多次，在叶子节点还会组成一个b+树。比如一个词在100w个文章中出现了。显然这些数据需要额外的b+树存储。

向量索引

向量索引的查找是基于嵌入向量的。但是通常，我希望在where子句中有额外的谓词，这些谓词无法被嵌入向量捕获。

最常见的方式是inverted file。获取到要的向量。利用k均值算法之类的聚类算法，将它们分层更小的组。当我想查找时，为我的查找向量或者embedding找到最近邻。然后在周围查找，找到靠近的条目。这是一个简单的分治算法

另一种方法是使用navigable small worleds，可导航小世界。

其核心思想是我们构建一个图结构，其中每个节点会指定发出多少条边，这些边将指向其余最近的邻居。数据结构中会有一个入口点，告诉我们搜索从哪里开始。然后我们只需要沿着图中的路径前进，选择一条更接近目标向量的路径。假设我们查询包含一个嵌入向量，它将我们定位到这个空间的某个位置。为了找到最临近，我们从入口点开始。然后沿着路径前进。找到所有更接近的节点。当我们到达一个无法更靠近的节点时，搜索就会停止。如果需要，我们可以在此结构下添加更多的层级（HNSW）。

优化算法

排序

问题是，如何在主内存无法容纳全部数据的情况下，仍然获得全局排序数据？如果所有数据能放入内存，大多数据库系统会使用快速排序或它的变体，有时野会使用插入排序（pgsql使用的是快速排序）。那么如何判断使用快速排序，归并排序还是其他基于磁盘的排序呢？这一半是通过估算查询中不同操作符的数量。

Top-N heap sort

：适用于你明确知道查询需求的时候，不需要对所有数据排序。外部归并排序则是我们用于磁盘排序的核心算法。

顶端堆排序是一种特殊情况，适用于带有limit的order by子句的查询，数据集就知道它不需要全局排序所有数据。它只需要根据order by子句获取最大或者最小的子集。

select * from enrolled order by sid asc fetch first 4 row with ties;

这条 SQL 语句的含义是：从 enrolled 表中查询所有列，按 sid 升序排列，并返回排名前 4 的所有记录（包含并列情况）。

大部分数据库都是这样做的，比如pgsql。

使用快速排序这类操作，在磁盘上非常慢，归并排序对于磁盘更加友好。

外部归并排序是一种分治的方法，我们将把需要排序的数据分割成为运行的较小单元。核心思想 是现在内存中把这些数据排好序。然后把它们写到磁盘上，为接下来要排序的数据腾出空间。然后通过多轮迭代来完成这个锅，直到得到一个全局排序的完整数据集。

物化：将某个中介结果或者逻辑表达式，从定义的状态，实实在在地计算出来并保存在内存里。

未物化：不持有具体数据，只持有位置引用，比如第三行第五航数据。

物化状态：把实际数据构造出来。拿着那几行，去order_id之类的列把对应的数据提取出来

提前物化的好处是，早早组好整行数据，用大量空间床底宽行，换的随用随去的遍历。

延迟物化：劲量值传递小体积的行号，节省空间和带宽，把物化的计算开销推迟到最后。

假设有10亿个元组，使用过滤器删除99%的数据之后再进行排序，之后我需要返回并获取剩余的数据。在这种情况下，延迟物化会带来优势。

一般来说行存数据库采用提前物化，列存数据库采用延迟物化。

外部归并排序是可以多路的。三路归并排序是带入三个有序页面并将它们合并。最简单的就是双路的。

理论上使用排序算法，内存越大运行越快，但较大的内存也可能导致其他操作的执行变慢。因此通常对于排序可用内存有一个可调节的参数。

如果我们尝试对很大的表进行排序，通常需要双倍的磁盘空间。但磁盘一般是便宜的，只是运行速度回非常慢。

下图中，1个page有2条数据。

这样每次都只需要加载俩个page到内存中。在归并排序的语境下，run是指待排序序列中一段已经有序的连续子序列。

排序的轮数为1+[log2N]，但是当以10亿为单位的数据大小时，以2为底就不是那么好了。为了让它更快，我们需要吧这个2改成更大的数值。这样我们就可以一次将更多的页面加载到内存中，从而拥有更大的排序运行空间。

但是如果和之前展示的一样只用单个线程按顺序处理每次运行，速度就不会那么快。因此有一些技巧可以优化它。

对于通用m路的排序算法，会有B个缓存池。n/b向上取整，这是因为末尾可能会有无法完全填满最后一次运行的页面。在后续的迭代中，我们只需要加载B-1个页面到内存中，因为始终需要一个页面作为输出。

我们可以把流程从 获取数据->计算->写入数据

变成在后台获取数据，计算完毕之后，执行写入磁盘的同时，先获取下一轮需要计算的数据。当然磁盘速度很快的情况下，这种优化作用有限。

比较键值可能比较耗时。比较2个32长度的数据是快速的，因为这只是cpu中的一条指令。但数据并不总是固定长度值。因此需要优化比较操作，在大数据中这会相当频繁。

排序优化核心思想是，与其使用通用的排序算法，传递函数指针，并调用函数进行比较。不如根据数据类型内联或者硬编码比较运算符。这样就不需要进行跳转调用。如果我知道将要比较俩个浮点数，我们可以直接在排序算法里加入浮点指令。在PG中它们使用一个perl脚本，获取排序算法的实现，然后复制它，生成多个版本，分别用于证书，浮点以及其他类型。因此编译到系统后就有了比较函数的不同版本或者变体。这类似c++的模板，但是pgsql是用c语言写的，所以他们才需要复制这些代码。

对于非常长的varchars或者字符串，可以适用于类似B+树的技巧。不必比较整个字符串来查找匹配项，而是可以传递数据。去掉键的前缀，基于此前缀进行排序，可以使内联操作非常快。然后如果前缀相同，可以回退并调用完整的比较运算符或者比较函数。

当然，如果你有保存索引，比如b+树，它已经存在于order by子句中需要排序的键上，那么再次排序就没有意义，因为它已经排序好了。

如pgsql，如果order by子句使用了A列和B列，我必须在A和B列上都建立索引才能使用。

哈希

当我们不需要进行排序，那么在进行分组时，使用哈希可能更有利，因为我们可以快速识别数据的位置。比如去重和聚合。哈希能够避免查找目标和顺序扫描所有数据的麻烦。

如果我们通过哈希进行聚合，方法是纤维查询创建一个临时的哈希表，然后将key放入其中。根据计算的内容这个值会是一个运行总计，或者用于计算总和，或者计算最小最大值等等。

对于如下查询

select distinct cid from enrolled where grade in('B','C');

从课表中找出，获得过B或者C成绩的学生，并去重。

我们先进行过滤得到去重的结果。然后现在在外部哈希聚合第一遍中，扫描这里拥有的任何数据。如果数据存不下就溢出到磁盘中。在第一轮中我们可以先将数据分区。这样相同的数据就不能跨分区存在。

然后现在在第二阶段，我们将引入这些分区，我将再次哈希它们，并将其写入内存中的哈希函数或者哈希表。这里的主要想法是，对于我正在查看的缓冲区集，哈希表足够小可以放入内存。一旦完成了对这组缓冲区所需的任何计算，我们就可以通过第一个哈希表写出结果后，将其放入一个新的哈希表中。

简单来说就是第一遍筛选，第二遍去重。在第二次去重的时候，我们可以分区进行，完成后，可以从哈希表中获取数据，生成发送给客户端最终结果的一部分。

这样不必进行顺序IO来遍历所有数据，维护一个可能很大的哈希表来查找匹配。这里将问题分解成了更小的子问题和数据块。

对于聚合，键不仅存在于哈希表中，还指向我们维护的总计，以便计算我们需要的聚合，因此聚合函数要求，探测哈希表找到key时，需要更新正在维护的运行值。如果key不存在，就放入到哈希表中。

比如运行avg的group by时，我们只需将行数和记录数记录，然后相除，就可以得到平均值。

在需要写入磁盘时，哈希处理的比排序更好，我们可以进行分治，即使它访问通常是随机io。

连接查询

连接算法

解决查询的常见方案是分治，具体来说就是把不适合放入内存的数据分解成适合放入内存的小块。当讨论哈希join时，也会使用同样的策略。

总的来说结论是，哈希join总是更好，更快的选择。我们重点关注的算法是inner echo join。也就是内部等值连接。

inner join和left join是最受欢迎的。反连接和半连接是特殊情况。在下文暂时只讨论二元（binary）连接，也就是只有俩张表进行连接。

如果需要连接更多的表，可以将前一次的连接结果作为输入，再运行二元连接算法与其他的表进行连接。

多路连接在文献中早已出现，因为其思路非常直观，就是同时连接多个表。但现实中，很少有人实现这些算法，因为它们的性能不够稳定。sql server在1998年添加了这个算法，但是在2001年移出了这个算法，因为这个算法的性能不太稳定。因此，你所知道的大部分系统都要执行二元连接。

还有一类更先进的算法。这些算法用于执行图遍历，例如社交网络表示图结构的网络。这些情况很少见，只有少数系统使用这类算法，比如德国的umbra和cedarDB。

具体的连接算法都由成本模型和优化器来决定。总的来说，我们可以总结出一个经验法则，我们希望把左边的表，也就是外表，设置为较小的表。

查询计划通常是一个有向无环图，图的顶端是返回的输出结果。

如果要将小表作为外部表，如果要连接三个表，我们怎么知道应该先连接哪俩个表，最后再连接第三个表呢？

我们使用late materialization（延迟物化）与early materialization（早期物化），结果是一样的，方式可能不一样。比如哈希join相比于排序来说，速度更快，但是输出us随机的。计算结果最终会被传递到最上面的投影操作符（projection）。这个操作符会丢弃不需要的数据。

连接操作就像把俩个东西混在一起，然后沿着查询计划向上传递，查询计划中更上层的运算符，就不需要回去获取更多数据了。数据从一个运算符传递到另一个运算符。在延迟物化中，核心思想是，在从底层数据源检索数据的那一刻，你只需要获取当前运算符所需要的最少量的数据。

比如对于

select R.id, S.cdate from R join S in R.id=S.id where S.value > 100

那么我们就不需要引入其他属性，比如名称，值，日期等等。只需要引入ID。然后我再存储一个记录ID，这个ID对应着这个元组在数据源中的位置。然后计算结果会被传递到它上面的运算符，在投影运算符丢弃所有不需要的数据。在这个例子中，在底层就获得了元组的所有内容，然后进行连接操作。在连接时，我们可以值传递id，而不传递全部数据。

判断连接好坏的标准就是计算连接所需的IO数量。

给定一个将表 R 与表 S 进行连接（JOIN）的查询，假设数据库管理系统（DBMS）已知这两个表具有以下信息：

• 表 R：共有 M 个数据页（pages），包含 m 条记录（tuples）。
• 表 S：共有 N 个数据页（pages），包含 n 条记录（tuples）。

实际上我们很难确定哪个是大表小表。因为可能在where过滤之后1亿条记录的该表只剩下1条记录。

不管用哪个算法，元组太多内存不够，都得溢出到磁盘。嵌套循环连接是最容易实现的。因为它的cpu开销很小，本质上就是一堆for循环而已。

对于哈希连接，需要对数据进行哈希运算，然后找到对应的存储位置。根据使用的算法，看能需要扫描哈希表。这在计算上可能会更加昂贵。但我们这里假设，磁盘I/O开销远大于任何计算操作。特别是我们的哈希表将会进行高度的优化。暂时不考虑网络开销，所有数据库都在单机环境中（分布式查询可以在多台机器上进行连接操作）。

• nested loop join
• sort-merge join
• hash join

如果你的系统想要支持事务，或OLAP负载，通常会实现索引嵌套循环连接。如果是OLAP工作负载，那么这些连接方式都会用到。高端系统（比如pgsql）会支持所有这些连接方式。mysql在2019年的8.0.18版本中首次引入哈希连接。

循环连接查询（NLJ）

这是最简单朴素的连接方式。

还是对于查询语句

select R.id, S.cdate from R join S in R.id=S.id where S.value > 100

朴素嵌套循环连接，就是俩个for循环。真正做的就是遍历表R中的所有元组，然后对于表R中的每个元素，遍历表S中的所有元素。

大多数系统中，查询计划中的表示为，join运算符左侧的表，被认为是外部的表。右侧被认为是内部表。有些系统比如snowflake会反转这个。但是千万不要这样做。对于R表中的每个元组，我们需要扫描一次S表，很显然是低效的。这个操作成本是M+N*N。其中+M是因为我们需要扫描外部表的所有页面一次。

下图展示的是该操作需要的时间

如果让小表驱动大表，执行性能会得到一定的改善。但是仍然很长（在不考虑系统磁盘缓存的情况下）。

但是这个表其实非常小，假设每个页面大小为4KB，那么S表只有6MB，这么小的数据量完全可以放在CPU的L3缓存中。

但是数据库会以块或者也的形式来存储页面，所以我们可以利用这一点，采用所谓的嵌套循环连接反复噶。

Block Nested Loop（BNL）算法

这里的想法是现在我们有更多的for循环包括外部循环。

外层循环获取R中的每个块，内层循环获取S中的一个块。然后在内存中对这俩个块进行for循环，检查它们俩是否匹配。

在数据库中，块和页面通常是一回事。硬件层面称之为块。

cost：M+(M*N)

现在算法有所改进，因为开始时仍然有M（外部表的扫描成本），但是扫描内部表的成本是M次。因为对于外部表中的每个页面，都要扫描内部表的所有页面。

这里我们假设了给外部表一个frame，内部表一个frame，显然我们还要非常多的内存可以使用。

因此对于所有这些算法，我们都希望较小的表作为外部表，这样可以尽可能多的保留在内存中。计算方式是基于实际拥有的表页数，而不是期望拥有的元组数。

数据集会在磁盘管理器或者页目录中，维护大量关于给定表的元数据，记录着我们拥有的所有页面。当然其中一些页面可能是空的，但这没有影响。

如果我们有B个可用Buffer，使用B-2个buffer给外部表的每一个块，使用一个buffer给内部表，一个buffer作为输出，因为我想尽可能多的将外部表存放到内存中。

现在的模型会变成

Cost：M+([M/(B-2)]*N)

的向上取整。因此对于外部表的每一批页面，都需要读取内部表的所有页面。

因此连接可以在150毫秒内完成

如果内存足够，比如mysql会把整个S表放入到内存中。

Index nested loop join

但是如果我们在表上已经存在索引。那么我们可以将其用于内部表。只在索引上查找匹配项。sql Server会动态构建索引，即便这个索引不存在。比如对于内部表进行一次顺序扫描，构建索引，探测它来连接，然后在查询结束后将其丢弃。

如果有索引成本将会变为

Cost：M+(m*C)

这里C是一个常数，用来代表探查索引的成本。

这个索引如果是B+树， 那么成本是log n，如果是哈希表，成本是O（1）

在查询的数据有索引过滤式，就会使用NLJ算法。没有索引就会采用BNL算法。

Sort-Merge join

排序合并连接的核心思想是，如果我先按照连接key对俩个表的数据进行排序。那么我可以遍历并扫描排序后的结果。而且我知道在某些情况下，永远不必回溯。

因为在向下扫描的过程中，如果内层表下方不存在于外层表当前匹配的key，我就知道不会错过任何匹配项。这样就可以简化扫描过程，避免盲目搜索连接所需的匹配项。

基本思想是，首先对俩个表进行排序，然后使用游标以同步的方式遍历外层和内层表。当游标确认不会再有匹配时，就会向下移动，因为键值是按顺序递增或递减的。对于内层表，如果外层表向下移动或者出现重复值，我们可能需要回溯，以防止错过匹配项。

比如对于排序好的数据，我们首先看俩边光标指向的数据是否相同。如果相同就知道有一个匹配上了，如果不系统，我们就根据实际的值向下移动。

我们会在内部表中维护一些关于这个最后值的元数据。以说明我查看的最近一批数据或某个值范围内那个值是什么。万一外表再次出现这个值，就需要进行回溯。还有一些额外的元数据需要说明跳回的偏移量是多少。

last value是用来遇到现在不匹配，之前匹配的值时，用来向上回溯的。合并算法的复杂度不是乘算的关系

成本

但是排序合并连接算法最坏的情况是，每一列都只有一个值，比如ID都是1。但是在时间中，这种算法也有时非常有用，特别是当查询有一个group by子句，而这个子句正好和join子句相同的时候。这样的情况下，对齐进行排序时也可以进行连接。然后连接的输出也被排序了（不必附加order by子句）。

这里的大部分成本都在排序中，，如果可以跳过排序，直接进行后面的步骤，那就相当于在使用索引嵌套循环连接了。

hash join

如果我基于一个表构建哈希表，然后在连接子句中查找另一个表里对应的key。如果值相同，就能得到匹配数据。我们会在外部表上构建哈希表。然后用内部表来探测它（在索引嵌套连接中，探测的是内部表的索引）。

一个简单的哈希连接算法包含俩个阶段。在构建阶段，扫描外部表，构建哈希表（通常是线性探测哈希，因为最快）。第二阶段，扫描哈希表来寻找匹配项。

此外，比如在构建链式哈希的时候，我们可以在每个链的前面放一个布隆过滤器。来加块查询速度。当key非常长时，我们就不需要逐key进行比较了。

但是上面的假设是哈希表能够被完全放到内存中。在内存中无法存放的情况下，我们将采用之前提到的类似技术，在进行聚合时，将表分解为多个桶，并将根据需要将桶溢出到磁盘。然后在第二阶段，我们每次将一个桶加载到内存中，确保其大小适用于内存。在第一阶段中已经完成了哈希和分区操作，因此需要连接的数据必然位于同一级别的存储桶中。这是一种经典金丝狐，称之为partitioned hash join（分区哈希连接），嘤的时候也成为grace hash join。在80年代内存不足的时候，几乎所有系统都实现了这种在内存不足时进行哈希连接的方法。

如果考虑到数据库系统需要支持的不同操作和功能，你会发现不需要通用CPU，它只需要一套规模适中的关系代数运算符。可以针对那些最耗费资源的部分进行专门的优化，从而获得显著的提升。现在也有许多数据库厂商是这样做的。但是这类硬件没成功的原因是，当你完成硬件设计，制造，交付给客户的时候，intel已经退出了最新款的CPU，很具摩尔定律，之前所有的优势都荡然无存。

因此专用硬件加速数据库成为了数据库领域的圣杯。人们今天仍然大量使用FPGA。

当进行哈希梳理的时候，大量的key集中在一个桶中，以至于该桶无法容纳与内存，即便是重新分区之后，该桶仍然无法放入内存。我们只能再次执行相同的操作，在进行一次划分，将无法放入内存的桶取出，使用不同的种子再次进行哈希处理。创建更多更小的桶，并且在所有数据再次溢出到磁盘后进行连接操作。

但是当某个key存在大量的数值，无论是否再次对其进行哈希处理，这些数值，仍然会集中在一个桶级别中。如果意识到这种情况发生，可以退回搭配嵌套循环连接，仅针对小部分键执行连接操作。

这是哈希连接的成本。

在分区阶段，必须读取外表和内表各一次，总共是2M+N，第二阶段可以将页面都读取回来。

这是hash join的成本。

一个优化方式叫做hybrid hash join

这个想法已经出现很久了，但是还没有人实际实现它，因为它很难被正确实现。因为必须先知道一些关于数据的信息，但你可能无法提前得知这些信息。

如果你能识别出某个key非常热门，那么与其在第一阶段将所有数据桶溢出到磁盘，不如保留一个小部分我知道是热点的数据，将其保存在内存中。让其他内容溢出到磁盘。

如果我能提前知道外部表的精确大小，我们就可以使用静态大小的哈希表，这样就能达到几乎完美的性能，但通常做不到。

因此在大多数数据系统中，你会指定，当运行查询是，允许查询为哈希表分配多少内存，估计错了就得锁定整个结构，将其大小翻倍，再重新加载。

总的来说对于大数据集，首选的永远是哈希。这里INLJ的C是可变的，可以是B+树，也可以是tire树，hash表等。