写在前面：文中提到的页面指向（如“p45”），除特别说明，都是指对应ppt上的页面，非同款ppt的友友可忽略
第一章
ER图和关系分解见讲义p69
ER图是常用的 概念模子
常用的逻辑模子
说白了：增删改查
几种数据模子的根本概念
层次模子：树状结构【只能处理一对多的关系，只有沿着从根节点到子节点的方向看才有意义】
【找到逐级的包罗关系，构建立】
网状模子：每个实体分别建表，然后实体间接洽再建一个表【维护代价大】
关系模子p45
关系，就是元组的聚集；元组的核心，在于主码。
模式p53
数据库模式体系：三层模式，两层映射
- 外模式【多个】：【局部数据的逻辑结构和接洽】一对多，一个应用只能访问一个外模式对应数据，但一个用户可以有多个应用，因此可以访问多个外模式，用户只能看见和访问对应外模式的数据
- 模式【一个】：【全部数据的逻辑结构和接洽，和完整性、规范性约束】
- 内模式【一个】：【数据的物理结构和存储方式】
第二章ppt1
n元关系只要n个域就行，不要求是差别的域
列是同质的： 一个列上的所有元素的类型是一样的
原子值：比如“姓名” 属性的值就是一个原子值，像 “张三”，它不能再分割成更小的有意义的数据部分 。
记：同质/来源/ 行序/列序 /元组唯一/分量原子值
参照关系
可以自己和自己参照！比如员工和其上级
两个完整性约束
下图最后一句是说：如果R的外码包罗多个属性，那么他们要么全都是空的，要么就是要和S中的某个元组对应
第二章：范式和函数依赖
四大范式NF
属于2NF但不属于3NF的例子：
学生，系别，宿舍区域；学生是主码，通过系别通报依赖于宿舍区
属于3NF但不属于BCNF的例子：
（A，B，C）中，有主码（A，B）-> C， 且C决定部分主码列C->A
函数依赖【讲义p76】
✅函数依赖x->y可以有，对于相同的y，有差别的x
易错例！
平凡& 非平凡函数依赖
完全依赖F，部分依赖P& 通报依赖T【注意有“不包罗，不反推”的要求】【注意各自箭头上的字母】
上面的这些叫函数依赖
多值依赖p30开始【不考】
第三章：
关系代数：\pi，\sigma，除法和多表查询
//去重问题：根据豆包的说法，一般投影运算pai会自动去重，但是sigema不会对元素去重
//注意：一般要综合使用，比如要选出“选出运送了1号货品的商家的编号”，应该先用sigema选出“1号货品”，再用pai选出商家编号
多表查询：查询的表为多个表的天然连接
sigema的角标“且，或” 的表示：用析取合取号
下图二：除法的使用【注意除法是一种关系代数】
看右图用例比较方便，注意除法变更不可逆（乘法是包罗关系）
除法使用例：找出至少使用了S1提供的全部零件的JNO<看到“全部”，想到除法>
<=> 找出S1提供的全部零件（用sigema_S1再用pai选出零件列）， 找出包罗全部零件和JNO映射关系的列（用pai选出），最后用后者除以前者。
天然连接的定义&特殊的天然连接
左外连接（Left Outer Join）的效果中，左边表的所有记载都会保存，而右边表中与左边表匹配的记载会正常体现，右边表中缺失的匹配项对应的字段值填 NULL。
内连接：删除所有不满足条件的
SQL语句
讲义索引：
模式的创建【CREATE SCHEME 模式名 AUTHORIZATION 用户】
表、视图的创建【p100】
字符串匹配 LIKE【p115】
聚集函数【p117】
GROUP BY【p118】
嵌套查询【p125】 where Sno in （select Sno where 。。。）
数目关系上的查询（如最值） 运算符和聚集函数如 any， <max，>min【p128】
聚集利用 Union Intersect Except 等【p129】
数据更新【p132】Insert， Update， Delete
数据控制语言【权限授予等p134】
表、视图和索引
表：中间的属性 not null；unique; primary key【别的可用check（第四章有讲）】
- 表的内部修改（列） Alter Table 表名+
- ADD 列名 列的新属性 --增加列
- DROP 列名 --删除列
- Alter 列名 列的新属性；--改属性值
视图View：创建后可以像Table一样查找
- 表和视图的删除都有Cascade级联选项，A（子表）参照B（父表），父表被级联删除，子表一并被删
- 物化视图（一般用于对于相同量的反复查找）：Create materialized view 视图名 as select...
索引：
- Create [unique][cluster] index on SC(Sno [ASC/ DESC])【缺项为ASC】
- Alter 旧索引名 rename to 新索引名
三种典型索引：
单一索引：去重性
聚簇索引：索引项和真实存储的物理顺序同等
三者的删除都是DROP，Cascade级联选项分别对应（同时删除模式中的数据，依赖于该表的表、视图）。与Cascade相对的是RESTRICT【如果不满足下面的限定条件，就不能删除】【不写的话默认是RESTRICT（记忆：这样更小心审慎，防止删除影响到其他）】
数据类型：
New：日期型DATE，半字长整数SMALLINT
数据更新（对表中的元组）
Insert into 表名（列1， 列2）values （值1，值2）
注意！⚠️INSERT INTO... VALUES 用于插入单行指定值，这里是查询效果插入，无需 VALUES ，直接跟 SELECT 语句。
Update 表名 Set 列名1 = 表达式1，列名2 = 表达式2 [where ..]
Delete From 表名 [where ..]
外连接：C LEFT OUTER JOIN
使用Exists语句之前：将天然语言终极转换成 “（不）存在。。。样的的记载” 的情势
嵌套查询：注意父子之间的连接：“他”<也即父查询“输出他的”，子查询“不存在他的”>，以是要记得在子查询的where语句中加入Sno = Student.Sno 的判断
用 Exists 语句实现全称量词：两次嵌套
选修全部课程 <==> 不存在这样的课程，不存在该同学对该课程的选修记载<p29>
典例 tip：记着就好了~
下面语义：找这样的学生，不存在 95002 选修的课程，该学生没选（即对于该学生而言，不存在自己选修该课程的记载）
理解：SCX，SCY，SCZ分别是差别层次对表的代称，其中SCY用来指代‘95002’号学生，SCX和SCZ都是用来指终极要输出的学生，层次关系是：SCX和SCZ学号相等
记忆：
- 第一层：找学生，这个好理解
- 第二次：在exists内部，以是select*，然后限定是95002
- 第三层：同二用select*，与第一层，第二层分别接洽：和第一层是同样的学生，和第二层是同样的课程
换一种方式实现上面的功能【Group by + Having】
一样的课程 <=> 找出我选了你也选了的课程，发现数目是一样的
- SELECT SCX.Sno
- FROM SC SCX
- WHERE SCX.Cno IN (SELECT Cno FROM SC WHERE Sno = '95002')--现在只留下了两人都选的课程
- GROUP BY SCX.Sno --用group by A，则select后面要么是A，要么是对于各列的聚集函数
- HAVING COUNT(DISTINCT SCX.Cno) = (SELECT COUNT(DISTINCT Cno) FROM SC WHERE Sno = '95002');
- --select 后面的东西本质上就是这一部分查询最终输出的东西
- select scx.sno
- from sc as scx
- where sc.cno in (select cno from sc where sno = '95002')
- group by scx.sno
- having count(distinct scx.sno) = (select count(distinct cno) from sc where sno = '95002')
例题：查询同时选了两个指定课程的学生ID
【利用子查询】
- SELECT ID
- FROM takes
- WHERE course_id = 'CS-101'
- AND ID IN (SELECT ID FROM takes WHERE course_id = 'CS-190');
SQLSheet系统注意事项
- 表格重命名要用as，“from student ST”会堕落，只能用 from student as s, 且一旦重命名就不能再用原始名字！
- 注意去重，查询要去重DISTINCT，风俗性select DISTINCT ID,注意：DISTINCT不能用于多个列
- 多表连接，select 对象要指明，比如from的多个表都有ID列，select的时候不能写select ID，而要详细写比如student.ID
-
画下划线的是表的主码，即这几列的整体才能唯一确定一个元组，也即单独几列不可以唯一确定一个元组
易错示例
注意from的范围：选了课程的学生 ！= 总学生
注意：下面这种查询对应的是“takes中没有选course_id 的学生”，而不是题目要求的“（所有学生中）没有选course_id 的学生”
Q8 [Query the student ID of students who have taken all courses]
- select distinct student.ID
- from student, takes
- where student.ID = takes.ID
- and takes.course_id in (select distinct course_id from takes)
- group by student.ID
- having count(takes.course_id) = (select count(distinct takes.course_id) from takes);
T16
误！题目理解错误！number of courses是指每个符合要求学生的详细85分以上课程的数目，并不是“总共有多少个85分以上课程（所有课程满分都💯哇！）”
后记：关于SQL
SQL是一种声明式语言，而不是一种过程式语言，即用户只指出做什么，但不指定怎么做（不描述执行的详细步调）
但任何一个SELECT语句，都可以等价转化为关系代数 的语句，后者是具有肯定过程性的（先做笛卡儿积，再用筛选，最后投影）
关系代数的范围性：关系代数算子的实现不清楚（实际上要落实到详细的物理利用符上）
第四章：完整性和安全性【自学】
GRANT 语句的书写者，需 具备 “授权权限” ，详细分场景：
- 数据库管理员（DBA）：拥有最高权限，可写 GRANT 给任意用户授权。
- 对象属主（OWNER）：创建表、视图等对象的用户，能写 GRANT 分配自己对象的权限。
- 有流传权限的用户：若被授予权限时带 WITH GRANT OPTION，可写 GRANT 把权限再授给他人（但不能循环授权 ）。
普通 “仅访问” 的用户，若无上述权限，不能写 GRANT
收回权限REVOKE
关于写和不写Cascade的区别：
不写 CASCADE ：
- 执行 REVOKE INSERT ON TABLE SC FROM U5（会查抄U5是否有级联，如果有，拒绝回收任何一个权限）：
数据库发现 U5 把权限传给了 U6，会拒绝回收（报错或提示需级联 ），U5、U6、U7 的权限都保存。
- 若 U5 没传给任何人：
执行 REVOKE... FROM U5（不写 CASCADE ），仅回收 U5 的权限，不影响其他用户。
数据库的角色：将一组权限打包
Create Role
With Admin Option
强制存取控制【办理自主存取方法的问题】
给用户和数据都标有肯定敏感度标记
⚠️：只有同等级才能写！
DAC【自主访问控制】，MAC【强制访问控制】
视图机制就是，把A用户能访问的数据打包成一个视图，然后把对该视图的相干权限授予给A，替代直接对原始表授权p26
三种完整性定义
实体完整性【主码，Primary key】
参照完整性【Foreign key A references on S(Sno)】
要求外码要么为空，要么等于参照表的某个主码值
用户完整性【定义表的时候设置要求，char（9），unique，not null等设置对单个属性的限定，用check实现对于单个或差别属性组之间的关系的限定】
综合例：【check 搭配使用】
- between 200 and 500（取的数值在什么范围之间）
- not like（“（用于字符串）不能是”）
- in（“取值只能是”）
域的完整性约束Domain
触发器p46
使用示例【转载】
- DELIMITER $$
-
- CREATE TRIGGER update_is_leave_cleanup
- AFTER INSERT ON community
- FOR EACH ROW
- BEGIN
- -- 检查新增小区楼栋数量是否 大于20栋 且 住户是否不低于150人
- IF NEW.term_count > 20 AND NEW.per_count >= 150 THEN
- -- 删除所有离开时间超过一年的访客记录
- DELETE FROM manual_record
- WHERE is_leave = 1
- AND out_time < DATE_SUB(NOW(), INTERVAL 1 YEAR);
- END IF;
- END$$
-
- DELIMITER;
两种堆文件存储方式【page之间的存储】：链表堆和目次堆（文件内部的页面之间的存储）
每个页page里面的存储：
定长元组：顺序存储
变长元组的存储：分槽slot页面结构
- Entries：实体数目
- 空闲空间末端指针：指向空闲空间
- slot中的元组：存储指针和巨细
下图：上边是元组的内容，下面是对应的存储
注意存储顺序：1 空值位图，2 定长属性值，3 变长属性的索引记载（起始位置，长度），每个索引长度固定为4 <有点像指针的思想> ；4 变长属性的详细值
空值位图：指示哪一位为空（NULL），为空的那一位计为1【如下图，第三位为1，就是第三个信息计为NULL】
- 行存：得当点查询（目标是精准定位 “单个或少少特定记载”）和删改
- 列存：得当对部分属性的大量查询，减少读负载上的IO使用
缓冲池：对应书 5.9节
CLOCK置换算法：只需要一个bit位作为标记位就可以大概实现LRU的效果
想象有一个环形的时钟，每个时钟位置都可以放置一个数据页。当数据页被访问时，标记位就从0酿成1（但此时时钟指向的位置稳定）。
当缓存空间满了，需要淘汰一个数据页时，算法就从当前指针位置开始，沿着时钟方向逐个查抄数据页。如果一个数据页没有被标记，那么就把它淘汰掉，由于这意味着它最近没有被使用过。如果遇到被标记的数据页，就把它的标记清除（熄灭灯），然后继续查抄下一个数据页，直到找到一个没有标记的数据页并淘汰它，替换成新的页面，并将新的页面记为0（调入后再执行缺页指令，才访问这个页面，然后将其置为1）。（理解：如果初始值设成1的话会出问题）
这里涉及到利用系统中 “页面调入” 和 “页面访问” 的时序区别。在 CLOCK 算法中，新页面初始标记为 0 而非 1 的核心原因是：页面调入内存的利用自己不等于对该页面的访问。
- 页面调入（Page Fault Handling）
当发生缺页中断时，利用系统需要从磁盘将所需页面调入内存。这个过程分为两个步调：
- 步调 1：物理页面分配
系统选择一个空闲帧（或淘汰一个旧页面），将新页面从磁盘复制到该帧。此时，新页面只是被加载到内存中，但尚未被 CPU 访问。
- 步调 2：访问权限规复
当页面加载完成后，CPU 会重新执行导致缺页的指令，此时才会真正访问该页面（读 / 写数据）。
关键点：CLOCK 算法在步调 1（页面加载）时就将新页面的标记位设为 0，而访问标记（设为 1）是在步调 2（CPU 实际访问）时才发生的。
索引的分类
根据存储的物理结构
- 聚簇索引：索引和数据绑定在一起，按照索引顺序存储（如果索引对应了n个元组，则这n个元组应该连续存储）
- 非聚簇索引：索引和数据分开存储
根据索引是否覆盖所有的搜索码
根据是否按照数据的顺序存储
注意：上面几个没有绝对的包罗关系，而是差别层面的实现情势
三种查找（1+2）【p88】
表扫描+两种索引扫描
B + 树的分支因子（也叫阶 ）：指B + 树非叶子节点能拥有的最大子节点（分支）数目
PS：老师课上提到，下面对数底数n/2中，n一般取100，也就是㏒底数一般是50
速记框架：
扫描和背面的连接的重要区别在于，扫描是针对一个表（或者多表连接后的一个表）而进行的利用，连接的对象是多个表
B+树
查找的复杂度与树的深度线性相干
各方面的数据限定
注意：B+树对叶子节点是元素数目的要求，但对非叶子（根节点和中间节点）节点是子节点数目（本质就是指针）的限定
m路B+树根节点的孩子数目：2~m个
插入&删除算法
都是先用find找到要利用的叶子节点，然后利用
注意，插入并不是简单放在空位上，还要对节点内部进行排序
潜伏问题和办理：
- 插入导致过满？拆分，拆分会反应到父节点改变，存在网上级联影响的可能
- 删除导致元素过少？先实行和左右兄弟节点归并（旁边兄弟有足够空位），归并会反应到父节点改变，存在网上级联影响的可能
- 当删除导致节点元素过少时，优先实行与兄弟节点归并（如果兄弟节点有足够空间）。
- 归并后，父节点的指针需要重新调整（例如，两个子节点归并为一个，父节点原来指向这两个节点的指针需要归并为一个），这就是指针重分布。
B+树的查询
下图中符号含义的说明：
- 指该节点左边指针对应的子树
- 指该节点右边指针对应的子树
- 为该节点最右边的子树（确定的）
哈希表
先计算该项对应的哈希值，作为插入的索引
两类哈希表&静态哈希表的两种实现情势
静态哈希表的 “静态” 体如今其哈希表的结构和巨细在初始化后就不再改变 。哈希表的桶数目固定，使用的哈希函数也是确定稳定的 。静态哈希表若要应对超出当前容量的数据，往往需要重修整个哈希表，开销较大 。动态哈希表则具备相应机制，如可扩展哈希表通过按需扩展目次深度、分裂桶等方式来容纳更多数据；线性哈希表以线性方式逐个增加桶来实现扩容 。
静态
动态【下图中】
i 位二进制，可以映射到 个哈希桶
右上角小的 j = 1，2代表“局部深度”，代表用 j 位二进制就可以识别到，比如00和01归并以后，用一位“0”就可以确定是第一个桶，以是是 j = 1
可扩展哈希表~插入利用（插入但当前桶满？）
先计算要插入项对应的哈希值
然后实行映射到对应的桶，看这个桶是否已经满了，若满了，进行下面判断：
- j<i (说明有桶归并了)：展开归并的桶
- j=i: 进行扩容（i值增加一位，原有的哈希桶重新映射到新的目次上去）
缺点：可能总是由于某一个桶满，导致所有桶都要扩展，致使添补率降低【下面未办理】
删除键值：墓碑标记（p113）
线性哈希表（利用哈希值的后m位）【优化了上面的缺点】
详细原理公式见下图
以插入1111为例，如果一开始没有对应11索引，11B = 3D（B指二进制，D指十进制），3-2^{m-1} = 1，以是先存在01桶
汲取可扩展哈希表的分裂桶履历，但以插入后添补率超过阈值作为判断，若超过，加新桶，分裂旧桶
制止全表扩展：由于不是某个桶满就全表扩展，而是关注整体添补率，以是不会因个别桶的情况轻易对整个哈希表进行利用。当添补率未超阈值时，即使有桶满了，也不会触发全表扩展，减少了不必要的空间浪费，维持了相对较高的添补率 。
解析：m为二进制位数，n为二进制可表示2^m-1的前n个数；若待查哈希值x<n，那就很好说，直接映射；反之，则用x-2^(m-1)算出新的哈希值【记忆：只有m才能到2的指数上去】
哈希表得当点查询，B+树进行范围查询更方便
第六章
总体脉络
查询解析
八大rules
（A ::= B 表示了一种映射关系，如果有B，那么就映射为A并存储）
如下图所示，A一般是类型，B一般是SQL详细的语言原子
逻辑重写
进步查找效率的方式：谓词拆分 & 投影下推（见下段）& 笛卡尔积转成等值连接来进行利用（两个表都有C列，笛卡儿积里面可能有两个C列不相同的归并到同一行）
谓词拆分 & 投影下推：凡是只涉及单表的利用，都可以放到前面去完成，比如多个σ，实际上选择利用可以拆分在单个表上完成，于是可以在笛卡儿积前先筛选
关于嵌套查询的处理方法
- 下图所示：【重写】将原始嵌套查询重写为连接查询【把子查询中的表放到外查询，与外查询的表连接起来】
- 【实体化暂时表】对于同一个复合表（如A join B on..）的多次查询，实体化只要进行一次聚合利用（然后讲这个聚合的效果就存下来了），反之就要每次查询都聚合。以是这个实体化的上风在于多次查询，单次查询的话实不实体化没区别【下图未明显体现】
查询优化
三. 物理算子
join算子，scan算子，sort算子等
查找的两种方式
两个变量的定义：B， T【这个关系所包罗的块数，元组数】
选择率：满足这个条件的元组数/ 总的元组数
- 关于查找唯一项的处理（=）【点查询】
- 关于查找范围的处理（>,<等比较谓词）【范围查询】
对于有序表
- 查找>=v： 找到v，向右扫
- 查找<=v：直接从头节点开始，向右扫，直到找到v
两类索引及其查找特点
- 聚簇索引（叶子节点包罗索引和数据块）：先定位到 v 对应的叶子节点（颠末 h 次查找，h为索引对应的B+树的树高 ），然后从该叶子节点指向的数据块开始顺序扫描后续所有数据块 。由于数据按索引顺序物理存储，后续数据块在磁盘上大概率是相邻的，是顺序 I/O 。
- 非聚簇索引（叶子节点只有索引）：先定位到 v 对应的叶子节点（h 次查找 ），之后顺序扫描叶子节点来提取所有指向记载的指针 。由于非聚簇索引叶子节点只存指针，需根据指针再去访问实际数据块，是随机 I/O 。
概念解析
- 搜索码不唯一：即待搜索对象可能有多个，找到一个不能保证剩下没有了
- 全表扫描（Table Scan）：遍历整张表的所有元组（记载）来查找满足条件的数据。比如要在学生信息表找年龄大于 20 岁的学生，全表扫描就会把表中每个学生记载都看一遍。
- 索引扫描（Index Scan）：利用已建立的索引来查找数据。索引雷同书籍目次，能快速定位数据位置。
- 选择率：满足谓词条件 p 的元组数目与关系 R 总元组数目的比值 ，权衡满足条件数据在全表中的占比。
- B(R)：关系 R 占用的块数 ，这里表示表数据占用磁盘块数目。
- T(R)：关系 R 中的元组（记载）总数 。
- 聚簇索引：数据物理存储顺序与索引顺序同等，查找时可利用顺序 I/O 特性，性能较好 。
- 非聚簇索引：索引顺序与数据物理存储顺序差别，查找时涉及随机 I/O ，相对复杂。
- 二叉树相干：对于一棵二叉树（分支因子n = 2 ），如果树高为h ，最多能存储\(2^h - 1\)个节点（满二叉树情况）。当要查找一个节点时，最多需要比较h次（也就是树的层数）。如果有N个节点，在均衡二叉树中，树高 ，这就是对数和查找次数相干的根本原理。在下面的景象中，N就是元组数T（R）
- 两个变量的定义：B， T【这个关系所包罗的块数，元组数tuple】
各类查询算法的平均复杂度【其中索引连接针对的是B+树索引的情况】
三种连接（PPT6.1中p95开始）
I/O利用是对应取表（页面）利用的，下面用T（R）是由于在当前逻辑下，对于每个R中元组，都要取出一次页面，以是数目是T（R）
注：【比较后的写回都不考虑IO，但排序/ 哈希后的写会考虑IO？】
【重要！】三种连接方式效率的比较
注意：只有嵌套循环能实现 连接【对应非等值连接】
注：NL连接即循环连接 Nested Loop
要实现效率最大化，需要提前知道B(R),B(S)的值，带入运算后比较
嵌套循环
关于B(R)的说明：将R中的每个页面逐一拉进内存（由此产生了B（R）），为后续比较做准备
一、左图算法：对每个元组，都将S中的一个页面拉进内存【没有缓冲池情境下的IO开销 】
二、右图（优化）：对R的每一个页面，将当前页面中的所有元组，和S中拉进来的页面都做了比较以后，再拉入下一个S的页面
注意：把小一点的表作外表（外层循环）
三、对于内存空间较大/ 或者有缓冲池的情况：
S的页面，一帧存比较的
【由于比较只能在主存中进行，而且要求比较的双方（外表的页面& 内表的页面）都在主存中。以是，一次拉入S页面，能比较的R页面越多，拉入S的页面次数就越少】
PS：预留出两帧：
- 一帧专门存 中间效果（比如连接、比较运算产生的暂时数据 ），存满后写回外存；
- 另一帧给 内表（也就是S） 做缓冲（制止频繁换入换出，加速数据访问 ）。
以是，对于有缓冲池M帧（一帧对应关系的一个页面，即BUFFER = M）的情况:
PS：这个叫做“写回外存”
排序归并
排序和哈希都是基于“先通过某种方式将相等的元组聚集，再进行等值连接”的思想
关于排序R的cost说明：
第一次利用（数据分块与内排序）
- 把表 R 的数据按块读入内存进行内排序。这里确实涉及对每一块数据进行一次内排序利用。总共有 B (R) 块数据，每一块都要经历读入内存、内排序、写回磁盘的过程。这一步的重要开销是将 B (R) 块数据依次处理，从磁盘 I/O 角度看，读入和写回利用整体上相当于对 B (R) 块数据进行了一次读写，再加上每一块内排序的计算开销（可近似看作一次利用对应一块数据 ），以是从本钱计算角度，这部分开销和 B (R) 相干 。
第二次利用（归并阶段）
- 归并过程雷同二叉树的归并。将已经内排序好的 B (R) 个有序子块进行归并，构建一棵归并树（雷同二叉树结构 ）。在这棵归并树中，每一层的归并利用都涉及对一些子块的归并。
- 假设子块数目为 B (R) ，那么归并的趟数近似于以 2 为底 B (R) 的对数（向上取整 ），即⌈log₂B (R)⌉ 。在每一趟归并中，又要对 B (R) 块数据进行处理（由于终极要把所有子块归并成一个有序序列 ），以是归并阶段的 I/O 开销就是 B (R) * ⌈log₂B (R)⌉ 。
考不考虑写回的Io呀，我觉得是一倍的B（R）*（1+log）呀
把这两部分开销综合起来，就是总的排序本钱 2B (R) × (1 + ⌈log₂B (R)⌉) ，其中 2B (R) 体现了两遍磁盘利用（读入分块排序、归并写出 ），(1 + ⌈log₂B (R)⌉) 分别对应内排序和归并阶段的相干利用次数。 你之前的理解正确抓住了关键的两个利用阶段和对应的开销影响因素呢。
关于n路外归并【2025年考点】
哈希连接
用相同的哈希函数，将R,S映射到桶里面，再分别在桶里面进行比较
2（BR+BS）：将R，S的页面分别拉进主存哈希运算后，写回外存【此时元组可以视作已经被映射到同一个桶里面了】
1（BR+BS）：将每个哈希桶拉进主存，进行比较【这里没考虑写会IO】
【开销模子p160左右】
基于代价的优化
基于代价的优化（CBO）【代价估计& 选代价最小的】
为了提前知道哪种利用比较合适，需要提前统计一些数据的信息，统称 ：“统计信息”
左深树【所有节点的右节点都是叶子节点】的数目比浓密树小不少
- 定义与原理：偏重于查询的物理优化，运用代价模子对利用进行代价估计，天生由物理利用符构成的物理执行筹划（树 ），且与关系实例相干。
- 目的：从物理执行角度，通过评估差别利用代价，选择较优执行方案。
对于两种假设造成的选择率的计算偏差的办理方法
- 对于均匀分布假设：通过统计直方图
- 对于属性独立假设：通过选择性地收集某些列的信息
对于上面这种复合谓词计 v：
- 连续合取：选择率 = 选择率 i 的乘积【这些就是基于”属性之间是相互独立的“假设运算的】
- 连续析取：选择率 = 1 - 选择率i的乘积
p169
基于规则的优化（RBO）【逻辑重写】
- 定义与原理：通过查询的逻辑重写，依据关系代数的等价变更规则，减少不公道开销。它不依赖详细关系实例。
- 目的：利用既定规则对查询进行优化，在逻辑层面提拔查询效率。
两种优化模子【RBO 与 CBO 】的结合
- 现状与问题：二者结合在查询优化中占比高，以致占据整个查询相应时间一半以上【也就是说，在开始执行之前，差不多会花这么久的时间先应用两个模子】，但由于是 NP 问题，无法确保找到最优执行筹划 （只能相对优化），不外仍是必要手段。
执行器的三种执行方式【物化，火山，向量】
✅物化模子（Materialization Model）
核心逻辑：每个利用算子（operator）一次性处理所有输入数据，处理完成后将全部效果一次性输出 。比如进行查询中的过滤、聚合等利用时，先把相干数据都拿到，处理完同一返回效果。
适用场景：更适配 OLTP（在线事务处理）负载，这类场景通常每次访问数据量小，所需函数调用少，物化模子可快速处理并输出效果，满足事务的快速相应需求 。
优缺点：优点是对于小数据量场景处理直接高效；缺点是面对大数据量时，一次性处理和存储全部中间效果可能带来较大内存压力，且不得当需要流式处理、逐步返回效果的场景 。
✅火山模子（Volcano Model，也叫迭代模子、Pipeline Model ）
核心逻辑：把关系代数里的每种利用抽象成一个算子（Operator），构建成算子树，查询执行时自顶向下调用 next() 接口，数据自底向上被拉取处理，是 “拉取执行模子（Pull Based）” 。像常见的关系型数据库（SQLite、MongoDB、DB2 等 ）许多用这种模子。
优缺点：
- 优点：实现简单，每个算子可单独编写逻辑，便于扩展和维护，差别算子组合灵活，能适配多样查询需求 。
- 缺点：因频繁调用 next() 接口，且一次仅处理一条数据，CPU 执行效率低，遇到连接（Joins）、子查询（Subqueries）、排序（Order By ）等利用时，还容易出现阻塞，影响整体查询性能 。
✅向量化模子（Vectorized / Batch Model，也叫批处理模子 ）
核心逻辑：和火山模子雷同需实现 next() 函数，但每次调用 next() 会返回一批元组（tuples）而非单个元组，基于 SIMD（单指令多数据流）指令集进行向量计算，是火山模子和物化模子的折衷 。像 Presto、Snowflake 等数据库支持这种模式，Spark 2.x 的 SQL 引擎也开始支持。
优缺点：
- 优点：大幅减少算子调用次数，降低虚函数调用开销，增加数据局部性，提拔数据麋集型任务（如大规模数据的分析查询，适配 OLAP 场景 ）的计算效率 。
- 缺点：实现相对复杂，对于小数据量计算，提效效果不明显，由于批处理的额外处理逻辑在数据量小时可能抵消上风 。
三大类（表明型）执行器【PPTp173开始】
物化模子：每一步利用后的效果存下来，作为下一步执行的输入
优化：边执行边实行归并，输出一个效果，就实行归并，不需要比及所有都处理完
火山模子：逐元组执行
优化：上一个菜就开吃，可能不够所有人吃，应该按照人数估计大概上几个菜开吃比较合适
向量化模子：按向量执行【一组元组】（攒够肯定规模再去执行）
编译型执行
即时编译：根据详细的数据情况天生查询代码，更有针对性
编译型和表明型区别
- 执行过程
- 编译型：先编译后执行，执行前完成翻译工作，天生可独立运行的可执行文件 。
- 表明型：边执行边翻译，程序运行时，由表明器逐行读取源代码，逐行翻译成呆板可执行指令并立即执行，不天生独立可执行文件 。例如 Python 程序运行时，Python 表明器逐行处理代码 。
- 执行效率
- 编译型：执行速度快、效率高，运行时无需额外翻译开销 。
- 表明型：逐行表明执行，每次运行都要翻译，存在额外性能开销，执行速度相对较慢 。不外部分表明型语言采用即时编译（JIT）等技术提拔了效率 。
- 开辟效率与灵活性
- 编译型：开辟过程中编译环节耗时，修改代码后需重新编译，开辟效率相对低，代码修改不灵活 。
- 表明型：开辟灵活，代码修改后可立即运行，无需繁琐编译过程，得当快速原型开辟和小型项目，开辟效率相对较高 。
有i个索引和有i个索引查找方式有什么区别【A：注意区别查找和连接！查找是对一个表进行的，有i个索引就是i个列上有索引，那么查找就可以分别从一个列的索引进去，进行开端筛选，再在剩下的元组里面看其他列，以是对应了i种索引入手的查找方式，外加一种全表查找：每一行，看条件中的所有筛选项】
第七章
事务：一个程序执行单元，要执行就要一起执行（原子性）【BEGIN ... COMMIT】，否则返回原始状态【BEGIN ... ROLLBACK】
数据库事务管理要办理的两个核心问题
- 如何应对系统瓦解（后的规复）：
- 日记的作用：数据库使用日记记载事务对数据的所有修改利用，而不是简单的 “记事本”。日记按时间顺序记载每个事务的开始、竣事以及对数据的修改细节，包罗修改前的值（旧值）和修改后的值（新值）等。日记记载先于实际数据修改写入长期存储【预写日记】，这是保证数据可规复的关键。
- 规复过程：当系统瓦解后进行规复时，数据库系统会读取日记。【对于（用户界面体现）已经提交的事务（但是内核中可能并没有执行完成），系统会根据日记中的记载重新执行对数据的修改利用，将数据规复到事务提交后的状态，这称为重做（Redo）利用；【对于未完成（未提交）的事务<完成了一半，比如执行了A（根据长期性原则，已经写到了A的外存），但还没有利用B】，系统会根据日记中的旧值将数据回滚到事务开始前的状态，取消这些未完成事务对数据的部分修改，这称为回滚（Undo）利用。【例如，一个事务对某条数据进行了多次修改但还未提交时系统瓦解，规复时就利用日记中的旧值把数据规复到事务开始前的状态，制止未完成事务对数据同等性的破坏。
- 说明：上面两种利用，本质是要保证外存的存储和用户界面的效果是同等的
- 多事务并发执行
【ACID】&实现手段
def：
- A原子性：一个事务内的利用，要执行就要一起执行，要不然就全部回滚
- Consistence同等性要求：修改数据前后，数据之间的核心关系应保持同等，执行过程中，允许暂时的不同等，比如转账，总额稳定
- Isolation隔离性要求：本质：从每条数据的角度来讲，单独访问得到的效果和与其他事务并发执行的效果应该同等
- Durable长期性要求：只要A，B有一个执行完了【不要求事务执行完成】，就要被固定下来【反馈到外存的长期性存储上】（就是说每次修改完就有写回利用）
实现手段：
事务特性（ACID）实现手段作用 / 实现逻辑原子性（A）Undo log 回滚日记记载事务修改前的数据状态，若事务失败，通过回滚日记取消（Undo ）未提交的修改，保证利用要么全做、要么全不做同等性（C）完整性约束 + AID 技术完整性约束（主键、外键等）保证数据格式合法；AID（原子性、隔离性、长期性）协同保障业务逻辑上的数据同等隔离性（I）隔离级别、并发控制（2PL、OCC 等）通过锁机制（如 2PL 两阶段锁）、MVCC（多版本并发控制）等，控制多个事务并发时的相互干扰，实现差别隔离级别长期性（D）Redo log 重做日记事务提交前，将修改利用记载到重做日记；若系统瓦解，重启后通过 Redo log 重放利用，保证已提交事务的修改长期化
两种等价& 可串行化p28
视图等价p30：关注首尾，和中间顺序
视图等价要求：说白了开始，中间和竣事的同等性
- 开始呀，你读某个值，我也读这个值
- 最后呀，你写我也写
- 中间呀，你读的值和我读的要一样（写这个值的事务和利用要同等）
最先读谁，最后写了谁，中间读利用关系（谁读另一个写的值，若中间没有读利用，省略），二者保持同等【满足这个定义即可】
每个辩论可串行化都是视图可串行化的
判断辩论可串行化的方法
有向边：凡是有写就是
✅见右图：可串行化《=》优先图无环【注意，环看的不是边，而是有向边，也就是对于同一变量的有向边首尾相连构成一个环才是不可串行化】
四种隔离级别
隔离级别从上往下依次升高
隔离级别核心差别点示例（事务 T1 两次读，事务 T2 中途修改并提交）读未提交可读到其他事务未提交的中间数据【所谓脏读】T1 第一次读值为 10，T2 修改为 20（未提交），T1 第二次读为 20；若 T2 回滚，T1 数据无效读已提交只能读到其他事务已提交的数据，两次读效果可能差别T1 第一次读值为 10，T2 修改为 20 并提交，T1 第二次读为 20可重复读事务内多次读，效果完全同等（不受其他已提交事务影响 ）T1 第一次读值为 10，T2 修改为 20 并提交，T1 第二次读仍为 10可串行化强制事务串行执行，完全隔离，无并发干扰T1 执行读时，T2 需等待；T1 两次读值始终为 10，T2 提交后 T1 再读才会变为 20 破坏同等性：脏读和丢失更新【相干几个概念】
调度：多个利用穿插执行
脏读（Dirty Read）【还没提交B就读，最后A回滚了】
- 定义：指一个事务读取了另一个未提交事务修改的数据。这就像是在一本书还没写完校对就被别人拿去阅读，可能读到的是错误或不完整的内容。
- 示例：假设有两个事务，事务 A 和事务 B。事务 A 修改了某条数据，但还未提交；此时势务 B 读取了被事务 A 修改后的数据。如果事务 A 随后回滚了利用，那么事务 B 读取到的数据就是无效的 “脏数据”。比如在银行系统中，事务 A 将账户余额从 1000 元改为 1100 元但未提交，事务 B 读取到余额为 1100 元。若事务 A 回滚，账户实际余额还是 1000 元，事务 B 读取的 1100 元就是脏数据，可能导致后续业务逻辑堕落。
丢失更新（Lost Update）【AB都写，A还没写完B就写】
- 定义：两个或多个事务同时对同一数据进行更新利用，其中一个事务的更新效果被其他事务覆盖，造成部分更新丢失。这雷同于多人同时修改一份文档，后生存的人覆盖了前面人的修改。
- 示例：假设事务 A 和事务 B 都读取了账户余额为 1000 元。事务 A 将余额增加 100 元并提交，此时余额变为 1100 元；事务 B 也进行同样的增加 100 元利用，但它是基于最初读取的 1000 元进行计算的（比如A的执行后还没有来得及将数据写回外存，就被B给读出了），以是事务 B 提交后，余额还是变为 1100 元，事务 A 增加的 100 元就被 “丢失” 了。正常情况下，两个事务都增加 100 元，余额应该是 1200 元，但由于丢失更新，少了 100 元的更新效果。
可重复读隔离级别下，一个事务在执行期间，对同一组数据的多次读取效果是同等的，无论其他事务如何修改数据（即使已提交）。
关键不是 “中间没有新写利用”，而是：
- 其他事务新增 / 修改的数据，不会被当前事务看到（除非当前事务提交后重新启动）。
- 其他事务删除的数据，当前事务仍能看到 “删除前的版本”（MVCC 机制下）。
ps:幻读：【一个读大，一个写小】数据库的幻读是指在同一事务中，对于同一个数据项，一个历程在写小范围，一个历程在读所有项，读历程两次读取同一范围的记载时，第二次读取发现有新的符合条件的记载被插入，使得两次读取效果不同等的征象 。
并发控制p42【乐观& 悲观的隔离性】
悲观：两阶段加锁（2PL）
锁【互斥锁X（RW）、共享锁S（R）】，时间戳【两个时间戳，分别维护读时间和写时间】
延迟解锁的问题
2-PL能制止饿死，但是不能制止死锁【不考】
两阶段封锁协议： 一旦开始解锁，不能再申请新锁【分为申请阶段和释放阶段】
允许锁转换：申请阶段可以升级，释放阶段可以降级
- 悲观方式：从源头就查抄
- 乐观方式：以为根本没辩论，先让你们无差别执行，执行后，在提交时再查抄
乐观的并发控制p67：时间戳排序（TO）
时间戳可以看作历程执行相对于开始执行的时间，越晚执行的历程时间戳越大【单调递增！】
日记📝【关键记载四个数据：事务，数据项，旧值，新值】p105
一、Undo Log（回滚日记）
- 触发时机：事务执行修改利用（如 INSERT/UPDATE/DELETE ）时，并非 “每一步利用” 都单独记，而是按事务阶段记载。
- 记载内容：
- 通常记 “数据项的旧值（初值）”，格式雷同 (事务 ID, 数据项, 旧值, 利用类型) 。
- 例：事务 T1 修改数据项 X 从 10→20，Undo Log 记 (T1, X, 10, UPDATE) ，用于回滚时规复旧值。
二、Redo Log（重做日记）
- 触发时机：事务执行修改利用时，先写 Redo Log 再落盘数据（WAL 机制）。
- 记载内容：
- 记 “数据项的新值（末值）” 及物理位置，格式雷同 (事务 ID, 数据页地点, 新值) 。
- 例：事务 T1 修改 X 为 20，Redo Log 记 (T1, 数据页地点, X=20) ，系统瓦解时重放该日记规复修改。
三、关键区别：“记初值还是末值”
- Undo Log：记初值（旧值） → 用于 “取消未提交事务”，让数据回退到修改前。
- Redo Log：记末值（新值） → 用于 “规复已提交事务”，让数据保持修改后状态。
？
表明：
蓝块中的感觉比较杂，不确定考不考
随机访问的意义：适用于非连续的存储：差别记载可能分布在差别磁盘块。随机访问允许直接定位并读取这些分散的数据，无需按顺序遍历大量无关数据。在特定场合下，随机访问有不可被替代的作用
文件内的三种构造类型
- OLAP：得当列存；
- OLTP：得当行存
- HTAP（散列）：差别hash桶之间无序，hash桶内部有序
多表聚簇雷同于将多个表连接后再存储，方便多表查询，适用于需要同时对多个表的查询
章节5.2中的PPT上不熟悉的部分p49起
章节四的开始p64
END PTR
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
|
发表于 
