数据模型和数据库
一、数据库
数据库是一个有组织的相互关联的数据集合，它对现实世界的某些方面进行建模。人们经常将"数据库"与"数据库管理系统"(例如，MySQL、Oracle、MongoDB)混淆。数据库管理系统（DBMS)是管理数据库的软件。
二、扁平化的文件形式
数据库被存储为DBMS管理的逗号分隔的值（CSV）文件。每个实体将被存储在自己的文件中。应用程序每次要读取或更新记录时，都必须解析文件。每个实体都有自己的属性集，所以在每个文件中，不同的记录用新的行来分隔，而记录中每个相应的属性都用逗号来分隔。
扁平化文件的问题：
1.不能保证数据的完整性
2.实施及扩展性较差：新建时需重写物理层
3.耐用性较差
三、数据库管理系统
DBMS是一种软件，允许应用程序在数据库中存储和分析信息。一个通用的DBMS被设计为允许定义、创建、查询、更新和管理数据库。
早期的DBMS：数据库应用很难建立和维护，因为逻辑层和物理层之间存在着紧密的耦合。逻辑层描述了数据库有哪些实体和属性，而物理层是这些实体和属性的存储方式。早期，物理层是在应用程序代码中定义的，所以如果我们想改变应用程序正在使用的物理层，我们将必须改变所有的代码来匹配新的物理层。
四、数据模型：概念模型+逻辑模型+物理模型
客观对象的抽象过程---两步抽象：现实世界中的客观对象抽象为概念模型(将现实世界抽象为信息世界)；概念模型转换为某一数据库管理系统支持的数据模型(将信息世界转换为机器世界)。
Ⅰ 概念模型: 实体-联系 （Entity-Relationship，ER图）
按用户的观点来对数据和信息建模，用于数据库设计。
Ⅱ 逻辑模型和物理模型
*逻辑模型主要包括网状模型、层次模型、关系模型、面向对象数据模型、对象关系数据模型、半结构化数据模型等。按计算机系统的观点对数据建模，用于DBMS实现。
*物理模型是对数据最底层的抽象，描述数据在系统内部的表示方式和存取方法，在磁盘或磁带上的存储方式和存取方法。
Ⅲ 常用的数据模型
①层次模型（Hierarchical Model）：用树形结构来表示各类实体以及实体间的联系
②网状模型（Network Model）
③关系模型（Relational Model)）
④面向对象数据模型（Object Oriented Data Model）
⑤对象关系数据模型（Object Relational Data Model）
⑥半结构化数据模型（Semistruture Data Model）
关系模型：避免改变物理层时需重写DBMS的尴尬情况
*关系（Relation）：一个关系对应通常说的一张表
*元组（Tuple）：表中的一行即为一个元组；笛卡尔积中每一个元素
*属性（Attribute）：表中的一列即为一个属性，给每一个属性起一个名称即属性名
*候选码（Candidate key）：若关系中的某一属性组的值能唯一地标识一个元组，则称该属性组为候选码
*主码（Key）：若一个关系有多个候选码，则选定其中一个为主码（Primary key）
*主属性:候选码的诸属性称为主属性（Prime attribute）不包含在任何侯选码中的属性称为非主属性（Non-Prime attribute）或非码属性（Non-key attribute）
*域（Domain）：是一组具有相同数据类型的值的集合。属性的取值范围来自某个域。
*分量：元组中的一个属性值；n笛卡尔积元素（d1，d2，…，dn）中的每一个值di
*关系模式：对关系的描述
关系名（属性1，属性2，…，属性n）
学生（学号，姓名，年龄，性别，系名，年级）
数据模型是描述数据库中数据的概念的集合。关系模型是数据模型的一个例子。模式是对一个特定的数据集合的描述﹐使用一个给定的数据模型。关系型数据模型定义了三个概念：
*结构：关系的定义和它们的内容，这是关系所具有的属性和这些属性所能持有的值。
*完整性：确保数据库的内容满足约束条件，一个约束的例子是：年份属性的任何值都必须是数字。①实体完整性②参照完整性③用户定义的完整性
*操纵：如何访问和修改数据库的内容。
五、结构化查询语言（Structured Query Language，SQL）
1、DML(data manipulation language)，数据库操纵语言：SELECT、UPDATE、INSERT、DELETE、CALL、EXPLAIN PLAN、LOCK TABLE
一种从数据库中存储和检索信息的语言。这方面有两类语言：
*程序性的。查询指定了DBMS应该用来寻找所需结果的（高级）策略。
*非程序性(声明性)。查询只指定想要什么数据，而不是如何找到它。
2、DDL（data definition language），数据库定义语言：CREATE、ALTER、DROP
在创建表的时候用到的一些sql，DDL主要是用在定义或改变表的结构，数据类型，表之间的链接和约束等初始化工作上
3、DCL（Data Control Language），数据库控制语言：GRANT、DENY、REVOKE
用来设置或更改数据库用户或角色权限的语句
六、关系代数
关系代数是一组基本操作，用于检索和处理关系中的图元。每个运算符都接受一个或多个关系作为输入，并输出一个新的关系。为了编写查询，我们可以将这些运算符"连锁"起来，以创建更复杂的操作。
（1）选择：Select接收一个关系，并从该关系中输出一个满足选择谓词的图元的子集。谓词的作用就像一个过滤器，我们可以使用连接词和非连接词来组合多个谓词。
语法︰opredicate(R)
（2）投影：投影接收一个关系并输出一个只包含指定属性的图元的关系，你可以在输入的关系中重新安排属性的顺序，也可以对值进行操作。
语法：πA1,A2...An(R)
（3）笛卡尔积：接收两个关系，并输出一个包含输入关系中所有可能组合的图元的关系（不能重复）。
语法：(RxS)
（4）并（Union）：Union接收两个关系并输出一个关系，该关系包含至少出现在一个输入关系中的所有图元。注意∶这两个输入关系必须有完全相同的属性。
语法：(RUS)
（5）交：交接收两个关系并输出一个包含所有出现在两个输入关系中的图元的关系。注意︰这两个输入关系必须有完全相同的属性。
语法：(R∩S)
（6）差：Difference接收两个关系并输出一个关系，这个关系包含所有出现在第一个关系中但没有出现在第二个关系中的图元。注意︰两个输入关系必须有完全相同的属性。
语法。(R-S)
（7）连接：Join接收两个关系并输出一个关系，该关系包含两个图元的所有组合。其中对于两个关系共享的每个属性，两个图元的该属性的值是相同的。
语法：(Rt><JS)
七、数据库系统的结构
1、从数据库应用开发人员角度看，数据库系统通常采用三级模式结构，是数据库系统内部的系统结构
①模式（Schema）/逻辑模式：数据库系统模式结构的中间层，是数据的全局逻辑结构
*数据库中全体数据的逻辑结构和特征的描述
*所有用户的公共数据视图
*与数据的物理存储细节和硬件环境无关
*与具体的应用程序、开发工具及高级程序设计语言无关
②外模式（External Schema）/子模式/用户模式：是数据的局部逻辑结构
*数据库用户（包括应用程序员和最终用户）使用的局部数据的逻辑结构和特征的描述
*数据库用户的数据视图，是与某一应用有关的数据的逻辑表示
③内模式（Internal Schema）/ 存储模式：一个数据库只有一个内模式
*数据物理结构和存储方式的描述
*数据在数据库内部的表示方式
l记录的存储方式（例如，顺序存储，按照B树结构存储，按hash方法存储等）
l索引的组织方式
l数据是否压缩存储
l数据是否加密
l数据存储记录结构的规定
2、从数据库最终用户角度看，数据库系统的结构分为:
①单用户结构
②主从式结构
③分布式结构
④客户-服务器
⑤浏览器-应用服务器／数据库服务器多层结构等
02 中级SQL
一、关系型语言SQL
二、SQL历史
关系型数据库的声明式查询语言。它最初是在20世纪70年代作为IBM系统R项目的一部分而开发的。IBM最初称它为"SEQUEL”(结构化英语查询语言)。该名称在20世纪80年代改为"SQL”(结构化查询语言)。该语言是由不同类别的命令组成的：
1. 数据操作语言(DML)。SELECT，INSERT，UPDATE，和DELETE语句。
2．数据定义语言(DDL)。表、索引、视图和其他对象的模式定义。
3．数据控制语言(DCL)。安全，访问控制。
SQL不是一种死的语言。它每隔几年就会有新的功能被更新。SQL92是一个DBMS必须支持的最低限度，以声称他们支持SQL。每个供应商都在一定程度上遵循该标准，但也有许多专有的扩展。
三、连接join
从一个或多个表组合列并生成一个新表。用于表示涉及跨多个表的数据的查询。
四、聚合
聚合函数接收一袋元组作为其输入，然后产生一个单一的标量值作为其输出，聚合函数几乎只能在SELECT输出列表中使用。
*AVG(COL)。COL中数值的平均值
*MIN(COL)。COL中的最小值
*MAX(COL)。COL中的最大值
*COUNT(COL)。关系中的图元数
五、字符串操作
SQL标准规定字符串只区分大小写和单引号。有些函数可以用于查询的任何部分。
1.模式匹配：
LIKE关键字用于谓词中的字符串匹配。
"%"匹配任何子字符串(包括空子字符串)。
"_"与任何一个字符匹配。
连接："||"将两个或多个字符串连接到一个字符串中。
2.字符串函数
substring(S,B,E) UPPER(S)
六、日期和时间
七、输出重定向
DBMS将结果存储到另一个表中，而不是将结果返回给客户端(例如终端)。然后可以在后续查询中访问此数据。
存入新表：select ... into newtable from ......;
存入旧表(相同列数和类型)：INSERT INTO 旧表 (SELECT ... FROM ...)。
八、输出控制
order by ASC/DESC
limit number：限制结果元组的数量
limit number1 offset number2 : 限制数量为number1，偏移量为number2
除非我们有限制地使用ORDERBY子句，否则DBMS可能在每次调用查询时在结果中产生不同的元组，因为关系模型不强制排序。
九、嵌套查询
调用其他查询中的查询，在单个查询中执行更复杂的逻辑。嵌套查询通常很难优化。外部查询的范围包含在内部查询中(即内部查询可以从外部查询访问属性)，而不是反过来。内部查询几乎可以出现在查询的任何部分。
嵌套查询结果表达式：
ALL：必须满足子查询中所有行的表达式。
Any：必须满足子查询中至少一行的表达式.
IN：等效于=any()。
EXISTS: 至少返回一行。
十、窗口功能
在一组相关的元组上执行“滑动”计算，就像聚合一样，但是元组不是分组在一个输出元组中。
函数：窗口函数可以是我们前面讨论过的任何聚合函数。还有一些特殊的窗口功能：
1.ROW_Number：当前行的编号。
2.RANK：当前行的顺序位置。
分组：over子句指定如何在计算窗口功能时将元组分组。使用PARTITION BY 指定组。
十一、常见的表格表达式
在编写更复杂的查询时，通用表表达式(CTE)是窗口或嵌套查询的一种替代方法。它们提供了一种在大型查询中为用户编写辅助语句的方法。CTEs可以被认为是一个临时表，它的范围是一个单一的查询。
WITH子句将内部查询的输出与一个具有该名称的临时结果绑定
SQL homework
sqlite3是linux上的小巧的数据库，一个文件就是一个数据库。
1.查看所有表：
2.查看单个表声明：
3.执行sql文件：
03 数据库存储一
一、存储
Volatile Devices（易失设备）：
*易失意味着如果你切断了电源，数据将会丢失。
*易失存储支持以字节为单位的快速的随机访问。这意味着程序可以跳到任何字节地址并获得这里的数据。
*出于我们的目的，我们总是将这个存储称为“内存”（memory）。
Non-Volatile Devices（非易失设备）：
*非易失意味着存储设备不需要提供持久的电力去保持数据的存储。
*它以块/页为单位。这意味着为了读取一个特定偏移的数据，程序需要先读取4KB的页到内存中，并从内存中读取这个数据。
*非易失存储在原理上（设计上）对顺序访问速度快（它可以同时读取多个连续的数据块）。
*我们将它称为“硬盘”（disk）。但我们不会区分固态硬盘（SSD）和机械硬盘（HDD）。
二、面向磁盘的DBMS概述
数据库都在磁盘上，数据库文件中的数据被组织成页，第一页是目录页。为了对数据进行操作，DBMS需要将数据引入内存。它通过拥有一个缓冲池来管理数据在磁盘和内存之间的来回移动。DBMS也有一个执行引擎，将执行查询。执行引擎将要求缓冲池提供一个特定的页面，而缓冲池将负责把该页面带入内存，并给执行引擎一个指向内存中该页面的指针。缓冲池管理器将确保该页的存在，同时执行引擎对该部分内存进行操作。
三、数据库 vs 操作系统
数据库的一个高层的设计目标是支持数据库存储的数据大小超过可用内存的大小。读取/写入数据到硬盘中是一个非常低效的操作，所以我们必须管理好这些操作。我们不希望从硬盘读取数据的时候出现大的空挡从而拖慢其他操作的速度。同时我们希望数据库在等待数据读取的时候可以同时运行其他查询。
这个高层的设计目标像虚拟内存，在虚拟内存中有一个较大的地址空间和一个供操作系统从磁盘引入页面的位置。
实现虚拟内存的一种方式是使用mmap去映射一个文件的内容到一个内存地址空间，操作系统负责从硬盘和内存之间移动页。但不幸的是，如果mmap遇到页错误，进程将被阻塞。如果你要写页，你永远不要考虑在数据库中使用mmap。
数据库总是希望自己可以控制操作，并且可以做的更好，因为他知道有哪些数据将要被访问，有哪些查询将要被运行。
操作系统支持以下操作：
madvise：告诉操作系统什么时候你计划读取特定的页。
mlock：告诉操作系统不要将内存交换到硬盘上。
msync：告诉操作系统同步内存的内容到硬盘上。
出于正确性和性能原因，我们不建议在数据库中使用mmap。即使系统也提供一些看起来类似的功能，但数据库自己实现这些功能可以控制的更好，并且能获得更好的性能。
四、文件存储
在最基本的形式中，数据库将数据存成文件。一些数据库可能使用文件层次结构（多文件），另一些可能使用单文件（例如SQLite）。
但操作系统不知道这些文件内容的意义，只有数据库知道如何解密这些文件，因为这些文件是数据库由特定的方式编码的。
数据库的存储管理器负责管理数据文件。它将文件表示为页的集合。它还跟踪哪些数据被读写到页中，以及页中有多少空闲的空间。
五、数据库的页
数据库将数据组织在一个或多个文件中，这些文件在存储在页中，他们具有固定大小的块。页中可以包括不同类别的数据（元组，索引）。当然大多数系统不会在一个页中混合存储这些类别。一些系统可能会要求页是自我包含的（self-contained），这意味着读取页的信息在页本身中。
每个页都有一个唯一的标识符。如果数据是单文件的，那页id可以是简单的用偏移表示。大多数数据库都有一个中间层来映射页id到文件路径和偏移的对应关系。高层的系统会直接询问特定的页id，存储管理器将会转换页id到文件路径和偏移并去寻找这个页。
大多数数据库使用固定长度的页去避免支持可变长度的页所需的工程开销。例如，使用可变长度的页，删除一个页可能会造成文件的一个碎片，数据库并不能很轻易的使用新的页填充这个碎片（比如大小过小，造成新的碎片等等）。
这里有3个数据库中page的概念：
①硬件的页（通常为4KB）
②操作系统的页（4KB）
③数据库的页（1-16KB）
存储设备保证对硬件的页大小的数据原子写操作。如果硬件的页是4KB，操作系统尝试去写4KB到硬盘中，这4KB要不完全写入成功，要不完全写入失败（不存在写入部分成功的情况）。这意味着如果数据库的页大于硬件的页，数据库将会使用额外的操作去保证安全的写入数据。因为当系统崩溃时，程序可能写入了部分数据。
六、数据库的堆
数据库有2种方式可以找到页在硬盘上的位置，堆文件组织是一种方式。
一个堆文件是一个页面的无序集合，其中元组以随机的顺序存储。
数据库可以使用链表或页字典的方式通过页id来定位页在硬盘上的位置。
**Linked List（链表）：**头部的页有一个指向空闲页的指针和一个数据页的指针。然而，如果数据库正在寻找一个特定的页，他需要顺序扫描数据页直到该页被找到。
**Page Directory（页字典）：**数据库维护一个特殊的页，它存储着每个数据页的位置以及每个页上的空闲空间。
七、页布局
每个页包含一个头部记录着每个页的元信息：
*页大小
*校验和
*数据库版本
*事务可见性
*是否自我包含（比如Oracle需要这个）
布局数据的一种方法是跟踪有多少元组存储在一个页中，并在每次添加新元组时追加到尾部。然而，当元组被删除或者元组有变长属性的情况下问题就出现了。
有2种主要的方法在page中布局数据：（1）槽页（2）日志结构
**Slotted Pages（槽页）：**页映射槽到偏移。
*头记录使用槽的数量、最后使用的槽的起始位置和一个跟踪了每个槽的起始位置的槽数组。
*当插入一个元组的时候，槽数组将从前往后插入，元组数据将从后往前插入。当槽数组和元组数据相遇的时候说明当前页已满。
**Log-Structured（日志结构）：**数据库存储日志代替存储数据
存储数据库如何被修改的记录（插入，更新，删除）。
为了读取记录，数据库需要从前往后扫描日志文件去重建元组。
写入速度快，读取速度非常慢。
在仅追加的情况下效果非常好，因为数据库不会回滚和更新数据。
为了避免读取过慢，数据库可以创建索引并跳到日志中特定的位置。它可以周期性的压缩日志。（如果有一个元组被更新了，我们可以只存储插入一个元组。）但压缩的问题会导致数据库的写放大。（他会一遍一遍的重写相同的数据。）
八、元组布局
一个元组的本质是一连串的字节。数据库将这些字节解释成属性类型和相应的值。
**Tuple Header（元组头部）：**包含元组的元数据
一些关于数据库并发控制的信息（例如哪个事务创建/修改这个元组）。
标记NULL的位图（bitmap）。
注意，数据库不需要在这里存储数据库模式的元数据。
**Tuple Data（元组数据）：**每个属性真实的数据
属性通常按照你创建表的时候的顺序存储。
大多数数据库不允许一个元组超过页的大小。
Unique Identifier（唯一标识）：
在数据库中的每个页都被赋予一个唯一的标识。
最常见的表示：页id + (偏移或槽号)。
应用程序不能依赖这些id来做任何事。
**Denormalized Tuple Data（规范化的元组数据）：**如果2个表是相关联的，数据库可以预先连接他们，这2个表会存在相同的页中。这样做可以让数据库只加载1个页而不是加载2个单独的页，从而大大提高速度。然而，它将会导致更新操作的代价非常大因为数据库对每个元组需要更多的空间。
04 数据库存储二
一、数据表示
元组里的数据本质上就是字节数组，DBMS知道如何去解释这些字节以得到真正的属性值。数据表示模式是DBMS如何通过字节去存储值。
有5种高层数据类型可以存储在元组中：整数、浮点数、固定精度数字、变长数据、日期/时间。
Integers（整数）
大多数DBMS使用IEEE-754标准的C/C++类型去编码整数，这些值是定长的。
例子：INTEGER, BIGINT, SMALLINT, TINYINT
Variable Precision Numbers（浮点数）
这些不精确的、精度变化的数字（浮点数）使用IEEE-754标准的C/C++类型去编码，这些值也是定长的。
操作浮点数的速度比操作固定精度的数字的速度要快，因为CPU可以直接对浮点数直接进行操作。然而，由于数字表示是不精确的，所以在计算的时候会出现误差。
例子：FLOAT, REAL
Fixed-Point Precision Numbers（固定精度数字，定点数）
这些是具有任意精度和小数位数的数字类型。它们通常以精确的，可变长度的二进制表示（像字符串一样）存储，另外还会存储元数据，这些元数据告诉系统数据的长度和小数点的位置。
当数据精确性要求很高的时候可以使用这种类型，但DBMS会花费更高的代价去进行计算。
例子：NUMERIC, DECIMAL
Variable-Length Data（变长数据）
他们表示任意长度的数据类型，他们通常在头部存储字符串的长度，以便跳转到下一个值，同时可能还包含数据的校验和。
大多数DBMS不允许一个元组大小超过单个页大小。有些则将数据存储在一个特别的”溢出“页上，并在元组上存储这个页的引用信息。
也有一些系统会存储大数据在额外的文件上，并在元组中记录文件指针。例如，如果数据库存储图片信息，DBMS会直接将图片存储在额外的文件中，而不是让它们在数据库中占用大量空间。这样做的缺点是DBMS无法操纵这个文件的内容，因此没有持久性和事务的保证。
例子：VARCHAR, VARBINARY, TEXT, BLOB
Dates and Times（日期和时间）
日期/时间的表示因系统的不同而不同。从unix时代开始，时间通常表示为单位时间（微/毫）秒（时间戳）。
例子：TIME, DATE, TIMESTAMP
System Catalogs（系统目录）
为了让DBMS解析元组，它需要维护一个内部的目录去告诉数据库的一些元信息。元信息包含数据库拥有哪些表和列以及他们的类型和值的顺序等信息。
大多数DBMS以表的形式在内部存储他们的目录，他们使用特殊的代码”引导“这些目录表。
二、工作类型
数据库系统有许多不同的工作类型，工作类型指的是系统处理的请求的一般类型。此处介绍2个类型：在线事务处理（OLTP），在线分析处理（OLAP）。
OLTP: Online Transaction Processing（在线事务处理）
OLTP工作类型的特点是快速、短时间运行的操作，一次操作单个实体的简单查询和重复查询。
OLTP工作类型的一个例子是Amazon storefront。用户可以添加商品到购物车，可以下单购买，但是这些操作只影响一个账户。
OLAP: Online Analytical Processing（在线分析处理）
OLAP工作类型的特点是长时间、复杂的查询，对数据库大量数据的读取。在OLAP工作类型中，数据库系统专注于分析，并从OLTP数据库中获取新数据（一般为同步链路）。
OLAP工作类型的一个例子是Amazon对某些地理位置计算一个月内购买最多的5件商品。
HTAP: Hybrid Transaction + Analytical Processing（混合事务分析处理）
最近流行的一种新型工作类型是HTAP，它类似于在同一个数据库上同时执行OLTP和OLAP的组合。
三、存储模型
在页中存储元组有很多种方式，到目前为止，我们假设n维存储模型。
N-Ary Storage Model（NSM n维存储模型）
在n维存储模型中，DBMS将一个元组的所有属性连续的存储在单个页中，所以NSM又称为“行存”。这种方法是OLTP工作类型的理想选择，因为在OLTP场景下，数据是大量插入的，事务只操作单一的实体。DBMS只需要单次获取就能获取一个元组的所有属性。
优点：
快速插入、更新和删除；对需要整个元组的查询友好。
缺点：
对大范围的扫描和查找一部分属性不友好，因为在查询中可能会获取不必要的数据来污染缓冲池。
Decomposition Storage Model（DSM 分解存储模型）
在分解存储模型中，DBMS将一个单独的属性（列）连续的存在一个块中。因此，这也被称为“列存”。该模型非常适合许多具有只读查询的OLAP工作类型，OLAP经常对一部分属性进行大范围扫描。
优点：
减少查询过程中浪费的数据，因为DBMS只读取查询所需的数据（制度去查询所需的属性）。
由于对同一属性的所有值连续存储，因此可以获得更好的压缩性能（或使用特定的压缩）。
缺点：
由于每个元组被存在不同的地方，因此对文件的点查、插入、更新和删除不友好。
为了将列存的元组组合回去，一般有2种常见的方法：
大多数使用的方法是*固定长度的偏移*。假设每个属性都是固定长度的，DBMS可以计算出每个元组中每个属性的偏移，然后当想要一个特定元组的属性的时候，它知道如何去跳转到某个文件某个位置。为了容纳可变长度的字段，系统可以填充字段来达到相同长度或者使用固定长度的字典来映射值（将超出长度的值存到另外的文件中并用字典记录偏移）。
另一个小众的方式是使用*嵌入式元组id*。对每个在列中的属性，DBMS同时存储一个元组id（例如主键）。系统会存储一个映射告诉如何找到每个属性id所对应的位置。但这个方法会浪费很多的存储空间，因为每个属性都会存储一个元组id。
05 缓冲池
一、简介
DBMS 的磁盘管理模块主要解决两个问题：
1.如何使用磁盘文件来表示数据库的数据（元数据、索引、数据表等）
2.如何管理数据在内存与磁盘之间的移动：在大多数情况下，数据不能直接在磁盘上操作，任何数据库都必须能够有效地将其磁盘上以文件形式表示的数据移动到内存中，以便能够使用。
管理数据在内存与磁盘之间的移动又分为两个策略：
空间控制（Spatial Control）：通过决定将 pages 写到磁盘的哪个位置，使得常常一起使用的 pages 能离得更近，从而提高 I/O 效率。
时间控制（Temporal Control）：通过决定何时将 pages 读入内存，写回磁盘，使得读写的次数最小，从而提高 I/O 效率。
局部性原理：
时间局部性：程序中的一条指令一旦执行，不久后改指令还可能再次被执行。产生时间局部性的原因是程序中存在大量的循环操作。
空间局部性：一旦程序访问了某个存储单元，在不久后，其附近的存储单元也会被访问。因为指令的顺序通常是顺序存储、顺序执行的。数据的存储也是向量、数组、表等形式
二、锁 与 锁存器
在讨论DBMS如何保护其内部元素时，我们需要对锁和锁存器进行区分：
锁：是一个更高层次的逻辑基元﹐它保护数据库的内容（如图元﹑表﹑数据库）不受其他事务的影响。事务会在其整个持续时间内持有一个锁·数据库系统可以在运行查询时向用户展示哪些锁正在被持有·锁需要能够回滚变化·
锁存器：是一种低级别的保护原素﹐DBMS在其内部数据结构（例如﹐哈希表﹑内存区域)中的宇键部分使用·锁存器只在正在进行的操作的时间内保持·锁存器不需要能够回滚变化·
三、缓冲池
缓冲池是一个从磁盘上读取页面的内存缓存·它本质上是在数据库内部分配的一个大的内存区域﹐用来存储从磁盘获取的页面。
DBMS 启动时会从 OS 申请一片内存区域，即 Buffer Pool，并将这块区域划分成大小相同的 pages，为了与 disk pages 区别，通常称为 frames，当 DBMS 请求一个 disk page 时，它首先需要被复制到 Buffer Pool 的一个 frame 中，如下图所示：
缓冲池的内存区域被组织成一个固定大小的页面阵列·每个数组条目被称为一个框架。当DBMS请求一个页面时﹐一个精确的副本被放置到缓冲池的一个框架中·然后﹐当一个页面被请求时﹐数据库系统可以首先搜索缓冲池·如果没有找到该页﹐那么系统就会从磁盘上获取该页的副本·同时 DBMS 会维护一个 page table，负责记录每个 page 在内存中的位置，以及是否被写过（Dirty Flag），是否被引用或引用计数（Pin/Reference Counter）等元信息，如下图所示：
当 page table 中的某 page 被引用时，会记录引用数（pin/reference），表示该 page 正在被使用，空间不够时不应该被移除；当被请求的 page 不在 page table 中时，DBMS 会先申请一个 latch（lock 的别名），表示该 entry 被占用，然后从 disk 中读取相关 page 到 buffer pool，释放 latch。以上两种过程如下图所示：
1.缓冲池元数据
缓冲池必须保持某些元数据﹐以便有效和正确地使用。
首先，页表是一个内存中的哈希表，用于跟踪当前内存中的页面·它将页面ID映射到缓冲池中的框架位置。由于缓冲池中的页面顺序不一定反映磁盘上的顺序﹐这个额外的中介层允许识别缓冲池中的页面位置◎注意，页面表不能与页面目录混淆，后者是从页面ID到数据库文件中的页面位置的映射·
页表还维护着每页的额外元数据﹐一个脏标志和一个引脚/参考计数器·
每当一个线程修改了一个页面﹐就会设置dirty-flag。这表明存储管理程序必须将该页写回磁盘。Pin/reference
Counier跟踪当前访问该页面的线程数量（无论是读取还是修改）·一个线程在访问该页之前必须增加该计数器。如果一个页面的计数大于0，那么存储管理器就不允许将该页面从内存中驱逐出去。
2.内存分配策略
数据库中的内存是根据两个策略分配给缓冲池的。
全局策略处理DBMS应该做出的决定﹐以有利于正在执行的整个工作负载·它考虑所有活动的事务﹐以找到分配内存的最佳决策。
另一种方法是本地策略做出决定，使单个查询或事务运行得更快﹐即使它对整个工作负载没有好处·本地策略将框架分配给特定事务﹐而不考虑并发事务的行为。
四、缓冲池优化：适应应用程序的工作负荷
1.多个缓冲池
DBMS可以为不同的目的维护多个缓冲池（即每个数据库缓冲池﹑每个页面类型的缓冲池）·然后﹐每个缓冲池可以采用为其内部存储的数据定制的本地策略·这种方法可以帮助减少锁存器的争用﹐并提高定位性
将所需页面映射到缓冲池的两种方法是对象ID和散列。
对象标识涉及到扩展记录标识﹐以包括矣于每个缓冲池管理哪些数据库对象的元数据·然后通过对象标识符，可以维护对象与特定缓冲池之间的映射尖系。
另一种方法是散列法，DBMS对页面ID进行散列以选择访问哪个缓冲池。
2.预取
DBMS也可以通过基于查询计划的预取页面来进行优化·然后﹐当第一组页面被处理时﹐第二组可以被预取到缓冲池中。这种方法是DBMS在连续访问许多页面时常用的。
3.扫描共享
查询游标可以重复使用从存储或操作者计算中获取的数据·这允许多个查询附加到一个扫描表的游标上。如果一个查询开始扫描﹐如果已经有一个在做这个﹐那么DBMS将附加到第二个查询的游标·DBMS跟踪第二个查询与第一个查询的连接位置﹐这样它就可以在到达数据结构的末端时完成扫描。
4.缓冲池旁路
顺序扫描操作者不会将获取的页面存储在缓冲池中以避免开销·相反﹐内存是运行中的查询的局部·如果操作者需要在
磁盘上读取连续的大序列页面﹐这种方法很有效·缓冲池旁路也可用于临时数据（排序·连接)。
五、操作系统页面缓存
大多数磁盘操作是通过操作系统的API进行的·除非被明确告知﹐操作系统会维护自己的文件系统缓存。大多数DBMS使用直接IO来绕过操作系统的缓存﹐以避免页面的冗余拷贝和不得不管理不同的驱逐策略。Postgres是一个使用操作系统页面缓存的数据库系统的例子。
六、缓冲区替代政策
当DBMS需要释放一个框架来为一个新的页面腾出空间时﹐它必须决定从缓冲池中驱逐哪个页面。替换策略是DBMS实现的一种算法﹐当它需要空间时﹐它决定将哪些页面从缓冲池中驱逐。
替换策略的实施目标是提高正确性﹑准确性·速度和元数据的开销。
1.最近使用最少的(LRU) 。
最近最少使用的替换策略维护着每个页面最后被访问的时间戳·这个时间戳可以存储在一个单独的数据结构中，比如一个队列﹐以便进行排序和提高效率·DBMS选择驱逐具有最古老时间戳的页面·此外﹐页面以排序的方式保存，以减少驱逐时的排序时间。
2.钟
CLOCK策略是LRU的一个近似值﹐不需要每页有单独的时间戳·在CLOCK策略中，每个页面被赋予一个参考位。当一个页面被访问时﹐设置为1。
为了形象地说明这一点﹐可以用"时钟指针
"在一个圆形缓冲区中组织页面·在清扫时检查一个页面的位是否被设置为1，如果是，则设置为0，如果不是，则驱逐它·通过这种方式﹐时钟指针在驱逐之间记住了位置。
3.替代品
LRU和CLOCK替换策略有很多问题。
也就是说﹐LRU和CLOCK很容易受到顺序泛滥的影响，即缓冲池的内容由于顺序扫描而被破坏·由于顺序扫描会读取每一页﹐所以读取的页面的时间戳可能并不反映我们真正想要的页面·换句话说﹐最近使用的页面实际上是最不需要的页面。
有三种解决万案可以解决LRU和CLOCK策略的缺点。一种解决方案是LRU-K，它以时间戳的形式跟踪最近的K次引用的历史﹐并计算出后续访问的间隔时间·这个历史记录被用来预测一个页面下次被访问的时间。
另一个优化是每个查询的定位。DBMS在每个事务/查询的基础上选择哪些页面要被驱逐·这使得每次查询对缓冲池的污染最小化。
最后，优先级提示允许事务根据查询执行期间每个页面的上下文告诉缓冲池页面是否重要。
4.脏页面
有两种方法来处理有脏位的页面·最快的方法是丢弃缓冲池中任何不脏的页面·一个较慢的方法是将脏页写回磁盘﹐以确保其变化被持久化。
这两种方法说明了快速驱逐与脏写页之间的权衡﹐脏写页在未来不会被再次读取。
避免不必要地写出页的问题的一个方法是后台写入。通过后台写入﹐DBMS可以周期性地走过页表并将脏页写入磁盘。当一个脏页被安全写入时﹐DBMS可以驱逐该页﹐或者直接取消脏页标志。
七、其他内存池
除了图元和索引之外﹐DBMS还需要内存。这些其他的内存池可能并不总是由磁盘支持，这取决于实现。
·分拣+连接缓冲器
·查询缓存
·维护缓冲区
·日志缓冲区
·词典缓存
07 哈希表
为了支持 DBMS 更高效地从 pages 中读取数据，DBMS 的设计者需要灵活运用一些数据结构及算法，其中对于 DBMS 最重要的两个是：Hash Tables、Trees
它们可能被用在 DBMS 的多个地方，包括：
Internal Meta-data 内部元数据
Core Data Storage 核心数据存储
Temporary Data Structures 临时数据结构
Table Indexes 表索引
在做相关的设计决定时，通常需要考虑两个因素：
Data Organization：如何将这些数据结构合理地放入 memory/pages 中，以及为了支持更高效的访问，应当存储哪些信息
Concurrency：如何支持数据的并发访问
一、数据结构
DBMS为系统内部的许多不同部分使用各种数据结构。例如：
·内部元数据。这是对数据库和系统状态信息进行跟踪的数据。例如∶页面表格﹑页面目录
·核心数据存储。数据结构被用来作为数据库中图元的基础存储。
·临时数据结构。DBMS可以在处理查询的过程中即时建立数据结构﹐以加快执行速度（例如，用于连接的哈希表）。
·表索引。辅助数据结构可以用来使查找特定的图元更加容易·在为DBMS实现数据结构时﹐有两个主要的设计决策需要考虑：
1.数据组织·我们需要弄清楚如何布局内存﹐以及在数据结构内存储哪些信息﹐以支持高效的访问。
2.并发性·我们还需要考虑如何使多个线程访问数据结构，而不造成问题。
二、哈希表
哈希表实现了一个分联数组的抽象数据类型﹐将键映射到值·它平均提供了O(1)的操作复杂度(最坏情况下为O(n))和O(n)的存储复杂度。请注意﹐即使平均操作复杂度为O(1)，也有恒定系数的优化﹐这在现实世界中是需要考虑的。
一个哈希表的实现由两部分组成：
·哈希函数（Hash Function）如何将一个大的密钥空间映射到一个较小的领域。它被用来计算进入一个桶或槽阵列的索引·我们需要考虑快速执行和碰撞率之间的权衡在一个极端，我们有一个总是返回一个常数的哈希函数（非常快﹐但一切都会发生碰撞）。在另一个极端，我们有一个"完美"的散列函数，没有碰撞，但计算时间非常长О理想的设计是介于两者之间。
·哈希方案（Hashing Scheme）这告诉我们如何处理散列后的密钥碰撞。在这里，我们需要考虑分配一个大的哈希表以减少碰撞和在发生碰撞时不得不执行额外的指合之间的权衡。
1、哈希函数
由于 DBMS 内使用的 Hash Function 并不会暴露在外，因此没必要使用加密（cryptographic）哈希函数，我们希望它速度越快，collision rate 越低越好。
散列函数接受任何键作为其输人。然后它返回该键的整数表示（即"哈希")。该函数的输出是确定的(即﹐相同的密钥应该总是产生相同的哈希输出）。DBMS不需要使用加密安全的哈希医数（例如SHA-256)，因为我们不需要担心保护密钥的内容·这些哈希函数主要由DBMS内部使用，因此信息不会泄露到系统之外。一般来说﹐我们只尖心哈希函数的速度和碰撞率。目前最先进的哈希函数是Facebook XXHash3
2、静态哈希方案
静态散列方案是指散列表的大小是固定的·这意味着如果DBMS在哈希表中的存储空间用完了﹐那么它就必须从头开始重建一个更大的哈希表﹐这非常昂贵·通常﹐新的哈希表是原始哈希表大小的两倍。
为了减少浪费的比较吹数﹐避免哈希键的碰撞是很重要的·通常情况下﹐我们使用两倍于预期元秦数量的槽位。
以下假设在现实中通常是不成立的。
1．元素的数量是提前知道的。
2．keys是独一无二的。
3．存在一个完美的哈希函数。
因此，我们需要适当地选择散列函数和散列模式。
2.1 线性探测
这是最基本的散列方案·它通常也是最快的·它使用数组槽的循环缓冲区·散列函数将键映射到槽。当碰撞发生时﹐我们线性地搜索相邻的槽﹐直到找到一个开放的槽·对于查找﹐我们可以检查键的哈希值所对应的槽﹐然后线性搜索﹐直到找到所需的条目·如果我们到达一个空槽﹐或者我们遍历了hashtable中的每一个槽，那么这个键就不在表中。请注意﹐这意味着我们必须在槽中同时存储键和值﹐以便我们可以检查一个条目是否是所需的·删除是比较棘手的·我们必须小心地从槽中删除条目﹐因为这可能会阻止未来的查询找到被放在现在空槽下面的条目·这个问题有两个解决方案。
·最常见的方法是使用"墓碑"。我们不删除这个条目﹐而是用一个"墓碑"条目来代替它，告诉未来的查找工作要继续扫描。
·另一个选择是在删除一个条目后移动相邻的数据以填补现在的空槽·然而﹐我们必须注意只移动最初被移位的条目。这在实践中很少实现。
非唯一键：keys 可能出现重复，但 value 不同﹐有两种方法。
·单独的链接列表О我们不将数值与键一起存储﹐而是将一个指针指向一个单独的存储区域﹐该区域包含所有数值的链接列表。（拉链法/链地址法）
·冗长的键。更常见的方法是简单地在表中多次存储同一个键·即使我们这样做﹐所有具有线性探测功能的东西仍然有效。
2.2 罗宾汉哈希
这是线性探测散列的一个扩展﹐为了防止 Linear Probe Hashing 出现连续区域导致频繁的 probe探测操作。基本思路是 “劫富济贫”，即每次比较的时候，同时需要比较每个 key 距离其原本位置的距离（越近越富余，越远越贫穷），如果遇到一个已经被占用的槽，如果它比自己富余，则可以直接替代它的位置，然后把它顺延到新的位置。
2.3布谷鸟哈希法
这种方法不是使用单一的哈希表﹐而是用不同的哈希函数维护多个哈希表。这些哈希函数是相同的算法（如XXHash、CityHash);它们通过使用不同的种子值为同一个密钥生成不同的哈希值。当我们插人时﹐我们检查每一个表﹐并选择一个有空闲位置的表(如果多个表都有空闲位置﹐我们可以比较一些东西﹐如负载系数﹐或者更常见的是﹐只是选择一个随机的表)·如果没有表有空闲的槽﹐我们就选择（通常是随机的）并驱逐旧条目·然后﹐我们将旧条目重新洗牌到一个不同的表中。在极少数情况下，我们可能会在一个循环中结束·如果发生这种情况﹐我们可以用新的哈希函数种子重建所有的哈希表(不太常见）或者用更大的表重建哈希表(更常见)。
布谷鸟散列保证了O(1)查找和删除﹐但插入可能更昂贵。
3、动态哈希方案
静态散列方案要求DBMS知道它要存储的元素的数量·否则﹐如果需要扩大/缩小表的大小﹐它就必须重建表。
动态散列方案能够根据需要调整散列表的大小﹐而不需要重建整个表。这些方案以不同的方式执行这种大小调整﹐可以最大限度地提高读取或写入。
3.1链式哈希算法
这是最常见的动态散列方案。DBMS为哈希表中的每个槽维护一个链接列表·对同一个槽进行散列的键被简单地插入到该槽的链接列表中。这么做的好处就是简单，坏处就是最坏的情况下 Hash Table 可能降级成链表，使得操作的时间复杂度降格为 O(n) 。
3.2可扩展的哈希算法
链式散列的改进版本﹐它将桶拆分﹐而不是让链永远增长·这种方法允许哈希表中的多个槽位指向同一个桶链。
重新平衡哈希表的核心思想是在拆分时移动桶的条目﹐并增加检查的位数﹐以便在哈希表中找到条目。这意味着DBMS只需要在分割链的桶内移动数据﹔所有其他的桶都不会被触动。
DBMS维护着全局和局部的深度位数﹐这些位数决定了在槽阵列中寻找桶所需的位数。·当一个桶满了﹐DBMS会分割这个桶并重新洗牌其元素·如果分割后的水桶的局部深度小于全局深度，那么新的水桶只是被添加到现有的槽阵列中·否则﹐DBMS将槽阵列的大小增加一倍以容纳新的槽﹐并增加全局深度计数器。
3.3 线性哈希
当一个桶溢出时﹐这个方案并不立即分割﹐而是保持一个分割指针，跟踪下一个要分割的桶。无论这个指针是否指向一个溢出的桶﹐DBMS都会进行分割·溢出的标准由实现者决定。
·当任何一个桶溢出时﹐通过添加一个新的槽条目﹐在指针位置分割该桶﹐并创建一个新的哈希医数。
·如果哈希函数映射到以前被指针指向的槽﹐则应用新的哈希函数·
·当指针到达最后一个槽时﹐删除原来的哈希函数﹐用一个新的哈希函数来代替它。
08 树状索引
一、表索引
table index 为提供 DBMS 数据查询的快速索引，它本身存储着某表某列排序后的数据，并包含指向相应 tuple 的指针。DBMS 需要保证表信息与索引信息在逻辑上保持同步。用户可以在 DBMS 中为任意表建立多个索引，DBMS 的工作是找出执行查询所需的最佳索引。但索引自身需要占用存储空间，因此在索引数量与索引存储、维护成本之间存在权衡。
二、B+树
B+ Tree 是一种自平衡树，它将数据有序地存储，且在 搜索、顺序访问、插入 以及 删除 操作的复杂度上都满足 O(logn) ，其中 顺序访问的最终复杂度还与所需数据总量有关。
B+ Tree 可以看作是 BST (Binary Search Tree，二叉查找树：左小右大) 的衍生结构，它的每个节点可以有多个 children，这特别契合 disk-oriented database （面向磁盘的数据库）的数据存储方式，每个 page 存储一个节点，使得树的结构扁平化，减少获取索引给查询带来的 I/O 成本。
B-Tree和B+Tree之间的主要区别是，B-Tree在所有节点中存储键和值，而B+树只在叶节点中存储值。现代B+树的实现结合了其他B-树变体的特征，例如Blink-树中使用的兄弟姐妹指针。
从形式上看，B+树是一棵M-way搜索树（其中M代表一个节点可以拥有的最大子女数），具有以下特性。
•它是完全平衡的（即每个叶子节点都处于相同的深度）。
• 除根以外的每个内部节点至少有一半是满的（M/21 < = 键的数量< = M1）。
• 每个有k个键的内部节点都有k+1个非空的子节点。
• 每个节点最多存储 M 个 key，有 M+1 个 children
• 除了 root 节点，所有其它节点中至少处于半满状态
• B+ Tree 的 leaf nodes 通过双向链表串联，从而为 sequential access 提供更高效的支持
B+Tree中的每个节点都包含一个键/值对数组。这些对中的键是由索引所基于的属性派生的。 这些值会根据一个节点是内部节点还是叶子节点而有所不同。 对于内部节点，值数组将包含指向其他节点的指针。 叶子节点值的两种方法是记录ID和元组数据。记录ID指的是一个指向元组位置的指针。有元组数据的叶子节点在每个节点中存储元组的实际内容。
B+树代码
B+ Tree 中的每个 node 都包含一列按 key 排好序的 key/value pairs，key 就是 table index 对应的 column，value 的取值与 node 类型相关，在 inner nodes 和 leaf nodes 中存的内容不同。
leaf node 的 values 取值在不同数据库中、不同索引优先级中也不同，但总而言之，通常有两种做法：
*Record/Tuple Ids：存储指向最终 tuple 的指针
*Tuple Data：直接将 tuple data 存在 leaf node 中，但这种方式对于 Secondary Indexes 不适用，因为 DBMS 只能将 tuple 数据存储到一个 index 中，否则数据的存储就会出现冗余，同时带来额外的维护成本。
此外，leaf node 还需要存储相邻 siblings 的地址以及其它一下元信息，如下图所示：
三、B+树操作
插入
要在B+树中插入一个新的条目，必须沿着树向下遍历，并使用内部节点来确定将钥匙插入哪个叶子节点。
1.找到对应的 leaf node，L
2.将 key/value pair 按顺序插入到 L 中
3.如果 L 还有足够的空间，操作结束；如果空间不足，则需要将 L 分裂成两个节点，同时在 parent node 上新增 entry，若 parent node 也空间不足，则递归地分裂，直到 root node 为止。
删减
在插入过程中，当树变得太满时，我们偶尔不得不分割叶子，而如果删除导致树少于半满，我们必须进行合并，以重新平衡树。
1.找到正确的叶子L。
2. 删除该条目。
•如果L至少是半满，操作就完成了。
•否则，你可以尝试重新分配，从兄弟姐妹那里借钱。
•如果重新分配失败，则合并L和兄弟姐妹。
3.如果发生合并，你必须删除指向L的父项。
选择条件
因为B+Tree是按排序的，所以查找有快速的遍历，也不需要整个键。如果查询提供了搜索键的任何属性，DBMS可以使用B+Tree索引。这与散列索引不同，散列索引需要搜索键中的所有属性。
非唯一索引
像散列表一样，B+Trees可以通过重复键或存储值列表来处理非唯一的索引。在重复键的方法中，使用相同的叶子节点布局，但重复的键被多次存储。 在值列表方法中，每个键只存储一次，并保持一个唯一值的链接列表。
重复的key
在B+Tree中，有两种方法来重复键。
第一种方法是将记录ID作为密钥的一部分。由于每个元组的记录ID是唯一的，这将确保所有的键都是可识别的。
第二种方法是允许叶子节点溢出到包含重复键的溢出节点。虽然没有多余的信息被存储，但这种方法的维护和修改更加复杂。
集群索引
该表按照主键指定的排序顺序存储，作为堆组织或索引组织的存储。由于一些DBMS总是使用聚类索引，所以如果一个表没有明确的主键，它们会自动做一个隐藏的行id主键，但是其他的DBMS根本不能使用它们。
堆积聚类
图元在堆的页面中使用聚类索引指定的顺序进行排序。如果聚类索引的属性被用来访问图元，DBMS可以直接跳到这些页面。
索引扫描页面排序
由于直接从非聚类索引中检索图元的效率很低，DBMS可以首先找出它所需要的所有图元，然后根据它们的页面ID进行排序。
三、B+树设计的选择
3.1节点大小
根据存储介质的不同，我们可能喜欢更大或更小的节点尺寸。例如，存储在硬盘上的节点通常是以兆字节为单位的，以减少寻找数据所需的次数，并将昂贵的磁盘读取分摊到一大块数据上，而内存数据库可能使用小到512字节的页面大小，以便将整个页面放入CPU缓存，并减少数据碎片。 这种选择也取决于工作负载的类型，如点查询会喜欢尽可能小的页面，以减少不必要的额外信息的加载量，而大型顺序扫描可能更喜欢大的页面，以减少它需要做的取数。
3.2合并阈值
虽然B+Trees有一条规则，即在删除后合并溢出的节点，但有时暂时违反该规则以减少删除操作的数量可能是有益的。例如，急于合并可能会导致激动，大量连续的删除和插入操作会导致不断的分裂和合并。它还允许分批合并，即一次发生多个合并操作，减少在树上进行昂贵的写锁存的时间。
3.3可变长度的key
目前我们只讨论了具有固定长度键的B+Trees。然而，我们可能也想支持可变长度的键，比如说一个大键的小子集导致大量空间浪费的情况。对此有几种方法。
1.指示器
我们可以不直接存储键，而只是存储一个指向键的指针。由于必须为每个键追寻一个指针的低效率，在生产中使用这种方法的唯一地方是嵌入式设备，其微小的寄存器和缓存可能会从这种空间的节省中受益
2.可变长度的节点
我们也可以像平常一样存储密钥，并允许可变长度的节点。这是不可行的，而且由于处理可变长度的节点有很大的内存管理开销，所以基本上没有使用。
3.填充物
我们可以不改变钥匙的大小，而是将每个钥匙的大小设置为最大钥匙的大小，并将所有较短的钥匙垫出。在大多数情况下，这是对内存的巨大浪费，所以你也不会看到有人使用这种方法。
4.关键地图/方向
几乎每个人都在使用的方法是用一个索引来代替键值对在一个单独的字典中的键值。这可以大大节省空间，并有可能缩短点查询（因为索引指向的键值对与叶子节点指向的键值对完全相同）。由于字典索引值的大小较小，有足够的空间将每个键的前缀放在索引旁边，可能允许一些索引搜索和叶子扫描，甚至不必追逐指针（如果前缀与搜索键有任何不同）。
3.4节点内搜索
一旦我们到达一个节点，我们仍然需要在该节点内进行搜索（要么从内部节点找到下一个节点，要么在叶子节点中找到我们的键值）。虽然这相对简单，但仍有一些权衡需要考虑。
1.线性
最简单的解决方案是直接扫描节点中的每个键，直到我们找到我们的键。一方面，我们不必担心对键进行排序，使插入和删除变得更快。另一方面，这也是相对低效的，每次搜索的复杂度为O(n)。这可以使用SIMD（或同等）指令进行矢量处理。
2.二进制
一个更有效的搜索方案是保持每个节点的排序，并使用二进制搜索来寻找钥匙。这就像跳到一个节点的中间，根据键的比较，向左或向右转动一样简单。这种方式的搜索效率更高，因为这种方法每次搜索的复杂度只有O(ln(n))。然而，插入变得更加昂贵，因为我们必须维护每个节点的排序。
3.内插法
最后，在某些情况下，我们可能会利用插值法来寻找钥匙。这种方法利用了存储在节点上的任何元数据（如最大元素、最小元素、平均数等），并利用它来生成钥匙的大致位置。例如，如果我们在一个节点中寻找8，我们知道10是最大的键，10（n+1）是最小的键（其中n是每个节点中的键的数量），那么我们知道从最大的键向下2个槽开始搜索，因为在这种情况下，离最大的键一个槽的键必须是9。 尽管这是我们给出的最快的方法，但由于其对具有某些属性（如整数）和复杂性的键的适用性有限，这种方法只在学术数据库中出现。
四、优化
指针挥舞
因为B+Tree的每个节点都存储在缓冲池的一个页面中，所以每次我们加载一个新的页面时，都需要从缓冲池中获取它，这需要锁存和查找。为了完全跳过这一步，我们可以用实际的原始指针来代替页面ID（称为 "swizzling"），完全避免缓冲池的获取。 与其手动获取整个树并手动放置指针，我们可以在正常遍历索引时简单地存储从页面查询中得到的指针。请注意，我们必须跟踪哪些指针被swizzled了，当它们所指向的页面被取消钉子，并成为受害者时，要把它们解冻成页面ID。
批量插入
当B+Tree最初建立时，必须以通常的方式插入每个键，这将导致持续的分割操作。由于我们已经给叶子提供了兄弟姐妹的指针，如果我们构建一个叶子节点的排序链表，然后使用每个叶子节点的第一个键从下往上轻松地建立索引，那么初始插入数据的效率会高很多。请注意，根据我们的情况，我们可能希望将叶子打包得越紧越好，，以节省空间，或者在每个叶子中留出空间，以便在有必要进行分割之前进行更多的插入。
前缀压缩
大多数情况下，当我们在同一节点中拥有键时，每个键的一些前缀会有部分重叠（因为类似的键最终会在排序的B+Tree中紧挨着）。 与其多次将这个前缀作为每个键的一部分来存储，我们可以简单地在节点的开头存储一次前缀，然后在每个槽中只包括每个键的独特部分。
重复数据删除
在一个允许非唯一键的索引的情况下，我们最终可能会出现叶子结点反复包含相同的键而附加不同的值。这方面的一个优化是只写一次键，然后在它后面加上所有相关的值。
后缀截断
在大多数情况下，内部节点中的关键条目只是作为路标，而不是其实际的关键值（因为即使一个关键存在于索引中，我们仍然要搜索到底部以确保它没有被删除）。我们可以利用这一点，只存储正确路由探针到正确节点所需的最小前缀。
09 索引并发控制
在前两节中讨论的数据结构中，我们都只考虑单线程访问的情况。实践中，绝大多数情况下，我们需要在并发访问情况下保证我们的数据结构还能够正常工作。除了 VoltDB，它用一个线程处理所有请求，彻底排除了并发的需要。
一、索引并发控制
到目前为止，我们假设我们所讨论的数据结构是单线程的。然而，大多数DBMS需要允许多个线程安全地访问数据结构，以利用额外的CPU内核和隐藏磁盘I/O停顿。
并发控制协议是DBMS用来确保对共享对象进行并发操作的"正确"结果的方法。
通常我们会从两个层面上来理解并发控制的正确性：
●逻辑上的正确性:线程能够读取它应该期望读取的值。例如，一个线程应该读回它之前写过的值。
●物理正确性:对象的内部表示是健全的，例如，在数据结构中没有指针会导致线程读取无效的内存位置。
二、锁与锁扣
在讨论DBMS如何保护其内部元素时，锁和锁扣之间有一个重要的区别。
锁
锁是一个更高层次的逻辑基元，它保护数据库的内容( 如图元、表、数据库)不受其他事务的影响。事务将在整个持续时间内持有一个锁。数据库系统可以向用户展示在运行查询时被持有的锁需要能够回滚变化。
锁存器
锁存器是用于DBMS内部数据结构(例如，数据结构、内存区域)的关键部分的低级保护基元，不受其他线程影响。锁存器只在正在进行的操作的持续时间内保持。锁存器不需要能够回滚变化有两种模式的锁存器。
●读:允许多个线程同时读取同一个项目。并发读
●写 :只允许一个线程访问该项目。如果其他线程在任何模式下都持有写锁存器，那么一个线程就不能获得写锁存器。一个持有写锁存器的线程也会阻止其他线程，获得一个读锁存器。
三、闩锁的实施
用来实现锁存器的基本原理是通过现代CPU提供的原子比较和交换(CAS) 指令。有了这个指令一个线程可以检查一个内存位置的内容，看它是否有某个值。如果它有，那么CPU将用一个新的值来交换旧的值。否则，该内存位置将保持不被修改。在DBMS中实现锁存器有几种方法。每种方法在工程复杂性和运行时性能方面都有不同的权衡。这些测试和设置步骤是以原子方式进行的( 也就是说，在测试和设置步骤之间没有其他线程可以更新值。
阻止操作系统Mutex
锁存器的一个可能实现是操作系统内置的互斥基础设施。Linux提供了Futex (快 速用户空间互斥.)，它由(1) 用户空间的自旋锁存器和(2) 操作系统级互斥组成。如果DBMS能够获得用户空间的锁存器，那么锁存器就会被设置。在DBMS看来，它是一一个单一的锁存器，尽管它包含两个.内部锁存器。如果DBMS不能获取用户空间的锁存器，那么它就会进入内核并试图获取-一个更昂贵的mutex。如果DBMS未能获得第二二个mutex，那么线程就会通知操作系统它在mutex.上被阻塞了然后它就会被取消计划。
在DBMS中，操作系统的mutex通常是- -个坏主意，因为它是由操作系统管理的，有很大的开销。
●例如: std: :mutex
●优点。使用简单，不需要在DBMS中进行额外编码。
●缺点。由于操作系统的调度，昂贵且不可扩展(每次锁/解锁调用约25 ns) 。
测试和设置旋转锁存器(TAS)
自旋锁存器是操作系统互斥器的一个更有效的替代品，因为它是由DBMSs控制的。自旋锁基本上是线程试图更新的内存位置(例如，将-一个布尔值设置为真)。 -一个线程执行CAS来尝试更新内存位置。DBMS 可以控制如果它不能得到锁存器会发生什么。它可以选择再次尝试(例如，使用一个while循环)或允许操作系统取消调度。因此，这种方法给了DBMS更多的控制权，而不是OS的mutex，在OS的mutex中， 失败的锁存器将控制权交给OS。
●例如: std::atomic<T>。
●优点。锁定/解锁操作是有效的(单指令锁定/解锁) 。
●劣势。不具有可扩展性，也不适合缓存，因为在多线程中，CAS指令会在不同的线程中被多次执行。这些浪费的指令在高竞争环境中会堆积起来;在操作系统看来，这些线程很忙，尽管它们并没有做有用的工作。这导致了缓存一致性问题，因为线程正在轮询其他CPU的缓存线。
读写器锁扣
Mutexes和Spin
Latches不区分读/写(也就是说，它们不支持不同的模式)。 DBMS需要一种允许并发读取的方式，所以如果应用程序有大量的读取，它将有更好的性能，因为读取者可以共享资源而不是等待。读者-写者锁存器允许锁存器以读或写模式被持有。它跟踪有多少线程持有该锁存器，并在每种模式下等待获取该锁存器。读者-写者锁存器使用前两种锁存器实现中的一种作为基元，并有额外的逻辑来处理读者写者队列。
这是在每种模式下对锁存器的队列请求。不同的DBMS对于如何处理队列可以有不同的策略。.
●示例: std: :shared mutex
●优点。允许并发的读者。
●缺点。DBMS必须管理读/写队列以避免饿死。由于额外的元数据，存储开销比自旋锁存器大。
四、哈希表锁存
由于线程访问数据结构的方式有限，因此在静态哈希表中支持并发访问很容易。例如，所有线程在从槽中移动到下一个槽时，都是朝同一个方向移动(即自上而下)。 线程每次也只访问一个页面/槽。因此，在这种情况下，死锁是不可能的，因为没有两个线程可以争夺对方持有的锁存器。当我们需要调整表的大小时，我们可以直接在整个表上取一个全局锁存器来执行操作。
动态散列方案中的锁存(例如，可扩展)是一个更复杂的方案，因为有更多的共享状态需要更新但一般的方法是相同的。
有两种方法来支持哈希表的锁存，它们在锁存的粒度上有所不同。
●页面锁存器。每个页面都有自己的读写锁存器，保护其全部内容。线程在访问一个页面之前会获得一个读或写锁。这降低了并行性，因为一-次可能只有一个线程可以访问一个页面，但是对于一个线程来说，访问一个页面中的多个槽会很快速，因为它只需要获取一一个锁存器。
●槽的锁扣。每个槽都有自己的锁存器。这增加了并行性，因为两个线程可以访问同一页面上的不同槽。但是它增加了访问表的存储和计算开销， 因为线程必须为他们访问的每个槽获得一个锁存器，每个槽必须为锁存器存储数据。DBMS可以使用单模式锁存器(即旋转锁存器)来减少元数据和计算开销，但要付出一-些并行性的代价。
也可以直接使用比较和交换(CAS)指令创建-一个无闩锁的线性探测哈希表。在- -一个槽的插人可以通过尝试将- 个特殊的"空. "值与我们想要插入的元组进行比较和交换来实现。如果失败了， 我们可以探测下一个槽，继续下去.直到成功。
五、B+树形锁存
B+Tree锁存的挑战在于防止以下两个问题。
●试图同时修改-一个节点的内容的线程。
●一个线程遍历树，而另一个线程拆分/合并结点。
闩锁抓取/耦合是一种协议，允许多个线程同时访问/修改B+Tree。其基本思想如下。
1.为父方获取闩锁。
2.为孩子准备好锁扣。
3.如果子节点被认为是"安全的"，则释放父节点的闩锁。一个."安全"的节点是在更新时不会分裂、合并或重新分配的节点。.注意，"安全"的概念取决 于操作是插入还是删除。-一个完整的节点对于删除来说是"安全"的，因为不需要合并， 但是对于插入来说就不"安全"了，因为我们可能需要分割节点。请注意，读锁存器不需要担心"安全"条件。
闩式捕蟹的基本协议。
●搜索。从根部开始，往下走，反复取得子代的锁扣，然后解开父代的锁扣。
●插入/删除。从根部开始，往下走，根据需要获得X个锁扣。一旦孩子被锁住，检查它是否安全。如果孩子是安全的，释放其所有祖先的锁扣。
从正确性的角度来看，释放锁存器的顺序并不重要。然而，从性能的角度来看， 最好是释放树中较高位置的锁存器，因为它们阻断了对较大部分叶子节点的访问。改进的闩锁抓取协议。基本锁存器抓取算法的问题是，每次插人/删除操作时，交易总是在根.上获得一个独占锁存器。这限制了并行性。相反，我们可以假设调整大小(即分割/合并节点)的情况很少，因此事务可以获得共享锁存器，直到叶节点。每个事务都会假设通往目标叶子节点的路径是安全的，并使用READ锁存器和抓取来到达它并进行验证。如果叶子节点不安全，那么我们就放弃，并执行之前的算法，即我们获取WRITE锁存器。
●搜索。与以前的算法相同。
●插入/删除。像搜索一样设置READ锁存器，进入叶子，在叶子上设置WRITE锁存器。如果叶子不安全，释放所有以前的锁存器，并使用以前的插入/删除协议重新开始交易。
叶子节点扫描
这些协议中的线程以"自上而下"的方式获取锁存器。这意味着一个线程只能从其当前节点以下的节点获取锁存器。如果想要的锁存器不可用，线程必须等待，直到它变得可用。鉴于此，不可能出现死锁。
然而，叶子节点扫描很容易出现死锁，因为现在我们有线程试图同时在两个不同的方向上获得外锁(例如，线程1试图删除，线程2进行叶子节点扫描)。 索弓|锁不支持死锁检测或避免。
因此，程序员处理这个问题的唯一方法是 通过编码纪律。叶子节点兄弟姐妹的锁存器获取协议必须支持"无等待"模式。也就是说，B+tree代码必须应对锁存器获取失败的问题。由于锁存器旨在被(相对)短暂地持有，如果一个线程试图在叶子节点上获取锁存器，但该锁存器不可用，那么它应该迅速中止其操作(释放它所持有的任何锁存器)并重新启动操作。
酷酷酷酷酷
