红黑树的落叶

占坑

基于时间戳的协议之前已经讲过了调度的概念，SQL 标准规定了四种隔离性级别，在不同的隔离性级别下，我们对调度的要求也不同但应当注意到，调度一般是由操作系统执行的，数据库系统无法直接控制并行事务的调度方式，因此，数据库系统需要通过一些方法，间接地影响并行事务的调度方式，保证只产生需要的调度，从而实现 SQL 规定的四种隔离性级别常见的能够间接影响并行事务调度方式的方法有：时间戳、锁、有效性...

事务的概念构成单一逻辑工作单元的操作集合称为事务（transaction）事务的 ACID 特性原子性（atomicity）同一个事务中的所有操作，要么全都执行，要么全都不执行，如果一个事务在执行过程中因为某些原因执行失败，那么已经执行的操作就要全部撤销，这个撤销的过程叫作回滚（rollback）一致性（consistency）如果数据库中的数据满足预设的全部规则，则称数据库中的数...

查询优化概述数据库优化器的输入是一个关系代数表达式，经过查询优化后，输出一个查询执行计划，并且使输出的执行计划的代价尽可能小查询优化的步骤可以分为三步：产生一些逻辑上与输入表达式等价的关系代数表达式将所产生的表达式转换成执行计划（一个表达式可能对应多个执行计划）对产生的每个执行计划，估计其执行代价，选择一个代价最小的执行计划输出代价估计我们已经知道应该用磁盘传输的块数和寻...

查询处理概述查询处理的步骤如下：查询处理可以大概分为三个部分：语法分析与翻译查询优化查询执行执行代价的度量设计查询执行方案之前，我们必须能度量一个查询执行方案的代价在大型数据库系统中，在磁盘上存取数据的代价是查询执行的主要代价，因为比起内存操作，磁盘存取速度很慢代码在 CPU 中执行也需要时间，但只要 CPU 的运算次数不算太多，CPU 时间相比于 I/O 耗时就可...

文件结构之前说过，数据库一般被保存在磁盘上，通常情况下，保存在磁盘上的数据库以文件的形式组织，文件由计算机操作系统来维护，因此，数据库系统只需要考虑文件的结构即可数据库的块是数据库读写文件的最小单位，之前介绍过的磁盘块，是计算机系统读写磁盘的最小单位，因此，数据库的块必须是磁盘块的正整数倍，之后不再区分数据库的块与磁盘块，而是将它们统称为块对于一组模式相同且只包含定长属性的记录，我们称它...

索引概述索引（index）是一些能够帮助数据库系统高效查询数据的数据结构的统称许多对表的查询只涉及表中很少的行，如找出学号是 114514 的学生的总学分，如果不借助索引，数据库系统就要读取表中每一行并检查其学号属性是否为 114514 ，这种方法无疑是低效的，而借助索引，我们可以通过某些方法直接定位到学号属性为 114514 的行用于定位到待查询行的属性或属性集称作搜索码（search...

物理存储介质概述常见物理存储介质高速缓冲存储器（cache）高速缓冲存储器是最快的存储介质，也是最昂贵的存储介质计算机系统中的高速缓冲存储器一般都很小，由计算机硬件来管理虽然数据库系统不用管理高速缓冲存储器，但在设计数据库系统的算法和数据结构时，通常会考虑到高速缓冲存储器的影响主存储器（main memory）用于存放可处理的数据和机器指令的存储介质如果电源关闭，主存储器中的内...