intro

写实验二的时候还是感觉头脑是一团浆糊, 归根结底还是B+tree操作不太熟悉, 还是不能跳过, 决定做一下hw2的B+Tree部分;

上图展现了我们要操作的b+tree的样子, 并且对B+Tree的结构做了简单的说明:

• 内部节点的左指针 指向了所有小于当前key的情况, 右指针指向了所有大于等于当前key的情况
• 叶子节点当关键字个数小于 d - 1 / 2向上取整的时候认为underflow, 在这个例子中d为4, 所以当#key小于2的时候发生下溢, 需要进行调整;
• 内部结点当指针数小于 d / 2向上取整的时候发生下溢, 这个例子中当指针数小于2的时候发生下溢, 需要调整

intro

一直想学分布式的知识, 上学期写了6.824一个lab后面半途而废了, 刚好这学期开了分布式与云计算这门课, 字节的面试官也建议我学一下, 故选之. 这篇文章主要记录分布式知识点, 一做复习只用, 二真的学点知识, 以后学6.824能够轻松一点. 希望不要挂科!!!

misc

拿了字节offer好开心. 10号考算法, 复习加水一篇博客. 希望不要被八强啊;

注: 以下代码都是直接再typora上敲的, 不保证其正确性

引言

什么是算法及其特征

算法是通过一个有限的指令序列集合对特定的问题进行求解的一种计算执行描述。

（1）输入：一个算法具有零个或多个取自指定集合的 输入值；

（2）输出：对算法的每一次输入，算法具有一个或多个与输入值相联系的输出值

（3）确定性：算法的每一个指令步骤都是明确的；

（4）有限性：对算法的每一次输入，算法都必须在有 限步骤（即有限时间）内结束；

（5）正确性：对每一次输入，算法应产生出正确的输 出值；

（6）通用性：算法的执行过程可应用于所有同类求解 问题，而不是仅适用于特殊的输入。

问题实例和问题规模

问题实例是计算问题的解决方案所需的全部输入

问题规模是算法的输入实例大小。

算法初步

插入排序算法

loop invariant: 当前指针左边数组已排序

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

void insertionSort(vector<int> &nums) {
    int n = nums.size();
    if (n < 2) return;
    for (int i = 1; i < n; ++i) {
        int num = nums[i];
        int j = i - 1;
        for ( ; j >= 0 && nums[j] > num; --j) {
            nums[j + 1] = nums[j];
        }
        nums[j] = num;
    }
}

分析: 整体复杂度显然为一个三角形, 面积为O(n^2), 对于基本有序的输入友好(O(n), 因为j指针动不了);

最坏O(n^2)、最好O(n^2)和平均O(n)情形复杂性

归并排序算法

可以用来计算逆序对;

归并的基本思想是分治, 而分治思想主要分为三个部分:

• divide - 归并中的取中间下标
• conquer- 递归调用
• combine -两个有序子数组的merge

同样使用分治思想的还有快速排序(combine过程无需做), 平面上找最近点对.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

void merge(vector<int> &nums, int lo, int mid, int hi) {
    // aux arr
   	int n1 = mid - lo + 1; //闭区间
    int n2 = hi - mid; // 左开右闭
   	vector<int> left(n1 + 1), right(n2 + 1); // 多申请一个空间作为哨兵
    // copy elem to aux arr
    for (int i = 0; i < n1; ++i) {
        left[i] = nums[i + lo];
    }
    left[n1] = INT_MAX;
    for (int i = 0; i < n2; ++i) {
        right[i] = nums[mid + 1 + i];
    }
    right[n2] = INT_MAX;
    // merge
    int i = 0, j = 0;
    for (int idx = lo; idx <= hi; ++idx) {
        if (left[i] <= right[j]) {
            nums[idx] = left[i++];
        }
        else {
            nums[idx] = right[j++];
        }
    }
}

void mergeSort(vector<int> &nums, int lo, int hi) {
    if (lo < hi) {
        int mid = lo + hi >> 1;
        mergeSort(nums, lo, mid);
        mergeSort(nums, mid + 1, hi);
        merge(nums, lo, mid, hi);
    }
}

时间复杂度为O(nlogn), 空间复杂度为: 递归栈logn, 辅助数组总长度On, 故为O(n)

常见排序算法复杂度:

堆排序

堆的逻辑结构是完全二叉树, 实际存储结构是数组

对于一个结点i, 其父亲为i/2, 左孩子为2 * i + 1, 右孩子为2 * i + 2;

堆主要核心的代码就是swim 和 sink, 具体就不写了.

中位数和顺序统计

最大最小值

单独求一个无序数组的最值, 比较次数显然为n - 1, 代码如下:

1
2
3
4
5
6
7
8
9

int maxVal(vector<int> &nums) {
    int res = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] > res) {
            res = nums[i];
        }
    }
    return res;
}

同时求最大最小值:

• 分别求: 则比较次数为 n - 1 + n - 2 = 2n - 3;
• 同时求显然可以减少比较次数, 循环执行了 n / 2次, 每次循环内3次比较, 所以只比较了3n / 2次;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

vector<int> minAndMax(vector<int> &nums) {
	int n = nums.size();
    int maxVal = INT_MIN, minVal = INT_MAX;
    for (int i = 1; i < n; i += 2) {
        int num1 = nums[i - 1];
        int num2 = nums[i];
        if (num1 > num2) {  // 保证num1 < num2, 第一次比较
            swap(num1, num2);
        }
        minVal = min(minVal, num1); // 第二次比较
        maxVal = max(maxVal, num2); // 第三次比较
    }
    if (i == n) { // 说明最后一个元素尚未比较
        int num = nums[n - 1];
        minVal = min(minVal, num);
        maxVal = max(maxVal, num);
    }
    return {minVal, maxVal};
}

topk问题: 期望时间为线性的选择

选出无序序列中第k大 或者 前k大个数字的时候 一定 一定使用这种方法(能放入内存的情况下)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

int topk(vector<int> &nums, int lo, int hi, int k) {
    if (k > nums.size()) return -1;
    if (lo == hi) return nums[lo];
    if (lo < hi) {
        int q = partition(nums, lo, hi);
        if (q == k) return nums[q];
        else if (q < k) {
            return topk(nums, q + 1, hi, k);
        }
        else {
            return topk(nums, lo, q - 1, k);
        }
    }
}

int partition(vector<int> &nums, int lo, int hi) {
    int pivot = nums[hi];
    int i = lo;
    for (int j = lo; j < hi; ++j) {
        if (nums[j] <= pivot) {
            swap(nums[i++], nums[j]);
        }
    }
    swap(nums[i], nums[hi]);
    return i;
}

时间复杂度O(n)

topk问题: 最坏时间为线性的选择

这算法有点难, 一般面试也不会用上, 随便看看吧

红黑树

红黑树是一种放宽了限制的avl树(通过引入红节点), 所以查询性能比avl树弱, 但是插入删除旋转次数较少, 它有如下五个基本性质:

• 每个结点红或者黑
• 根为黑
• nil结点为黑
• 若节点为红, 则两个孩子必为黑(即没有两个红节点直接连接)
• 每个结点到所有后代叶子的路径有同样多的黑结点(黑高相等)

一棵n个内点的红黑树的高度至多 是2log(n+1)。

插入算法的时间、至多使用2次旋转

删除算法的时间、至多使用3次旋转

红黑树左旋

红黑树插入

step 1：将z节点按BST树规则插入红黑树中， z是叶子节点；

step 2：将z涂红；

step 3：调整使其满足红黑树的性质；

OS树

os树就是红黑树维护了size属性;

OS-select(x, i): 选择以x为根的子树中, 查找第i个最小元素

1
2
3
4
5
6
7
8
9
10

TreeNode *OSSelect(TreeNode *x, int i) {
    int rank = x->left->size + 1;
    if (rank == i) return x;
    else if (i < rank) {
        return OSSelect(x->left, i);
    }
    else {
        return OSSelect(x->right, i - rank);
    }
}

OSRank(TreeNode *x): 在以x为根的自述中求x的秩:

不相交集合的数据结构

主要是并查集, 主要用来计算连通分量个数, 计算朋友圈…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class UF {
public: 
    UF(int n) { // init a uf with n nodes
        p.resize(n);
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
        setCount = n;
    }
    
    int find(int x) { // find with path compression
        return x == p[x] ? x : p[x] = find(p[x]);
    }
    
    void connect(int x, int y) {
        int f1 = find(x), f2 = find(y);
        if (f1 != f2) {
            --setCount;
            p[f1] = f2;
        }
    }
    
    
    vector<int> p; // parent
    int setCount; // # of sets
};

图论

BFS和DFS算法

• 白色、灰色和黑色结点概念和作用
  • 所有节点一开始被初始化为白色, 颜色属性保存再结点color域中
  • 所有与黑色结点邻接的结点都已经被发现
  • 灰色结点是代表的是已访问和未访问两个集合的边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

enum {white = 0, gray = 1, black = 2};
struct Node {
    int color;
    int dist;
    Node *pre;
};

void bfs(graph g, Node *s) {  // g代表整张图, s为bfs搜索起始节点
    // 初始化其余节点信息
    for (Node *node : g.vertices - s) { // 半伪代码
        node->color = white;
        node->dist = INT_MAX;
        node->pre = nullptr;
    }
    s->color = gray; // 因为gray代表的是已知和未知两个集合之间的边界
    s->dist = 0;
    s->pre = nullptr;
    queue<Node *> q;
    q.push(s);
    while (q.size()) {
        Node *u = q.front();
        q.pop();
        for (Node *v : u->adj()) { // 假设adj能够返回邻接的结点指针
            if (v->color == white) { // v尚未被访问过
                v->color = gray;
                q.push(v);
                v->dist = u->dist + 1;
                v->pre = u;
            }
        }
        u->color = black; // 至此, u之和黑色或者灰色结点邻接
    }
}

• 计算过程及其时间复杂度

overview

The third programming project is to add support for executing queries in your database system. You will implement executors that are responsible for taking query plan nodes and executing them.

需要支持以下操作:

• Access Methods: Sequential Scans, Index Scans (with your B+Tree from Project #2)
• Modifications: Inserts, Updates, Deletes
• Miscellaneous: Nested Loop Joins, Index Nested Loop Joins, Aggregation, Limit/Offset

We will use the Iterator query processing model (i.e., the Volcano model). Every query plan executor implements a Next function. When the DBMS invokes an executor’s Next function, the executor returns either (1) a single tuple or (2) a null pointer to indicate that there are no more tuples. With this approach, each executor implements a loop that keeps calling Next on its children to retrieve tuples and then process them one-by-one.

参考博文: http://patshaughnessy.net/2014/10/13/following-a-select-statement-through-postgres-internals

这文章写的太好了!!!

task1 SYSTEM CATALOG

A database maintains an internal catalog to keep track of meta-data about the database. For example, the catalog is used to answer what tables are present and where.

misc

进入到proj3的理论部分, proj2可太难了, 把我整自闭了…

正文

• 操作符以树的形式来排布
• 数据流从叶子节点往上流
• 根节点的输出就是query的结果

observation

我们前面讨论的都是单线程环境, 现在我们需要支持对这些数据结构的多线程访问安全来充分利用多核cpu并减少磁盘IO的等待.

redis和voltDB是单线程的;

A concurrency control protocol is the method that the DBMS uses to ensure “correct” results for concurrent operations on a shared object.

A protocol’s correctness criteria can vary:

• Logical Correctness: Can a thread see the data that it is supposed to see?
• Physical Correctness: Is the internal representation of the object sound?

misc

昨天终于把proj1改到满分了, 终于可以放心得开始proj2了, proj2应该是整个项目中最难得部分, 加油!争取三天拿下!

The second programming project is to implement an index in your database system. The index is responsible for fast data retrieval without having to search through every row in a database table, providing the basis for both rapid random lookups and efficient access of ordered records.

intro

这两节的ppt是关于B+树索引的, 会直接和proj2相关, 所以一定要学好.

索引是表的属性的一些排序了的子集(比如key)的replica(复制), 有了这个索引就能够快速找到tuple的位置.

DBMS保证表的内容和index的内容都是逻辑上同步的.

It is the DBMS’s job to figure out the best index(es) to use to execute each query.

There is a trade-off on the number of indexes to
create per database.

• Storage Overhead

• Maintenance Overhead

intro

前面我们已经写完了buffer pool, 现在我们在一个数据库系统中的第三部分acess methods 这一部分支持了DBMS执行引擎对page上的数据的读写;

Specification

正式进入proj1, 需要实现使用lru替换策略的并发安全的bufferpool manager;

The first programming project is to implement a buffer pool in your storage manager.

Your implementation will need to be thread-safe.