排序

在CS61B中，您了解了许多不同的排序算法。为什么我们在这节课上又学了一个新的？所有传统的排序算法（即快速排序、插入排序等）都依赖于我们能够将所有数据存储在内存中。这是我们在开发数据库时没有的奢侈。事实上，在大多数情况下，我们的数据将比我们可用的内存大一个数量级。

1 I/O Review

请记住，无论何时从内存向磁盘写入页面或从磁盘向内存读取页面，都会产生1个I/O。由于进入磁盘非常耗时，在分析算法性能时，我们只考虑算法产生的I/O数量，而不是像big-O这样的传统算法复杂性度量。因此，在开发我们的排序算法时，我们将尝试最小化它将导致的I/O数量。在计算I/O时，我们忽略缓冲区管理器进行的任何潜在缓存。这意味着，一旦我们解开页面并说我们已经使用它，下一次尝试访问页面时，它将总是花费1个I/O。

2.双向外部合并排序

让我们从开发一个排序算法开始，该算法可以工作，但不尽可能好。因为我们不能一次将所有数据保存在内存中，所以我们知道我们将分别对数据的不同部分进行排序，然后将它们合并在一起。

为了有效地合并两个列表，必须首先对它们进行排序。这意味着排序算法的第一步应该是对每个页面上的记录进行排序。我们将第一阶段称为“控制”阶段，因为我们正在控制单个页面。

之后，让我们开始使用合并排序中的合并算法将页面合并在一起。我们将调用这些合并排序运行的结果。排序运行是一系列已排序的页面。

算法的其余部分将只是继续合并这些排序运行，直到只剩下一个排序运行。一次排序运行意味着我们的数据已完全排序！请参阅下一页的图像，了解算法运行到完成的图表。

关系代数

1 动机

在前面的注释中，我们讨论了SQL是一种声明性编程语言。这意味着您可以指定想要什么，但不必指定如何执行。从用户的角度来看，这很好，因为它使查询更容易编写。然而，作为数据库工程师，我们通常需要一种更具表现力的语言。当我们在几周内研究查询优化时，我们将需要一种方法来表达数据库可以用来执行查询的许多不同的有效计划。为此，我们将使用关系代数，这是一种过程编程语言（这意味着查询将精确指定要使用的运算符和顺序）。

2 关系代数导论

关系代数中的所有运算符都取一个关系并输出一个关系。基本查询如下所示：

π运算符只选择要前进到下一个运算符的列（就像SQL SELECT）。在这种情况下，运算符将dogs关系作为参数，并返回一个仅具有dogs关系的name列的关系。关于关系代数的一个重要事实是，关系是元组的集合，这意味着它们不能有重复。如果dogs关系最初为：

上述查询将返回：

最初，这两个buster是不同的，因为它们具有不同的年龄，但一旦去掉年龄列，它们就会变成重复的，因此输出关系中只保留一个。

让我们正式介绍关系代数运算符。

缓冲区管理

1 简介

到目前为止，我们已经讨论了如何在数据库管理系统的最低级别管理磁盘空间，以及如何在基于页面的数据库系统中管理文件和索引。我们现在将探讨DBMS上这两个级别之间的接口-缓冲区管理器。

缓冲区管理器负责管理内存中的页面，并处理来自文件和索引管理器的页面请求。请记住，内存空间是有限的，因此我们无法在缓冲池中存储所有页面。缓冲区管理器负责收回策略，或者在空间已满时选择要收回的页面。当从内存中逐出页面或将新页面读入内存时，缓冲区管理器与磁盘空间管理器通信以执行所需的磁盘操作。

2 缓冲池

通过将空间划分为可放置页面的帧，将内存转换为缓冲池。缓冲帧可以保存与页面相同数量的数据（因此页面完全适合于帧）。为了有效地跟踪帧，缓冲区管理器为元数据表分配额外的内存空间。

该表跟踪4条信息：

1.与存储器地址唯一关联的帧ID

2.用于确定帧当前包含的页面的页面ID

3.用于验证页面是否已修改的脏位

4.用于跟踪当前使用页面的请求者数量的Pin计数

B+ 树

1 简介

在前面的笔记中，我们讨论了数据存储的不同文件和记录表示。本周，我们将介绍索引，它是一种在数据文件之上运行的数据结构，有助于加快对特定键的读取。您可以将数据文件视为书籍的实际内容，将索引视为快速查找的内容表。我们使用索引使查询运行得更快，尤其是那些频繁运行的查询。考虑一个web应用程序，它在登录过程中根据用户名在用户表中查找用户的记录。用户名列上的索引将通过快速查找试图登录的用户的行来加快登录速度。在本课程注释中，我们将学习B+树，这是一种特定类型的索引。下面是一个B+树的示例：

2 属性

• d是B+树的阶，每个节点（根节点除外）必须有 $d \leq x \leq 2d$ 项，如果没有删除发生的话（删除数据后叶子节点可能少于d项）。节点中的项必须排序。
• 在内节点的两项之间有一个指针指向孩子节点，因为最多有2d项在节点中，内节点最多有2d+1个指针指向孩子节点。这也被称为树的扇出。
• 条目左侧子结点中的键必须小于条目，而右侧子节点中键必须大于或等于条目。
• •所有叶片深度相同，且具有d和2d个条目（即至少半满）

举个例子，一个阶为2的树：

请注意，节点满足阶要求（d≤ x≤ 2d），因为d=2并且该节点具有3个条目满足2≤ x≤ 4.

• 由于sorted和children属性，我们可以遍历树到叶子，以找到所需的记录。这类似于BST（二进制搜索树）。
• 每个根到叶路径都有相同数量的边-这是树的高度。从这个意义上说，B+树总是平衡的。换句话说，只有根节点的B+树的高度为0。
• 只有叶节点包含记录（或指向记录的指针-这将在后面解释）。内部节点（即非叶节点）不包含实际记录。

磁盘和文件

1 内存和硬盘

不论数据库什么时候使用数据，数据必须在内存中，访问这些数据相对较快，但是一旦数据量变得很大，将所有数据装进内存将变得不可能。磁盘配用来便宜的储存数据库的数据，但无论何时访问数据或写入新数据，它们都会产生巨大的成本。

2 文件、页面、记录

关系型数据库最基本的单位是记录（行）。这些记录被组织成关系（表），他们可以被修改，删除或者在内存中创建。

对磁盘来说基本的单位是页，是从磁盘到内存传输的最小单位，反之亦然。为了以与磁盘兼容的格式表示关系数据库，每个关系都存储在自己的文件中，其记录被组织到文件中的页面中。基于关系的模式和访问模式，数据库将确定：（1）使用的文件类型，（2）文件中页面的组织方式，（3）每个页面上记录的组织方式，以及（4）每个记录的格式。

CS61A难题摘录

HW02

problem

The logician Alonzo Church invented a system of representing non-negative integers entirely using functions. The purpose was to show that functions are sufficient to describe all of number theory: if we have functions, we do not need to assume that numbers exist, but instead we can invent them.

Your goal in this problem is to rediscover this representation known as Church numerals. Here are the definitions of zero, as well as a function that returns one more than its argument:

CS61A (2020summer)

from operator import truediv,floordiv

truediv == /

floordiv == //

可以编写文档进行测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

"""Our first Python source file"""

from operator import floordiv,mod

def divide_exact(n,d):
    """Return the quotient and remainder of dividing N by D.

    >>> q, r = divide_exact(2013,10)
    >>> q
    201
    >>> r
    3
    """
    return floordiv(n, d),mod(n, d)

执行方法：

1

python3 -m doctest file.py

假值有 False， 0，‘’，None

Functions have as their parent the frame in which they were defined.

tuple 可以作为字典的 key

list 不能作为字典的key

可变的默认参数是危险的

示例如下：

1
2
3
4
5
6
7
8
9
10
11

>>> def f(s = []):
...     s.append(5)
...     return len(s)
...
>>> f()
1
>>> f()
2
>>> f()
3
>>>

迭代器的for 语句只能迭代一次。

迭代器可以迭代字典的key、value、item ，当字典的结构发生变化时，迭代器失效。

Built-in Functions for Iteration

返回 yield 语句的是 generator ，一个 generator 可以返回多个 yield 语句。

Version Control (Git)

git init创建仓库

1
2

git init
Initialized empty Git repository in /home/rust/missing/playgroud/demo/.git/

git help 查看帮助，后面要加上参数，比如说git init

我们创建一个文件。

1

echo "hello world" > hello.txt

这个时候查看 git status

1
2
3
4
5
6

No commits yet

Untracked files:
  (use "git add <file>..." to include in what will be committed)

        hello.txt

我们可以看到一个`Untracked files 。